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