Matlab利用遺傳算法GA求解非連續(xù)函數(shù)問題詳解

第Matlab利用遺傳算法GA求解非連續(xù)函數(shù)問題詳解目錄遺傳算法基本思想遺傳算法的主要步驟遺傳編碼二進(jìn)制編碼實(shí)數(shù)編碼遺傳算法流程實(shí)際演示

遺傳算法基本思想

遺傳算法（GeneticAlgorithm,GA）起源于對生物系統(tǒng)所進(jìn)行的計算機(jī)模擬研究。它是模仿自然界生物進(jìn)化機(jī)制發(fā)展起來的隨機(jī)全局搜索和優(yōu)化方法，借鑒了達(dá)爾文的進(jìn)化論和孟德爾的遺傳學(xué)說。其本質(zhì)是一種高效、并行、全局搜索的方法，能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識，并自適應(yīng)地控制搜索過程以求得最佳解。

遺傳算法的主要步驟

（1）編碼：將問題的候選解用染色體表示，實(shí)現(xiàn)解空間向編碼空間的映射過程。遺傳算法不直接處理解空間的決策變量，而是將其轉(zhuǎn)換成由基因按一定結(jié)構(gòu)組成的染色體。編碼方式有很多，如二進(jìn)制編碼、實(shí)數(shù)向量編碼、整數(shù)排列編碼、通用數(shù)據(jù)結(jié)構(gòu)編碼等等。本文將采用二進(jìn)制編碼的方式，將十進(jìn)制的變量轉(zhuǎn)換成二進(jìn)制，用0和1組成的數(shù)字串模擬染色體，可以很方便地實(shí)現(xiàn)基因交叉、變異等操作。

（2）種群初始化：產(chǎn)生代表問題可能潛在解集的一個初始群體（編碼集合）。種群規(guī)模設(shè)定主要有以下方面的考慮：從群體多樣性方面考慮，群體越大越好，避免陷入局部最優(yōu)；從計算效率方面考慮，群體規(guī)模越大將導(dǎo)致計算量的增加。應(yīng)該根據(jù)實(shí)際問題確定種群的規(guī)模。產(chǎn)生初始化種群的方法通常有兩種：一是完全隨機(jī)的方法產(chǎn)生；二是根據(jù)先驗(yàn)知識設(shè)定一組必須滿足的條件，然后根據(jù)這些條件生成初始樣本。

（3）計算個體適應(yīng)度：利用適應(yīng)度函數(shù)計算各個個體的適應(yīng)度大小。適應(yīng)度函數(shù)（FitnessFunction）的選取直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解，因?yàn)樵谶M(jìn)化搜索中基本不利用外部信息，僅以適應(yīng)度函數(shù)為依據(jù)，利用種群每個個體的適應(yīng)程度來指導(dǎo)搜索。

（4）進(jìn)化計算：通過選擇、交叉、變異，產(chǎn)生出代表新的解集的群體。選擇（selection）：根據(jù)個體適應(yīng)度大小，按照優(yōu)勝劣汰的原則，淘汰不合理的個體；交叉（crossover）：編碼的交叉重組，類似于染色體的交叉重組；變異（mutation）：編碼按小概率擾動產(chǎn)生的變化，類似于基因突變。

（5）解碼：末代種群中的最優(yōu)個體經(jīng)過解碼實(shí)現(xiàn)從編碼空間向解空間的映射，可以作為問題的近似最優(yōu)解。這是整個遺傳算法的最后一步，經(jīng)過若干次的進(jìn)化過程，種群中適應(yīng)度最高的個體代表問題的最優(yōu)解，但這個最優(yōu)解還是一個由0和1組成的數(shù)字串，要將它轉(zhuǎn)換成十進(jìn)制才能供我們理解和使用。

遺傳編碼

遺傳編碼將變量轉(zhuǎn)化為基因組的表示形式，優(yōu)化變量的編碼機(jī)制有二進(jìn)制編碼、十進(jìn)制編碼（實(shí)數(shù)編碼）等。

二進(jìn)制編碼

這里簡單介紹以下二進(jìn)制編碼的實(shí)現(xiàn)原理。例如，求實(shí)數(shù)區(qū)間[0,4]上函數(shù)f(x)的最大值，傳統(tǒng)的方法是不斷調(diào)整自變量x的值，假設(shè)使用二進(jìn)制編碼新式，我們可以由長度6的未穿表示變量x，即從000000到111111，并將中間的取值映射到實(shí)數(shù)區(qū)間[0,4]內(nèi)。由于哦才能夠整數(shù)上來看，6位長度二進(jìn)制表示范圍為0~63，所以對應(yīng)的[0,4]區(qū)間，每個相鄰值之間的階躍值為4/640.00635。這個就是編碼的精度，編碼精度越高，所得到的解的質(zhì)量也越高。

實(shí)數(shù)編碼

在解決高維、連續(xù)優(yōu)化問題等是，經(jīng)常采用實(shí)數(shù)編碼方式。實(shí)數(shù)編碼的優(yōu)點(diǎn)是計算精度搞，便于和經(jīng)典連續(xù)優(yōu)化算法結(jié)合。

遺傳算法流程

1）初始化。設(shè)置進(jìn)化代數(shù)計數(shù)器g=0，設(shè)置最大進(jìn)化代數(shù)G，隨機(jī)生成NP個個體作為初始群體P(0)

2）個體評價P(t)。計算群體中各個個體的適應(yīng)度

3）選擇運(yùn)算。將選擇算子作用域群體，根據(jù)個體適應(yīng)度，按照一定的規(guī)則和方法，選擇一些優(yōu)良個體遺傳到下一代群體。

4）交叉運(yùn)算。將交叉算子作用于群體，對選中的成對個體，以某一概率交換他們之間的部分染色體，產(chǎn)生新的個體

5）變異運(yùn)算。將變異算子作用于群體，對選中的個體，以某一概率改變某一個或某一些基因值為其他的等位基因。群體P(t)經(jīng)過選擇、交叉、和變異運(yùn)算之后得到下一代群體P(t+1)。計算其適應(yīng)度值，并根據(jù)適應(yīng)度值進(jìn)行排序，準(zhǔn)備進(jìn)行下一代遺傳操作。

6）終止條件判斷：若gG，則g=g+1，轉(zhuǎn)到步驟2）；若g＞G，則終止計算

實(shí)際演示

計算函數(shù)

的最小值。這是一個簡單的平方和問函數(shù)，只有一個極小點(diǎn)，理論最小值f(0,0,...,0)=0

仿真過程如下：

（1）初始化種群數(shù)目為NP=100，染色體基因維數(shù)D=10，最大進(jìn)化迭代數(shù)G=1000，交叉概率為Pc=0.8，變異概率Pm=0.1

（2）產(chǎn)生初始種群，計算給體適應(yīng)度值；進(jìn)行始數(shù)編碼的安澤以及交叉和變異操作。選擇和交叉操作采用君主方案，即在對群體根據(jù)適應(yīng)度值高低進(jìn)行排序的基礎(chǔ)上，用最優(yōu)個體與其他偶數(shù)位的所有個體進(jìn)行交叉，每次交叉產(chǎn)生兩個新個體。在交叉過后，對信產(chǎn)所的群體進(jìn)行多點(diǎn)變異產(chǎn)生子群體，再計算器適應(yīng)度值，然后和父群體合并，并且根據(jù)適應(yīng)度值進(jìn)行排序，取前NP個個體為新群體，進(jìn)行下一次遺傳操作。

（3）判斷是否滿足終止條件：若滿足，結(jié)束搜索過程，輸出最優(yōu)值；若不滿足，繼續(xù)迭代優(yōu)化

%%%%%%%%%%%%%%%%%%%%實(shí)值遺傳算法求函數(shù)極值%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

clearall;%清除所有變量

closeall;%清圖

clc;%清屏

D=10;%基因數(shù)目

NP=100;%染色體數(shù)目

Xs=20;%上限

Xx=-20;%下限

G=1000;%最大遺傳代數(shù)

f=zeros(D,NP);%初始種群賦空間

nf=zeros(D,NP);%子種群賦空間

Pc=0.8;%交叉概率

Pm=0.1;%變異概率

f=rand(D,NP)*(Xs-Xx)+Xx;%隨機(jī)獲得初始種群

%%%%%%%%%%%%%%%%%%%%%%按適應(yīng)度升序排列%%%%%%%%%%%%%%%%%%%%%%%

fornp=1:NP

MSLL(np)=func2(f(:,np));

[SortMSLL,Index]=sort(MSLL);

Sortf=f(:,Index);

%%%%%%%%%%%%%%%%%%%%%%%遺傳算法循環(huán)%%%%%%%%%%%%%%%%%%%%%%%%%%

forgen=1:G

%%%%%%%%%%%%%%采用君主方案進(jìn)行選擇交叉操作%%%%%%%%%%%%%%%%

Emper=Sortf(:,1);%君主染色體

NoPoint=round(D*Pc);%每次交叉點(diǎn)的個數(shù)

PoPoint=randi([1D],NoPoint,NP/2);%交叉基因的位置

nf=Sortf;

fori=1:NP/2

nf(:,2*i-1)=Emper;

nf(:,2*i)=Sortf(:,2*i);

fork=1:NoPoint

nf(PoPoint(k,i),2*i-1)=nf(PoPoint(k,i),2*i);

nf(PoPoint(k,i),2*i)=Emper(PoPoint(k,i));

%%%%%%%%%%%%%%%%%%%%%%%%%%變異操作%%%%%%%%%%%%%%%%%%%%%%%%%

form=1:NP

forn=1:D

r=rand(1,1);

ifrPm

nf(n,m)=rand(1,1)*(Xs-Xx)+Xx;

%%%%%%%%%%%%%%%%%%%%%子種群按適應(yīng)度升序排列%%%%%%%%%%%%%%%%%%

fornp=1:NP

NMSLL(np)=func2(nf(:,np));

[NSortMSLL,Index]=sort(NMSLL);

NSortf=nf(:,Index);

%%%%%%%%%%%%%%%%%%%%%%%%%產(chǎn)生新種群%%%%%%%%%%%%%%%%%%%%%%%%%%

f1=[Sortf,NSortf];%子代和父代合并

MSLL1=[SortMSLL,NSortMSLL];%子代和父代的適應(yīng)度值合并

[SortMSLL1,Index]=sort(MSLL1);%適應(yīng)度按升序排列

Sortf1=f1(:,Index);%按適應(yīng)度排列個體

SortMSLL=SortMSLL1(1:NP);%取前NP個適應(yīng)度值

Sortf=Sortf1(:,1:NP);%取前NP個個體

trace(gen)=SortMSLL(1);%歷代最優(yōu)適應(yīng)度值

Bestf=Sortf(:,1);%最優(yōu)個體

tra