人工免疫算法在TSP中的應(yīng)用研究.pdf

1、隨著免疫學(xué)理論研究的不斷發(fā)展，人們對(duì)生物免疫系統(tǒng)的認(rèn)識(shí)不斷深入，提出了人工免疫系統(tǒng)，該系統(tǒng)已經(jīng)被廣泛應(yīng)用于科學(xué)研究和工程實(shí)踐的眾多領(lǐng)域。
　　 免疫算法(Immune Algorithm，簡(jiǎn)稱(chēng)IA)構(gòu)造簡(jiǎn)單，在一定條件下具有強(qiáng)大的搜索能力和全局收斂性。由于使用隨機(jī)搜索技術(shù)，保證了算法全局收斂性，但其局部尋優(yōu)的性能受到損害，且收斂速度也不理想。而蟻群算法(Ant Colony Algorithm，簡(jiǎn)稱(chēng)ACA)充分利用了目標(biāo)問(wèn)題的信

2、息，局部尋優(yōu)能力強(qiáng)，收斂速度快，但是，容易陷入局部最優(yōu)的陷阱?？梢哉f(shuō)，IA提供了全局性的點(diǎn)搜索方法，而ACA提供了局部性的面搜索方法，兩類(lèi)方法各有利弊。
　　 針對(duì)IA存在的上述問(wèn)題，本文對(duì)其進(jìn)行改進(jìn)得到了一種基于蟻群的免疫算法(TheImmune Algorithm based on Ant Colony，簡(jiǎn)稱(chēng)IAAC)，該算法利用ACA局部尋優(yōu)能力強(qiáng)、收斂速度快的優(yōu)點(diǎn)，結(jié)合其正反饋的思想，逐漸在每只螞蟻所走過(guò)的禁忌表中形成較

3、優(yōu)解，然后將這些較優(yōu)解的片段提取出來(lái)作為IA的疫苗，在群體更新階段注入IA，求解問(wèn)題。這樣既保持了種群的多樣性，又避免了每次迭代中由于新更新的抗體親和力低而被淘汰。此方法利用了點(diǎn)面結(jié)合的方法進(jìn)行搜索，使得兩種算法互為補(bǔ)充。
　　 針對(duì)旅行商問(wèn)題(Traveling Saleman Problem，簡(jiǎn)稱(chēng)TSP)中存在的親和力計(jì)算方法值域范圍較大的缺點(diǎn)，本文根據(jù)當(dāng)前代中最優(yōu)解和最差解設(shè)計(jì)了一種計(jì)算親和力的方法，其值域?yàn)閇0，1]，親