面向TSP问题的免疫遗传算法研究

龙源期刊网 https://www.docsj.com/doc/7b19008717.html,

面向TSP问题的免疫遗传算法研究

作者：谢旻

来源：《软件导刊》2011年第06期

摘要：TSP问题作为NP 难题的典型代表，计算机算法理论研究的热点，各种针对该问题的算法层出不穷。对近期出现的面向TSP问题的免疫遗传算法进行了介绍与总结，在分析了

算法特点之后，提出了算法的改进方向，对TSP问题的研究进行了展望。

关键词：TSP问题；NP 难题；免疫遗传算法

中图分类号：TP301.6 文献标识码：A 文章编号：1672-7800（2011）06-0050-

1 TSP问题的几类求解方法

由于TSP是一个NP难题,国内外许多研究人员尝试用各种算法来求解TSP问题。其中，遗传算法以其良好的鲁棒性、灵活性、通用性,以及特别适合于求解大规模组合优化问题等特点,得到了应用。但由于算法本身还存在着一些缺陷 ,如易出现未成熟收敛,局部搜索能力差,进

化过程中不能很好地利用系统信息,进化后期易出现振荡现象等,因此不能保证以最大概率收敛到全局最优解。

此外，近年来出现的免疫算法借鉴生物免疫机理,能充分利用最优个体及系统的信息,且能有效保持种群多样性,在优化过程中,吸取了已有优化算法的有益思想,将随机搜索和确定性的变化结合在一起,减小了随机因素对算法本身的影响,能较好地消除不成熟收敛及振荡现象。因此在TSP问题的求解中得到广泛应用。

免疫遗传算法是基于生物免疫机制提出的一类改进的遗传算法。生物免疫系统在免疫应答过程中, 部分抗体作为记忆细胞保存下来, 当同类抗原再次侵入时, 记忆细胞被激活并产生大量抗体, 使再次应答比初次应答更迅速,体现了免疫系统的记忆功能。同时, 抗体与抗体之间也相

互促进和抑制, 以维持抗体的多样性及免疫平衡, 体现了免疫系统的自我调节功能。免疫遗传算

法保留了遗传算法的强大的全局随机搜索能力，提高了算法的搜索进度和速度。

2 免疫遗传算法原理

免疫遗传算法模拟生物抗体浓度自适应调节过程，将最优化解的目标函数对应为入侵生命体的抗原, 而解Xi的适应度f(Xi)对应为免疫系统产生的抗体，并根据抗体的浓度自适应的调

节搜索方向和解群的分布，从而大大提高算法克服局部收敛的能力。免疫遗传算法的内容包