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

1、用于函數(shù)優(yōu)化的遺傳算法一、遺傳算法介紹1 .綜述遺傳算法 （ Genetic Algorithm ） 是由美國Michigan 大學(xué) Holland 教授和他的學(xué)生發(fā)展建立起來的，其思想是起源于生物遺傳學(xué)適者生存的自然規(guī)律，是一種新興的自適應(yīng)隨機(jī)搜索方法，它對優(yōu)化對象既不要求連續(xù)，也不要求可微，并具有極強(qiáng)的魯棒性和內(nèi)在的并行計(jì)算的機(jī)制，特別適合于非凸空間中復(fù)雜的多極值優(yōu)化和組合優(yōu)化問題。2 .基本原理傳統(tǒng)的優(yōu)化理論都是通過調(diào)整模型的參數(shù)來得到期望的結(jié)果，而遺傳優(yōu)化算法是根據(jù)生物界的遺傳和自然選擇的原理來實(shí)現(xiàn)的，它的學(xué)習(xí)過程是通過保持和修改群體解中的個體特性，并且保證這種修改能夠使下一代的群體中

2、的有利于與期望特性相近的個體在整個群體份額中占有的比例越來越多。與基于代數(shù)學(xué)的優(yōu)化方法一樣，遺傳算法是通過連續(xù)不斷地隊(duì)群體進(jìn)行改進(jìn)來搜索函數(shù)的最大值。遺傳算法的搜索結(jié)果會有很大的差異。遺傳學(xué)習(xí)的基本機(jī)理是使那些優(yōu)于群體中其他個體的個體具有生存、繁殖以及保持更多基因給下一代的機(jī)會。遺傳算法實(shí)質(zhì)上是在群體空間中尋求較優(yōu)解。3 .主要構(gòu)成遺傳算法主要由編碼、適應(yīng)度、遺傳算子（選擇算子、交叉算子、變異算子）構(gòu)成，包含的主要進(jìn)化參數(shù)有編碼長度、種群規(guī)模、交叉概率、變異概率、終止進(jìn)化代數(shù)。4 .基本步驟（ 1）初始化：確定種群規(guī)模，交叉概率Pc ， 變異概率Pm 和終止進(jìn)化準(zhǔn)則，隨機(jī)生成初始種群X（t）；

3、置 t 0 ;個體評價:計(jì)算或估計(jì)X（t）中各個個體的適應(yīng)度。（3）選擇：從X（t）運(yùn)用選擇算子選擇出一些母體。（ 4）交叉：對所選個體依概率Pc 執(zhí)行交叉，形成新的種群。（ 5）變異：隨所選個體依概率Pm 執(zhí)行變異，形成新的種群。反復(fù)執(zhí)行步驟（2） -（ 4） ，直到滿足終止進(jìn)化準(zhǔn)則為止。、遺傳算法的設(shè)計(jì)流程圖運(yùn)行參數(shù)：種群大小初始種群三、二進(jìn)制遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)1、編碼本次實(shí)驗(yàn)我們選擇二進(jìn)制編碼方案，它是遺傳算法中最常用的一種編碼方 法，以二進(jìn)制字符0和1為等位基因的定長字符串編碼。如果給定編碼精度e , 取編碼長度m為滿足的最小整數(shù)。其中a,b是優(yōu)化區(qū)間。2m 1在實(shí)驗(yàn)中,由于有兩個自

4、變量我們選定長度=2*Length ,每個自變量編碼長度mx a ( bJ2j1)為為Length=10 ；其解碼公式為j 1,其中i=1 , 2是兩個自變量的編號。2、適應(yīng)度函數(shù)對優(yōu)化的目標(biāo)函數(shù)處理，使其轉(zhuǎn)化為適應(yīng)度函數(shù)。滿足適應(yīng)度大于0的條件，對于求函數(shù)的極大值，只須做非負(fù)化處理。對于求極小值的情況則在目標(biāo) 函數(shù)前加負(fù)號作為適應(yīng)度函數(shù)轉(zhuǎn)換為求極大值。3、選擇算子本次實(shí)驗(yàn)采用的是轉(zhuǎn)盤式選擇算子和最優(yōu)保留策略相結(jié)合的方法來 實(shí)現(xiàn)。計(jì)算種群中每個個體的適應(yīng)度 F,將適應(yīng)度最大的五個個體保留下來不進(jìn) 行交叉變異而直接進(jìn)入下一代，然后將每個個體的適應(yīng)度求和得到ada_sum最為選擇概率pi ,選擇時

5、產(chǎn)生一個rand*ada_sum 的隨機(jī)數(shù)，如果 F F(2) F(i 1) ada_sum * rand F(1) F(2)F 則選擇個體 i。我們采取的策略是最優(yōu)個體保留和轉(zhuǎn)盤式算子結(jié)合的方法，目的是在遺 傳操作中，不僅能不斷提高群體的平均適應(yīng)度，而且能保證最佳個體的適應(yīng)值 不減小。4、交叉算子我們采用的是單點(diǎn)交叉的方法。它是等概率的隨機(jī)指定一個基因位置 作為交叉點(diǎn)，把母體對中兩個個體從交叉點(diǎn)分為前后兩段，確定一個交叉概率 Pc=0.9,當(dāng)產(chǎn)生的隨機(jī)數(shù)小于交叉概率時將兩個個體的后半部分交換，得到兩個新的個體。5、變異算子我們選擇變異概率Pm=0.05對個體編碼用每一位進(jìn)行變異運(yùn)算，采用 單

6、點(diǎn)變異作為變異算子，當(dāng)某位基因處產(chǎn)生的隨機(jī)數(shù)小于變異概率時實(shí)施變異 操作。當(dāng)該位基因是0時變異為1,基因是1時變異為006、終止條件我們以進(jìn)化代數(shù)作為遺傳算法的終止條件。對于不同的測試函數(shù)，我們選 用了不同的迭代次數(shù)。四、運(yùn)行結(jié)果及結(jié)果分析1、運(yùn)行結(jié)果我們選擇了八個檢測函數(shù)對程序進(jìn)行了實(shí)驗(yàn)，每個函數(shù)運(yùn)行10次取最優(yōu)值和最差值，表1為函數(shù)優(yōu)化結(jié)果函數(shù)最優(yōu)值最差值平均值實(shí)際 最優(yōu) 值f1(x)-1.2207 e-0081.2207e-0056.6530 e-0060f2（X）2.2631e-0061.9232e-0048.9500 e-0050f3(x)33.000133f4（X）6.8081e-

7、0082.2219e-0058.5730 e-0060f5（X）-1.0316-1.0309-1.0143-1.031628f6（X）-0.1848-0.1848-0.1848-0.1848f7（X）-186.73 08-186.7012-186.7291-186.73L(X)-2.1188-2.1188-2.1188-2.118檢測函數(shù)1二維球形函數(shù)運(yùn)行結(jié)果19次藪圖一檢測函數(shù)2De Jong函數(shù)運(yùn)行結(jié)果見圖二量優(yōu)值平均值一圖二檢測函數(shù)3Goldstein-price函數(shù)運(yùn)行結(jié)果為圖三檢測函數(shù)4himmelbaut函數(shù)運(yùn)行結(jié)果如圖四圖四檢測函 婁攵5Six-hump camelback函數(shù)運(yùn)

8、行結(jié)果如圖五6 7 8 9-1 一 . - 圖五檢測函數(shù)6Bohachevsky函數(shù)運(yùn)行結(jié)果如圖六次數(shù)o圖六檢測函數(shù)7Shubert函數(shù)運(yùn)行結(jié)果如圖七量優(yōu)值平場點(diǎn)-l I-I l口III,IIII-n10020ason400eoneno7m eno sonimo5000OO檢測函數(shù)8多峰函數(shù)運(yùn)行結(jié)果如圖八1050由5-15001COO2 C42.161500次數(shù)乎均值-1QOO13QC次數(shù)圖八2、結(jié)果分析我們選用賭盤選擇法和最優(yōu)個體保留法相結(jié)合的選擇方案，保證每次迭代的適 應(yīng)度較高的個體保存下來，直接遺傳進(jìn)入下一代。使得局部最優(yōu)個體不被淘汰， 從而使算法的全局搜索能力增強(qiáng)。從表一中可以看出運(yùn)行

9、10次的結(jié)果偏差較小, 最優(yōu)值接近實(shí)際最優(yōu)值。從函數(shù)的運(yùn)行結(jié)果曲線可以看出收斂特性較好，結(jié)果 比較穩(wěn)定。算法尋優(yōu)能力較強(qiáng)，說明此方法較為可靠。五、總結(jié)本次實(shí)習(xí)我們做的是最基本的遺傳算法，首先，在這個過程中，發(fā)現(xiàn)要設(shè) 計(jì)好這個算法，重點(diǎn)在于三個方面。一是編碼的選擇，遺傳算法的編碼有多種 選擇，而如何選擇方便有效的編碼是算法的前提；二是各算子的選擇會影響算 法的效果在設(shè)計(jì)過程中感受最大的就是選擇算子的不同會對結(jié)果造成很大的影 響；三是對于隨機(jī)數(shù)的控制，如何能實(shí)現(xiàn)真正的隨機(jī)，如何初始種群的隨機(jī)而 不是偽隨機(jī)。matlab 程序代碼clear all;close all;clc;% 遺傳算法參數(shù)設(shè)定和

10、初始化M=50; % 種群大小20 個T=1000; % 遺傳運(yùn)算得終止進(jìn)化代數(shù)120代Length=16; % 二進(jìn)制編碼長度16位pc=0.9; % 交叉概率F=0.7pm=0.04; % 變異概率Bi=0.05Max=10; % 輸入值的取值上限Min=-10;%輸入值的取值下限G=round(rand(M,Length*2); % 初始化，使其成為布爾型數(shù)值NG=zeros(M,Length*2);for k=1:1:TT(k)=k;for s=1:1:MN=G(s,:);y1=0;y2=0;N1=N(1:Length);% 對 x1 進(jìn)行解碼，for i=1:Lengthy1=y1+

11、N1(i)*2A(i-1);endx1=(Max-Min)*y1/(2ALength-1)+Min;x1_G(k)=x1;% 為了便于最后圖形輸出，而引進(jìn)的類似指針型變N2=N(Length+1:2*Length);% 對 x2 進(jìn)行解碼for i=1:Lengthy2=y2+N2(i)*2A(i-1);endx2=(Max-Min)*y2/(2ALength-1)+Min;x2_G(k)=x2;% 為了便于最后圖形輸出，而引進(jìn)的類似指針型變f1=0;f2=0;for i=1:5f1=f1+i*(cos(i+1)*x1+i);%f2=f2+i*(cos(i+1)*x2+i); endF(s尸-

12、f1*f2;%x1A2+2*x2A2-0.3*cos(3*pi.*x1)+0.3*cos(4*pi.*x2)+0.3;%4*x 1A2-2.1*x1A4+1/3*x1A6+x1*x2-4*x2A2+4*x2A4;%(x1A2+x2-11)A2+(x1+x2 A 2-7)A2;%1+(1+x1+x2)A2*(19-14*x1+3*x1A2-14*x2+6*x1*x2+3*x2A2)*30+(2*x1- 3*x2)A2*(18-32*x1+12*x1A2+48*x2-36*x1*x2+27*x2A2);%100*(x1.A2-x2).A2+(1-x1).A2;%F(s)=f1*f2; % 目標(biāo)函數(shù)

13、表達(dá)式endFit=F;%+max(F);Order,Index=sort(Fit);% 將適應(yīng)度從小到大進(jìn)行排列BF=Index(M);%Order(M); % 選出適應(yīng)度最大得值BFI(k)=F(BF);% 最小函數(shù)值BFM(k)=mean(BFI);% 每次迭代函數(shù)值的平均值BG=G(Index(M),:);In=M;% 保護(hù) 5個最優(yōu)個體for i=1:1:5BGG(i,:)=G(Index(In),:);In=In-1;end% 采用賭盤選擇法ada_sum=0;for i=1:1:M% 直到累加和>=fit_n ，最后的累加就是復(fù)制個體ada_sum=ada_sum+F(i)

14、;endfor i=1:(M-5)%選擇 39 次，最后一個個體留給歷代最優(yōu)解r=rand*ada_sum; % 隨機(jī)產(chǎn)生一個數(shù)ada_temp=0; % 初始化累加值為0j=1;while(ada_temp<r&&j<20)ada_temp=ada_temp+F(j);j=j+1;endif j=1j=1;elsej=j-1;endNG(i,:)=G(j,:);end%Cn=ceil(2*Length*rand);% 產(chǎn)生單點(diǎn)交叉起始位，%ceil(x)返回大于或等于x的最小整數(shù)值。X的絕對值一定要小于最大整數(shù) 值for i=1:2:(M-5)Rn=rand;%R

15、n 為 0-1 之間的隨機(jī)數(shù)if pc>Rn % 交叉條件，pc=0.6， Rn<0.6 時就進(jìn)行交叉運(yùn)算Cn=ceil(2*Length*Rn);if or(Cn=0,Cn>=20)continue;endfor j=Cn:1:2*Length %隨機(jī)交換部分染色體的基因，交換的位從Cn 到末位止temp=NG(i,j);NG(i,j)=NG(i+1,j);NG(i+1,j)=temp;endend end %Rs=4;% 對第76位到第80位(即后五位)進(jìn)行保優(yōu)for i=1:1:(M-5)%變異運(yùn)算for j=1:1:2*LengthMr=rand;% 產(chǎn)生基本位變異位

16、，同樣Mr 是 0-1 之間的數(shù)if pm>Mr% 變異條件，只有當(dāng)Mr<0.001 時才會進(jìn)行變異運(yùn)算，保證if NG(i,j)=0NG(i,j)=1;elseNG(i,j)=0;endendend end Rs=4;% 對第76位到第80位(即后五位)進(jìn)行保優(yōu)for i=1:1:5NG(M-Rs,:)=BGG(i,:);Rs=Rs-1; endG=NG; endMin,index=max(BFI);Min=-Min%BFI 每次迭代最優(yōu)值，Max 最優(yōu)值%Max=max(BFI)% 歷代最優(yōu)值中的最差最優(yōu)值mean=mean(BFM)% 平均值x1=x1_G(index)% 最

17、優(yōu)值處橫坐標(biāo)x1 的值x2=x2_G(index)% 最優(yōu)值處橫坐標(biāo)x2 的值% 畫圖部分%figure(1)subplot(2,1,1);plot(T,BFI,'b',T,BFM,'r');legend('it 最優(yōu)值 ','it 平均值');xlabel(' 次數(shù)');ylabel(' 函數(shù)值');%hold on%plot(T,BFM,'r'); xlabel(' 次數(shù) ');ylabel(' 平均值 ');%hold off%subplot(2

18、,2,1);plot(T,x1_G); xlabel(' 次數(shù)');ylabel('X1');%subplot(2,2,2);plot(T,x2_G); xlabel(' 次數(shù)');ylabel('X2');X1_G,X2_G=meshgrid(-10:.05:10,-10:.05:10);f1=0;f2=0;for i=1:5f1=f1+i.*(cos(i+1).*X1_G)+i);f2=f1+i.*(cos(i+1).*X2_G)+i);endH=f1.*f2;%X1_G A2+X2_G A2-0.3*cos(3*pi.*X1_G)+0.3*cos(4*pi.*X2_G)+