曹辛鑫，全海燕

　　(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650500)

　　摘要：針對(duì)經(jīng)典遺傳算法的早熟及精度問題進(jìn)行了研究，提出了一種基于隨機(jī)基因?qū)崝?shù)交叉與多倍體策略的遺傳算法。借鑒生物界中多倍體的概念，采用了實(shí)數(shù)編碼并利用多倍體分別保存最優(yōu)單體、保留單體及變異單體，從而組成多樣性種群；選擇操作采用了輪盤賭算法；交叉操作引入隨機(jī)基因交叉概念。最后應(yīng)用測試函數(shù)對(duì)算法進(jìn)行測試，并與經(jīng)典遺傳算法進(jìn)行了比較。仿真實(shí)驗(yàn)結(jié)果表明，該改進(jìn)算法不僅保持了種群的多樣性，有效抑制了早熟收斂，還降低了算法的復(fù)雜度，提高了搜索精度，使得算法能以較高的精度達(dá)到復(fù)雜高維度函數(shù)的全局最優(yōu)。

　　關(guān)鍵詞：遺傳算法；實(shí)數(shù)編碼；多倍體；隨機(jī)基因交叉

0引言

　　遺傳算法（GA）是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型［1］。 其搜索不依賴于梯度信息，不要求被優(yōu)化對(duì)象，具有連續(xù)、可導(dǎo)、單峰等特性［23］。它尤其適用于處理傳統(tǒng)搜索方法難于解決的復(fù)雜和非線性問題，可廣泛用于組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、規(guī)劃設(shè)計(jì)和人工生命等領(lǐng)域［47］。

　　然而，基本遺傳算法會(huì)遇到早熟收斂現(xiàn)象［810］。為防止過早陷于局部最優(yōu)，本文提出了多倍體概念，增加了種群中個(gè)體的多樣性。其次，本文搜索過程是通過隨機(jī)的基因交叉完成并通過多倍體策略保留的。

1隨機(jī)基因?qū)崝?shù)交叉

　　本算法中尋優(yōu)搜索過程是通過隨機(jī)基因交叉完成的。在本文中設(shè)種群大小為m，個(gè)體上每個(gè)維度的變量用基因表示，每個(gè)染色體包含的基因數(shù)量為n。基因隨機(jī)選取概率為p。根據(jù)p×n確定選取基因個(gè)數(shù)k，從每個(gè)染色體上隨機(jī)選出k個(gè)（Ckn）做算術(shù)交叉。若設(shè)隨機(jī)從父代染色體中選取出的一組基因?yàn)閤ir(t)，xis(t)；交叉操作后對(duì)應(yīng)的基因xir(t+1)，xis(t+1)（1≤i≤n）由式（1）得出：

　　其中，λ是［0,1］間的隨機(jī)數(shù)，并且每次交叉操作中的λ不同。

　　采用此種交叉操作可以有效提高局部勘探能力，并改善算法的搜索效率。

2多倍體搜索保存策略

　　本文引入生物學(xué)中的多倍體概念，即在個(gè)體中含有3個(gè)或3個(gè)以上的染色體組；提出的多倍體是由攜帶不同功能基因的染色體構(gòu)成的，包括最優(yōu)種群、保留種群和變異種群。每次搜索后多倍體保存的策略為：交叉后對(duì)得到的配子進(jìn)行適應(yīng)度值的計(jì)算，再根據(jù)以下步驟進(jìn)行配子的保存：

　?。?）如果配子的適應(yīng)度值優(yōu)于最優(yōu)單體，則用配子替換最優(yōu)單體。而此時(shí)配種二倍體中保留的單體和變異單體保持不變，以保留父代信息，使優(yōu)秀的信息不被破壞。

　?。?）如果配子的適應(yīng)度值劣于最優(yōu)單體，則最優(yōu)單體保持不變，確保搜索方向不變。隨機(jī)選取一個(gè)子代配子替換保留單體，而另一子代配子進(jìn)行變異操作后替換變異單體，以增加種群的多樣性。變異操作如下：

　　設(shè)變異概率為pm,xij(t)為父代第j個(gè)染色體中第i個(gè)基因，變異操作后得到的子代第j個(gè)染色體中第i個(gè)基因xij(t+1)，1≤i≤n,1≤j≤m，由式（2）得出：

　　其中，xmax表示搜索空間內(nèi)基因的允許的最大值，xmin表示搜索空間內(nèi)基因的允許的最小值，rand、rand’均表示［0,1］間的隨機(jī)數(shù)。

3基于隨機(jī)基因交叉與多倍體策略的遺傳算法

　　根據(jù)以上描述的基本思想，本文對(duì)遺傳算法進(jìn)行了改進(jìn)，以下是改進(jìn)遺傳操作的詳細(xì)描述。

　　本文采用實(shí)數(shù)編碼［10］，便于大空間搜索，可以減少算法的復(fù)雜度。并采用輪盤賭選擇［11］，但同時(shí)，為了防止適應(yīng)度值高的個(gè)體被淘汰，本文最優(yōu)種群不參與選擇操作，直接進(jìn)入子代種群。在保留種群與變異種群組成的配種二倍體中進(jìn)行輪盤賭選擇操作，在選中的二倍體中隨機(jī)選出一個(gè)染色單體，使之與最優(yōu)種群個(gè)數(shù)相匹配并進(jìn)入子代種群，從而與最優(yōu)種群進(jìn)行隨機(jī)基因交叉操作。交叉概率通過實(shí)驗(yàn)確定，并將在4.1節(jié)中討論不同概率的實(shí)驗(yàn)結(jié)果。產(chǎn)生的子代按照多倍體搜索策略進(jìn)行取舍。具體步驟如下：

　?。?）設(shè)置控制參數(shù)，初始化進(jìn)化種群，設(shè)定迭代次數(shù)變量t=0,最大迭代次數(shù)為T。

　?。?）計(jì)算所有個(gè)體的適應(yīng)度值，保存最優(yōu)種群，剩余的作為配種二倍體。

　?。?）檢測t<T。若滿足，繼續(xù)；若不滿足，則輸出最優(yōu)解，結(jié)束。

　　（4）最優(yōu)種群中最優(yōu)單體與配種二倍體進(jìn)行隨機(jī)基因交叉，產(chǎn)生新配子。

　?。?）計(jì)算新配子適應(yīng)度值，排序。

　?。?）判斷新配子與父代個(gè)體適應(yīng)度值的優(yōu)劣，依照多倍體保存策略進(jìn)行個(gè)體替換。

　?。?）判斷新個(gè)體數(shù)量是否小于種群個(gè)體個(gè)數(shù)。若小于種群個(gè)體個(gè)數(shù)，則轉(zhuǎn)到步驟（4）,繼續(xù)循環(huán)；若已經(jīng)等于種群個(gè)體個(gè)數(shù)，則轉(zhuǎn)到步驟（2），更換新種群。

4測試結(jié)果

　　本文選用了3個(gè)測試函數(shù)用MATLAB對(duì)多倍體遺傳算法進(jìn)行測試實(shí)驗(yàn)，實(shí)驗(yàn)中，設(shè)定參數(shù)為：實(shí)數(shù)編碼，根據(jù)不同函數(shù)，染色體長度分別為f1=10、f2=2、f3=2。進(jìn)化代數(shù)為1 000，種群個(gè)數(shù)為70，對(duì)每個(gè)測試函數(shù)，獨(dú)立運(yùn)行50次。

　　這3個(gè)測試函數(shù)在點(diǎn)（0,0,0,…,0）處取全局最優(yōu)解為0。

　　4.1基因交叉概率實(shí)驗(yàn)分析

　　首先對(duì)算法本身的參數(shù)進(jìn)行實(shí)驗(yàn)討論。實(shí)驗(yàn)中選取的基因交叉概率分別為0.2、0.3以及0.4，而此時(shí)種群個(gè)數(shù)為70保持不變，進(jìn)化代數(shù)為1 000。獨(dú)立運(yùn)行50次后，平均最優(yōu)解的進(jìn)化結(jié)果如圖1~圖3所示。

　　由圖1~圖3組可知，當(dāng)維度低時(shí)，基因交叉概率越小，算法搜尋最優(yōu)解速度稍快，但效果不是非常明顯；當(dāng)染色體維度較高時(shí)，基因交叉概率越小，算法搜尋最優(yōu)解的速度明顯越快，搜尋精度也有提高。

　　4.2對(duì)比實(shí)驗(yàn)結(jié)果

　　將多倍體遺傳算法與經(jīng)典遺傳算法的搜索結(jié)果進(jìn)行比較。

　　表1列出了兩種不同方法的實(shí)驗(yàn)結(jié)果，其中SRGA為基本實(shí)數(shù)編碼的遺傳算法，RGPGA為本文提出的隨機(jī)基因交叉和多倍體策略的遺傳算法。表1中Optima表示尋到的最優(yōu)解，AVG表示進(jìn)行50次實(shí)驗(yàn)得到最優(yōu)解的平均值，σ表示進(jìn)行50次實(shí)驗(yàn)得到最優(yōu)解的方差。

　　從表1中3個(gè)函數(shù)的實(shí)驗(yàn)結(jié)果可知，本文算法在搜索精度上有明顯改進(jìn)。無論函數(shù)維數(shù)的高低，本文算法都可以或近似搜尋到最優(yōu)解，并且搜索結(jié)果相對(duì)穩(wěn)定，未有大的波動(dòng)。

5結(jié)論

　　通過對(duì)經(jīng)典遺傳算法的研究，得知算法中的交叉操作具有重要作用，決定了算法的最終收斂結(jié)果，并且影響著算法的收斂速度。與此同時(shí)，種群的多樣性以及新個(gè)體獲取信息的多樣性又與交叉操作的效率有著密切關(guān)系。根據(jù)以上分析，提出了一種改進(jìn)的遺傳算法。引入多倍體概念，利用不同的種群保存不同功能的染色單體，從而增加種群的多樣性。并且在多倍體的基礎(chǔ)上提出了隨機(jī)基因?qū)崝?shù)交叉以及多倍體搜索保存策略。通過3個(gè)測試函數(shù)對(duì)該算法進(jìn)行了測試。仿真測試表明，該改進(jìn)遺傳算法有效抑制了早期收斂，提高了搜索的效率；從與標(biāo)準(zhǔn)遺傳算法的比較也可以看出，該改進(jìn)算法可以更加有效地求解高維度復(fù)雜函數(shù)的優(yōu)化問題。

參考文獻(xiàn)

　?。?］ HOLLAND J H. Adaptation in nature and artificial systems［M］. Cambridge MIT Press,1975.

　?。?］ 周明,孫樹棟. 遺傳算法原理及應(yīng)用［M］. 北京：國防工業(yè)出版社，1999.

　?。?］ 陳國良,王熙法,莊鎮(zhèn)泉，等. 遺傳算法及其應(yīng)用［M］. 北京：人民郵電出版社，1996.

　?。?］ NEBRO A J, DURILLO J J, LUNA F, et al. A cellular genetic algrithm for multiobject optimization［J］. International Journal of Intelligent Systems,2009,24:726746.

　?。?］ 吳永明, 吳晟. 改進(jìn)的遺傳算法在神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化中的應(yīng)用［J］. 微型機(jī)與應(yīng)用, 2011, 30(3):7981.

　?。?］ 杜雯超, 陳其松, 周瑩. 基于分段自適應(yīng)遺傳算法的圖像閾值分割［J］. 微型機(jī)與應(yīng)用, 2015, 34(3):5859.

　?。?］ 屈波. 基于GA優(yōu)化的入口匝道可調(diào)模糊控制器設(shè)計(jì)［J］. 微型機(jī)與應(yīng)用, 2014,33(8):9092.

　　［8］ PHOLDEE N, BUREERAT, S. Hybrid realcode populationbased incremental learning and approximate gradients for multiobjective truss design［J］. Engineering Optimization, 2014, 46(8):10321051.

　?。?］ 申曉寧，郭毓，陳慶偉，等. 一種保持群體多樣性的多目標(biāo)遺傳算法［J］. 控制與決策，2008,23（12）：14351440.

　?。?0］ 齊暢，王東霞，韓穎. 多種遺傳算法在函數(shù)優(yōu)化方面的性能比較分析［J］.遼寧工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2013,33（5）：290293.

　?。?1］ 王小平,曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安: 西安交通大學(xué)出版社，2002.