基于C＋＋遺傳算法實(shí)現(xiàn)及其在連續(xù)最優(yōu)化問題中的性能檢測.doc

基于C遺傳算法實(shí)現(xiàn)及其在連續(xù)最優(yōu)化問題中的性能檢測2004年第20卷第1期2004.Vo1.20No.1電子機(jī)械工程ElectroMechanicalEngineering53基于C+遺傳算法實(shí)現(xiàn)及其在連續(xù)最優(yōu)化問題中的性能檢測岳振興,李莉(南京電子技術(shù)研究所,江蘇南京210013)摘要:對遺傳算法在解連續(xù)優(yōu)化問題中的關(guān)鍵技術(shù)進(jìn)行了討論.運(yùn)用C/C+實(shí)現(xiàn)了遺傳算法的程序編制.數(shù)值仿真結(jié)果驗(yàn)證了遺傳算法計(jì)算性能穩(wěn)健,能夠?qū)?fù)雜,非線性的多峰連續(xù)函數(shù)進(jìn)行全局尋優(yōu).關(guān)鍵詞:遺傳算法;優(yōu)化;凸交叉;動態(tài)變異中圖分類號:TP391.9文獻(xiàn)標(biāo)識碼:B文章編號:10085300(2004)O1005304ProgramofGeneticAlgorithmUsingC+andItsApplicationinContinuousOptimizationYUEZhen-xingLILi(NaResearchInstituteofElectronicsTechnology,Nanjing210013,China)Abstract:Thekeytechniqueaboutgeneticalgorithmappliedtocontinuousoptimizationisdiscussedinthispa.per.AndthesourcecodeforgeneticalgorithmisprogrammedusingC/C+.Simulationshowsthatthegeneticalgorithmisrobustandcanfindtheglobaloptimumforanon-linearmulti-peakcontinuousfunction.Keywords:geneticalgorithm;optimization;convex-crossover;dynamicmutation0引言遺傳算法是一種借鑒生物界自然選擇和自然遺傳機(jī)制的高度并行,隨機(jī),自適應(yīng)搜索算法,其隱含的對全局信息的有效利用能力使遺傳算法具有穩(wěn)健性,能夠很好地處理傳統(tǒng)優(yōu)化方法解決不了的復(fù)雜和非線性問題I.遺傳算法的執(zhí)行過程可以簡單描述為隨機(jī)地在參變量空間中進(jìn)行搜索,由串組成的群體在遺傳算子的作用下,同時對空間中不同的區(qū)域進(jìn)行采樣計(jì)算,從而構(gòu)成一個不斷迭代進(jìn)化的群體序列.遺傳算法的突出表現(xiàn)能力是能夠把注意力集中到搜索空間中期望值最高的部分,這是遺傳算法中雜交算子作用的直接結(jié)果.雜交過程就是模擬生物界中的有性繁殖,它是遺傳算法中最重要的部分,是遺傳算法區(qū)別于其它優(yōu)化算法的根本所在.遺傳算法以迭代群體中的所:有個體為操作對象,從本質(zhì)上講屬于一種群體操作算法,其基本流程如圖1所示.一個標(biāo)準(zhǔn)的遺傳算法程序包含收稿日期:200304114個基本組成部分:(1)參數(shù)編碼;(2)初始群體生成;(3)適應(yīng)值檢測;(4)遺傳操作.其中遺傳操作是遺傳算法的核心,它由3個基本操作算子組成,即選擇算子,交叉算子和變異算子,不同的遺傳算子對算法的運(yùn)行性能有著各不相同的影響.文章主要從遺傳算法在求解連續(xù)最優(yōu)化問題中的設(shè)計(jì)與實(shí)現(xiàn)環(huán)節(jié)上對遺傳算法進(jìn)行研究.根據(jù)所求解問題的性質(zhì),設(shè)計(jì)合理的遺傳算法程序,使之滿足求解問題的要求.1基于C/C+遺傳算法設(shè)計(jì)與實(shí)現(xiàn)1.1連續(xù)最優(yōu)化問題連續(xù)最優(yōu)化通常是極大或極小某個多變量的連續(xù)函數(shù)并使其滿足一些等式/不等式約束.在實(shí)際工程應(yīng)用中大多數(shù)優(yōu)化問題都屬于約束優(yōu)化類型,但是對無約束優(yōu)化問題的研究是求解約束優(yōu)化問題的基礎(chǔ),因此這里取無約束優(yōu)化模型為優(yōu)化算法設(shè)計(jì)求解的目54電子機(jī)械工程第20卷選出兩個個體執(zhí)行交叉Ilgen=O.l一初始群體初始化回兩赫一出個體執(zhí)行變制父代到群體空日插入到群體空閩lll插入到群體空間IlL_.J擴(kuò)大的群體空間_J執(zhí)行選擇更新群體圖1遺傳算法基本流程圖標(biāo)函數(shù).一般,無約束優(yōu)化問題可用如下數(shù)學(xué)模型描述:minf()s.t.X力其中是實(shí)值函數(shù),可行域力是E的子集.若點(diǎn)力是上/的局部最優(yōu)點(diǎn),如果存在占>0使得所有X力與距離不大于占的點(diǎn)滿足f(X)/(X),則點(diǎn)是/在力上的全局最優(yōu)點(diǎn).1.2算法的設(shè)計(jì)與實(shí)現(xiàn)在遺傳算法的實(shí)現(xiàn)上,編碼方法,遺傳算子選擇,控制參數(shù)選取等都是十分關(guān)鍵的問題.下面針對這些問題進(jìn)行設(shè)計(jì)并實(shí)現(xiàn)遺傳算法源代碼程序編制.(1)編碼方法遺傳算法的編碼方式有多種,這里采用實(shí)數(shù)編碼技術(shù)來表達(dá)給定問題的解.在實(shí)數(shù)編碼中,每個染色體編碼為一個和解向量維數(shù)相同的實(shí)向量X=(,x,).這種編碼方式可以直接對解向量進(jìn)行遺傳操作,從而便于引入與優(yōu)化問題領(lǐng)域相關(guān)的啟發(fā)式信息以增加遺傳算法的搜索能力.遺傳個體的簡要類定義形式如下:classPPpublic:doubleX:doubleobjvalue;intparentl,parent2;PP();PP()deletex;其中,實(shí)向量表示個體染色體;objvalue表示對應(yīng)個體染色體的適值,由于程序采用最好種群選擇策略,因此取objvalue等值于優(yōu)化函數(shù)的目標(biāo)值.(2)選擇算子選擇是遺傳算法的推動力,選擇操作決定了父代和子代中哪些個體將被保存到下一代中作為父代.程序中采用(+A)一選擇J,這種選擇策略是由Back和Hoffmeister最先引入到遺傳算法中的,按這種策略,個父代和A個后代競爭生存,最后選出個最好的父代和后代構(gòu)成下一代的父代.(+A)一選擇策略放寬了交叉概率和變異概率的選取范圍,使較大的概率值不會造成個體太多的隨機(jī)變動.程序中實(shí)現(xiàn)選擇操作的源代碼:for(j=0;j<popsize;j+)for(j1=0;jl<freesize;jl+)newpopj.xj1=listpopj.xj1;newpopj.objvalue:listpopj.objvalue;newpopj.parentl=listpopj.parentl;newpopj.parent2=listpopj.parent2;其中,數(shù)組listpop是擴(kuò)大的種群采樣空間(+A);數(shù)組newpop是選出進(jìn)行進(jìn)化操作的下一代種群.(3)交叉算子在遺傳算法中,交叉算子的作用非常重要.一方面,它使原群體中優(yōu)良個體的特性能夠在一定程度上保持;另一方面,它使算法能夠探索新的基因空間,從而使新種群中的個體具有多樣性.依所處理問題性質(zhì)的不同可有多種交叉方式,程序中采用基于算術(shù)運(yùn)算的凸交叉策略,根據(jù)交叉概率進(jìn)行判斷,由父代中選出參加交叉的兩個個體按照公式(1),(2)計(jì)算產(chǎn)生兩個新的后代:XI=AIXI+A2X2=At+A2Xt(1)(2)其中,AI,A2均為實(shí)數(shù)且滿足AI+A2=1.0,A>0,A,>0.程序中交叉算子子函數(shù)源代碼:voidcrossover(doubleparentl,doubleparent2,PPpop,intk5)inti;第1期岳振興.等:基于c+遺傳算法實(shí)現(xiàn)及其在連續(xù)最優(yōu)化問題中的性能檢測55doublerr;rr=0.4689;ncross+;for(J=0;j<freesize;j+)Ipopk5.xj=rrparentlj+(1.0一rr)parent2j;popk5+1.xJ=rrparent2J+(1.0一rr)parentlJ;其中,變量freesize表示個體染色體長度,這里等于優(yōu)化向量的維數(shù);pop表示種群中的個體實(shí)例.(4)變異算子變異是對種群中個體串的某些基因位置上的基因值作變動.在遺傳算法中變異算子的使用使遺傳算法具有局部隨機(jī)搜索能力,同時還使遺傳算法維持種群的多樣性.變異操作基本過程:在群體中所有個體的基因串范圍內(nèi)以事先設(shè)定的變異概率P來選擇進(jìn)行變異操作的基因位,然后對選中的基因位作設(shè)定的變異操作.程序中針對染色體實(shí)數(shù)編碼方式而采用動態(tài)變異l6運(yùn)算規(guī)則來實(shí)現(xiàn)變異操作,主要思想是將變異算子與進(jìn)化代數(shù)聯(lián)系起來,使在進(jìn)化初期,變異范圍相對較大,而隨著種群的進(jìn)化,變異范圍越來越小.這一處理方式提高了算法的運(yùn)算精度,增加了變異算子對進(jìn)化的微調(diào)作用.動態(tài)變異操作的具體實(shí)現(xiàn)步驟描述:對于父親=(.,),通過變異概率P,逐次判斷各基因位是否發(fā)生變異;假設(shè)元素z被選出作變異,則產(chǎn)生的后代=(,:,),其中是按公式(3),(4)兩種可能選得的:或=+a(t,9CU)=a(t,)(3)(4)函數(shù)(t,Y)返回0,Y之間的一個值且隨t增加而趨于0(t是進(jìn)化代數(shù)).函數(shù)a(t,Y)按公式(5)計(jì)算:()=Y(1一專).(5)其中,r是0,1之間的隨機(jī)數(shù);T是最大進(jìn)化代數(shù);b是確定不均勻度的參數(shù).程序中變異算子子函數(shù)源代碼:doublemutation(doublex,intk)Iintrand0;doubletempi,temp2,rand1,value:doublerr,b;nmutation+:srand(unsigned)time(NULL);randl=random(1001)/moo.0:b=3.0;rr=1.0一gen/maxgen:rr=pow(rr,b);tempi=x+rand1rr(topk一x);temp2=xrandlrr(xbottomk);rand0=random(2);if(randO=0)value=tempi;elsevalue=temp2;return(value);f(5)參數(shù)選擇及初始化算法中控制參數(shù)主要包括群體規(guī)模(popsize),交叉概率(pcross)和變異概率(pmutation)等,它們對整個遺傳算法的計(jì)算效能有著不同影響:群體規(guī)模影響算法最終性能和效率,當(dāng)群體規(guī)模較大時,群體中個體的多樣性較強(qiáng),從而阻止算法過早收斂到局部最優(yōu)解;然而,群體規(guī)模過大,每一代中需要的計(jì)算量將很大,這樣可能導(dǎo)致極慢的收斂速度.交叉概率控制交叉算子的應(yīng)用頻率,在每代新的群體中有pcrosspopsize個個體進(jìn)行交叉.交叉概率越高,群體中個體更新越快,如果交叉概率過高,相對選擇能夠產(chǎn)生的改進(jìn)而言,高性能的個體被破壞得更快;交叉概率過低,搜索會由于太小的探察率而可能停滯不前.變異概率是遺傳算法的一個重要參數(shù),它直接影響到算法的收斂性和最終解的性能.較大的變異概率使算法不斷探索新的解空間,增加群體中個體的多樣性,但是過高的變異概率造成的實(shí)質(zhì)是隨機(jī)搜索.實(shí)際上,一個低水平的變異概率足以防止整個群體中任一給定位保持永遠(yuǎn)收斂到單一的值.程序的初始化是由函數(shù)voidinitialize()實(shí)現(xiàn)的,在程序初始運(yùn)行時需要提供種群規(guī)模(popsize),優(yōu)化向量維數(shù)(freesize)即染色體長度,最大進(jìn)化代數(shù)(maxgen),交叉概率(pcross)和變異概率(pmutation)等五個參數(shù)的值以及優(yōu)化向量的界限值bottom和top.初始種群是在向量取值域內(nèi)隨機(jī)產(chǎn)生的,由函數(shù)viodinitpop()實(shí)現(xiàn).2仿真例為檢測基于C/C+設(shè)計(jì)編制的遺傳算法程序的優(yōu)化計(jì)算性能,我們選取Ackley函數(shù)作為檢測函數(shù).Ackley函數(shù)是指數(shù)函數(shù)迭加上適度放大的余弦波再經(jīng)調(diào)制而得到的連續(xù)型實(shí)驗(yàn)函數(shù),它的拓?fù)湫螤钊鐖D2所示,其特征是在一個幾乎平坦的區(qū)域內(nèi)由余弦波調(diào)制形成一個個孔或峰,從而使曲面起伏不平.Ackley函數(shù)如下:電子機(jī)械工程第20卷mi)=_clp-2/nj=lj1一exp(一季lc.s(c.?)+cl+e(6)這里,一5xj5,cl=20,c2=0.2,c3=2rr,e=2.71282=1,2.該函數(shù)的最優(yōu)解為(,X2)=(0,0)XI,X2)=0.l-ffl鼉圖2Ackley函數(shù)按照式(5)中所述控制參數(shù)對遺傳算法計(jì)算效能的不同影響規(guī)律,程序測試中分別取各輸人參數(shù)的值:popsize=160,freesize=2,maxgen=100,pcross=0.4,pmutation=0.05.圖3和圖4是通過仿真繪出的圖形,其中圖3中黑點(diǎn)表示60代遺傳運(yùn)算后得到的各代函數(shù)最小值點(diǎn),圖4是仿真實(shí)驗(yàn)得到的Ackley函數(shù)的尋優(yōu)過程曲線,由圖可以看出經(jīng)過55次進(jìn)化計(jì)算就已找到了最小函數(shù)值min=一5.461828e一003,此時對應(yīng)的=(一4.070457e一011,一1.518713e一010).每圖3優(yōu)化結(jié)果圖4函數(shù)最小值與進(jìn)化代數(shù)關(guān)系3結(jié)論利用C/C+語言設(shè)計(jì)并實(shí)現(xiàn)了遺傳算法中各遺傳操作算子的源代碼編制,如交叉算子,變異算子及選擇算子等.仿真計(jì)算結(jié)果檢驗(yàn)了遺傳算法程序的有效性,表明編制的遺傳算法具有穩(wěn)健的全局尋優(yōu)性能,是求解連續(xù)最優(yōu)化問題的一種有效方法,從而為解決實(shí)際工程設(shè)計(jì)問題提供了良好的優(yōu)化設(shè)計(jì)手段.參考文獻(xiàn):1劉勇,康立山.非數(shù)值并行算法(第二冊)M.北京:科學(xué)出版社,1995.2陳國良.遺傳算法及其應(yīng)用M.北京:人民郵電出版社,1996.3玄光男,程潤偉.遺傳算法與工程設(shè)計(jì)M.北京:科學(xué)出版社,2000.4FogelD.AnIntroductiontoSimulatedEvolutionaryOptimi?zationJ.IEEETransactionsonNeuralNeorks,1994,5:3一l4.5MichalewiczZ.GeneticAlgorithm+DataStructure=Evo?utionProgramM.2nd.SpringVerl