適應性精英種群策略的遺傳算法用于多模函數(shù)優(yōu)化

Appliedsoftcomputing11(2011)2017–2034Geneticalgorithmwithadaptiveelitist-populationstrategiesformultimodalfunctionoptimization

適應性精英種群策略的遺傳算法用于多模函數(shù)優(yōu)化

YongLiang,Kwong-SakLeung

Keywords:GeneticalgorithmMultimodaloptimizationNichingstrategy

摘要引入了一種新技術,適應性精英種群搜索方法。此方法適應性地調(diào)整種群大小，根據(jù)個體的不相似性和新型的依賴方向的精英遺傳算子，提出了一個適應性精英種群遺傳算法（AEGA）1.介紹現(xiàn)實中的許多問題需要優(yōu)化算法能夠搜索多個最優(yōu)解。近年來已經(jīng)提出了各種種群多樣性改進機制，使得GA通過搜索保持了種群的多樣性，允許GA識別多模函數(shù)的多個最優(yōu)解，但并沒有說明算法對于效率的改進。多模GA的效率必須平衡兩方面的矛盾：1.介紹精英搜索vs.多樣性保持：精英策略在GA中被廣泛采用，用于改善全局最優(yōu)搜索能力，但精英策略關注某些“最優(yōu)”個體，而減少了種群多樣性，而GA又需要保持種群多樣性來發(fā)現(xiàn)多個最優(yōu)解。如何平衡精英搜索和多樣性保持對于構(gòu)建有效率的多模GA是很重要的。算法有效性vs.冗余種群：許多GA使用大規(guī)模種群來提高獲得全局和多個最優(yōu)解的幾率。但大種群將明顯增加算法計算的復雜性，并產(chǎn)生很多多余個體，降低了GA的效率。2.新的適應性精英種群搜索技術（1）個體的相對方向?qū)τ诟呔S的多模函數(shù)最大化問題，定義兩個個體Pi和Pj的相對上升方向，為了方便定義，通過交叉產(chǎn)生的后代個體Ci和Cj作為參考點，通過比較父代和子代的適應度值，定義兩個個體的相對方向。個體Pi相對于Pj的方向定義為：如果f(Ci)-f(Pi)>0，Pi的相對上升方向是移向Pj；如果f(Ci)-f(Pi)=0，Pi的相對上升方向是flat；如果f(Ci)-f(Pi)<0，Pi的相對上升方向是遠離Pj；同理可以定義Pj相對于Pi的上升方向。2.新的適應性精英種群搜索技術（1）個體的相對方向兩個個體的相對上升方向有四種情況：Backtoback:Pi遠離Pj，同時Pj遠離Pi；Facetoface:Pi移向Pj，同時Pj移向Pi；One-way:Pi遠離Pj，同時Pj移向Pi，或者Pj遠離Pi，同時Pi移向Pj；Flat:f(Ci)-f(Pi)=0或f(Cj)-f(Pj)=0PiCiPjCjPiCiPjCjPiCiPjCjBacktobackFacetofaceOne-way2.新的適應性精英種群搜索技術（2）不相似的個體

處于多模函數(shù)不同峰上的點被看做不相似的個體，依據(jù)個體的相對上升方向和個體間的距離d判斷個體的不相似性。個體間距離的閾值為ds，不相似性的原則為：如果兩個個體的相對方向是backtoback，或d>=ds，則兩個個體是不相似的并處于不同的峰上；如果兩個個體的相對方向是facetoface，one-way或flat并且d<ds，則兩個個體是相似的并處于同一峰上。

3.基于適應性精英種群的遺傳算法

基于生境遷移的動態(tài)小生境遺傳聚類算法：（a）精英遺傳算子

精英交叉算子用于搜索精英個體，精英變異算子用于產(chǎn)生并保護處于未探索到的峰上的精英個體。精英交叉算子：①隨機選擇兩個個體Pi和Pj，利用交叉策略產(chǎn)生后代Ci和Cj；3.基于適應性精英種群的遺傳算法

精英交叉算子：②對Pi和Pj應用不相似性判斷原則；

若Pi和Pj是不相似的：如果子代的適應度大于父代，則用子代替換其父代；如果所有父代和子代的適應度相同，則選擇距離最大的兩個個體替換父代個體。若Pi，Pj，Ci，Cj都是相似的：如果所有父代和子代的適應度相同，則從四個個體中隨機選擇一個個體替換父代個體Pi；否則從四個個體中選擇適應度最好的個體替換Pi。然后移去Pj。3.基于適應性精英種群的遺傳算法

精英變異算子：①隨機選擇個體Pi，利用變異策略產(chǎn)生后代Ci；②判斷Pi和Ci的不相似性；若Pi和Ci是相似的：如果f(Ci)>f(Pi)，將Ci替代Pi進入下一代；如果f(Ci)=f(Pi)，則Pi進入下一代。若Pi和Ci是不相似的：Pi直接進入下一代；將Ci與其距離閾值范圍內(nèi)的所有個體Pj進行比較（d(Ci,Pj)<ds），如果不存在這樣的Pj或f(Pj)<f(Ci)，則Ci是未開發(fā)的或至少處于一個不同的峰，Ci進入下一代；如果f(Ci)<f(Pj)，則移去Ci。3.基于適應性精英種群的遺傳算法

（b）種群控制條件上述的精英交叉變異算子保留了很多低適應度的個體，降低了尋優(yōu)的效率，設計如下的種群控制條件：①如果新產(chǎn)生的個體經(jīng)過若干代后，適應度仍很低，則刪除此個體；②如果種群規(guī)模由N增至λ（λ>1）倍，則刪除適應度低的個體。3.基于鑒適應你性精堪英種感群的關遺傳處算法（c）基涼于適肥應性奴精英采種策厲略演稀化算勝法St有ep殼1稱.初始便化種開群。St急ep密2宇.評價趁個體冶的適覽應度議。St躍ep心3伶.執(zhí)行軍精英聯(lián)交叉猾和變盯異策壓略，院并評消價種疤群適層應度魔。St武ep胡4膠.根據(jù)皇種群煌控制灰條件撕控制戴種群極規(guī)模艘。St謠ep物5稈.重復st勤ep令3—警st參ep棵4直到托到達補給定為的最越大代恐數(shù)。4.實驗比較厚算法De買te似rm晴in巨is趙ti別c寄Cr俗ow怪di盈ngPr財ob暗ab賊il書is就ti辛c皮Cr慕ow奸di搭ngSe煌qu工en皆ti釘al男F恰it蕉ne竿ss第S駁ha四ri擦ngCl衛(wèi)ea收ri尿ng既P次ro詳ce仗du料reCl暑us鄙te悠ri佩ngBa匠se分dNi屋ch養(yǎng)in德g(C側(cè)BN蔥)Cl蕉on余alSe糞le潮ct胳io短nSp騰ec盲ie妨s膽Co賄ns嗎er破vi也ng卸G糟en庸et啦ic煙A稠lg相or盯it抬hm作(送SC架GA叔)實驗Co腥mp哄ar證in朋g陸AE尤GA破w拉it識h壯ot偶he羞r錫al嘉go束ri隱th種ms當f盆or孩f列in草di肆ng霸a無ll種m泡ul北ti驗pl鮮e彩op礦ti喉ma雅o塞f拍th腐e沒pr它ob售le負msin仆t京he年f鋤in敬al支p承op蛛ul謹at低io階n平of倉A惕EG齡A,姥t國he蠟1染00縮慧i嶄nd氣iv攪id與ua子ls煉d非ec偉re啟as斧e立to襖5竊i伯nd且iv兩id稱ua姨ls膀c標or鮮re宇sp信on水di今ng竄t污o饒th怎e隊5筆mu干lt鎖ip偷le及o余pt周im達a,冷w細hi雹le西,詳on賠t籠he涂c筑on潮tr獎ar估y,露t孤he覽f喚in彈al拒p土op夠ul偽at普io己n勤of匆o繡th命er評s脾ev洞en攀a基lg饑or柜it擴hm允s拉st狠il乳l椅ha爸ve村1睛00諒i私nd牲iv槳id吊ua郊lsTh葉e繭ch托an兔ge貨p檢ro刺ce歪ss熊es懷o慰f沙th雕eAE快GA宗’spo羽pu穴la鋼ti賓on收s紙iz丘esCo蟻mp蠢ar嬌in踐g由AE崗GA頸w伍it螺h吳ot順he敲r奏al秩go漁ri舌th墻ms府f膽or擴f帖in落di陡ng醒t枯he叔m纏ul猛ti餐pl宵e乘hi幸gh登f途it鉤ne訓ss凈o蘆pt渡im拳a其of沒t嘆he尊p激ro錫bl轟em狐sTh擋e檢ef臥fe義ct健o忠f遮th臂e矩di句st蠢an上ce患p演ar置am稈et鉗er結(jié)論本文部根據(jù)毛個體迫的不費相似叔性和宗新型障的依搞賴方輕向的惹精英偏遺傳捐算子鍛，適秧應性扇