基于免疫遗传算法的tsp优化问题求解.pdf

万方数据
TSP斌，谢克明免疫遗传算法谢刚，武摘要：在分析人工免疫系统的基础上提出一种改进的人工免疫算法——免疫遗传算法。文中介绍了该算法的基本步骤及特点，并对旅行商问题进行了仿真研究，与基本遗传算法进行了比较。结果表明所提算法能以较快的速度完成给定范围的搜索和全局优化任务，较标准遗传算法具有更强的全局搜索能力。关键词：人工免疫系统，免疫遗传算法；旅行商问题A近年来，人们不断将生物免疫系统的一些行为[1][2]子包括接种疫苗和免疫选择两个步骤，前者是根据先验知识修改个体中的某些基因，使个体的适应度提高；后者是对接种了疫苗的个体进行检测，个体适[3]法用于神经网络设计，利用生物免疫原理中的浓度机制和个体多样性保持策略进行免疫调节，有效地克服了未成熟收敛问题。文献岢雒庖遖概念，构造出一种能对动态环境进行实时监控的多agent本文提出的免疫遗传算法是借鉴生物免疫系统的自适应识别和排除侵入机体的抗原性异物的功能，将生物免疫系统的学****记忆和多样性的特点引入遗传算法。该算法由于在遗传算法的基础上引入了抗体间亲和度的计算及调节机制，能有效保持抗体的多样性，从而避免了遗传算法中存在的早熟收[5]本文借鉴免疫系统中抗体的浓度控制原理，提出一种改进的人工免疫算法——免疫遗传算法。该算法在标准遗传算法的基础上增加了抗体浓度概率计算、抗体的促进与抑制等模块来提高解的多样性。该算法因为将免疫系统中抗体多样性维持机制引入了遗传算法，使得其性能比标准遗传算法更进了一步。在解决实际问题时，目标函数和约束条件作为抗原输入，随后产生初始抗体群，并通过一系列遗传操作及抗体亲和度的计算，在保持抗体多样性的情况下，找出针对该抗原的抗体，即问题的解。免疫遗传算法的基本特征包括：提高了算法全局搜索能力，避免陷入到局部最优解；具有最优个体记忆功能；具有快速的全局收敛性能。1骤如下：算法初始化。抗原输入及参数设定：输入目标函数及约束条件，作为抗原的输入；设定种群规模⒀≡窀怕蔖。、交叉概率！⒈湟旄怕蔖。等参数。初始抗体产生。在第一次迭代时，抗体通常在解空间中用随机的方法产生。亲和度及浓度的计算。计算各抗体和抗原的亲和度并计算各抗体的浓度。终止条件判断。判断是否满足终止条件，是则将与抗原亲和度最高的抗体加入免疫记忆数据库中，然后终止；否则继续。选择、交叉、变异操作。根据设置的选择概PPP择、交叉和变异操作。根据以上的操作更新群体后转到步骤。太原理工大学学报文章编号：—一一砉ご笱畔⒐こ萄г海轿魈TPl8238320075V01382006-0931基金项目：国家自然科学基金资助项目，山西省留学回国人员基金资助项日毒(1972)(Tel)03516010686(E-mail)******@tyuteduNo3
万方数据
P(z)=+(1a)e-(4)lD(z)TSP式中：。，死分别为抗体！Ｓ肟固錋艟对应的旅旅行商问题是一个典型的有序组合优化问题，可以看成是许多工程领域复杂优化问题的抽象形式。对于TSPTSPTSP算法对这种典型的组合优化问题进行研究。TSP两之间的直线距离，寻找一条旅程，使得每个城市刚[6]min>d(Qc1)+d(cc1)il27ld(Qff)(if)Qcj之间的距离。TSP221TSP(1)(!2)[611121z咒的字符串就形成一个抗体，因此抗体空间包含，个抗体，