基于Elitism策略的改進免疫遺傳算法求解TSP問題

摘要:TSP問題是一類典型的NP完全問題。作者結合Elitism策略提出了一種新的改進免疫遺傳算法。該算法既保留了遺傳算法的全局隨機搜索的優點，又避免了免疫遺傳算法的早熟、收斂速度慢等缺點。經仿真實驗對比，在求解TSP問題時，該文提出的新算法具有收斂速度快及動態收斂性好的優點。

關鍵詞: Elitism策略;遺傳算法;免疫遺傳算法;旅行商問題;優化

中圖分類號:TP301文獻標識碼:A文章編號:1009-3044(2010)01-193-03

A Modified Immune Genetics Algorithm with Elitism Strategy for Traveling Salesman Problems

WANG Shu-xia， TU Jun-ying， ZHENG Yan-jun

(School of Computer and Information Science， Xiaogan University， Xiaogan 432100， China)

Abstract: In this paper， a new modified immune genetics algorithm with elitism is designed to solve traveling salesmen problems(TSP). The proposed algorithm holds the global searching， and avoids the shortcomings of the immune genetics algorithm， such as converging slowly and precocity. As the experimentations show， the new algorithm has quick convergence speed and better dynamic convergence for solve TSP.

Key words: elitism strategy; genetics algorithm; immune genetics algorithm; traveling salesman problems; optimization

旅行商問題(Traveling Salesman Problem，簡稱TSP)就是從n個城市中的某一城市出發，不重復地走完其余n-1個城市并回到原出發點，在所有可能的回路中求出回路長度最短的一條[1]。或者說搜尋整數子集X={1，2，…，n}(X的元素表示對n個城市的編號)的一個排列X={x1，x2，…，xn}，使得閉合路徑取最小值。式中的d(xx，xj)表示城市xi到城市xj的距離。TSP問題是組合優化問題的代表，屬于NP完全問題。[2]

遺傳算法(Genetic Algorithm，GA) 作為一種生物進化計算模型，是在1975年由Michigan大學Holland教授提出的一種啟發式優化算法，具有全局并行搜索的特點，但這種算法的主要問題在于容易陷入局部最優解、早熟收斂、局部搜索能力較差及收斂速度慢等。人工免疫算法模擬了自然免疫系統的抗體繁殖策略，引入了抗體濃度調節機制，從而有效的調節了選擇壓力，保持了解群體的多樣性，克服了遺傳算法容易出現早熟收斂和陷入局部最優的缺點。但AIA存在運行速度和收斂速度都較慢的不足[3]。

針對這些問題，本文利用精英選擇策略(elitism strategy)提出了一種新的改進免疫遺傳算法，簡稱為IGAE(Immune Genetic Algorithm with Elitism)，用來求解TSP問題。IGAE有兩個重要特點，其一是抗體的親和力和期望繁殖率在進化時可以動態調整，以達到平衡群體的多樣性和算法的收斂速度的目的，使算法能快速求出優質解;其二是采用了Elitism策略，可以確保算法收斂到全局最優解。與遺傳算法和免疫算法進行對比，結果表明，在相同條件下， IGAE具有收斂速度快及動態收斂性好等優點。

1 改進的免疫遺傳算法的設計思想

免疫遺傳算法與遺傳算法一樣，包含選擇、交叉和變異三種操作。兩者不同的是，在遺傳算法中，個體的品質只用適應度一個指標評價;但在免疫遺傳算法中，個體(即抗體)的品質同時采用了適應度和濃度兩個指標共同來評價。抗體的濃度的概念是由Fukuda首先提出來的[4]。引入濃度概念之后，和遺傳算法對比，免疫遺傳算法的群體更新策略有了較大改變。并且，在克隆操作時，在遺傳算法中，個體的選擇概率只與適應度有關;而在免疫遺傳算法中，個體的選擇概率則既與適應度有關，也與濃度有關。同遺傳算法相比，免疫遺傳算法具有更好的群體多樣性保持能力，其收斂性也更好[5]。

1.1 本算法涉及的幾個定義

假定有一個規模為Sp的抗體群，其中每一個抗體都可表示成一個具有n個元素的一維向量。以下給出涉及的幾個定義，包括抗體的親和力、濃度、期望繁殖率、選擇概率以及抗體群多樣性的指標等。

定義1.1 在特定的、規模為Sp的抗體群中，任取兩個抗體v和w，設抗體v和w的適應度分別為fv和fw，抗體v和w的歐氏距離記為d(v，w)，親和力指標記為J(v，w)。假定ε是一個適當小的正常數，若有:

成立，則稱抗體v與抗體w相似。式中，α>0是反映歐氏距離d(v，w)和適應度差值|fv-fw|各自在J(v，w)中相對重要性的一個參數;ε稱為抗體親和力閥值。

在這個定義中，歐氏距離用來反映兩個抗體在結構上的相似性，而適應度的差值用來反映兩個抗體在品質上的相似性。其中，抗體v與抗體w之間的歐氏距離定義為:

將式2代入式1，可得:

式(3)是本文給出的一種新的抗體親和力定義方法。這樣定義有兩個優點:第一，將抗體相似的兩個重要特征，即歐氏距離和適應度值，統一在一個公式中，使抗體親和力的定義變得更為簡潔、規范;第二，通過引入可調參數α ，可對歐氏距離和適應度值兩者在親和力指標中的相對重要性進行調整，這種調整對免疫遺傳算法在進化過程中同時兼顧群體的多樣性和收斂速度以保證快速獲得高質量的解是非常重要的。

通常情況下，在免疫遺傳算法進化過程的初期和中期，為了使群體保持良好的多樣性，避免算法陷入局部最優，我們希望α取較大的值;而在進化過程的后期，由于群體中各個體的品質己被大大改進，所以希望α取較小的值，以加速算法的收斂速度。基于這一考慮，我們將參數α隨算法迭代指針t的變化關系定義為如下的公式:

式中，α0是參數 的初始值，0.5<α0<2;1

定義1.2 在特定的、規模為Sp的抗體群中，與抗體v相似的抗體的個數稱為抗體v的濃度，記為Cv。

定義1.3 對于特定的、規模為Sp的抗體群，抗體v的期望繁殖率ev定義為:

式中，β是反映抗體的適應度和濃度各自在期望繁殖率中非常重要的一個參數。

式(5)是本文給出的一種新的抗體期望繁殖率的定義方法。已往的人工免疫算法中，抗體的期望繁殖率與其適應度和濃度的關系是完全固定的(相當于在式5中取β=1)，無法調整適應度和濃度各自在期望繁殖率中的相對重要性，本文給出的這個定義很好地解決了這個問題。

定義1.4 對于特定的、規模為Sp的抗體群，設抗體v的期望繁殖率為ev，則抗體v被選擇進行復制的概率Qsv為:

從該式可以看出，人工免疫算法的選擇概率不僅與個體的適應度有關，而且與個體的濃度有關。這是人工免疫算法與遺傳算法最大的差別之處。

定義1.5 對于特定的、規模為Sp的抗體群，其多樣性指標Idiv定義為:

式中，ci為第i個抗體的濃度。

1.2 Elitism策略

遺傳算法的最大缺陷就是容易陷入局部最優，為了防止當前群體的最優個體在下一代發生丟失，導致遺傳算法陷入局部最優而不能收斂到全局最優解，De Jong在其博士論文中提出了“精英選擇”(elitist selection or elitism)策略[6]，也稱為“精英保留”(elitist preservation)策略。其主要思想是，將群體在進化過程中迄今出現的最好的個體直接復制到下一代中，而不進行配對交叉。這種選擇操作即復制。De Jong在其論文中對精英選擇策略作了如下定義:

定義1.6 設到第m代時，群體中a*(m) 為最優個體。又設A(m+1)為新一代群體，若A(m+1)中不存在a*(m)，則把a*(m)加入到A(m+1)中作為A(m+1)的第Sp+1個個體，這里Sp為群體的大小。

將精英個體加入到新一代群體中后，為了保持群體的大小規模和原先一致，則可以將新一代群體中適應度值最小的個體淘汰掉。精英保留策略對改進標準遺傳算法的全局收斂能力產生了重大作用[7]。

2 IGAE求解TSP的算法及步驟

2.1 使用IGAE求解TSP的算法

以上面定義的抗體親和力、濃度、期望繁殖率、選擇概率等概念和計算公式以及精英保留策略為基礎，給出如下求解TSP的改進免遺傳疫算法:

在TSP問題中，走遍n個城市的最短距離就是算法的抗原，而從其中的一個城市出發，走遍其余(n-1)個城市只去一次的路徑有(n!/2n)條[8]。對這n個城市編號，其號碼分別為1，2，…，n，并且把商人所在城市即出發城市編為第1號，其它城市可隨意編號。把這n個城市的編號任意排列成一個長度為n的字符串就形成一個抗體，因此抗體空間包含n!個抗體，而解空間包含(n!/2n)個可行解。為了縮小抗體空間，提高搜索效率，本文采用對于TSP問題較直觀的抗體編碼方式，即將每個抗體的第一個基因位(即字符串的第一個字符)固定為出發的城市編號1。這樣每個抗體只有(n-1)個基因位可任意排列，抗體空間包含(n-1)!個抗體。而這種編碼方式也更加符合TSP問題的實際情況，只是從固定的第一個城市出發，最終又返回到第一個城市。

在仿真實驗中，針對TSP問題的特殊性，在選擇算法中，采用比例選擇法;在交叉算法中，采用順序交叉算子;在變異時，采用單點基因位換位算子和多對基因位換位算子。

2.2 使用IGAE求解TSP的步驟

Step1:初始化參數。設置群體規模為100，迭代次數為20，抗體親和力閥值ε=0.1， α0=1.2，β0=1.6;

Step2:初始化抗體群。在目標函數的解空間中隨機產生n個初始抗體，組成抗體群;

Step3:確定每個抗體的適應度，并將適應度最大的抗體作為精英抗體賦予變量x;如果是第一代抗體群，則轉到Step6，否則繼續;

Step4:如果這一代抗體群中找不到與精英抗體適應度相同的抗體，則將保存在變量x中的精英抗體復制一個到抗體群中，同時將該抗體群中適應度最小的那個抗體刪除，否則繼續;

Step5:如果這一代抗體群中適應度最大的抗體其適應度的值大于精英抗體的適應度值，則將抗體群中適應度最大的抗體復制一個，并以它作為新的精英抗體替代保存在專用變量中的精英抗體，否則繼續;

Step6:根據抗體的親和力定義，即公式(3)，計算出每個抗體的濃度;

Step7:根據公式(5)計算出每個抗體的期望繁殖率;根據公式(6)計算出每個抗體的選擇概率;根據選擇概率對抗體群執行選擇和復制操作;

Step8:對抗體群執行交叉操作，設置交叉概率Pc∈[0，l]，本實驗取值為0.6;

Step9:對抗體群執行變異操作，設置變異概率Pm∈(0，l)，本實驗取值為0.01;

Step10:判斷設置的終止條件是否滿足。若終止條件滿足，則輸出結果，算法停止;若終止條件不滿足，則返回Step5，繼續循環操作。

3 仿真實驗

利用MATLAB7.0編程實現遺傳算法GA、免疫算法IA和加入精英選擇策略的改進免疫遺傳算法IGAE求解TSP問題。分別取頂點數為10，15，20，30，50，在邊長為20的正方形區域內隨機選擇頂點。每種算法重復進行10次計算。表1～表3分別給出了三種算法求解TSP問題的實驗結果。

表1 遺傳算法(GA)求解TSP的實驗結果表2 免疫算法(IA)求解TSP的實驗結果

從表1～表3來看，在同種條件下，遺傳算法收斂速度快但容易陷入局部最優;人工免疫算法求出的最優解較之遺傳算法好，但運行速度和收斂速度都較慢;引入Elitism策略的改進免疫遺傳算法無論是求出的最優解還是所用時間較之前兩種算法都大大提高了。

4 結束語

該文將Elitism策略運用到免疫遺傳算法中，提出了一種新的基于Elitism策略的改進免疫遺傳算法。該算法可以動態調節抗體的親和力和期望繁殖率，使算法具有更快的運行速度和更強的求解能力。通過仿真實驗，在求解TSP問題時，基于Elitism策略的改進免疫遺傳算法具有更快的收斂速度及動態收斂性好等優點。由于本仿真實驗中采用的城市數屬小規模TSP，對于大中型規模的TSP求解，筆者將作進一步的探討。

參考文獻:

[1] 王曙霞，葛東媛.一種TSP求解的人工免疫遺傳算法[J]. 孝感學院學報，2005，25(3):69-71.

[2] Johnson D S，McGeoch L A. The Traveling Salesman Rob-lem:A Case Study in Local Optimization[M].Aarts E H L，Lenstra J K，eds. Local Search in Optimization，1997:215-310.

[3] Yuji Watanabe，Akio Ishiguro，Yoshiki Uehikawa. Decentralized Behavior Arbitration Meehanism for Autonomous Mobile Robot Using Irnrnune Network In Artificial Immune Systems and their Applications， Dasgupta D.(ed.)， Springer Verlag， 1998:187-209.

[4] Toyoo Fukuda， Kazuyuki Mori and Makoto Tsukiyama. Parallel Search for Multi-Modal Function Optimization with Diversity and Learning of Immune Algorithm. In Artificial Immune Systems and Their Applications， Dipankar Dasgupta (Ed.)， Springer，1998:210-220.

[5] Dipankar Dasgupta and Hal Brian. Mobile Security Agents for Network Traffic Analysis， 0-7695-1212-7/01， 2001IEEE:332-340.

[6] 何琳，王科俊. 最優保留遺傳算法及其收斂性分析[J].控制與決策，2000，15(1):63-66.

[7] 危明， 李元香， 姜大志，等. 基于精英策略的反序—雜交算法[J].武漢理工大學學報(信息與管理工程版)，2008，30(4):514-518

[8] 羅印升， 李人厚. 人工免疫算法在函數優化中的應用[J].西安交通大學學報， 2003， 37(8):840-843.