曹辛鑫，全海燕

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

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

　　關鍵詞：遺傳算法；實數編碼；多倍體；隨機基因交叉

0引言

　　遺傳算法（GA）是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型［1］。 其搜索不依賴于梯度信息，不要求被優化對象，具有連續、可導、單峰等特性［23］。它尤其適用于處理傳統搜索方法難于解決的復雜和非線性問題，可廣泛用于組合優化、機器學習、自適應控制、規劃設計和人工生命等領域［47］。

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

1隨機基因實數交叉

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

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

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

2多倍體搜索保存策略

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

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

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

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

　　其中，xmax表示搜索空間內基因的允許的最大值，xmin表示搜索空間內基因的允許的最小值，rand、rand’均表示［0,1］間的隨機數。

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

　　根據以上描述的基本思想，本文對遺傳算法進行了改進，以下是改進遺傳操作的詳細描述。

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

　?。?）設置控制參數，初始化進化種群，設定迭代次數變量t=0,最大迭代次數為T。

　?。?）計算所有個體的適應度值，保存最優種群，剩余的作為配種二倍體。

　?。?）檢測t<T。若滿足，繼續；若不滿足，則輸出最優解，結束。

　?。?）最優種群中最優單體與配種二倍體進行隨機基因交叉，產生新配子。

　?。?）計算新配子適應度值，排序。

　?。?）判斷新配子與父代個體適應度值的優劣，依照多倍體保存策略進行個體替換。

　　（7）判斷新個體數量是否小于種群個體個數。若小于種群個體個數，則轉到步驟（4）,繼續循環；若已經等于種群個體個數，則轉到步驟（2），更換新種群。

4測試結果

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

　　這3個測試函數在點（0,0,0,…,0）處取全局最優解為0。

　　4.1基因交叉概率實驗分析

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

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

　　4.2對比實驗結果

　　將多倍體遺傳算法與經典遺傳算法的搜索結果進行比較。

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

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

5結論

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

參考文獻

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

　　［2］ 周明,孫樹棟. 遺傳算法原理及應用［M］. 北京：國防工業出版社，1999.

　?。?］ 陳國良,王熙法,莊鎮泉，等. 遺傳算法及其應用［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］. 微型機與應用, 2011, 30(3):7981.

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

　　［7］ 屈波. 基于GA優化的入口匝道可調模糊控制器設計［J］. 微型機與應用, 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.

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

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

　　［11］ 王小平,曹立明.遺傳算法——理論、應用與軟件實現［M］.西安: 西安交通大學出版社，2002.