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