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

摘要：針對(duì)標(biāo)準(zhǔn)遺傳算法易陷入局部最優(yōu)而出現(xiàn)早熟，提出了一種基于捕食搜索策略的遺傳算法。該算法在進(jìn)化中模擬動(dòng)物捕食搜索的過(guò)程，并根據(jù)種群中個(gè)體最優(yōu)適應(yīng)值來(lái)動(dòng)態(tài)改變交叉和變異概率，從而加強(qiáng)算法的全局搜索和局部?jī)?yōu)化的能力。仿真實(shí)驗(yàn)表明該算法是有效的。

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

中圖分類(lèi)號(hào)：TP301文獻(xiàn)標(biāo)志碼：A

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

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

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

1．1PSGA算法描述

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

捕食搜索是一種用于解決組合優(yōu)化問(wèn)題的空間搜索策略[8]，它是在模擬動(dòng)物捕食行為的基礎(chǔ)上提出的。動(dòng)物在捕食時(shí)，在沒(méi)有發(fā)現(xiàn)獵物或獵物跡象時(shí)在整個(gè)捕食空間沿著一定的方向以很快的速度尋找獵物；一旦發(fā)現(xiàn)獵物或發(fā)現(xiàn)獵物跡象，它們就放慢步伐，在發(fā)現(xiàn)獵物或有獵物跡象的區(qū)域進(jìn)行集中搜索，以期望找到獵物。在尋找一段時(shí)間而沒(méi)有找到獵物后，捕食動(dòng)物將放棄這種集中的區(qū)域，而繼續(xù)在整個(gè)捕食空間尋找獵物。捕食搜索策略是一種平衡全局探索能力和局部開(kāi)發(fā)能力的方法。將其應(yīng)用到遺傳算法中，首先以較大的交叉概率Pc1和較小的變異概率Pm1進(jìn)行全局搜索；一旦發(fā)現(xiàn)一個(gè)較好的解，則改變?yōu)橐暂^大的變異概率Pm2和較小的交叉概率Pc2進(jìn)行局部搜索；如果在搜索過(guò)程中最優(yōu)解得不到改善，則再以較大的交叉概率Pc1和較小的變異概率Pm1進(jìn)行全局探索。

1．2編碼策略

遺傳算法的編碼方式很多，本研究中采用實(shí)數(shù)編碼。實(shí)數(shù)編碼克服了二進(jìn)制編碼解碼的換算占用計(jì)算機(jī)時(shí)間問(wèn)題以及表達(dá)精度的要求與計(jì)算量之間的矛盾。采用實(shí)數(shù)編碼時(shí)，個(gè)體的表達(dá)形式為

2．2結(jié)果分析

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

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

3結(jié)束語(yǔ)

本文提出了一種基于捕食搜索策略的遺傳算法。該算法根據(jù)當(dāng)代最優(yōu)適應(yīng)度和歷代最優(yōu)適應(yīng)度的比值來(lái)更新交叉概率和變異概率，從而加強(qiáng)算法的全局搜索和局部?jī)?yōu)化的能力。從測(cè)試函數(shù)仿真實(shí)驗(yàn)的結(jié)果來(lái)看，該算法是可行的。

參考文獻(xiàn)：

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

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

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

［4］陳小平，于盛林. 實(shí)數(shù)遺傳算法交叉策略的改進(jìn)[J]. 電子學(xué)報(bào)，2003，31(1):71－74.

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

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

［7］鄒琳，夏巨，胡國(guó)安.基于實(shí)數(shù)編碼的多種群并行遺傳算法研究[J].小型微型計(jì)算機(jī)系統(tǒng)，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］宗敬群. 一類(lèi)混合自適應(yīng)遺傳算法及性能分析[J].系統(tǒng)工程理論與實(shí)踐，2001，21(4):14－18.

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

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”