基于多種群遺傳?模式搜索算法的函數(shù)優(yōu)化與仿真

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

關(guān)鍵詞： 多種群遺傳算法； 模式搜索算法； 復(fù)雜函數(shù)優(yōu)化； 仿真運算

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

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

1 基本算法簡介

1.1 遺傳算法

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

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

1.2 模式搜索法

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

2.1 算法框架

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

3 仿真測試

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

4 結(jié) 語

本文提出的優(yōu)化算法MGPS融合了MGA強大的全局搜索能力PS搜索算法的局部尋優(yōu)精度高優(yōu)勢。算法首先使用MGA實現(xiàn)粗搜索，可迅速逼近全局最優(yōu)解的臨近區(qū)域；然后利用PS 實現(xiàn)細搜索，可準(zhǔn)確定位全局最優(yōu)解。實驗表明MGPS算法優(yōu)于單獨執(zhí)行的SGA和MGA算法。MGPS提高了算法的成功率，并減少了陷入局部最優(yōu)的可能，且收斂速度較快，是一種有效的優(yōu)化算法。在后期的工作中將MGPS 算法運用于其他領(lǐng)域，如無人機航跡規(guī)劃[8]，圖像處理[9]，目標(biāo)識別等[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] 王凌.智能優(yōu)化算法及其應(yīng)用[M].北京：清華大學(xué)出版社，2001.

[4] 周文彬，蔡永銘，陳華艷.實值多種群遺傳算法求解動態(tài)規(guī)劃問題[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] 聶沖，王維平，趙雯.基于學(xué)習(xí)算子的自學(xué)習(xí)遺傳算法設(shè)[J].計算機仿真，2006（9）：168?171.

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

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

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