摘 要： 運用MATLAB編程實現遺傳算法，數值仿真驗證了該實現方法的有效性，表明它能夠對函數進行全局尋優。這種實現方法既可以熟悉MATLAB語言，又可以加深對遺傳算法的認識和理解，以此來設計智能系統。
關鍵詞： MATLAB 遺傳算法 優化
遺傳算法(Genetic Algoritms，簡稱GA)是以自然選擇和遺傳理論為基礎，將生物進化過程中適者生存規則與群體內部染色體的隨機信息交換機制相結合的搜索算法。自從1975年John H.Holland教授出版GA的經典之作“Adaptation in Natural and Artificial Systems”以來，GA已獲得廣泛應用。
1 遺傳算法簡介
遺傳算法是具有“生成+檢測”的迭代過程的搜索算法。基本流程如圖1所示。可見，遺傳算法是一種群體型操作，該操作以群體中的所有個體為對象。選擇(selection)、交叉(crossover)和變異(mutation)是遺傳算法的三個主要操作算子。遺傳算法包含如下6個基本要素：
(1)參數編碼：由于遺傳算法不能直接處理解空間的解數據，因此必須通過編碼將它們表示成遺傳空間的基因型串結構數據。
(2)生成初始群體：由于遺傳算法的群體型操作需要，所以必須為遺傳操作準備一個由若干初始解組成的初始群體。初始群體的每個個體都是通過隨機方法產生的。
(3)適應度評估檢測：遺傳算法在搜索進化過程中一般不需要其他外部信息，僅用適應度(fitness)值來評估個體或解的優劣，并作為以后遺傳操作的依據。
(4)選擇(selection)：選擇或復制操作是為了從當前群體中選出優良的個體，使它們有機會作為父代為下一代繁殖子孫。個體適應度越高，其被選擇的機會就越多。本文采用與適應度成比例的概率方法進行選擇。具體地說，就是首先計算群體中所有個體適應度的總和(∑f)，再計算每個個體的適應度所占的比例(fi/∑f)，并以此作為相應的選擇概率ps。
(5)交叉操作：交叉操作是遺傳算法中最主要的遺傳操作。簡單的交叉(即一點交叉)可分兩步進行：首先對種群中個體進行隨機配對；其次，在配對個體中隨機設定交叉處，配對個體彼此交換部分信息。
(6)變異：變異操作是按位(bit)進行的，即把某一位的內容進行變異。變異操作同樣也是隨機進行的。一般而言，變異概率pm都取得較小。變異操作是十分微妙的遺傳操作，它需要和交叉操作配合使用，目的是挖掘群體中個體的多樣性，克服有可能限于局部解的弊病。
2 基于MATLAB的遺傳算法的實現
為簡單起見，我們假設尋求一單變量函數F(x)的全局最優解，x對應于[a,b]，下面介紹實現步驟。
2.1 初始化
首先用二進制串表示初始種群中的個體，每一個體由一系列二進制位(0和1)組成，stringlength和popsize分別表示二進制序列的長度和初始種群的個體個數，每一個體用如圖2的方式來編碼，整個初始種群的數據結構由大小為popsize*(stringlength+2)的矩陣實現。
第一列stringlength包括了初始真值x的二進制編碼，該串是隨機產生的，但必須滿足在x的定義域[a,b]中，交叉和變異操作將會對此串進行操作，第(stringlength+1)和(stringlength+2)列分別包含x真值和x的適應度函數F(x)，于是用以下代碼實現初始化過程：
function[pop]＝initialise(popsize,stringlength,fun);
pop＝round(rand(popsize,stringlength+2));
pop(:,stringlength+1)＝sum(2.＾(size(pop(;,1:stringlength),2)－1:－1:0).
pop(:,1:stringlength)(b－a)/(2.＾stringlength－1)+a;
pop(:,stringlength+2)＝fun(pop(;,stringlrngth+1);
end
在上面代碼中，首先隨機產生二進制串，然后用x的真值和目標函數填充到(stringlength+1)和(stringlength+2)中，其中fun為目標函數，以.m的文件形式存在。
2.2 交叉
交叉過程選取兩個體作為父代parent1,parent2，產生出兩新的子代個體child1和child2，pc表示交叉概率，交叉算子的實現過程如下：
function[child1,child2]＝crossover(parent1,parent2,pc);
if(rand＜pc)
cpoint＝round(rand*stringlength－2))+1;
child1＝[parent(:,1:cpoint)parent2(:,cpoint1+1:stringlength)];
child2＝[parent2(:,1:cpoint)parent1(:,cpoint1+1:stringlength)];
child1(:,stringlength+1)＝sum(2.＾(size(child1(:,1:stringlength),2)－1:－1:0).
*child1(:,1:stringlength))*(b－a)/(2.＾stringlength－1)+a;
child2(:,stringlength+1)＝sum(2.＾(size(child2(:,1:stringlength),2)－1:－1:0).
*child2(:,1:stringlength))*(b－a)/(2.＾stringlength－1)+a;
child1(:,stringlength+2)＝fun(child1(:,stringlength+1));
child2(:,stringlength+2)＝fun(child1(:,stringlength+1));
else
child1＝parent1;
child2＝parent2;
end
end
在交叉過程的開始，先產生隨機數與交叉概率相比較，如果隨機數比pc小，則進行交叉運算，否則將不會進行交叉運算，直接返回父代。一旦進行交叉運算，交叉斷點cpoint將在1和stringlength之間選取，交叉點cpoint是由隨機函數在1和(stringlength－1)之間返回一偽隨機整數，于是獲得新的子代個體的真值和其適應度。
2.3 變異
變異操作由一個父代parent產生單個子代child，pm表示變異概率，如果在目前父代允許變異的情況下，我們選擇變異點mpoint使該位取反，可同樣獲得新的子代的真值和適應度。
function[child]＝mutation(parent,pm);
if(rand＜pm)
mpoint＝round(rand*(stringlength－1))+1;
child＝parent;
child[mpoint]＝ads([parent[mpoint]－1);
child(:,stringlength+1)＝sum(2.＾(size(child(:,1:stringlength),2)－1:－1:0).
*child(:,1:stringlength))*(b－a)/(2.＾stringlength－1)+a;
child＝(:,stringlength+2)＝fun(child(:,stringlength+1);
else
child＝parent;
end
end
2.4 選擇
選擇或復制操作是決定哪些個體可以進入下一代。程序中采用賭輪盤選擇法選擇，這種方法較易實現。根據方程fi/∑f＞0計算出每個個體被選擇的概率，向量prob包含了選擇概率之和，向量rns包含歸一化過的隨機數，經過比較rns和prob向量中的元素，我們可以選擇出進入下一代的個體。
function[newpop]＝roulette(oldpop);
totalfit＝sum(oldpop(:,stringlength+2);
prob＝oldpop(:,stringlength+2)/totalfit;
prob＝cumsum(prob);
rns＝sort(rand(popsize,1));
fitin＝1;newin＝1;
while newin＜＝popsize
if(rns(newin)＜prob(fitin))
newpop(newin,:)＝oldpop(fitin,:);
newin＝newin+1;
else
fitin＝fitin+1;
end
end
3 仿真例
為了驗證基于MATLAB設計的遺傳算法的全局尋優能力，舉例驗證。考慮一單變量函數為：
f(x)＝x+10*sin(5x)+7*cos(4x)????????? (2)
x∈[0,9]。按照上述方法，取popsize＝10,stringlength＝20,pc＝0.95,pm＝.08。圖3為此函數的特性，圖中‘+’表示隨機產生的10個函數值；圖4中‘o’為經過一代遺傳，得到的尋優值；經過25代遺傳運算，得到函數的全局最大值，如圖5中的‘*’：即當x為7.8569時函數取得最大值24.8554。
本文用MATLAB語言實現了遺傳算法的各項遺傳操作，如交叉、變異和選擇等，仿真例檢驗了該方法的有效性。采用這種方法既可以使大家熟悉MATLAB語言，又可以加深對遺傳算法的認識和理解，以此來設計智能系統。
參考文獻
1 D.E.Goldberg.Genetic algorithms in search,optimization and machine learning.Addison－Wesley,1989
2 孫增圻.智能控制理論與技術.北京：清華大學出版社，1997
3 席裕庚.遺傳算法綜述.控制理論及應用，1996，13(6)：697－708
4 Y.J.Cao,Q.H.Wu.Teaching Genetic Algorithm Using MAT－LAB.Int.Journal Electrical Engineering on Education,1998(2):139－152