曹辛鑫，全海燕

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

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

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

0引言

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

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

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

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

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

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

2多倍體搜索保存策略

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

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

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

　　設(shè)變異概率為pm,xij(t)為父代第j個染色體中第i個基因，變異操作后得到的子代第j個染色體中第i個基因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ù)以上描述的基本思想，本文對遺傳算法進(jìn)行了改進(jìn)，以下是改進(jìn)遺傳操作的詳細(xì)描述。

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

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

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

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

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

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

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

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

4測試結(jié)果

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

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

　　4.1基因交叉概率實驗分析

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

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

　　4.2對比實驗結(jié)果

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

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

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

5結(jié)論

　　通過對經(jīng)典遺傳算法的研究，得知算法中的交叉操作具有重要作用，決定了算法的最終收斂結(jié)果，并且影響著算法的收斂速度。與此同時，種群的多樣性以及新個體獲取信息的多樣性又與交叉操作的效率有著密切關(guān)系。根據(jù)以上分析，提出了一種改進(jìn)的遺傳算法。引入多倍體概念，利用不同的種群保存不同功能的染色單體，從而增加種群的多樣性。并且在多倍體的基礎(chǔ)上提出了隨機(jī)基因?qū)崝?shù)交叉以及多倍體搜索保存策略。通過3個測試函數(shù)對該算法進(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.

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

　?。?］ 屈波. 基于GA優(yōu)化的入口匝道可調(diào)模糊控制器設(shè)計［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.

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

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