之前兩篇轉載的文章：
[遺傳算法入門到掌握（一）](http://blog.csdn.net/u013007900/article/details/43523975)、[遺傳算法入門到掌握（二）](http://blog.csdn.net/u013007900/article/details/43524005)
對遺傳算法的數學推導講解得非常詳細，同時我也附帶了一份[遺傳算法的C語言實現](http://blog.csdn.net/u013007900/article/details/43524261)，這篇文章將要運用遺傳算法對一個多項式求最小值，要求在(-8,8)間尋找使表達式達到最小的x，誤差為0.001。
但是那篇文章僅僅講解了關于本例的遺傳算法的規則，并沒有詳細的算法過程。
這篇文章簡介一下遺傳算法的具體算法過程，并且用MATLAB實現遺傳算法的代碼，該算法將解決[模擬退火](http://blog.csdn.net/u013007900/article/details/50351523)一文中的例題。
### 遺傳算法簡介
遺傳算法（Genetic Algorithms，簡稱 GA）是一種基于自然選擇原理和自然遺傳機制的搜索（尋優）算法，它是模擬自然界中的生命進化機制，在人工系統中實現特定目標的優化。遺傳算法的實質是通過群體搜索技術，根據適者生存的原則逐代進化，最終得到最優解或準最優解。它必須做以下操作：初始群體的產生、求每一個體的適應度、根據適者生存的原則選擇優良個體、被選出的優良個體兩兩配對，通過隨機交叉其染色 體的基因并隨機變異某些染色體的基因后生成下一代群體，按此方法使群體逐代進化，直到滿足進化終止條件。其實現方法如下：
- （1） 根據具體問題確定可行解域，確定一種編碼方法，能用數值串或字符串表示 可行解域的每一解。
- （2） 對每一解應有一個度量好壞的依據，它用一函數表示，叫做適應度函數，適 應度函數應為非負函數。
- （3） 確定進化參數群體規模M 、交叉概率pc 、變異概率pc 、進化終止條件。
為便于計算，一般來說，每一代群體的個體數目都取相等。群體規模越大、越容易找到最優解，但由于受到計算機的運算能力的限制，群體規模越大，計算所需要的時間也相應的增加。進化終止條件指的是當進化到什么時候結束，它可以設定到某一代進化結束，也可能根據找出近似最優是否滿足精度要求來確定。表1 列出了生物遺傳概念在遺傳算法中的對應關系。
表1 生物遺傳概念在遺傳算法中的對應關
| 生物遺傳概念 | 遺傳算法中的作用 |
|-----|-----|
| 適者生存 | 算法停止時，最優目標值的解有最大的可能被留住 |
| 個體 | 解 |
| 染色體 | 解的編碼 |
| 基因 | 解中每一分量的特征 |
| 適應性 | 適應度函數值 |
| 種群 | 根據適應度函數值選取的一組解 |
| 交配 | 通過交配原則產生一組新解的過程 |
| 變異 | 編碼的某一分量發生變化的過程 |
### 模型及算法
我們用遺傳算法研究上次提到的問題。
- 種群大小：M=50
- 最大代數：G=1000
- 交叉率： pc=1 ，交叉概率為1 能保證種群的充分進化。
- 變異率： pm=0.1 ， 一般而言，變異發生的可能性較小。
（1） 編碼策略
采用十進制編碼，用隨機數列ω1,ω2,…,ω102 作為染色體，其中 0<ωi<1（i=2,3,…,101）， ω1=0，ω102=1 ；每一個隨機序列都和種群中的一個個體相對應，例如一個9 城市問題的一個染色體為
[0.23，0.82，0.45，0.74，0.87，0.11，0.56，0.69，0.78]
其中編碼位置i代表城市i，位置i的隨機數表示城市i在巡回中的順序，我們將這些隨 機數按升序排列得到如下巡回：
6→1→3→7→8→4→9→2→5
（2） 初始種群 本文中我們先利用經典的近似算法—改良圈算法求得一個較好的初始種群。即對于初始圈C=π1…πu?1πuπu+1…πv?1πvπv+1…π102，2≤u<v≤101，2≤πu<πv≤101，交換u與v之間的順序，此時的新路徑為：
π1…πu?1πvπv+1…πu+1πuπv+1…π102
記Δf=(dπu?1πv+dπuπv+1)?(dπu?1πu+dπvπv+1)，若Δf<0，則以新的路經修改舊的路經，直到不能修改為止。
（3） 目標函數
目標函數為偵察所有目標的路徑長度，適應度函數就取為目標函數。我們要求
minf(π1,π2,…,π102)=∑i=1101dπiπi+1
（4） 交叉操作
我 們 的 交 叉 操 作 采 用 單 點 交 叉 。 設 計 如 下 ， 對 于 選 定 的 兩 個 父 代 個 體f1=ω1ω2…ω102，f2=ω1ω2…ω102，我們隨機地選取第t個基因處為交叉點，則經過交叉運算后得到的子代編碼為s1 和s1， s1 的基因由f1的前t個基因和f2 的后102?t個基因構成， s2的基因由f2 的前t個基因和f1的后102?t個基因構成，例如：
f1=[0,0.14,0.25,0.27,??∥??0.29,0.54,…,0.19,1]f2=[0,0.23,0.44,0.56,??∥??0.74,0.21,…,0.24,1]
設交叉點為第四個基因處，則
s1=[0,0.14,0.25,0.27,??∥??0.74,0.21,…,0.24,1]s2=[0,0.23,0.44,0.56,??∥??0.29,0.54,…,0.19,1]
交叉操作的方式有很多種選擇，我們應該盡可能選取好的交叉方式，保證子代能繼承父代的優良特性。同時這里的交叉操作也蘊含了變異操作。
（5） 變異操作
變異也是實現群體多樣性的一種手段，同時也是全局尋優的保證。具體設計如下，按照給定的變異率，對選定變異的個體，隨機地取三個整數，滿足1<u<v<w<102，
把u,v之間（包括u和v）的基因段插到w后面。
（6） 選擇
采用確定性的選擇策略，也就是說選擇目標函數值最小的M個個體進化到下一代，這樣可以保證父代的優良特性被保存下來。
### MATLAB 程序
~~~
clc,clear
load sj.txt %加載敵方100 個目標的數據
x=sj(:,1:2:8);x=x(:);
y=sj(:,2:2:8);y=y(:);
sj=[x y];
d1=[70,40];
sj0=[d1;sj;d1];
%距離矩陣d
sj=sj0*pi/180;
d=zeros(102);
for i=1:101
for j=i+1:102
temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2));
d(i,j)=6370*acos(temp);
end
end
d=d+d';L=102;w=50;dai=100;
%通過改良圈算法選取優良父代A
for k=1:w
c=randperm(100);
c1=[1,c+1,102];
flag=1;
while flag>0
flag=0;
for m=1:L-3
for n=m+2:L-1
if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))<d(c1(m),c1(m+1))+d(c1(n),c1(n+1))
flag=1;
c1(m+1:n)=c1(n:-1:m+1);
end
end
end
end
J(k,c1)=1:102;
end
J=J/102;
J(:,1)=0;J(:,102)=1;
rand('state',sum(clock));
%遺傳算法實現過程
A=J;
for k=1:dai %產生0～1 間隨機數列進行編碼
B=A;
c=randperm(w);
%交配產生子代B
for i=1:2:w
F=2+floor(100*rand(1));
temp=B(c(i),F:102);
B(c(i),F:102)=B(c(i+1),F:102);
B(c(i+1),F:102)=temp;
end
-280-
%變異產生子代C
by=find(rand(1,w)<0.1);
if length(by)==0
by=floor(w*rand(1))+1;
end
C=A(by,:);
L3=length(by);
for j=1:L3
bw=2+floor(100*rand(1,3));
bw=sort(bw);
C(j,:)=C(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102]);
end
G=[A;B;C];
TL=size(G,1);
%在父代和子代中選擇優良品種作為新的父代
[dd,IX]=sort(G,2);temp(1:TL)=0;
for j=1:TL
for i=1:101
temp(j)=temp(j)+d(IX(j,i),IX(j,i+1));
end
end
[DZ,IZ]=sort(temp);
A=G(IZ(1:w),:);
end
path=IX(IZ(1),:)
long=DZ(1)
toc
xx=sj0(path,1);yy=sj0(path,2);
plot(xx,yy,'-o')
~~~
計算結果為 40 小時左右。其中的一個巡航路徑如圖2 所示。
