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

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

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

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