基本遺傳算法遺傳策略優化與Java實現

吳力榮

(浙江工業職業技術學院 人文社科部，浙江 紹興 312000)

1 引言

遺傳算法(Genetic Algorithm，GA)是Darwin生物進化理論的哲學思想啟發的搜索技術．GA的基本概念和理論框架，是由Holland首先提出的[1]，并由Goldberg作了廣泛的探索[2]．GA最具有吸引力的特點是它不需要指導搜索的附加知識．一般而言，GA通過生物進化啟發的復制、交叉和變異算子搜索字符串的各種結構．模式定理證明了GA具有全局搜索的能力．但經研究表明，若算法結構、操作和參數設計不合理，則遺傳算法容易產生早熟收斂．因此，GA研究的重點在于如何避免早熟收斂及均衡GA的全局搜索和局部趨化能力[3-4]．迄今已提出許多改進策略，譬如參數自適應、混合或并行GA算法[5]．GA早熟收斂的原因本質上可歸結為遺失種群多樣性.因此，本文一方面引入最優策略，使雜交后適應度高的個體能進入下一代，同時增加篩選策略以維持種群多樣性，即基于種群性能差別和種群地域差別刪去一些性能相對差的冗余個體，同時隨機產生新個體的方法保持種群的多樣性．基于典型函數的仿真表明，本遺傳算法的全局收斂速度和命中全局最優解的概率均好于傳統方法．

2 基本遺傳算法

2.1 問題描述

一般需要進行優化計算的實際問題可以表示如下：

2.2 基本遺傳算法過程

Step1:確定決策變量和約束條件，建立優化模型(如2．1)．決策變量Xj=(x1，x2，…，xn)(即染色體，也稱為個體)，組成問題的解空間(即染色體搜索空間)．

Setp2:確定編碼方法．由于基本遺傳算法采用二進制編碼，染色體長度根據問題的精度確定，并設計好相應的解碼方法．

Setp3:確定個體評價方法．

Setp4:初始化種群．在約束條件下，利用隨機生成函數initialize隨機生成popsize個個體Xj(j=1，2，…，popsize)作為初始種群P(t)，t=0．

Step5:遺傳操作．設計遺傳算子，對群體P(t)執行遺傳操作，產生新種群P(t+1)，即下一代群體．遺傳操作是遺傳算法的精髓所在，主要包括選擇、交叉和變異等基本遺傳運算．本文將主要對此進行優化．

Setp6:是否滿足終止條件．t=t+1，若條件滿足輸出最優解，結束．否則轉向Step5．

3 基本遺傳算法遺傳策略優化

3.1 交叉保優算法

3.2 篩選策略

在交叉算法中結合保優算法，雖然會提高遺傳算法的收斂性和收斂速度，但是降低了種群的多樣性，容易使遺傳算法收斂到局部最優解．因此需對遺傳算法結束后的種群個體進行篩選，將一些冗余個體淘汰，同時隨機增加新個體來提高種群的多樣性．

為衡量種群的多樣性，給出如下定義:

定義1定義種群性能分散度為D(f(X1)，…，f(Xn))，即種群P={X1，X2，…，Xn}中各個體性能的方差．

定義2定義種群地域分散度為E(‖X1-G‖，…，‖Xn-G‖).其中,G=E(X1，…，Xn)為種群的重心，‖‖定義歐氏距離．

對種群P篩選步驟如下：

(1)對種群P進行性能篩選．設置閥值為ε，按個體性能的好壞順序刪掉不滿足|f(Xi)-f(Xj)|≥ε的個體．剩余個體構成的種群為

P'={X|X∈P，?i≠j，|f(Xi)-f(Xj)|≥ε}

(2)對P'進行基于地域差別的篩選．記‖Xi-Xj‖=max{|xi，k-xj，k|}，設置閥值ω，按個體地域好壞依次刪除不滿足‖Xi-Xj‖≥ω的個體，得到種群

P"={X|X∈P'，?i≠j，‖Xi-Xj‖≥ω}

(3)若size ofP"

4 算法的Java實現與數值仿真

4.1 Java實現代碼

基于二維Rosenbrock函數

Java實現代碼見(http://my．oschina．net/thinkinginc/blog/11472)．

4.2 數值仿真

4.1中的二維Rosenbrock函數，有兩個局部極大值，分別是

f(2.048，-2.048)=3897.7342和f(-2.048，-2.048)=3905.9262，其中后者為全局最大值．我們用基本遺傳算法和本文優化后的遺傳算法分別進行100次運算，得到如下數據：

表1 100次Rosenbrock函數的GA仿真結果

基本遺傳算法進化過程與優化后的遺傳算法進化過程分別如圖1、圖2所示：

圖1 基本遺傳算法進化過程

圖2 優化后的遺傳算法進化過程

從圖中可以看出，優化后的遺傳算法，在進化的初始階段，種群適應度平均值較低，個體具有較好的多樣性．在進化的中期，能迅速找到最優值，并收斂于最優值，與基本遺傳算法相比較，優化后的遺傳算法全局收斂速度和命中全局最優的概率大大提高．

5 結論

典型的遺傳操作在解決問題時存在較大的缺陷，如算法不穩定、易陷入局部極值等．仿真結果表明，本文提出的遺傳策略優化后的GA算法，它具有高效率的全局尋優以及良好的穩定性的優點．

參考文獻：

[1]Holland J H．Adaptation in Natural and Artificial Systems[M]．USA:Univ．of Michigan，1975．

[2]Goldberg D E．Genetic Algorithms In Search，Optimization，and Machine Learning[M]．Addison-Wesley professional，1989．

[3]王凌．智能優化算法及其應用[M]．北京:清華大學出版社，2001．

[4]Gong D，Sun X，Guo X．Novel survival of the fittest genetic algorithm [J]．Control and Decision，2002，17(6):908-911．

[5]Guo G Q，Yu S Y．Evolutionary parallel local search for function optimization[J]．IEEE Trans. on Systems，Man，and Cybernetics，2003，33(6):864-876．