李月

(中國傳媒大學(xué) 計算機學(xué)院，北京 100024)

基于遺傳算法的免疫算法對TSP問題的改進與研究

李月

(中國傳媒大學(xué) 計算機學(xué)院，北京 100024)

基于生物學(xué)種群遺傳原理的遺傳算法，在解決種群迭代次數(shù)過多的復(fù)雜問題中，由于遺傳算子總是以隨機的方式來迭代子代種群，在遺傳過程中難免會出現(xiàn)退化的現(xiàn)象，因此引入免疫算法來對其進行改進。通過增加免疫算子，即抽取問題的特征信息，經(jīng)過疫苗檢驗和退火選擇降低算法的退化概率，從而對遺傳算法進行了改進。最后，應(yīng)用TSP問題來具體說明免疫算法是如何對遺傳算法進行優(yōu)化與改進的。

遺傳算法；免疫算法；TSP問題

1 引言

近年來遺傳算法應(yīng)用非常廣泛，其基于生物學(xué) “物競天擇，適者生存”種群遺傳原理來解決了很多傳統(tǒng)方法很難解決的復(fù)雜問題，比如組合優(yōu)化類問題、工程類問題、圖像處理等等，就連機器人領(lǐng)域也有遺傳算法的應(yīng)用。但在解決問題的過程中遺傳算法也暴露了很多問題，為了解決這些問題，又引進了另一個同樣基于生物學(xué)原理的算法——免疫算法。免疫算法通過生物學(xué)免疫原理改進了遺傳算法，解決了遺傳算法的退化問題。本文通過使用TSP問題來研究免疫算法對遺傳算法所做的改進。

2 遺傳算法

2.1 遺傳算法生物學(xué)原理

遺傳算法顧名思義就是依據(jù)遺傳學(xué)衍化過來，它的生物學(xué)原理是根據(jù)生物學(xué)家達爾文所提出的進化論。它來源于自然選擇。而自然選擇的核心概括為三方面：遺傳、變異和選擇。

遺傳就是子代繼承親代，并保持相似的特性。自然界中的生物都有遺傳性，親代將自身的信息遺傳給子代，因此子代就可以保持和親代相同或者相似的性狀，就是這個特性，才使得物種能夠在生物界中穩(wěn)定的存在。遺傳學(xué)進步很大程度上促進和推動了進化論。

變異和遺傳不同，它體現(xiàn)出了不同子代之間以及子代和親代之間的差異性表現(xiàn)，生物因為就了變異的基因才能產(chǎn)生生物個體之間的不同。而變異則是隨機發(fā)生的，變異的選擇與積累使得生命體之間產(chǎn)生多樣性。它為生物的進化發(fā)展產(chǎn)生了可能。

選擇就是指生物體本身具有淘汰與保留的特征，它決定了生物進化的方向。生物上指的是自然選擇，也就是適者生存。自然界中的生物通過互相生存斗爭選擇出存留下來的生物基因，從而形成了自然選擇。因此具有了適應(yīng)性變異特征的生物體將被保留下來，相反不具有的個體將被自然界所淘汰，那些有利于生物生存下去的的變異基因就遺傳下去，日積月累，經(jīng)過了一代代的生存環(huán)境的選擇，逐步產(chǎn)生了新的物種。

染色體是生物的遺傳性狀的主要載體，基因通過染色體將特性傳遞給后代，而上問所講的三個內(nèi)容都是通過染色體來實現(xiàn)的。生物的進化論表明了自然界中的生物通過長期自然選擇的進化，科學(xué)家們從中獲得啟發(fā)，將自然選擇過程中蘊含的一些優(yōu)秀的思想應(yīng)用于工程技術(shù)領(lǐng)域，發(fā)展成為遺傳算法。

2.2 遺傳算法原理

遺傳算法簡稱GA，Genetic Algorithms，是由美國Holland教授提出的仿照自然界的生物的遺傳特性以及進化論從而形成的一種隨機搜索最優(yōu)化方法，又叫基因進化算法，或進化算法[1]。屬于啟發(fā)式搜索算法一種。 “優(yōu)勝劣汰，適者生存”是生物進化理論最為核心的思想，遺傳算法將其深化，把生物進化這種奇異的本領(lǐng)看成一種值得效仿的東西。遺傳算法在應(yīng)用于實際中的問題時，針對于優(yōu)化問題抽象為編碼，每一個編碼內(nèi)容表示為一個個體，而個體的組合稱為群體。首先選擇適應(yīng)度函數(shù)將這些個體編碼進行篩選，并通過遺傳學(xué)當中的基因復(fù)制、交叉以及變異的方法，保留適應(yīng)度高的個體，這種方法可以保證當前選擇的群體中擁有很高適應(yīng)度的個體將以更大的概率被保留，這些被保留的個體將通過繁衍和復(fù)制得到新的種群，新的種群將會繼承上一代的基因信息，并且比上一代更加優(yōu)秀。通過這樣一代代傳承，種群中個體適應(yīng)度將會不斷提高，直到這些個體達到了一定的條件。[1]

算法流程如圖1所示：

圖1 遺傳算法流程

(1)要產(chǎn)生初始群體，這里的群體概念就如上文提到的，是由通過某一編碼方式表示的個體組成的。這里選擇二進制進行編碼，基因是用0或1表示，還有其他方法比如互換編碼，這種編碼常用于解決排序問題，在著名的旅行商問題中，通過遍歷題目中的城市，形成的序列可以通過一串基因編碼來表示。還有樹形編碼和值編碼等等，不同的實際問題可以選擇不同的方式進行編碼。

(2)計算群體中每個個體的適應(yīng)度值，這里會涉及到適應(yīng)度函數(shù)這個概念。適應(yīng)度函數(shù)的解可以評價遺傳算法個體的好壞，適應(yīng)度函數(shù)的結(jié)果值越大，就越接近最優(yōu)解，也表明了個體更優(yōu)。因此，必須在這個過程中，我們需要確定一種轉(zhuǎn)換規(guī)則，這種規(guī)則可以使目標函數(shù)值和個體適應(yīng)度函數(shù)之間發(fā)生轉(zhuǎn)換。

(3)選擇算法，這一步選擇了個體中優(yōu)秀的基因，適應(yīng)度高的個體將以更大的概率遺傳到下一代群體中，反之則被淘汰。根據(jù)輪盤賭選擇算法，個體被選中的概率是與一個比值相關(guān)，這個比值是由個體的適應(yīng)度函數(shù)值與群體中所有的個體適應(yīng)度函數(shù)的和來決定的，值的大小為兩個的比值。

(4)交叉運算，根據(jù)兩個配對的生物體，將他們的染色依據(jù)設(shè)定好的交叉概率將他們之間的部分基因進行交換，因此將產(chǎn)生出兩個新的個體。其中的交叉方式也有很多對應(yīng)于二進制編碼，有單交叉點法、雙交叉點法等等。

(5)變異，個體的基因編碼會根據(jù)變異的概率被其他基因所取代，由此產(chǎn)生出新的個體，變異決定了局部搜索，并保證了種群的多樣性。單一般變異概率比較小，而交叉概率通常情況下設(shè)置的較大。最后產(chǎn)生新一代群體，這幾個步驟一直循環(huán)，一直到滿足停止準則就可以跳出。這里的停止準則可以理解為連續(xù)N代后的子代種群的最優(yōu)的個體適應(yīng)度都小于等于父代最優(yōu)個體的適應(yīng)度，就可以終止運算，但是不同的實際問題這里的終止條件不同。

2.3 遺傳算法的優(yōu)劣

遺傳算法可以應(yīng)用在很多領(lǐng)域，原因就在于它的特點：

?遺傳算法的操作對象是經(jīng)過編碼得到的參數(shù)，并不是原參數(shù)，這樣的好處是與問題領(lǐng)域無關(guān)可以快速隨機的搜索。而且搜索通過使用評價函數(shù)來進行啟發(fā)，過程簡潔，但是功能很強大。

?魯棒性強：遺傳算法通過“適者生存”這一進化原理，能在不同問題中通過在功能之間的協(xié)調(diào)平衡從而達到很高的生存能力。

?遺傳算法是群體搜索，可以使用并行處理，并不是通過沒有目的的窮舉，而是基于啟發(fā)式的搜索方法。

遺傳算法的優(yōu)點絕對不止上面三條，但是除了優(yōu)點，還有一些缺點更值得我們關(guān)注：

?在實際過程中會發(fā)生早熟收斂問題.

?由于遺傳算子產(chǎn)生于一定的條件概率下，迭代搜索過程是隨機的，因此這些算子能使群體中的個體發(fā)生進化，也會使他們發(fā)生退化。

2.4 遺傳算法的應(yīng)用

(1)函數(shù)優(yōu)化。遺傳算法的一個非常典型的應(yīng)用領(lǐng)域是函數(shù)優(yōu)化，也是評價遺傳算法性能的常用方法。在解決函數(shù)優(yōu)化問題時，相比起其他算法，該算法在針對非線性、多模型、多目標這類特殊問題時表現(xiàn)極好。

(2)組合優(yōu)化。在問題空間非常大的條件下，對于從復(fù)雜的組合問題出優(yōu)化出最優(yōu)解，遺傳算法效果最好。例如，旅行商問題、裝箱問題、背包問題等等，這些問題再采用傳統(tǒng)方式時，則變得很難解決。[2]

(3)機器人。在使機器人變得更加智能的過程中，也離不開遺傳算法的幫助。遺傳算法可以為機器人規(guī)劃行動路徑，對于機器人各個關(guān)節(jié)結(jié)構(gòu)的協(xié)同運轉(zhuǎn)也起到了很關(guān)鍵的作用。

(4)在圖像處理、生產(chǎn)調(diào)度等問題也有很好的應(yīng)用。

3 基于遺傳算法的免疫算法

3.1 免疫算法生物學(xué)原理

圖2是免疫算法的生物學(xué)原理，抗原與T細胞接觸，被T細胞的受體識別，把自身的信息傳遞給T細胞，從而活化了T細胞?；罨腡細胞通過分泌淋巴因子來進一步活化B細胞，促進B細胞活化、增值與分化，并產(chǎn)生抗體來與抗原進行結(jié)合，抗體在產(chǎn)生過程中也會經(jīng)過選擇、交叉和變異等過程更新抗體群體；在這個過程中，抗原與抗體以及抗體與抗體之間互相的刺激和抑制關(guān)系維持著免疫平衡[4]。而圖中的記憶細胞也是T細胞分化成的，這些記憶細胞會保存抗原侵入的一些信息，等到再有同樣的抗原侵入時會立刻產(chǎn)生大量特異性抗體。

圖2 生物免疫機制的抽象模型

3.2 免疫算法的基本原理及對遺傳算法的改進

上章的內(nèi)容中，介紹了遺傳算法的缺點主要因為遺傳算子總是以隨機的方式進行子代迭代，因此在遺傳過程中會出現(xiàn)退化的現(xiàn)象，而且在求解過程中，遺傳算法對特征信息利用也明顯不夠。很多實踐以及理論表明，僅僅通過遺傳算法在研究很多復(fù)雜問題上還是遠遠不足的，因此借助其他算法的優(yōu)秀的相關(guān)知識與理論和遺傳算法結(jié)合起來是很有必要的，可以很大程度上提高算法的整體性能。這里可以引入免疫算子相關(guān)操作。因此該算法的核心在于考慮免疫算子的構(gòu)造，免疫算子包括兩個步驟來確定，一個是為了提高子群適應(yīng)度而對個體進行接種疫苗，另一個是為了避免發(fā)生退化來進行免疫選擇[5]。

免疫算法針對遺傳算法的步驟進行了改進(如圖3)。

圖3 免疫算法的流程示意

(1)初始化抗體群體，提取出求解問題的基本特征。這里涉及疫苗的概念，這里的疫苗實際上是對實際問題中的目標函數(shù)和約束條件的描述，這些先驗知識的提取就是抽取疫苗，而在免疫算法中抗原在實際問題中對應(yīng)的就是要求解的問題。

(2)計算抗體的適應(yīng)度當滿足條件時停止，否則就進行交叉和變異操作，根據(jù)不同的抗體和抗原的親和力值的高低，使用輪盤賭選擇兩個抗體，以一定的概率將這兩個抗體變異編碼基因，再進行交叉操作后，最終可以得到到新的抗體。

(3)整個免疫算法的核心。

首先介紹一下免疫算子，在生物原理中的免疫系統(tǒng)由兩種免疫機制，特異性和非特異性免疫，它和這兩種免疫方式相對應(yīng)，分別為目標免疫和全免疫。全免疫是在初始化階段進行的，即群體中每個個體發(fā)生變異后，每個環(huán)節(jié)都要發(fā)生一次免疫；而目標免疫就顧名思義是在特定點發(fā)生免疫反應(yīng)，它在伴隨著每代抗體群體進化的過程中都發(fā)揮作用。免疫算子包括接種疫苗和免疫選擇兩個內(nèi)容，接種疫苗是按照疫苗，也就是實際問題抽取出來的先驗知識對個體某基因位做出修改，得到的個體將以更大的概率擁有更高的適應(yīng)度[4]。

免疫選擇在注射免疫之后執(zhí)行，它分為兩步，首先檢測接種的疫苗，如果他的適應(yīng)度低于它的父代，說明發(fā)生了退化，說明這個個體不如他的父代，因此用父代代替這個個體。相反，如果子代的適應(yīng)度高，那他將作為新的父代，繼續(xù)執(zhí)行下一次迭代。第二步是退火選擇，依賴于適應(yīng)度函數(shù)的結(jié)果，以一概率選擇子代群體加入新的父代群體。整個流程的最后一步就是更新群體，并且迭代循環(huán)這個過程。在免疫算法的流程中，疫苗非常重要，它決定了算法的運行效率，但是它的好壞并不影響算法收斂性，而疫苗只會影響免疫算子中的接種疫苗這一步[5]。

3.3 免疫算法的應(yīng)用及現(xiàn)狀

免疫算法從提出至今，在不斷改進的基礎(chǔ)上，其功能越發(fā)強大，而它的應(yīng)用領(lǐng)域也越來越多：包括在TSP組合優(yōu)化問題、圖像處理、機器人(多智能體決策系統(tǒng)和分布式自動機器人系統(tǒng)等)、人工神經(jīng)網(wǎng)絡(luò)的規(guī)劃等等問題都有其應(yīng)用，領(lǐng)域涉及非常廣泛。但是由于免疫算法發(fā)展并不如遺傳算法那么好，在很多方面需要投入更多的研究。第一個問題就是免疫算法性能的研究，其中最低程度上包括了收斂性問題以及有效性等等，但目前相關(guān)的研究成果不多。還有就是免疫算法和其他算法的對比研究也并不深入，這個研究對于認識人工免疫系統(tǒng)特點有很重要的意義。

4 兩種算法TSP問題的比較

TSP問題稱為旅行商問題，假設(shè)一個旅行商人要去n個城市，他需要選擇行走路線，從而達到每個城市只能走一次，最終回到原點城市，路徑選擇的目標是得到最短路徑。這是一種組合優(yōu)化問題。而組合優(yōu)化問題會在很多部分中產(chǎn)生極值點，復(fù)雜性比較強，因此想要準確求出問題的最優(yōu)解采用傳統(tǒng)方法是很困難的。

4.1 遺傳算法求解TSP問題的思想

對于遺傳算法來說，解決的重點包括編碼方案的選擇，適應(yīng)度函數(shù)的設(shè)計，如何設(shè)置約束條件，以及選擇機制等等內(nèi)容，這些問題解決好了，對于求解實際問題來說就能使遺傳算法可以發(fā)揮它的優(yōu)勢。

(1)編碼方案 在TSP問題中，由于最終目標是找到一條路徑策略，使得路徑之和最小，并且每個城市且只能出現(xiàn)一次，最終回到初始城市，所以這里使用二進制編碼就不太合適，可以使用互換編碼，即把一個城市節(jié)點看做一個基因，編碼遍歷過得城市序列。

(2)適應(yīng)度函數(shù) 適應(yīng)度函數(shù)可以評價出一個個體的優(yōu)劣，對每個個體進行評估，它是算法的關(guān)鍵，在實現(xiàn)優(yōu)勝劣汰起到重要的作用。還是研究待求解問題，找出一條路徑之和最小的解，因此可以把路徑之和的倒數(shù)作為算法的適應(yīng)度函數(shù)。路徑越短，分數(shù)越高。即

(1)

其中Td表示這個個體的總路徑長度。

(3)選擇運算 選擇算法的目的是選擇適應(yīng)度值高的個體，賦予它高概率進行后代遺傳，這是優(yōu)勝劣汰最重要的一步。在這里使用輪盤賭選擇方法，把該個體的適應(yīng)度值和群體適應(yīng)度總值計算比值，得到的結(jié)果作為這個個體的遺傳概率。因此公式為

(2)

(4)交叉 首先要設(shè)置交叉概率，交叉概率應(yīng)該設(shè)置的比較大，可以設(shè)置為80%或者更高，這樣可以讓得到更多的交叉新個體。最好的解決方式是采用自適應(yīng)的方法。交叉方式有很多種，這里可以采用部分匹配交叉的方式，簡單舉個例子來說明部分匹配交叉方式。

A= 3 1 ‖ 2 4 5 ‖6 7 8

B= 5 2 ‖ 8 6 3 ‖7 1 4

將這兩個個體進行交叉，來獲得新個體

A’=3 1 ‖ 8 6 3 ‖6 7 8

B’=5 2 ‖ 2 4 5 ‖7 1 4

可以看出得到的兩個個體中里面有重復(fù)的城市號，因此需要將這兩個進行調(diào)整將A’第一個3替換成B’最后一個4，將A’中倒數(shù)第三個6替換成B’中第二個2，將A’中最后一個8替換成B’中第一個5，得到結(jié)果如下：

A”=4 1 ‖ 8 6 3 ‖2 7 5

B”=8 6 ‖ 2 4 5 ‖7 1 3

(5)變異 變異是基于變異概率來執(zhí)行，變異概率應(yīng)當設(shè)的很小，一般為0.05，變異有兩種方法，一種是內(nèi)變異另一種是外變異，內(nèi)變異指的是個體內(nèi)部兩個基因互換，是自己內(nèi)部發(fā)生的一種變異；外變異指的將某一基因用外部基因替換。在TSP問題中使用內(nèi)變異更加合理，這樣可以由一個初始串經(jīng)過變異得到很多新的個體。

但是交叉或者變異的結(jié)果有時可能是無效解，這時候可以選擇拋棄這個個體，生成新的有效個體，也可以人為的進行調(diào)整。而交叉概率和變異概率有時候會給結(jié)果帶來截然不同的結(jié)果，可能會使算法退化。

4.2 改進遺傳算法

免疫算法在改進遺傳算法的問題上主要有疫苗的提取和免疫算子構(gòu)造這兩方面，因此主要介紹這兩個問題在解決TSP問題上的是如何實現(xiàn)的。

(1)抽取疫苗 疫苗是問題的特征信息，在解決問題的過程中，時刻以問題的特性作為我們的參考依據(jù)。首先要做的就是分析TSP問題，當處于某一城市，首先應(yīng)當選擇離自己最近的一個城市作為下一個目的地，但是如果最近的城市是走過的城市，就取次近的城市作為下一個節(jié)點，以此類推。因此可以把這個策略作為疫苗。

(2)免疫算子的構(gòu)造 注射疫苗：在一個個體上，隨機選取某一基因也就是某一個城市，按照上述疫苗描述將選定的下一個城市節(jié)點寫到該城市的后面，并將這個選定的下一個城市節(jié)點從之前的位置刪除。例如圖4所示。

圖4 城市遍歷示意圖

原來的序列為123456，我們選定2號城市，離它最近的是5，因此我們將5移到2之后，將5原來位置刪去，得到的序列為125346，在由253組成的三角形中，d25一定為最短邊，而在由456組成的三角形中，d46就不一定。因此多數(shù)情況下我們可以得到d25+d53-d23

疫苗檢測：這個步驟中和之前在介紹原理時所介紹的一樣，新的子代和父代進行比較，選擇好的作為新的父代，然后在執(zhí)行退火選擇算法，其中的概率表達式為：

(3)

其中，f(xi)為適應(yīng)度函數(shù)。

5 總結(jié)

遺傳算法采取了自然界中適者生存的理念，將遺傳學(xué)的內(nèi)容引入到工程技術(shù)中，解決了很多問題，這是一種隨機的，啟發(fā)式的算法，每一代都以高概率遺傳優(yōu)秀的個體，并且得到優(yōu)秀后代，通過交叉、變異等操作，一代代進行迭代，最終產(chǎn)生最優(yōu)的個體。雖然遺傳算法自身存在缺陷，但是這種算法實現(xiàn)簡單，功能強大，是很多后續(xù)算法的基礎(chǔ)。

針對遺傳算法出現(xiàn)退化現(xiàn)象以及對于問題的特征信息的關(guān)注度不高的問題，引入了免疫算法，基于遺傳算法的免疫算法增加了疫苗的概念，即對問題分析，抽取他的特征信息，在最重要的免疫算子階段注射疫苗，并且通過疫苗檢驗和退火選擇降低算法的退化概率，從而增強了算法的功能。

免疫算法實際上依據(jù)的生物原理是免疫系統(tǒng)，將問題抽象為抗原，抗體作為解決問題的解，通過交叉變異以及免疫算子等操作，得到相對而言最優(yōu)的抗體。免疫算法和遺傳算法很多思想相似，但是應(yīng)用的生物學(xué)背景不一樣。免疫算法較遺傳算法在處理很多問題上更加有效，對于多峰值的搜索問題也更加高效并且準確，免疫算法在應(yīng)用領(lǐng)域上完善了遺傳算法，而他并非僅僅是改進遺傳算法，而且用有更大的發(fā)展前景，目前免疫算法的研究還不是那么深入，有很多領(lǐng)域值得研究，在未來相信免疫算法會有更大的發(fā)展。算法之間的結(jié)合來解決實際問題也有著更多實用價值，畢竟一種算法總是有他的局限性，通過幾種算法的結(jié)合，相信會發(fā)揮更大的作用。

[1]陳國良，王煦法，莊鎮(zhèn)泉.遺傳算法及其應(yīng)用[M].北京：國防出版社，2001.

[2]王宏生，孟國艷.人工智能及其應(yīng)用[M].北京：國防工業(yè)出版社，2009.

[3]陳光.遺傳算法在人工智能中的應(yīng)用[J].福建電腦，2005，(11)：40-41.

[4]王磊，潘進，焦李成.免疫算法[J].電子學(xué)報.2000，(07).

[5]吳昳恬.基于免疫算法的TSP問題求解[J].科技信息，2011，(36)：451-452.

[6]TangZ，YamaguchiT，TashimaK，etal.Multiple-valuedimmunenetworkmodelanditssimulations[C].Proceedingsofthe27thInternationalSymposiumonMultiple-valuedlogic，Autigonish，Canada，May28-30，1997：233-238.

[7]王小平，曹立明.遺傳算法理論應(yīng)與軟件實現(xiàn)[M].西安：西安交通大學(xué)出版社，2002：129.

[8]王煦法，等.一種基于免疫原理的遺傳算法[J].小型微型計算機系統(tǒng)，1999，20(2)：117-120.

[9]孫曉亮.邵定宏基于疫苗接種的免疫算法[J].計算機工程與設(shè)計，2007，(16).

[10]LeeW，LeeS，LeeBH，etal.AnEfficientPlanningAlgorithmforMulti-headSurfaceMountingMachinesUsingaGeneticAlgorithm[J].JournalofUniversalComputerScience，1999，5(12)：833-854.

(責(zé)任編輯：王謙)

Improvement and Research on TSP Problem by Immune Algorithm Based on Genetic Algorithm

LI Yue

(School of Computer Science，Communication University of China，Beijing 100024，China)

Genetic algorithm based on the genetic principle of biological population，in the complex problem of solving the number of population iterations，because the genetic operators always in a random way to iterate the progeny population，in the genetic process will inevitably degenerate，so the immune algorithm is introduced to improve it.By increasing the immune operator，that is，extracting the characteristic information of problems，the degradation probability of the algorithm is reduced by the vaccine test and the annealing method，and the genetic algorithm is improved.Finally，the TSP problem is used to describe how the immune algorithm can optimize and improve the genetic algorithm.

immune algorithm；genetic algorithm；TSP

2017-04-06

李月(1992-)，女(漢族)，北京市人，中國傳媒大學(xué)碩士研究生.E-mail：nemoly@sina.com

TN

A

1673-4793(2017)04-0058-06