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

1、基于c遺傳算法實現(xiàn)及其在連續(xù)最優(yōu)化問題中的性能檢測2004年第20卷第1期2004.vo1.20no.1電子機(jī)械工程electromechanicalengineering53基于c+遺傳算法實現(xiàn)及其在連續(xù)最優(yōu)化問題中的性能檢測岳振興,李莉(南京電子技術(shù)研究所,江蘇南京210013)摘要:對遺傳算法在解連續(xù)優(yōu)化問題中的關(guān)鍵技術(shù)進(jìn)行了討論.運用c/c+實現(xiàn)了遺傳算法的程序編制.數(shù)值仿真結(jié)果驗證了遺傳算法計算性能穩(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)o1005304p

2、rogramofgeneticalgorithmusingc+anditsapplicationincontinuousoptimizationyuezhen-xinglili(naresearchinstituteofelectronicstechnology,nanjing210013,china)abstract:thekeytechniqueaboutgeneticalgorithmappliedtocontinuousoptimizationisdiscussedinthispa.per.andthesourcecodeforgeneticalgorithmisprogrammedu

3、singc/c+.simulationshowsthatthegeneticalgorithmisrobustandcanfindtheglobaloptimumforanon-linearmulti-peakcontinuousfunction.keywords:geneticalgorithm;optimization;convex-crossover;dynamicmutation0引言遺傳算法是一種借鑒生物界自然選擇和自然遺傳機(jī)制的高度并行,隨機(jī),自適應(yīng)搜索算法,其隱含的對全局信息的有效利用能力使遺傳算法具有穩(wěn)健性,能夠很好地處理傳統(tǒng)優(yōu)化方法解決不了的復(fù)雜和非線性問題i.遺傳算法的執(zhí)行

4、過程可以簡單描述為隨機(jī)地在參變量空間中進(jìn)行搜索,由串組成的群體在遺傳算子的作用下,同時對空間中不同的區(qū)域進(jìn)行采樣計算,從而構(gòu)成一個不斷迭代進(jìn)化的群體序列.遺傳算法的突出表現(xiàn)能力是能夠把注意力集中到搜索空間中期望值最高的部分,這是遺傳算法中雜交算子作用的直接結(jié)果.雜交過程就是模擬生物界中的有性繁殖,它是遺傳算法中最重要的部分,是遺傳算法區(qū)別于其它優(yōu)化算法的根本所在.遺傳算法以迭代群體中的所:有個體為操作對象,從本質(zhì)上講屬于一種群體操作算法,其基本流程如圖1所示.一個標(biāo)準(zhǔn)的遺傳算法程序包含收稿日期:200304114個基本組成部分:(1)參數(shù)編碼;(2)初始群體生成;(3)適應(yīng)值檢測;(4)遺傳操

5、作.其中遺傳操作是遺傳算法的核心,它由3個基本操作算子組成,即選擇算子,交叉算子和變異算子,不同的遺傳算子對算法的運行性能有著各不相同的影響.文章主要從遺傳算法在求解連續(xù)最優(yōu)化問題中的設(shè)計與實現(xiàn)環(huán)節(jié)上對遺傳算法進(jìn)行研究.根據(jù)所求解問題的性質(zhì),設(shè)計合理的遺傳算法程序,使之滿足求解問題的要求.1基于c/c+遺傳算法設(shè)計與實現(xiàn)1.1連續(xù)最優(yōu)化問題連續(xù)最優(yōu)化通常是極大或極小某個多變量的連續(xù)函數(shù)并使其滿足一些等式/不等式約束.在實際工程應(yīng)用中大多數(shù)優(yōu)化問題都屬于約束優(yōu)化類型,但是對無約束優(yōu)化問題的研究是求解約束優(yōu)化問題的基礎(chǔ),因此這里取無約束優(yōu)化模型為優(yōu)化算法設(shè)計求解的目54電子機(jī)械工程第20卷選出兩個

6、個體執(zhí)行交叉ilgen=o.l一初始群體初始化回兩赫一出個體執(zhí)行變制父代到群體空日插入到群體空閩lll插入到群體空間ill_.j擴(kuò)大的群體空間_j執(zhí)行選擇更新群體圖1遺傳算法基本流程圖標(biāo)函數(shù).一般,無約束優(yōu)化問題可用如下數(shù)學(xué)模型描述:minf()s.t.x力其中是實值函數(shù),可行域力是e的子集.若點力是上/的局部最優(yōu)點,如果存在占>0使得所有x力與距離不大于占的點滿足f(x)/(x),則點是/在力上的全局最優(yōu)點.1.2算法的設(shè)計與實現(xiàn)在遺傳算法的實現(xiàn)上,編碼方法,遺傳算子選擇,控制參數(shù)選取等都是十分關(guān)鍵的問題.下面針對這些問題進(jìn)行設(shè)計并實現(xiàn)遺傳算法源代碼程序編制.(1)編碼方法遺傳算法的編

7、碼方式有多種,這里采用實數(shù)編碼技術(shù)來表達(dá)給定問題的解.在實數(shù)編碼中,每個染色體編碼為一個和解向量維數(shù)相同的實向量x=(,x,).這種編碼方式可以直接對解向量進(jìn)行遺傳操作,從而便于引入與優(yōu)化問題領(lǐng)域相關(guān)的啟發(fā)式信息以增加遺傳算法的搜索能力.遺傳個體的簡要類定義形式如下:classpppublic:doublex:doubleobjvalue;intparentl,parent2;pp();pp()deletex;其中,實向量表示個體染色體;objvalue表示對應(yīng)個體染色體的適值,由于程序采用最好種群選擇策略,因此取objvalue等值于優(yōu)化函數(shù)的目標(biāo)值.(2)選擇算子選擇是遺傳算法的推動力,選

8、擇操作決定了父代和子代中哪些個體將被保存到下一代中作為父代.程序中采用(+a)一選擇j,這種選擇策略是由back和hoffmeister最先引入到遺傳算法中的,按這種策略,個父代和a個后代競爭生存,最后選出個最好的父代和后代構(gòu)成下一代的父代.(+a)一選擇策略放寬了交叉概率和變異概率的選取范圍,使較大的概率值不會造成個體太多的隨機(jī)變動.程序中實現(xiàn)選擇操作的源代碼:for(j=0;j<popsize;j+)for(j1=0;jl<freesize;jl+)newpopj.xj1=listpopj.xj1;newpopj.objvalue:listpopj.objvalue;newpo

9、pj.parentl=listpopj.parentl;newpopj.parent2=listpopj.parent2;其中,數(shù)組listpop是擴(kuò)大的種群采樣空間(+a);數(shù)組newpop是選出進(jìn)行進(jìn)化操作的下一代種群.(3)交叉算子在遺傳算法中,交叉算子的作用非常重要.一方面,它使原群體中優(yōu)良個體的特性能夠在一定程度上保持;另一方面,它使算法能夠探索新的基因空間,從而使新種群中的個體具有多樣性.依所處理問題性質(zhì)的不同可有多種交叉方式,程序中采用基于算術(shù)運算的凸交叉策略,根據(jù)交叉概率進(jìn)行判斷,由父代中選出參加交叉的兩個個體按照公式(1),(2)計算產(chǎn)生兩個新的后代:xi=aixi+a2x2

10、=at+a2xt(1)(2)其中,ai,a2均為實數(shù)且滿足ai+a2=1.0,a>0,a,>0.程序中交叉算子子函數(shù)源代碼:voidcrossover(doubleparentl,doubleparent2,pppop,intk5)inti;第1期岳振興.等:基于c+遺傳算法實現(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;其中,變量fr

11、eesize表示個體染色體長度,這里等于優(yōu)化向量的維數(shù);pop表示種群中的個體實例.(4)變異算子變異是對種群中個體串的某些基因位置上的基因值作變動.在遺傳算法中變異算子的使用使遺傳算法具有局部隨機(jī)搜索能力,同時還使遺傳算法維持種群的多樣性.變異操作基本過程:在群體中所有個體的基因串范圍內(nèi)以事先設(shè)定的變異概率p來選擇進(jìn)行變異操作的基因位,然后對選中的基因位作設(shè)定的變異操作.程序中針對染色體實數(shù)編碼方式而采用動態(tài)變異l6運算規(guī)則來實現(xiàn)變異操作,主要思想是將變異算子與進(jìn)化代數(shù)聯(lián)系起來,使在進(jìn)化初期,變異范圍相對較大,而隨著種群的進(jìn)化,變異范圍越來越小.這一處理方式提高了算法的運算精度,增加了變異算

12、子對進(jìn)化的微調(diào)作用.動態(tài)變異操作的具體實現(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)計算:()=y(1一專).(5)其中,r是0,1之間的隨機(jī)數(shù);t是最大進(jìn)化代數(shù);b是確定不均勻度的參數(shù).程序中變異算子子函數(shù)源代碼:doublemutation(doublex,intk)iintrand0;doubletempi,temp2,

13、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)和變異概率(pmuta

14、tion)等,它們對整個遺傳算法的計算效能有著不同影響:群體規(guī)模影響算法最終性能和效率,當(dāng)群體規(guī)模較大時,群體中個體的多樣性較強(qiáng),從而阻止算法過早收斂到局部最優(yōu)解;然而,群體規(guī)模過大,每一代中需要的計算量將很大,這樣可能導(dǎo)致極慢的收斂速度.交叉概率控制交叉算子的應(yīng)用頻率,在每代新的群體中有pcrosspopsize個個體進(jìn)行交叉.交叉概率越高,群體中個體更新越快,如果交叉概率過高,相對選擇能夠產(chǎn)生的改進(jìn)而言,高性能的個體被破壞得更快;交叉概率過低,搜索會由于太小的探察率而可能停滯不前.變異概率是遺傳算法的一個重要參數(shù),它直接影響到算法的收斂性和最終解的性能.較大的變異概率使算法不斷探索新的解空

15、間,增加群體中個體的多樣性,但是過高的變異概率造成的實質(zhì)是隨機(jī)搜索.實際上,一個低水平的變異概率足以防止整個群體中任一給定位保持永遠(yuǎn)收斂到單一的值.程序的初始化是由函數(shù)voidinitialize()實現(xià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()實現(xiàn).2仿真例為檢測基于c/c+設(shè)計編制的遺傳算法程序的優(yōu)化計算性能,我們選取ack

16、ley函數(shù)作為檢測函數(shù).ackley函數(shù)是指數(shù)函數(shù)迭加上適度放大的余弦波再經(jīng)調(diào)制而得到的連續(xù)型實驗函數(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ù)對遺傳算法計算效能的不同影響規(guī)律,程序測試中分別取各輸人參數(shù)的值:p

17、opsize=160,freesize=2,maxgen=100,pcross=0.4,pmutation=0.05.圖3和圖4是通過仿真繪出的圖形,其中圖3中黑點表示60代遺傳運算后得到的各代函數(shù)最小值點,圖4是仿真實驗得到的ackley函數(shù)的尋優(yōu)過程曲線,由圖可以看出經(jīng)過55次進(jìn)化計算就已找到了最小函數(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è)計并實現(xiàn)了遺傳算法中各遺傳操作算子的源代碼編制,如交叉算子,變異算子及選擇算子等.仿真計算結(jié)果檢驗了遺傳算法程

18、序的有效性,表明編制的遺傳算法具有穩(wěn)健的全局尋優(yōu)性能,是求解連續(xù)最優(yōu)化問題的一種有效方法,從而為解決實際工程設(shè)計問題提供了良好的優(yōu)化設(shè)計手段.參考文獻(xiàn):1劉勇,康立山.非數(shù)值并行算法(第二冊)m.北京:科學(xué)出版社,1995.2陳國良.遺傳算法及其應(yīng)用m.北京:人民郵電出版社,1996.3玄光男,程潤偉.遺傳算法與工程設(shè)計m.北京:科學(xué)出版社,2000.4fogeld.anintroductiontosimulatedevolutionaryoptimi?zationj.ieeetransactionsonneuralneorks,1994,5:3一l4.5michalewiczz.geneticalgorithm+datastructure=evo?utionprogramm.2nd.springverl