基于捕食搜索策略的遺傳算法研究

摘要：針對標準遺傳算法易陷入局部最優而出現早熟，提出了一種基于捕食搜索策略的遺傳算法。該算法在進化中模擬動物捕食搜索的過程，并根據種群中個體最優適應值來動態改變交叉和變異概率，從而加強算法的全局搜索和局部優化的能力。仿真實驗表明該算法是有效的。

關鍵詞：捕食搜索策略； 遺傳算法； 交叉概率； 變異概率

中圖分類號：TP301文獻標志碼：A

文章編號：1001－3695(2008)04－1006－02

遺傳算法（genetic algorithm， GA）是由Holland教授于1975年首次提出的一種模擬生物進化論的計算模型，是一種有效的全局并行優化計算技術。GA采用群體搜索技術，通過對當前群體采用選擇、交叉和變異等一系列遺傳操作，從而產生新一代的群體，并逐步使群體進化到包含或接近最優解的狀態。由于GA具有簡單、通用、魯棒性強和適應于并行分布處理等特點，已經成功應用到很多領域。雖然GA具有很多優點，但是GA也容易出現個體早熟現象，使算法不能跳出局部極值，這也是GA的最大不足。產生早熟的主要原因在于種群模式多樣性的喪失[1，2]。為了克服這一缺點，改進方法主要在兩個方面，即改進遺傳操作、調整參數[1~6]和采用多種群遺傳算法[7]。

1基于捕食搜索策略的遺傳算法（PSGA）

1．1PSGA算法描述

遺傳算法的收斂主要取決于交叉算子和變異算子。交叉算子提供了全局搜索能力，而變異算子則提供了局部搜索能力。進化初期，應確保種群在大范圍內搜索，進行全局進化以避免過早收斂；進化后期，種群成熟度較高，個體更加逼近最優解，種群應該在局部范圍內搜索，重點進化，盡可能提高精度。因此，交叉概率和變異概率很難選擇，通常根據理論分析中參數的大致范圍來選擇或根據經驗來確定，具有很大的盲目性。一旦選擇不當，容易陷入局部最優，出現早熟現象。本文對此引入了捕食搜索策略。

捕食搜索是一種用于解決組合優化問題的空間搜索策略[8]，它是在模擬動物捕食行為的基礎上提出的。動物在捕食時，在沒有發現獵物或獵物跡象時在整個捕食空間沿著一定的方向以很快的速度尋找獵物；一旦發現獵物或發現獵物跡象，它們就放慢步伐，在發現獵物或有獵物跡象的區域進行集中搜索，以期望找到獵物。在尋找一段時間而沒有找到獵物后，捕食動物將放棄這種集中的區域，而繼續在整個捕食空間尋找獵物。捕食搜索策略是一種平衡全局探索能力和局部開發能力的方法。將其應用到遺傳算法中，首先以較大的交叉概率Pc1和較小的變異概率Pm1進行全局搜索；一旦發現一個較好的解，則改變為以較大的變異概率Pm2和較小的交叉概率Pc2進行局部搜索；如果在搜索過程中最優解得不到改善，則再以較大的交叉概率Pc1和較小的變異概率Pm1進行全局探索。

1．2編碼策略

遺傳算法的編碼方式很多，本研究中采用實數編碼。實數編碼克服了二進制編碼解碼的換算占用計算機時間問題以及表達精度的要求與計算量之間的矛盾。采用實數編碼時，個體的表達形式為

2．2結果分析

從表1可以看出，本文提出的PSGA相對于SGA、MCGA和MGA在成功率上有了較大的提高，但是在進化代數上有所增加。其主要原因是PSGA在發現較好解之后要進行局部搜索，由此降低了交叉概率，從而使種群中產生較好新個體的可能性變小。特別是在進化早期，對算法的影響更大。

從PSGA的三種算法的計算結果來看，在進化代數較少的情況下，PSGA3算法的成功率較高，平均最優值更接近全局最優值；而在進化代數較大的情況下，PSGA2算法的成功率較高，平均最優值更接近全局最優值，但算法收斂的平均進化代數也最大。其主要原因是，當k值取值較小時，進入局部搜索的次數就較多，因此算法收斂的平均進化代數也越大；當k值取值較大時，算法進入局部搜索的次數較少，而進行全局搜索越多，因此算法收斂的平均進化代數較小，但算法的成功率也較小。由此可以看出，k值的選擇要根據具體情況來確定。

3結束語

本文提出了一種基于捕食搜索策略的遺傳算法。該算法根據當代最優適應度和歷代最優適應度的比值來更新交叉概率和變異概率，從而加強算法的全局搜索和局部優化的能力。從測試函數仿真實驗的結果來看，該算法是可行的。

參考文獻：

[1]付旭輝，康玲. 遺傳算法的早熟問題探究[J]. 華中科技大學學報:自然科學版，2003，31(7):53－54.

[2]汪民樂，高曉光，劉剛. 遺傳算法早熟問題的定量分析及其預防策略[J].系統工程與電子技術，2006，28(8):1249－1251，1288.

［3］蔡良偉，李霞. 遺傳算法交叉操作的改進[J]. 系統工程與電子技術，2006，28(6):925－928.

［4］陳小平，于盛林. 實數遺傳算法交叉策略的改進[J]. 電子學報，2003，31(1):71－74.

［5］許義海，李曉東. 一種快速尋優的新型改進遺傳算法[J].中山大學學報:自然科學版，2006，45(2):36－40.

［6］王斌，李元香.一種防止遺傳算法過早收斂的“兩階段交替”算法[J].小型微型計算機系統，2003，24(3):537－539.

［7］鄒琳，夏巨，胡國安.基于實數編碼的多種群并行遺傳算法研究[J].小型微型計算機系統，2004，25(6):982－986.

［8］LINHARES A. Preying on optima: a predatory search strategy for combinatorial problems[C]//Proc of IEEE International Conference of Systems， Man and Cybernetics. Piscataway NJ:[s.n.]， 1998:2974－2978.

［9］宗敬群. 一類混合自適應遺傳算法及性能分析[J].系統工程理論與實踐，2001，21(4):14－18.

［10］潘偉，刁華宗，井元偉. 一種改進的實數自適應遺傳算法[J].控制與決策，2006，21(7):792－795，800.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”