论文部分内容阅读
随着免疫学理论研究的不断发展,人们对生物免疫系统的认识不断深入,提出了人工免疫系统,该系统已经被广泛应用于科学研究和工程实践的众多领域。免疫算法(Immune Algorithm,简称IA)构造简单,在一定条件下具有强大的搜索能力和全局收敛性。由于使用随机搜索技术,保证了算法全局收敛性,但其局部寻优的性能受到损害,且收敛速度也不理想。而蚁群算法(Ant Colony Algorithm,简称ACA)充分利用了目标问题的信息,局部寻优能力强,收敛速度快,但是,容易陷入局部最优的陷阱。可以说,IA提供了全局性的点搜索方法,而ACA提供了局部性的面搜索方法,两类方法各有利弊。针对IA存在的上述问题,本文对其进行改进得到了一种基于蚁群的免疫算法(The Immune Algorithm based on Ant Colony,简称IAAC),该算法利用ACA局部寻优能力强、收敛速度快的优点,结合其正反馈的思想,逐渐在每只蚂蚁所走过的禁忌表中形成较优解,然后将这些较优解的片段提取出来作为IA的疫苗,在群体更新阶段注入IA,求解问题。这样既保持了种群的多样性,又避免了每次迭代中由于新更新的抗体亲和力低而被淘汰。此方法利用了点面结合的方法进行搜索,使得两种算法互为补充。针对旅行商问题(Traveling Saleman Problem,简称TSP)中存在的亲和力计算方法值域范围较大的缺点,本文根据当前代中最优解和最差解设计了一种计算亲和力的方法,其值域为[0,1],亲和力越接近1,抗体越趋于最优解,亲和力越接近0,抗体越差。本文把IAAC算法应用到TSP中,在Visual C++6.0平台上对BIA和IAAC进行了仿真,并对标准的TSPLIB中的八个问题(Uleysses16、Uleysses22、Att48、Eil51、Berlin52、St70、Eil76、Gr96)进行了测试,测试结果表明,该方法求解TSP是有效的。