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

遺傳算法基本思想

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

遺傳算法的主要步驟

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

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

（3）計算個體適應度：利用適應度函數計算各個個體的適應度大小。適應度函數（FitnessFunction）的選取直接影響到遺傳算法的收斂速度以及能否找到最優解，因為在進化搜索中基本不利用外部信息，僅以適應度函數為依據，利用種群每個個體的適應程度來指導搜索。

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

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

遺傳編碼

遺傳編碼將變量轉化為基因組的表示形式，優化變量的編碼機制有二進制編碼、十進制編碼（實數編碼）等。

二進制編碼

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

實數編碼

在解決高維、連續優化問題等是，經常采用實數編碼方式。實數編碼的優點是計算精度搞，便于和經典連續優化算法結合。

遺傳算法流程

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

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

3）選擇運算。將選擇算子作用域群體，根據個體適應度，按照一定的規則和方法，選擇一些優良個體遺傳到下一代群體。

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

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

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

實際演示

計算函數

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

仿真過程如下：

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

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

（3）判斷是否滿足終止條件：若滿足，結束搜索過程，輸出最優值；若不滿足，繼續迭代優化

%%%%%%%%%%%%%%%%%%%%實值遺傳算法求函數極值%%%%%%%%%%%%%%%%%%%%%

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

clearall;%清除所有變量

closeall;%清圖

clc;%清屏

D=10;%基因數目

NP=100;%染色體數目

Xs=20;%上限

Xx=-20;%下限

G=1000;%最大遺傳代數

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

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

Pc=0.8;%交叉概率

Pm=0.1;%變異概率

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

%%%%%%%%%%%%%%%%%%%%%%按適應度升序排列%%%%%%%%%%%%%%%%%%%%%%%

fornp=1:NP

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

[SortMSLL,Index]=sort(MSLL);

Sortf=f(:,Index);

%%%%%%%%%%%%%%%%%%%%%%%遺傳算法循環%%%%%%%%%%%%%%%%%%%%%%%%%%

forgen=1:G

%%%%%%%%%%%%%%采用君主方案進行選擇交叉操作%%%%%%%%%%%%%%%%

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

NoPoint=round(D*Pc);%每次交叉點的個數

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;

%%%%%%%%%%%%%%%%%%%%%子種群按適應度升序排列%%%%%%%%%%%%%%%%%%

fornp=1:NP

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

[NSortMSLL,Index]=sort(NMSLL);

NSortf=nf(:,Index);

%%%%%%%%%%%%%%%%%%%%%%%%%產生新種群%%%%%%%%%%%%%%%%%%%%%%%%%%

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

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

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

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

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

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

trace(gen)=SortMSLL(1);%歷代最優適應度值

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

tra