遺傳算法用于函數(shù)優(yōu)化

..PAGEPAGE9/9遺傳算法用于函數(shù)優(yōu)化求解一、實驗?zāi)康谋緦嶒炓笤谡莆者z傳算法的基本思想、原理和算法流程的基礎(chǔ)上,能夠針對指定的單變量優(yōu)化目標(biāo)函數(shù),設(shè)計相應(yīng)的遺傳算法優(yōu)化程序,并求得全局最優(yōu)解.二、實驗要求針對目標(biāo)函數(shù)

y1x1)2x[0,2],設(shè)計利用遺傳算法進行優(yōu)化求解的程交叉和變異概率,分析這些變量對算法精度與收斂性的影響.三、實驗步驟1、初始化種群,確定種群規(guī)模M=20,編碼位數(shù)n=5和編碼機制<二進制編碼>；初始化種群：E=round<rand<M,n>>；每個編碼對應(yīng)的二進制數(shù)值：

y yiix

2(i1)x

yi為第i位二進制代碼；x max min*yxy

2n1

min；2、根據(jù)給定的目標(biāo)函數(shù),計算各個種群的適應(yīng)度值；3、采用輪盤選擇法對種群進行選擇復(fù)制；4、設(shè)定交叉概率為0.9,進行遺傳操作〔交叉〕；5、設(shè)定變異概率0.05,進行遺傳操作〔變異〕；6、產(chǎn)生下一代種群,與終止條件比較,不滿足返回到步驟2直到滿足條件退出.算法的流程如圖7.1所示.圖7.1算法流程圖 開始四、實驗結(jié)果與分析我們采用遺傳算法來20

初始化種群〔編碼〕 尋求目標(biāo)函數(shù)的最大值.碼位數(shù)為5位,采用二進制編碼,交叉0.05,最大迭樣本隨機選應(yīng)度變化小指標(biāo).MATLAB的平均適應(yīng)與最差解,繪1運行時間的 N值〔見表1〕,由表可知,0.65

計算適應(yīng)度函數(shù)選擇、復(fù)制交叉、變異達到系統(tǒng)指標(biāo)？迭代次數(shù)達上限？

概率為0.9,變異概率為代次數(shù)為1000次,初始擇,當(dāng)父代與子代間適于0.001時,達到系統(tǒng)模擬運行輸出迭代種群度變化、種群的最優(yōu)解Y 較快.由圖可知,前期平均 輸出結(jié)果 適應(yīng)于波動平衡狀態(tài).通過對遺傳算內(nèi)的所有個體幾乎都已經(jīng)接近

均適應(yīng)度在0.9以上后,就基本處結(jié)束 法的分析,這是因為種群最優(yōu)值,上升空間比較小且由于有變異的可能性,所以平均適應(yīng)度在后期處于波動狀態(tài).由圖可發(fā)現(xiàn),每代的最大值都差不多,幾乎都是1,但每代的最小值的變化就比較多了,但從趨勢可以基本看出,最小值在逐漸變大,向最大值靠攏.因為要找的最優(yōu)解是最大值,所以在迭代過程中,最小值淘汰幾率最大,它的基因難以遺傳下來,因此最小值會逐漸變大.圖1表1次數(shù)第一次第二次第三次第四次第五次平均時間〔s〕0.7000.6210.6220.5980.6690.642最大值10.99610.99610.99610.99610.99688最小值0.85940.80860.85940.80860.33980.73516改變初始種群的規(guī)模,其他參數(shù)不變,多次運行程序,觀察初始種群規(guī)模大小210的曲折,每代的最大值基本相似,但最小值是近似地隨著平均適應(yīng)度的曲線變化210間和得到的最終最大值最小值,由表可見,運行平均時間為0.6s左右,最終獲得3320030.75s右,每次運行最終最大值幾乎都為1,最小值接近0,與目標(biāo)函數(shù)的最大值基本相10<2,1,133發(fā)現(xiàn),種群規(guī)模越大,平均適應(yīng)度的波動越小,上升坡度越平緩,且最終獲得的最大值和最小值的差別越大,最大值越接近目標(biāo)函數(shù)的實際最大值.由此可分析出,0.001〕,退出循環(huán),而這樣,最終的最小值就會接近最大值,種群內(nèi)部每個個體的差別很小,最大值很難達到目標(biāo)函數(shù)的最大值.只要大多數(shù)個體的基因達到較高適應(yīng)度,就能夠滿足系統(tǒng)標(biāo)準,退出循環(huán),因此每次迭代的最高適應(yīng)度的個體與最低適應(yīng)度的個體幾乎可以共存,最終獲得的最大值幾乎就是目標(biāo)函數(shù)的最大值,最小值也接近目標(biāo)函數(shù)的小的值.圖2時間〔〕最大值最小值第一次第二次第三次第四次第五次平均0.5700.6540.6110.5900.5890.60280.96480.96480.93750.99610.90230.95310.96480.80860.93750.98440.90230.91952圖3次數(shù)〔M=200次數(shù)〔M=200〕第一次第二次第三次第四次第五次平均時間〔s〕0.7360.6800.7980.7980.7150.7454最大值111111最小值0.12110.23440.5273000.1765620,0.4,觀察結(jié)果〔見圖4,40.91,10.64s左右,最終獲得的最大值也差別不大,唯一差別較大的是最終獲得的最0.05〕,可忽略,當(dāng)交叉概率低時,子代個體基本是由父代中適應(yīng)度高的個體〔即目標(biāo)函數(shù)值大的個體〕復(fù)制粘貼而來,所以最終獲得的最小值比較大,而交叉概率高時,子代個體多是由父代優(yōu)秀個體交叉變換而來,可能會使某些子代適應(yīng)度稍微降低,某些又稍微升高,所以相比交叉概率低的時候,最終獲得的最小值比較小.圖4表4次數(shù)第一次第二次第三次第四次第五次平均時間〔s〕0.6480.6200.6700.6210.6440.6406最大值0.99610.98440.99610.984410.9922最小值0.93750.85940.93750.85940.85940.8906420,0.9,0.5,5,550.70.9導(dǎo)致種群無法收斂于一個穩(wěn)定的最佳狀態(tài),由表5可知,改變變異概率對運行時間,最終能達到的最大值影響不大,但影響了最小值,因為變異的概率高,所以種近.圖5表5次數(shù)第一次第二次第三次第四次第五次平均時間〔s〕0.6690.6150.6320.6230.6480.6374最大值0.99610.99611110.99844最小值0.12110.121100.33980.33980.18436初始種群的規(guī)模為20,交叉的概率為0.9,變異概率為0.05,改變編碼位數(shù)分別為8位、5位、3位,其他參數(shù)不變,多次運行程序,觀察結(jié)果〔見圖6,表6,圖7,76與表6是編碼位數(shù)為3位時的情況,圖1與表1的編碼位數(shù)為5位,圖7與表是編碼位數(shù)為8位時的情況.由圖617的平均適應(yīng)度對比發(fā)現(xiàn),雖然適應(yīng)度曲線基本是上升趨勢,但編碼位數(shù)為3時,波動較大,而編碼位數(shù)為5和8時,適應(yīng)度曲線相似,波動都較小.對比每代的最大值最小值發(fā)現(xiàn),最小值對波動的影響都比較大.由表6、表1、表7發(fā)現(xiàn),運行的平均時間都差不多,都是0.6s多,每次運行最編碼位數(shù)較多時,最小值較大.這是因為當(dāng)編碼位數(shù)少時,目標(biāo)函數(shù)y=1-<x-1>^2的x取值就比較有限,比如編碼位數(shù)為3時,x最多只能在0到2之間均勻取8個數(shù),而當(dāng)編碼位數(shù)為8時,能最多取256個數(shù),取的數(shù)越多,個體與個體間的最小差異就越小,因此編碼位數(shù)多時,平均適應(yīng)度的波動會比較小,且最終達到的整體平均適應(yīng)度相對較高,最終最小值也比較大.而編碼位數(shù)少時正好相反.別為5和8的情況,我們發(fā)現(xiàn)編碼位數(shù)也不是越多越好,它們最終達到的最大值基本相似,適應(yīng)度曲線也相似,由此可知道,編碼位數(shù)到達一定程度后不會再對平均適應(yīng)度造成很大影響,而編碼位數(shù)少時,對我們來說,復(fù)雜程度也比較低,所以編碼位數(shù)選擇適中較好.圖6表6次數(shù)第一次第二次第三次第四次第五次平均時間〔s〕0.6390.6530.5990.6000.6080.6198最大值110.9375110.9875最小值0.75000.93750.937500.43750.65625圖7表7次數(shù)第一次第二次第三次第四次第五次平均時間〔s〕0.6420.6340.6260.6520.6220.6352最大值0.99700.99980.99700.99950.98020.9947最小值0.96770.94130.84120.97800.83500.91264通過實驗對比分析發(fā)現(xiàn),種群規(guī)模是影響適應(yīng)度與最終獲得的最優(yōu)解的一個重要因素,當(dāng)種群規(guī)模大時,適應(yīng)度曲線的上升程度比較平緩,且獲得的最優(yōu)值更接近實際的最優(yōu)解.另外,變異概率不能過大,否則適應(yīng)度曲線沒有上升的趨勢,一直處于波動狀態(tài),種群無法收斂于最優(yōu)解附近.編碼位數(shù)不宜過少,不然適應(yīng)度曲線波動較大,不那么容易收斂,最終達到的整體適應(yīng)度較低,編碼位數(shù)也不應(yīng)過多,適中最好.五、MATLAB 編程代碼functiongenetic1%遺傳算法%目標(biāo)函數(shù)y=1-<x-1>^2;M=20; 群規(guī)模%n=5;n=8;

碼位數(shù)p_crossover=0.9; 交叉概率p_mutation=0.05; parent_adptability=[];children_adptability=[];variance_adptability=0;adptability=[];times=1000;time=0;y_min=[];y_max=[];%y_y=[];

代種群適應(yīng)度代種群適應(yīng)度應(yīng)度變化迭代次數(shù)迭代次數(shù)E=round<rand<M,n>>;%初始化種群x=[]; 相應(yīng)的十進制% 求適應(yīng)度 forj=1:Me=0;fori=1:n

進制轉(zhuǎn)十進制e=E<j,i>+e*2;end

x在[0,2]x在[0,2]y=1-<x-1>.^2; 目標(biāo)函數(shù)%y_y=[y_y,y];ysum=0;forj=1:Mysum=y<j,1>+ysum;end

和parent_adptability=y./ysum;%父代的適應(yīng)度parent_ave=ysum/M; 代的目標(biāo)函數(shù)平均值adptability=[adptability;parent_ave];y_max=[y_max;max<y>];y_min=[y_min;min<y>];%end% 遺傳算法 fork=1:times% 選擇 y_Erand<M,1>; 機數(shù)M個y_distributeProbability=[];forj=1:My_probability=0;fori=1:j

率分區(qū)[0,1]y_probability=parent_adptability<i,1>+y_probability;endend%y_distributeProbabilityE_new=[];forj=1:Mfori=1:M

擇個體ify_E<j,1><=y_distributeProbability<i,1>E_new=[E_new;E<i,:>];break;endendend% 交叉變異 E_new_new=[]; 子代forj=1:M/2a=rand<1>;b1=rand<1>;b2=rand<1>;ifa>p_crossover %E_new_new=[E_new_new;E_new<j,:>;E_new<j+M/2,:>];continue;elseA=E_new<j,:>;E_new<j+M/2,:>;E_new<j,1:2>=E_new<j+M/2,1:2>;E_new<j+M/2,1:2>=A<1,1:2>;E_new<j,:>;E_new<j+M/2,:>;E_new_new=[E_new_new;E_new<j,:>;E_new<j+M/2,:>];endelse

if<b1>p_mutation>;

%b1=floor<b1*k>+1;if<E_new_new<j,b1>==0>E_new_new<j,b1>=1;elseE_new_new<j,b1>=0;endendif<b2>p_mutation>;elseb2=floor<b2*k>+1;E_new_new<j+1,b2>=1;elseE_new_new<j+1,b2>=0;endendend% 求適應(yīng)度 x=[];forj=1:Me=0;fori=1:n

進制轉(zhuǎn)十進制end

e=E_new_new<j,i>+e*2;%e=e/16;

e=e/128;x=[x;e];y=1-<x-1>.^2;

在[0,2]之間ysum=0;forj=1:Mysum=y<j,1>+ysum;end

和children_adptability=y./ysum;%子代適應(yīng)度children_ave=ysum/M; 代目標(biāo)函數(shù)平均值adptability=[adptability;children_ave];y_max=[y_max;max<y>];y_min=[y_min;min<y>];%退出條件與下次迭代準備variance_adptability=abs<children_ave-parent_ave>;兩代的變化率ifvariance_adptability<0.001break;end

出條件parent_adptability=children_adptability;parent_ave=children_ave;time=time+1;E=E_new_new;%plot<x,y