基于歐式距離的多種群克隆免疫遺傳算法研究

彭業(yè)飛　馮智鑫　張維繼

摘要： 為了克服基本免疫遺傳算法最優(yōu)解質(zhì)量不高、種群多樣性較低的缺陷，將免疫系統(tǒng)中抗體多樣性的維持機(jī)制引入遺傳算法，同時提高種群多樣性和避免出現(xiàn)早熟，提出了歐式距離的多種群克隆免疫遺傳算法，并分析了歐式距離原理、多種群原理和克隆選擇原理?；跉W式距離的多種群劃分提高了算法全局收斂性能，克隆選擇操作則提高了算法的局部搜索能力。利用測試函數(shù)分別對免疫算法、免疫遺傳算法和本文提出的改進(jìn)算法進(jìn)行仿真比較，結(jié)果表明所提方法可行有效，收斂性好。

關(guān)鍵詞：免疫遺傳；種群多樣性；歐式距離；多種群；克隆

中圖分類號：TP312 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）05-0214-04

Abstract：The base Immune Genetic Algorithm has the deficiency such as the low-quality optimal solution and the monotonous species diversity. In order to overcome the deficiency， the Multiple Population Clone Immune Genetic Algorithm has been put forward in this paper. The antibody diversity maintaining mechanism has been join in the Genetic Algorithm inside the new algorithm.The theory of the Euclidean- Distance、Multiple -Population and Clone- Select has been analyzed in the paper. The global convergence ability is enhanced when multiple population diving based Euclidean Distance， while local search ability is strengthened when clone selecting. The Immune Algorithm 、Immune Genetic Algorithm and The new algorithm is contrasted through simulating based test functions. The results show that the new algorithm is feasible.

Key words：Immune Genetic； Species Diversity； Euclidean Distance； Multiple Population； Clone

1 概述

免疫遺傳算法（Immune Genetic Algorithm，IGA）將遺傳算法（Genetic Algorithm，GA）和人工免疫算法（Immune Algorithm，IA）相互交叉融合，如今已經(jīng)發(fā)展成為一種應(yīng)用廣泛的新型算法[1]?；贕A 算法的迭代架構(gòu)，IGA算法利用生命科學(xué)中的免疫原理，以先驗(yàn)知識、啟發(fā)式的規(guī)則作為疫苗并構(gòu)造免疫算子，加快了全局收斂的速度，同時又避免了局部早熟的缺陷。IGA 算法在解決諸如組合優(yōu)化、車間調(diào)度等復(fù)雜優(yōu)化問題方面較GA 算法及IA算法有較大優(yōu)勢。近年來，也有很多學(xué)者 IGA 算法進(jìn)行了改進(jìn)研究，文獻(xiàn)[2]中基于克隆增殖思想對 IGA 算法進(jìn)行了改進(jìn)，并結(jié)合CVRP問題的典型算例對新算法進(jìn)行了實(shí)例驗(yàn)證，取得較好結(jié)果；文獻(xiàn)[3]將分布式遺傳算法（Distributed Genetic Algorithm， DGA）的思想引入到 IGA 算法中，提出多種群策略和遷移算子策略，從而有效提高了算法的搜索范圍。但在諸多先進(jìn)的人工智能算法發(fā)展融合的背景下，仍然出現(xiàn)如最優(yōu)解質(zhì)量不高、種群多樣性較低等不足之處。本文基于多種群克隆思想，并引入歐式距離對算法進(jìn)行改進(jìn)，以解決算法存在的缺陷。

2免疫算法（IA）

IA算法借鑒生物免疫系統(tǒng)基本機(jī)制，模擬生物免疫系統(tǒng)自適應(yīng)調(diào)節(jié)過程，實(shí)現(xiàn)了包括抗原識別、細(xì)胞分化和免疫記憶等功能?；诜植甲赃m應(yīng)和動態(tài)平衡的免疫系統(tǒng)，IA算法在處理各種問題上具有顯著的識別“自己”、“非己”和根據(jù)環(huán)境進(jìn)行自動調(diào)節(jié)的優(yōu)勢。

IA算法在優(yōu)化領(lǐng)域應(yīng)用廣泛，但也存在下列缺點(diǎn)[4]：

1）抗體評價較單一；

2）對高親和度抗體和低親和度抗體不能很好利用；

3）記憶庫往往只在產(chǎn)生初始群體時被使用，沒有真正起到加速收斂的效果。

3免疫遺傳算法（IGA）

IGA算法沿用類似遺傳算法的搜索策略，通過構(gòu)造免疫算子，利用疫苗接種和免疫選擇兩個步驟完成種群的進(jìn)化。IGA算法中引進(jìn)了免疫記憶庫和濃度控制機(jī)制，克服了GA算法容易陷入局部收斂等缺點(diǎn)。

4 基于歐式距離的多種群克隆免疫遺傳算法

IGA算法在解決復(fù)雜優(yōu)化問題上與傳統(tǒng)的GA算法相比已具明顯優(yōu)勢，但由于交叉和變異操作的參數(shù)不容易確定，導(dǎo)致算法出現(xiàn)早熟收斂現(xiàn)象。同時，算法在迭代尋優(yōu)過程中，雖然通過疫苗接種和免疫選擇兩個操作進(jìn)行有選擇、有目的地尋找最優(yōu)解，但是單純地接種疫苗有可能使種群朝著一個方向進(jìn)化，降低了種群的多樣性[5]。針對IGA算法的這些不足，本文提出基于歐式距離的多種群克隆免疫遺傳算法（Multiple Population Clone Immune Genetic Algorithm，MPCIGA）。

4.1 歐氏距離原理

為了提高搜索的速率，采用歐氏距離代替信息熵，來反映抗體的多樣性和計算抗體與抗體的親和度。其具體做法如下：在特定的抗體群中共有[N]個抗體，給定抗體[u]，其任一抗體[j]的歐氏距離記為[d（u，j），j=1，2…N]對應(yīng)于所求問題給定一常數(shù) a1>0若：d（u，j）< a1則稱抗體[u]和抗體[j]相似； 與抗體[u]相似的抗體（包括抗體[u]）的個數(shù)稱為抗體[u]的濃度，記為Lu。

4.2 多種群原理

基本的IGA算法是一種單種群進(jìn)化算法，它只重視種群內(nèi)部個體的資源競爭，忽視了種群層次的遺傳操作。為解決這個問題，我們可以將遺傳的競爭過程分為子群體間的競爭和子群體內(nèi)個體間的競爭兩個部分，前者代表算法的全局搜索能力，后者則代表局部搜索能力，這樣可以有效地克服模式欺騙問題[6]?；谏鲜鏊枷?，本文提出了基于歐式距離的多種群克隆免疫遺傳算法。

為了消除IGA算法中種群的單一性，防止算法陷入局部最優(yōu)，我們根據(jù)各個種群的種群多樣性而動態(tài)地產(chǎn)生一個雜交參數(shù)k，通過衡量各個種群的平均成熟程度，進(jìn)而自適應(yīng)地選擇每一個種群中的k個個體和最優(yōu)個體，并互相交換，以打破種群的平衡。

圖7為隨機(jī)選取的四組初始值的尋優(yōu)曲線?？贵w的生成和種群的分組均由計算機(jī)隨機(jī)分配的，仿真表明，初始值的優(yōu)劣會直接影響收斂進(jìn)程和尋優(yōu)曲線的浮動性。較好的初始值，尋優(yōu)的曲線較穩(wěn)穩(wěn)定，較差的初始值則相反。因?yàn)槌跏贾递^好，很快地就進(jìn)入準(zhǔn)確的搜索方向，而初始值較差，計算機(jī)智能擴(kuò)大搜索范圍，不斷地跳出局部最優(yōu)的禁錮，因此尋優(yōu)曲線會較不穩(wěn)。

6 結(jié)語

本文提出的MPCIGA算法是針對IGA算法所存在的缺陷而進(jìn)行的改進(jìn)，通過多種群進(jìn)化和克隆變異，增強(qiáng)了種群多樣性，提高了最優(yōu)解質(zhì)量，消除了在解決復(fù)雜問題時IGA算法計算量呈爆炸式增長的現(xiàn)象。克隆變異使得尋解過程中的搜索范圍擴(kuò)大，把局部搜索和全局搜索有機(jī)結(jié)合起來；引入多種群的思想使得各種群能夠協(xié)作搜索發(fā)展，防止早熟和加快進(jìn)化速度。仿真結(jié)果也證明了本文所做的算法改進(jìn)的正確性。

參考文獻(xiàn)：

[1] L.C.Jiao，L.Wang.A Novel Genetic Algorithm Basedon Immunity[J].IEEE Tran.onSystem，Man，and Cybemetics.2000，30（5）：552-561.

[2] 崔紅建，改進(jìn)免疫遺傳算法在組合優(yōu)化問題中的應(yīng)用研究[D].大連海事大學(xué).2012：30-41.

[3] 苑立杰，免疫遺傳算法在車輛路徑問題中的應(yīng)用研究[D].大連海事大學(xué).2013：44-51.

[4] 蘇彩紅，朱學(xué)鋒，毛宗源.一類免疫優(yōu)化算法及其應(yīng)用[J].西南交通大學(xué)學(xué)報，2002，37（6）：677-680.

[5] 馬佳，改進(jìn)免疫遺傳算法及其在優(yōu)化調(diào)度問題中的應(yīng)用研究[M].東北大學(xué).2007：27-70.

[6] 司書賓，孫樹棟，徐婭萍.求解Job-shop調(diào)度問題的多種群雙倍體免疫算法研究[J]，西北工業(yè)大學(xué)學(xué)報，2007，25（1）：27-30.

[7] 焦李成，杜海峰，劉芳，等.免疫優(yōu)化計算！學(xué)習(xí)與識別[M].北京：科學(xué)出版社，2006：60-82.

[8] 王凌.智能優(yōu)化算法及其應(yīng)用[M].北京：清華大學(xué)出版社，2001：1-24.