遺傳算法的實現(xiàn)及應用舉例

第六節(jié)算法實現(xiàn)及應用一、算法實現(xiàn)遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架。對于具體問題，可按下述步驟來構造：確定問題編碼方案確定適配值函數(shù)設計遺傳算子（選擇、交叉、變異）確定算法參數(shù)確定算法終止條件生成初始種群SGA實現(xiàn)①個體適應度評價在遺傳算法中，以個體適應度的大小來確定該個體被遺傳到下一代群體中的概率。個體適應度越大，該個體被遺傳到下一代的概率也越大；反之，個體的適應度越小，該個體被遺傳到下一代的概率也越小?；具z傳算法使用比例選擇算子來確定群體中各個個體遺傳到下一代群體中的數(shù)量。為正確計算不同情況下各個個體的遺傳概率，要求所有個體的適應度必須為正數(shù)或0，不能是負數(shù)。為滿足適應度取非負值的要求，基本遺傳算法一般采用下面兩種方法之一將目標函數(shù)值變換為個體的適應度。方法一：對于目標函數(shù)是求極大化，方法為：式中，為一個適當?shù)叵鄬Ρ容^小的數(shù)它可用下面幾種方法之一來選取:預先指定的一個較小的數(shù)；進化到當前代為止的最小目標函數(shù)值；當前代或最近幾代群體中的最小目標值。

②比例選擇算子比例選擇實際上是一種有退還隨機選擇，也叫做賭盤(RouletteWheel)選擇，因為這種選擇方式與賭博中的賭盤操作原理非常相似。比例選擇算子的具體執(zhí)行過程是：先計算出群體中所有個體的適應度之和；其次計算出每個個體的相對適應度的大小，此值即為各個個體被遺傳到下一代群體中的概率；最后再使用模擬賭盤操作（即0到1之間的隨機數(shù)）來確定各個個體被選中的次數(shù)。③單點交叉算子單點交叉算子是最常用和最基本的交叉操作算子。單點交叉算子的具體執(zhí)行過程如下：對群體中的個體進行兩兩隨機配對；對每一對相互配對的個體，隨機設置某一基因座之后的位置為交叉點；對每一對相互配對的個體，依設定的交叉概率在其交叉點處相互交換兩個個體的部分染色體，從而產(chǎn)生出兩個新個體。④基本位變異算子基本位變異算子的具體執(zhí)行過程為：對個體的每一個基因座，依變異概率指定其為變異點；對每一個指定的變異點，對其基因值做取反運算或用其他等位基因值來代替，從而產(chǎn)生出一個新的個體。簡單演示問題：求（1）編碼：編碼長度為5（2）初始群體生成：群體大小設置為4，隨機產(chǎn)生四個個體：編碼：01101，11000，01000，10011

解碼：1324819

適應度：16957664361（3）適應度函數(shù)：（4）輪盤賭選擇：選擇概率個體：01101，11000，01000，10011

適應度：16957664361

選擇概率：0.140.490.060.31選擇11000和01101交配產(chǎn)生下一代（5）交叉操作：發(fā)生交叉的概率取大交叉點位置的選取是隨機的（單點交叉）

0110101100

1100011001（6）變異：發(fā)生變異的概率取小改變某個字節(jié)1100111101（7）新群體的產(chǎn)生：保留上一代最優(yōu)個體，1個新個體取代舊個體

11101，11000，01000，10011（8）重復上述操作20次，或許就能夠得到最優(yōu)解！

應用實例：TSP問題回顧給定n個城市以及兩兩城市之間的距離，求解一條從某個城市出發(fā)、不重復地遍歷所有其它城市并最終又回到起始城市的最短路徑。數(shù)學描述給定圖G=(V,E),V為頂點集,E為邊集，確定一條長度最短的Hamilton回路TSP問題問題復雜度:指數(shù)增長的！(NP完全問題)12個城市，具有39916800條不同的路徑。一條路徑對應一個排列！交叉算子傳統(tǒng)的交叉算子可能產(chǎn)生無效路徑。交叉算子（1）基于位置的交叉把一個父代在向量上的被選元的位置強加到另一個父代。父代1：12345678910父代2：59246110738所選位置：****子代1：19236457810子代2：92345618107交叉算子（2）部分映射交叉利用父代所選段內元的對應定義子代。父代1：26438151079父代2：85110762439子代1：51437621089子代2：72610815439變異算子起雙重作用：1、提供和保持群體的多樣性；

2、搜索算子的作用。(1)基于位置的變異：隨機選擇兩個元，然后把第二個元放在第一個元之前；(2)基于次序的變異：隨機選擇兩個元，然后交換他們的位置；(3)打亂變異：隨機選擇一段，然后打亂這段內的次序。編碼方案路徑表達：對一個旅行最自然的表達一個旅行5—>1—>7—>8—>9—>4—>6—>2—>3的編碼就是（517894623）編碼空間和解空間一一對應，總量為n!個？其實一些解是相同的，因為（51789|4623）=（4623|51789）二者是同一個解(n-1)!/2應用實例1：TSP適應度函數(shù)就取為目標函數(shù)的倒數(shù)，即路徑總長度的倒數(shù)初始種群隨機生成40個終止條件2000次迭代參數(shù)設置自定......p1p2pir選擇操作算子:輪盤式選擇首先計算每個個體

i被選中的概率然后根據(jù)概率的大小將將圓盤分為n個扇形，每個扇形的大小為。選擇時轉動輪盤，參考點r落到扇形i則選擇個體i

。交叉操作算子Davis提出OX算子：通過從一個親體中挑選一個子序列旅行并保存另一個親體的城市相對次序來構造后代例如：p1=（123|4567|89）p2=（452|1876|93）首先保持中間部分

o1=（XXX|4567|XX）

o2=（XXX|1876|XX）交叉操作算子然后移走p2中已在o1中的城市4、5、6和7后，得到2—1—8—9—3該序列順次放在o1中：o1=（218|4567|93）類似地，可以得到另一個后代：o2=（234|1876|59）變異操作算子采用倒置變異：在染色體上隨機地選擇兩點，將兩點間的子串反轉例如原個體：（123456789）隨機選擇兩點：（12|3456|789）倒置后的個體：（12|6543|789）中國城市TSP的一個參考解應用實例2：函數(shù)優(yōu)化函數(shù)優(yōu)化編碼方案采用二進制編碼對子變量定義域根據(jù)計算精度進行離散化處理，然后根據(jù)離散化后待定解的個數(shù)選擇合適長度的二進制字符串進行編碼例如；[0，1]，計算精度0.001,則0，0.001,0.002,…,0.998,0.999,1.000，個數(shù)為1001則用長度為10的二進制字符串一次表征所有離散點0000000000，000000001，…，1111110001。適應度函數(shù)例如，f(x)=x2-

x5，取Cmax=2,即可得到滿足要求的F(x)其它的就類似于TSP的求解了

已知函數(shù)

其中，用遺傳算法求解y的最大值。

例1多元函數(shù)優(yōu)化問題運行步驟運行步驟運行步驟運行步驟運行步驟運行步驟運行步驟

例2一元函數(shù)優(yōu)化問題問題的提出

一元函數(shù)求最大值：問題的提出

用微分法求取

f(x)

的最大值：解有無窮多個：問題的提出

當i為奇數(shù)時xi對應局部極大值點，i為偶數(shù)時xi對應局部極小值。x19即為區(qū)間[-1,2]內的最大值點此時，函數(shù)最大值

f(x19)

比f(1.85)=3.85稍大。編碼表現(xiàn)型：x

基因型：二進制編碼（串長取決于求解精度）

串長與精度之間的關系：若要求求解精度到6位小數(shù)，區(qū)間長度為2-(-1)＝3，即需將區(qū)間分為3/0.000001=3×106等份。所以編碼的二進制串長應為22位。產(chǎn)生初始種群

產(chǎn)生的方式：隨機產(chǎn)生的結果：長度為22的二進制串產(chǎn)生的數(shù)量：種群的大?。ㄒ?guī)模），如30，50，…111101001110000101100011001100111010101011101010100011110010000100101111001001110011100100011001010011000000110000011010010000000000……計算適應度

不同的問題有不同的適應度計算方法本例：直接用目標函數(shù)作為適應度函數(shù)①將某個體轉化為[-1,2]區(qū)間的實數(shù)：

s=<1000101110110101000111>→x=0.637197②計算x的函數(shù)值（適應度）：

f(x)=xsin(10πx)+2.0=2.586345計算適應度

二進制與十進制之間的轉換：

第一步，將一個二進制串（b21b20…b0）轉化為10進制數(shù)：第二步，x’對應的區(qū)間[-1,2]內的實數(shù)：(0000000000000000000000)→-1(1111111111111111111111)→2遺傳操作

選擇：輪盤賭選擇法；交叉：單點交叉；變異：小概率變異模擬結果

設置的參數(shù)：

種群大小50；交叉概率0.75；變異概率0.05；最大代數(shù)200。

得到的最佳個體：

smax=<1111001100111011111100>;

xmax=1.8506;

f(xmax)=3.8503;模擬結果

進化的過程：世代數(shù)自變量適應度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503主程序

%用遺傳算法進行簡單函數(shù)的優(yōu)化clearbn=22;%個體串長度inn=50;%初始種群大小gnmax=200;%最大代數(shù)pc=0.75;%交叉概率pm=0.05;%變異概率Continue…

算法的設計與實現(xiàn)

主程序

%產(chǎn)生初始種群，0,1向量s=round(rand(inn,bn));%計算適應度,返回適應度f和累積概率p[f,p]=objf(s);Continue…主程序

gn=1;whilegn<gnmax+1forj=1:2:inn%選擇操作

seln=sel(s,p);%交叉操作

scro=cro(s,seln,pc);

scnew(j,:)=scro(1,:);scnew(j+1,:)=scro(2,:);%變異操作

smnew(j,:)=mut(scnew(j,:),pm);smnew(j+1,:)=mut(scnew(j+1,:),pm);endContinue…主程序

s=smnew;%產(chǎn)生了新的種群%計算新種群的適應度

[f,p]=objf(s);

%記錄當前代最好和平均的適應度[fmax,nmax]=max(f);fmean=mean(f);ymax(gn)=fmax;ymean(gn)=fmean;Continue…主程序

%記錄當前代的最佳個體x=n2to10(s(nmax,:));xx=-1.0+x*3/(power(2,bn)-1);

xmax(gn)=xx;

gn=gn+1endgn=gn-1;Continue…主程序

%繪制曲線subplot(2,1,1);plot(1:gn,[ymax;ymean]);title('歷代適應度變化','fonts',10);legend('最大適應度','平均適應度');string1=['最終適應度',num2str(ymax(gn))];gtext(string1);subplot(2,1,2);plot(1:gn,xmax,'r-');legend('自變量');string2=['最終自變量',num2str(xmax(gn))];gtext(string2);End計算適應度和累計概率函數(shù)

%計算適應度函數(shù)function[f,p]=objf(s);r=size(s);%讀取種群大小inn=r(1);%有inn個個體bn=r(2);%個體長度為bnContinue…計算適應度和累計概率函數(shù)

fori=1:innx=n2to10(s(i,:));%將二進制轉換為十進制xx=-1.0+x*3/(power(2,bn)-1);%轉化為[-1,2]區(qū)間的實數(shù)

f(i)=ft(xx);%計算函數(shù)值，即適應度endf=f‘;%行向量轉列向量Continue…計算適應度和累計概率函數(shù)

%計算選擇概率fsum=0;fori=1:inn

fsum=fsum+f(i)*f(i);endfori=1:inn

ps(i)=f(i)*f(i)/fsum;endContinue…計算適應度和累計概率函數(shù)

%計算累積概率p(1)=ps(1);fori=2:inn

p(i)=p(i-1)+ps(i);endp=p';Backtomain.m計算目標函數(shù)值函數(shù)

%目標函數(shù)functiony=ft(x);y=x.*sin(10*pi*x)+2;Backtoobjf.m函數(shù)n2to10()

Continue…functionx=n2to10(s)x=0;forj=1:22x=x+s(j)*2^(22-j);end

functionx=n2to10(s)x=s(1);forj=1:21x=x*2+s(j+1);end選擇操作函數(shù)

%“選擇”操作functionseln=sel(s,p);inn=size(p,1);%從種群中選擇兩個個體fori=1:2r=rand;%產(chǎn)生一個隨機數(shù)

prand=p-r;j=1;whileprand(j)<0j=j+1;end

seln(i)=j;%選中個體的序號endBacktomain.m交叉操作函數(shù)

%“交叉”操作functionscro=cro(s,seln,pc);r=size(s);inn=r(1);bn=r(2);pcc=pro(pc);%根據(jù)交叉概率決定是否進行交叉操作，1則是，0則否Continue…交叉操作函數(shù)

ifpcc==1

chb=round(rand*(bn-2))+1;%在[1,bn-1]范圍內隨機產(chǎn)生一個交叉位scro(1,:)=[s(seln(1),1:chb)s(seln(2),chb+1:bn)];scro(2,:)=[s(seln(2),1:chb)s(seln(1),chb+1:bn)];elsescro(1,:)=s(seln(1),:);scro(2,:)=s(seln(2),:);endBacktomain.m變異操作函數(shù)

%“變異”操作functionsnnew=mut(snew,pm);r=size(snew);bn=r(2);snnew=snew;Continue…變異操作函數(shù)

pmm=pro(pm);%根據(jù)變異概率決定是否進行變異操作，1則是，0則否ifpmm==1

chb=round(rand*(bn-1))+1;%在[1,bn]范圍內隨機產(chǎn)生一個變異位

snnew(chb)=abs(snew(chb)-1);endBacktomain.m運行程序

運行程序

運行程序

運行程序

策略調整針對不同實際問題需要調整相應策略同一個實際問題不同的人也有不同的做法編碼方案適應度函數(shù)設計選擇算子交叉算子變異算子初始種群編碼方案本質：如何表示解二進制：自變量高維、大范圍連續(xù)、高精度的時候很難處理冗余問題，離散化后解的個數(shù)介于2(n-1)和2n之間D進制,D=3,8,16,…實數(shù)編碼：無需編碼和解碼序列編碼：例如TSP的路徑表達樹編碼：非定長自適應編碼-長度可調節(jié)適應度函數(shù)是進行自然選擇的定量標準直接采用目標函數(shù)引入適應值調節(jié)線性變換乘冪變換指數(shù)變換自適應變換選擇算子輪盤賭選擇(roulettewheelselection)最基本、最常用的方式，又叫適應度比例選擇算子最佳個體保存(elitistmodel)把適應度最高的個體保留到下一代，又叫精英保留排序模型(rank-basedmodel)按適應度函數(shù)大小排序，根據(jù)事先設定的概率表分配選擇概率聯(lián)賽選擇模型(tournamentselectionmodel)隨機選擇幾個進行比較，高的被選，又叫錦標賽模型選擇算子期望值模型(expectedvaluemodel)排擠模型(crowdingmodel)濃度控制策略共享機制截斷選擇交叉算子簡單交叉最基本、最常用的方式，雙親互換子串平坦交叉二者之間均勻隨機產(chǎn)生算術交叉雙親的凸組合線性交叉1：1，3：1，1：3比較最好的兩個留下交叉算子混合交叉離散交叉啟發(fā)式交叉模擬二進制交叉單峰正態(tài)分布交叉單純形交叉父體中心交叉幾何交叉均勻交叉基于模糊聯(lián)接的交叉變異算子隨機變異區(qū)間內均勻隨機取非一致變異某個區(qū)間內隨機擾動邊界變異取邊界值多項式變異高斯變異Cauthy變異自適應變異Muhlenbein變異初始種群對計算結果和計算效率有影響全局性要求初始解盡量分散設計一些生成方法求解TSP的策略調整編碼方案二進制編碼：交叉和變異很難處理順序表示：1985年

Grefenstette提出，序表示是指所有城市依次排列構成一個順序表(orderlist),對于一條旅程,可以依旅行經(jīng)過順序處理每個城市,每個城市在順序表中的順序就是一個遺傳因子的表示,每處理完一個城市,從順序表中去掉該城市.處理完所有城市以后,將每個城市的遺傳因子表示連接起來,就是一條旅程的基因表示.例如,順序表C=(1,2,3,4,5,6,7,8,9),一條旅程為5-1-7-8-9-4-6-3-2.按照這種編碼方法,這條旅程的編碼為表l=(5155533321)編碼方案路徑表示：最自然、直接的表示方法布爾矩陣表示：將一個旅程定義為一個優(yōu)先權布爾矩陣M,當且僅當城市i排在城市j之前時矩陣元素mij=1.這種方法用n×n矩陣M代表一條旅程,M具有如下三個性質:1)矩陣中1的數(shù)目為n(n-1)/2;2)mii=0,i=1,2,.,n;3)若mij=1,且mjk=1,那么mik=1.選擇算子輪盤賭選擇(roulettewheelselection),最佳個體保存(elitistmodel),期望值模型(expectedvaluemodel),排序模型(rank-basedmodel),聯(lián)賽選擇模型(tournamentselectionmodel)排擠模型(crowdingmodel)濃度控制策略上述機制混合交叉算子依賴于編碼方式基于路徑表示的順序交叉基于路徑表示的部分匹配交叉貪心交叉法：在一個父個體中選擇第一個城市作為子個體的第一個城市,然后在兩個父個體中進行比較并找到與已經(jīng)選擇的那個城市相鄰且距離較近的城市作為下一個城市擴展到旅程中;如果與該城市相鄰的兩個城市有一個已經(jīng)在旅程中,那么選擇另外一個,如果兩個都在旅程中,那么就選擇其它沒有被選擇的城市.循環(huán)交叉邊重組交叉變異算子全局意義點位變異：變異僅以一定的概率(通常很小)對串的某些位做值的變異;逆轉變異：在串中,隨機選擇兩點,再將這兩點內的子串按反序插入到原來的位置中;對換變異：隨機選擇串中的兩點,交換其值(碼);插入變異：從串中隨機選擇1個碼,將此碼插入隨機選擇的插入點中間.變異算子貪心對換變異：從一個染色體中隨機的選擇兩個城市(即兩個碼值),然后交換它們,得到新的染色體,以旅程長度為依據(jù)比較交換后的染色體與原來的染色體的大小,保留旅程長度值小的染色體.倒位變異算子：在個體編碼串中隨機選擇兩個城市,第一個城市的右城市與第二個城市之間的編碼倒序排列,從而產(chǎn)生一個新個體。如，若有父個體P(14

5236),假設隨機選擇的城市是4,3,那么產(chǎn)生的新個體為Offspring(14

3256).遺傳算法的前景性能分析并行遺傳算法分類系統(tǒng)圖像處理和模式識別優(yōu)化與調度機器學習智能控制其它……人工生命自動程序設計應用

遺傳算法的應用二、算法應用領域遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于很多學科。下面列舉一些遺傳算法的主要應用領域。

函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調度、自動控制、機器人學、圖象處理、人工生命、遺傳編程、機器學習等。函數(shù)優(yōu)化。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應用領域，也是對遺傳算法進行性能測試評價的常用算例。對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而遺傳算法卻可以方便地得到較好的結果。組合優(yōu)化。遺傳算法是尋求組合優(yōu)化問題滿意解的最佳工具之一，實踐證明，遺傳算法對于組合優(yōu)化問題中的NP完全問題非常有效。

TSP問題、背包問題、圖劃分問題生產(chǎn)調度問題。生產(chǎn)調度問題在很多情況下所建立起來的數(shù)學模型難以精確求解，即使經(jīng)過一些簡化之后可以進行求解也會因簡化得太多而使求解結果與實際相差太遠?，F(xiàn)在遺傳算法已經(jīng)成為解決復雜調度問題的有效工具。自動控制。遺傳算法已經(jīng)在自動控制領域中得到了很好的應用，例如基于遺傳算法的模糊控制器的優(yōu)化設計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學習、利用遺傳算法進行人工神經(jīng)網(wǎng)絡的結構優(yōu)化設計和權值學習等。如：瓦斯管道控制、導彈控制、機器人控制等

機器人學。機器人是一類復雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對人工自適應系統(tǒng)的研究，所以機器人學自然成為遺傳算法的一個重要應用領域。圖象處理。圖像處理是計算機視覺中的一個重要研究領域。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地存在一些誤差，這些誤差會影響圖像處理的效果。如何使這些誤差最小是使計算機視覺達到實用化的重要要求，遺傳算法在這些圖像處理中的優(yōu)化計算方面得到了很好的應用。

如，模式識別、特征抽取人工生命。人工生命是用計算機、機械等人工媒體模擬或構造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。。自組織能力和自學習能力是人工生命的兩大重要特征。人工生命與遺傳算法有著密切的關系，基于遺傳算法的進化模型是研究人工生命現(xiàn)象的重要理論基礎。遺傳編程。Koza發(fā)展了遺傳編程的概念，他使用了以LISP語言所表示的編碼方法，基于對一種樹形結構所進行的遺傳操作來自動生成計算機程序。機器學習。基于遺傳算法的機器學習，在很多領域中都得到了應用。例如基于遺傳算法的機器學習可用來調整人工神經(jīng)網(wǎng)絡的連接權，也可以用于人工神經(jīng)網(wǎng)絡的網(wǎng)絡結構優(yōu)化設計。規(guī)劃生產(chǎn)規(guī)劃、并行機任務分配等；設計通信網(wǎng)絡設計、噴氣發(fā)動機設計等；信號處理濾波器設計等；機器人路徑規(guī)劃等。

遺傳算法的應用

函數(shù)優(yōu)化

是遺傳算法的經(jīng)典應用領域;組合優(yōu)化

實踐證明，遺傳算法對于組合優(yōu)化中的NP完全問題非常有效;自動控制

如基于遺傳算法的模糊控制器優(yōu)化設計、基于遺傳算法的參數(shù)辨識、利用遺傳算法進行人工神經(jīng)網(wǎng)絡的結構優(yōu)化設計和權值學習等;機器人智能控制

遺傳算法已經(jīng)在移動機器人路徑規(guī)劃、關節(jié)機器人運動軌跡規(guī)劃、機器人逆運動學求解、細胞機器人的結構優(yōu)化和行動協(xié)調等;組合圖像處理和模式識別

目前已在圖像恢復、圖像邊緣持征提取、幾何形狀識別等方面得到了應用;

遺傳算法的應用

人工生命

基于遺傳算法的進化模型是研究人工生命現(xiàn)象的重要理論基礎，遺傳算法已在其進化模型、學習模型、行為模型等方面顯示了初步的應用能力；遺傳程序設計

Koza發(fā)展了遺傳程序設計的慨念，他使用了以LISP語言所表示的編碼方法，基于對一種樹型結構所進行的遺傳操作自動生成計算機程序;

遺傳算法的應用

遺傳算法的應用

約束最優(yōu)化問題（ConstrainedOptimizationProblems）的表述

1解決帶約束的函數(shù)優(yōu)化問題

解決途徑將有約束問題轉化為無約束問題（罰函數(shù)法，penaltyfunctionmethod），歷史較長；改進無約束問題的方法，使之能用于有約束的情況（梯度投影算法），發(fā)展較晚。遺傳算法解決有約束問題的關鍵是對約束條件的處理（直接按無約束問題處理是行不通的：隨機生成的初始點中可能有大量不可行解；遺傳算子作用于可行解后可能產(chǎn)生不可行解）。

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

一般方法罰函數(shù)法

將罰函數(shù)包含到適應度評價中：關鍵是如何設計罰函數(shù)，需要謹慎地在過輕或過重懲罰之間找到平衡，針對不同問題設計罰函數(shù)。

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

一般方法協(xié)同進化遺傳算法（CoevolutionaryGeneticAlgorithm,1997）

以食物鏈關系、共生關系等為基礎的生物進化現(xiàn)象稱為協(xié)同進化；一個種群由問題的解組成，另一個種群由約束組成，兩個種群協(xié)同進化，較好的解應滿足更好的約束，較優(yōu)的約束則被更多的解所違背。

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

罰函數(shù)法評價函數(shù)的構造：

加法

乘法

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

罰函數(shù)法罰函數(shù)分類：

定量懲罰——簡單約束問題

變量懲罰——復雜約束問題，包含兩個部分：可變懲罰率和違反約束的懲罰量。違反約束程度——隨違反約束程度變得嚴重而增加懲罰壓力，靜態(tài)懲罰；進化迭代次數(shù)——隨著進化過程的進展而增加懲罰壓力，動態(tài)懲罰。

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

罰函數(shù)法交叉運算：設父個體為x=[x1,x2,…,xn]和y=[y1,y2,…,yn]

簡單交叉單點算術交叉整體算術交叉基于方向的交叉：x’=r(x-y)+x，r為(0,1)之間的隨機數(shù)，并假設f(x)≥f(y)。

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

罰函數(shù)法變異運算：設父個體為x=[x1,x2,…,xn]

均勻變異非均勻變異（動態(tài)變異）邊界變異：x’=[x1,x2,…,xk’,…,xn]，xk’等概率地取用變異量的上界或下界，當最優(yōu)解在可行域邊界上或附近時，邊界變異算子較為有效；基于方向的變異：x’=x+r?d，d為目標函數(shù)的近似梯度。

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法

線性約束優(yōu)化問題一般形式為：

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法

線性約束優(yōu)化問題：

目標函數(shù)可以是線性函數(shù)或非線性函數(shù)；

思路——消除可能的變量，消除等式約束設計罰函數(shù)設計特別的遺傳操作

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法例：7×7運輸規(guī)劃問題將物品由7個起運站運到7個目的地；已知由i站運到j

地的單位運費是Cij，

ai表示i

站的供應量，

bj表示j

地的需求量，

xij表示從i

站到j

地的運量。（i,j=1,2,…,7）

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法

例：7×7運輸規(guī)劃問題

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法

例：7×7運輸規(guī)劃問題

對于非線性目標函數(shù)的構造，可以選用以下幾種測試函數(shù)：（1）函數(shù)A

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法

例：7×7運輸規(guī)劃問題

（2）函數(shù)B

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法例：7×7運輸規(guī)劃問題

（3）函數(shù)C

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法

例：7×7運輸規(guī)劃問題

（4）函數(shù)D

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法

例：7×7運輸規(guī)劃問題

（5）函數(shù)E

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法

例：7×7運輸規(guī)劃問題

（6）函數(shù)F

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法

例：7×7運輸規(guī)劃問題

目標函數(shù)為罰函數(shù)為其中，k=1，P=1/14，f為第t代群體的平均適應度，T為最大運行代數(shù)，dij為約束的違反度。

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法例：7×7運輸規(guī)劃問題對于約束，個體染色體表示為（v11,…,v77），其約束違反度定義為：

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法

例：7×7運輸規(guī)劃問題

費用參數(shù)表對于函數(shù)A，取S＝2，對于函數(shù)B、E和F，取S＝5。cij27282520202020200215062937710002021017546710004820501706098672523625460027100038269367982704742257710006710004703526100048253842350

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法

例：7×7運輸規(guī)劃問題

消除多余變量：可以消除13個變量，x11,x12,…,x17,x21,x31,x41,x51,x61,x71，其余36個變量設定為y1,y2,…,y36

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法

例：7×7運輸規(guī)劃問題

將原規(guī)劃問題轉化為：

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法

例：7×7運輸規(guī)劃問題

采用的參數(shù)：種群大小40，均勻變異概率0.08，邊界變異概率0.03，非均勻變異概率0.07，簡單交叉概率0.10，單一算術概率0.10，整體算術概率0.10，運行代數(shù)8000。

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

遺傳算法的應用

1解決帶約束的函數(shù)優(yōu)化問題

求解線性約束優(yōu)化問題的遺傳算法

例：7×7運輸規(guī)劃問題結果比較：GENOCOP（約束優(yōu)化的遺傳算法）GAMS（擬牛頓法非線性最優(yōu)化算法）函數(shù)ABCDEFGAMS96.001141.602535.29565.15208.2543527.54GENOCOP24.15205.602571.04480.16204.82119.61誤差%297.52455.25-1.4117.701.6736291.22多目標優(yōu)化問題

解的存在性怎樣求解

遺傳算法的應用

2

解決多目標優(yōu)化問題

Pareto最優(yōu)性理論

在一個有k個目標函數(shù)最小化的問題中，稱決策向量x*∈F是Pareto最優(yōu)的，當不存在另外一個決策向量x∈F同時滿足

遺傳算法的應用

2

解決多目標優(yōu)化問題

Pareto最優(yōu)性理論

多目標優(yōu)化問題的解通常是多個滿意解的集合，稱為Pareto最優(yōu)集，解集中的決策向量稱為非劣的。

遺傳算法的應用

2

解決多目標優(yōu)化問題

傳統(tǒng)方法

多目標加權法層次優(yōu)化法目標規(guī)劃法等特點：將多目標函數(shù)轉化為單目標函數(shù)處理，只能得到特定條件下的某一Pareto解。

遺傳算法的應用

2

解決多目標優(yōu)化問題

多目標優(yōu)化的遺傳算法

優(yōu)勢：

并行地處理一組可能的解；不局限于Pareto前沿的形狀和連續(xù)性，易于處理不連續(xù)的、凹形的Pareto前沿。目前基于Pareto的遺傳算法占據(jù)主要地位。

遺傳算法的應用

2

解決多目標優(yōu)化問題

多目標優(yōu)化的遺傳算法

聚合函數(shù)法：把多個目標函數(shù)表示成一個目標函數(shù)作為遺傳算法的適應函數(shù)（聚合）；無需改動遺傳算法，但權值難以確定；

改進：自適應權值。

遺傳算法的應用

2

解決多目標優(yōu)化問題

多目標優(yōu)化的遺傳算法

向量評價遺傳算法（非Pareto法）：

子種群的產(chǎn)生根據(jù)每一個目標函數(shù)分別進行選擇。

遺傳算法的應用

2

解決多目標優(yōu)化問題

多目標優(yōu)化的遺傳算法

基于排序的多目標遺傳算法：

根據(jù)“Pareto最優(yōu)個體”的概念對所有個體進行排序，依據(jù)這個排列次序來進行進化過程中的選擇運算，從而使得排在前面的Pareto最優(yōu)個體將有更多的機會遺傳到下一代群體。

遺傳算法的應用

2

解決多目標優(yōu)化問題

多目標優(yōu)化的遺傳算法小生境Pareto遺傳算法：

為了保證尋優(yōu)過程不收斂于可行域的某一局部，使種群向均勻分布于Pareto前沿面的方向進化，通過共享函數(shù)定義一小生境加以實現(xiàn)。

遺傳算法的應用

2

解決多目標優(yōu)化問題

TSPBenchmark問題

4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450

遺傳算法的應用

3

解決組合優(yōu)化問題

TSPBenchmark問題

編碼：直接采用解的表示形式,30位（30個城市）長，每位代表所經(jīng)過的城市序號（無重復）；

適應度函數(shù)：個體所代表的路徑距離的倒數(shù)；

選擇：輪盤賭方法

遺傳算法的應用

3

解決組合優(yōu)化問題

TSPBenchmark問題

交叉：有序交叉法

1）隨機選取兩個交叉點；

2）兩個父個體交換中間部分；

3）替換交換后重復的城市序號。X1:98|45671|320X2:87|14032|965X1’:98|14032|320X2’:87|45671|965X1’:98|14032|756X2’:83|45671|902

遺傳算法的應用

3

解決組合優(yōu)化問題

TSPBenchmark問題

變異：隨機選擇同一個個體的兩個點進行交換；

初始參數(shù)：種群規(guī)模100

交叉概率0.8

變異概率0.8

終止代數(shù)2000

遺傳算法的應用

3

解決組合優(yōu)化問題

TSPBenchmark問題運行結果：

遺傳算法的應用

3

解決組合優(yōu)化問題

TSPBenchmark問題運行結果：

遺傳算法的應用

3

解決組合優(yōu)化問題

TSPBenchmark問題運行結果：

遺傳算法的應用

3

解決組合優(yōu)化問題

TSPBenchmark問題運行結果：

遺傳算法的應用

3

解決組合優(yōu)化問題

TSPBenchmark問題運行結果：

遺傳算法的應用

3

解決組合優(yōu)化問題

TSPBenchmark問題運行結果：

遺傳算法的應用

3

解決組合優(yōu)化問題

TSPBenchmark問題運行結果：

遺傳算法的應用

3

解決組合優(yōu)化問題

優(yōu)化神經(jīng)網(wǎng)絡的權值神經(jīng)網(wǎng)絡建模：x1輸出層隱藏層輸入層x2yxn…………

遺傳算法的應用

4

在過程建模中的應用

優(yōu)化神經(jīng)網(wǎng)絡的權值

例：聚丙烯生產(chǎn)過程熔融指數(shù)的軟測量模型輸入變量：加氫量、釜壓、升溫時間、反應時間、攪拌電流；輸出變量：熔融指數(shù)；樣本數(shù)據(jù)：240組現(xiàn)場數(shù)據(jù)；

遺傳算法的應用

4

在過程建模中的應用

優(yōu)化神經(jīng)網(wǎng)絡