遺傳算法詳解及Java實現(xiàn)

遺傳算法詳解及Java實現(xiàn)遺傳算法的起源20世紀(jì)60年代中期，美國密西根大學(xué)的JohnHolland提出了位串編碼技術(shù)，這種編碼既適合于變異又適合雜交操作，并且他強調(diào)將雜交作為主要的遺傳操作。遺傳算法的通用編碼技術(shù)及簡單有效的遺傳操作為其廣泛的應(yīng)用和成功奠定了基礎(chǔ)。遺傳算法的目的解決經(jīng)典數(shù)學(xué)方法無法有效地求出最優(yōu)解的復(fù)雜的、大規(guī)模的難題。遺傳算法的思想遺傳算法通常使用二進制編碼來仿照基因編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代(generation)演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應(yīng)度(fitness)大小選擇個體，并借助于自然遺傳學(xué)的遺傳算子(geneticoperators)進行組合交叉(crossover)和變異(mutation)，產(chǎn)生出代表新的解集的種群。遺傳算法的步驟?(1)用固定長度的染色體表示問題變量域，選擇染色體種群數(shù)量為N，交叉概率為C，突變概率為M?(2)定義適應(yīng)性函數(shù)來衡量問題域上單個染色體的性能或適應(yīng)性。適應(yīng)性函數(shù)是在繁殖過程中選擇配對染色體的基礎(chǔ)。?(3)隨機產(chǎn)生一個大小為N的染色體的種群。?(4)計算每個染色體的適應(yīng)性。?(5)在當(dāng)前種群中選擇一對染色體。雙親染色體被選擇的概率和其適應(yīng)性有關(guān)。適應(yīng)性高的染色體被選中的概率高于適應(yīng)性低的染色體。?(6)通過執(zhí)行遺傳操作一一交叉和突變產(chǎn)生一對后代染色體。?(7)將后代染色體放入新種群中。?(8)重復(fù)步驟5,直到新染色體種群的大小等于初始種群的大小N為止。?(9)用新(后代)染色體種群取代初始(雙親)染色體種群。?(10)回到步驟4,重復(fù)這個過程直到滿足終止條件為止。"升始5~隨機初湘匕七群Ptoht。。ilRHO）甲每牛個體的■廷應(yīng)俏.TOC\o"1-5"\h\z―[”輸出量bn個體雜交_]'[—IC~~）|變妹''計算pg何榮個體的酒兩值~擇仇生成新種群（選擇）t6t十1輸出t代few算法思路:?（i）變量作為實數(shù)，可以視為演化算法的表現(xiàn)型形式。從表現(xiàn)型到基因型的映射稱為編碼。我們這里采用二進制編碼，將某個變量值代表的個體表示為一個｛0,1｝二進制串。串長取決于求解的精度。?（2）用遺傳算法解決函數(shù)優(yōu)化問題，先隨機產(chǎn)生0和1填充10個46位基因數(shù)字串來創(chuàng)建染色體的初始種群，再通過自然選擇，交叉，變異等步驟得出下一代種群。?（3）迭代，再次執(zhí)行步驟2直到滿足需求或達到迭代次數(shù)。遺傳算法解決函數(shù)優(yōu)化問題（1）問題描述其他函數(shù)優(yōu)化問題min[3-siiiJava實現(xiàn)代碼：/*將染色體轉(zhuǎn)換成x,y變量的值*/privatedouble口calculatefitnessvalue(Stringstr)((/x】)一血Java實現(xiàn)代碼：/*將染色體轉(zhuǎn)換成x,y變量的值*/privatedouble口calculatefitnessvalue(Stringstr)(?其中其中環(huán)&』0,6］，戶2?對于此例，我們所知對于戶2,3,4和5分別有16,36,64和10。個全局最優(yōu)解。要求；求該函數(shù)的最小值'戶2,精確到小數(shù)點后6位最小值:L000000(2)編碼與解碼確定求解精度到6位小數(shù)，由于區(qū)間長度為6,必須將區(qū)間［0,6］分為6x10人6等份。因為由2A22<6x10A6<2A23得，使用23位的二進制數(shù)來表示變量，故單個染色體需46位基因(以表示x和y兩個變量)示例：一進制申轉(zhuǎn)化為十進制:10<b[Qbgb%b7b2b{>=(旗0.2，)=Vx例如s=<01000110000>「心文=560玲0453<00000000000>與v11111111111a表示區(qū)間的兩『

5//二進制數(shù)前23位為x的二進制字符串，后23位為y的二進制字符串inta=Integer.parseInt(str.substring(0,23),2);intb=Integer.parseInt(str.substring(23,46),2);9doublex=a*(6.0-0)/(Math.pow(2,23)-1);//x的基因doubley=b*(6.0-0)/(Math.pow(2,23)-1);//y的基因14//需優(yōu)化的函數(shù)doublefitness=3-Math.sin(2*x)*Math.sin(2*x)-Math.sin(2*y)*Math.sin(2*y);18double口returns=(x,y,fitness);returnreturns;}(3)(3)輪盤選擇III基本思想：個體被選中的概率與其適應(yīng)度值成正比，即按由個體適應(yīng)度值所決定的某個規(guī)則選擇將進入下一代的個體。(詳細(xì)解析)Java實現(xiàn)代碼：?/***輪盤選擇*計算群體上每個個體的適應(yīng)度值；*按由個體適應(yīng)度值所決定的某個規(guī)則選擇將進入下一代的個體；*/privatevoidselect()(doubleevals[]=newdouble[ChrNum];//所有染色體適應(yīng)值doublep[]=newdouble[ChrNum];//各染色體選擇概率doubleq[]=newdouble[ChrNum];//累計概率doubleF=0;//累計適應(yīng)值總和for(inti=0;i<ChrNum;i++)(evals[i]=calculatefitnessvalue(ipop[i])[2];if(evals[i]<bestfitness)(//記錄下種群中的最小值，即最優(yōu)解bestfitness=evals[i];bestgenerations=generation;beststr=ipop[i];}

1920F=F+evals[i];//所有染色體適應(yīng)值總和21}2223for(inti=0;i<ChrNum;i++)(24p[i]=evals[i]/F;25if(i==0)26q[i]=p[i];27else(28q[i]=q[i-1]+p[i];29}30}31for(inti=0;i<ChrNum;i++)(32doubler=Math.random();33if(r<=q[0])(34ipop[i]=ipop[0];35}else(36for(intj=1;j<ChrNum;j++)(37if(r<q[j])(38ipop[i]=ipop[j];39}40}41}42}}（4）組合交叉（雜交）單點雜交：設(shè)定雜交概率與雜交個體，按照斷裂點進行染色體雜交示例：雜交前：a=<0101l0000>,b=<0111l1111>雜交后：a=<0101l1111>,b=<0111l0000>Java實現(xiàn)代碼：/***交叉操作交叉率為60%，平均為60%的染色體進行交叉*/privatevoidcross()(Stringtemp1,temp2;for(inti=0;i<ChrNum;i++)(

if(Math.random()<0.60)(intpos=(int)(Math.random()*GENE)+1;//pos位}進制串交叉temp1=ipop[i].substring(0,pos)+ipop[(i+1)%ChrNum].substring(pos);temp2=ipop[(i+1)%ChrNum].substring(0,pos)+ipop[i].substring(pos);ipop[i]=temp1;ipop[(i+1)/ChrNum]=temp2;}}}⑸變異基本思想：根據(jù)變異概率選擇變異位點，將二進制位改變Java實現(xiàn)代碼:/***基因突變操作1%基因變異*/privatevoidmutation()(for(inti=0;i<4;i++)(intnum=(int)(Math.random()*GENE*ChrNum+1);intchromosomeNum=(int)(num/GENE)+1;//染色體號8intmutationNum=num-(chromosomeNum-1)*GENE;//基因號if(mutationNum==0)1112131415161718異位點為0時1920212223mutationNum=1;1112131415161718異位點為0時1920212223chromosomeNum=chromosomeNum-1;if(chromosomeNum>=ChrNum)chromosomeNum=9;Stringtemp;Stringa;//記錄變異位點變異后的編碼if(ipop[chromosomeNum].charAt(mutationNum-1)=='0')(a=1;}else(a=〃0〃；}〃當(dāng)變異位點在首、中段和尾時的突變情況if(mutationNum==1)(temp=a+ipop[chromosomeNum].substring(mutationNum);

}else(if(mutationNum!=GENE)(temp=ipop[chromosomeNum].substring(0,mutationN+a+ipop[chromosomeNum].substring(mutationNum);}else(temp=ipop[chromosomeNum].substring(0,mutatio]1)+a;}}〃記錄下變異后的染色體ipop[chromosomeNum]=temp;}}(6)運行結(jié)果1234567891011121314151617181920212223publicstaticvoidmain(Stringargs[])(GATryer=newGA();Tryer.ipop1234567891011121314151617181920212223Tryer.generation=i;}double口x=Tryer.calculatefitnessvalue(Tryer.beststr);str=〃最小值〃+Tryer.bestfitness+'\n'+〃第〃+Tryer.bes