..PAGEPAGE9/9遺傳算法用于函數優化求解一、實驗目的本實驗要求在掌握遺傳算法的基本思想、原理和算法流程的基礎上,能夠針對指定的單變量優化目標函數,設計相應的遺傳算法優化程序,并求得全局最優解.二、實驗要求針對目標函數

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

y yiix

2(i1)x

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

2n1

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

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

計算適應度函數選擇、復制交叉、變異達到系統指標？迭代次數達上限？

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

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

碼位數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=[];

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

進制轉十進制e=E<j,i>+e*2;end

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

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

率分區[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% 求適應度 x=[];forj=1:Me=0;fori=1: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;%子代適應度children_ave=ysum/M; 代目標函數平均值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