基于多種群遺傳?模式搜索算法的函數優化與仿真

摘 要： 為改善遺傳算法局部尋優能力較差和易早熟的固有缺陷，提出一種多種群遺傳?模式搜索算法。算法利用遺傳算法的強全局搜索能力，模式搜索算法的局部尋優精度高的優勢及多種群的多樣性，加入人工選擇算子保留各種群最優值，以提高遺傳算法的收斂性，并且對各種群采用不同控制參數兼顧算法的全局搜索和局部搜索。通過對復雜函數進行仿真測試，結果表明多種群遺傳?模式搜索算法比單獨使用標準遺傳算法和多種群遺傳算法精度高，而且可跳出局部最優，快速收斂，是一種有效可行的優化算法。

關鍵詞： 多種群遺傳算法； 模式搜索算法； 復雜函數優化； 仿真運算

中圖分類號： TN911?34； TP301.6 文獻標識碼： A 文章編號： 1004?373X（2013）10?0001?03

遺傳算法（Genetic Algorithm，GA）[1]是基于生物進化機制的隨機搜索算法，其本質是一種高效、并行、全局搜索的方法，它能在搜索過程中自動獲取和積累有關搜索空間的知識，并自適應地控制搜索過程以求得最優解，且它不依賴于問題的具體領域、具有強魯棒性。然而，盡管遺傳算法有很多優點，但目前存在的問題依然很多，其具體表現為：遺傳算法的早熟現象，即很快收斂到局部最優解而不是全局最優解[2]；快要接近最優解時在最優解附近左右擺動，收斂較慢[3]；接近最優解的個體總是被淘汰，進化過程不收斂。對此，本文將多種群遺傳算法和模式搜索法相結合。采用多個種群并行進化，拓寬搜索空間，增加群體多樣性；各種群取不同的控制參數（交叉，變異概率），這樣就彌補了簡單遺傳算法的不足[4]；采用最優個體保留策略，從而保證最終可以搜索到全局最優解；引進模式搜索算法，利用其快速局部搜索能力，使算法在最優解附近迅速收斂[5]；通過對復雜函數的仿真運算，結果說明這種搜索方法是可行的。

1 基本算法簡介

1.1 遺傳算法

遺傳算法的思想是：首先將代表問題的解用染色體編碼，形成種群，再通過適應度函數計算每個個體的適應性，按照適者生存、優勝劣汰的原理，在每一代選擇性能優異的個體，對其使用交叉、變異算子，產生新種群。交叉操作交換兩個染色體的一部分，變異操作改變染色體上某個隨機位置的基因值。經過多次重復迭代，適應性較弱的個體被淘汰，適應性強的則統治種群，最終生成符合優化目標的染色體，獲得問題的近似最優解。

多種群可拓寬搜索空間，增加群體多樣性。多樣性是遺傳算法必不可少的本質屬性，這是因為它能使遺傳算法搜索一個比較大的解的空間區域。采用最優個體保留策略，每一次的演化過程中，子代總是保留了父代種最好的個體，以在“高適應度模式為祖先的家族方向”搜索出更好的樣本，從而保證最終可以搜索到全局最優解。

1.2 模式搜索法

2 多種群遺傳?模式搜索算法

2.1 算法框架

各種群采用不同的控制參數[7]，大多數學者建議選擇較大的[pc]（0.7～0.9）和較小的[pm]（0.01～0.05）。但是[pc]和[pm]的取值方式還是有無數種，對于不同的選擇，優化結果差異很大。MGA彌補了簡單遺傳算法的這一不足，通過多個設有不同控制參數的種群協同進化，同時兼顧了算法的全局搜索和局部搜索。各種群之間通過移民算子進行聯系，實現多種群的協同進化；最優解的獲取是多個種群協同進化的綜合結果。加入人工選擇算子保存各種群每個進化代中的最優個體，并作為判斷算法收斂的依據。精華種群和其他種群有很大不同。精華種群不進行選擇、交叉、變異等遺傳操作，保證進化過程中各種群產生的最優個體不被破壞和丟失。同時，精華種群也是判斷算法終止的依據，這里采用最優個體最少保持代數作為終止判據。這種判據充分利用了遺傳算法在進化過程中的知識積累，較最大遺傳代數判據更為合理。

3 仿真測試

該非線性函數在給定范圍內分布著許多局部極值，通常的尋優算法極易陷入局部極值或在各局部極值間振蕩，比較適用于驗證多種群遺傳?模式搜索算法的性能。標準遺傳算法運行3次得到的結果如表1所示，其進化過程如圖3所示。

4 結 語

本文提出的優化算法MGPS融合了MGA強大的全局搜索能力PS搜索算法的局部尋優精度高優勢。算法首先使用MGA實現粗搜索，可迅速逼近全局最優解的臨近區域；然后利用PS 實現細搜索，可準確定位全局最優解。實驗表明MGPS算法優于單獨執行的SGA和MGA算法。MGPS提高了算法的成功率，并減少了陷入局部最優的可能，且收斂速度較快，是一種有效的優化算法。在后期的工作中將MGPS 算法運用于其他領域，如無人機航跡規劃[8]，圖像處理[9]，目標識別等[10]。

參考文獻

[1] ELANSARY A M， ELDAMATTY A A， NASSEF A O. A coupled finite element genetic algorithm technique for optimum design of steel conical tanks [J]. Thin?Walled Structures， 2010， 48（3）： 260?273.

[2] VIDOSSICH G. An addition and a correction to my paper “Diffe?

rential inequalities for evolution equations” [J]. Nonlinear Analysis： Theory， MethodsApplications， 2010， 72（2）： 618?623.

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

[4] 周文彬，蔡永銘，陳華艷.實值多種群遺傳算法求解動態規劃問題[J].控制工程，2007（z1）：103?104.

[5] NICOSIA G， STRACQUADANIO G. Generalized pattern search algorithm for peptide structure prediction [J]. Biophysical Journal， 2008， 95（10）： 4988?4999.

[6] WETTER M， POLAK E. Building design optimization using a convergent pattern search algorithm with adaptive precision simulations [J]. Energy and Buildings， 2005， 37（6）： 603?612.

[7] 聶沖，王維平，趙雯.基于學習算子的自學習遺傳算法設[J].計算機仿真，2006（9）：168?171.

[8] 鄭銳，馮振明，陸明泉.基于遺傳算法的無人機航路規劃優化研究[J].計算機仿真，2011（6）88?91.

[9] 田瑩，苑瑋琦.遺傳算法在圖像處理中的應用[J].中國圖象圖形學報，2007（3）：389?397.

[10] 楊淑瑩，何丕廉.基于遺傳算法的多目標識別實時系統設計[J].模式識別與人工智能，2006（3）：325?330.