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