《MATLAB遺傳算法工具箱及應用》課件第2章

第二章基本遺傳算法及改進 2.1遺傳算法的運行過程

2.1.1完整的遺傳算法運算流程

遺傳算法的一般步驟如圖2.1所示。

完整的遺傳算法運算流程可以用圖2.2來描述。

由圖2.2可以看出，使用上述三種遺傳算子(選擇算子、交叉算子和變異算子)的遺傳算法的主要運算過程如下：圖2.1遺傳算法的一般步驟圖2.2遺傳算法運算流程

(1)編碼：解空間中的解數(shù)據(jù)x作為遺傳算法的表現(xiàn)型形式。從表現(xiàn)型到基因型的映射稱為編碼。遺傳算法在進行搜索之前先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結構數(shù)據(jù)，這些串結構數(shù)據(jù)的不同組合就構成了不同的點。

(2)初始群體的生成：隨機產生N個初始串結構數(shù)據(jù)，每個串結構數(shù)據(jù)稱為一個個體，N個個體構成了一個群體。遺傳算法以這N個串結構作為初始點開始迭代。設置進化代數(shù)計數(shù)器t←0；設置最大進化代數(shù)T；隨機生成M個個體作為初始群體P(0)。

(3)適應度值評價檢測：適應度函數(shù)表明個體或解的優(yōu)劣性。對于不同的問題，適應度函數(shù)的定義方式不同。根據(jù)具體問題，計算群體P(t)中各個個體的適應度。

(4)選擇：將選擇算子作用于群體。

(5)交叉：將交叉算子作用于群體。

(6)變異：將變異算子作用于群體。

群體P(t)經(jīng)過選擇、交叉、變異運算后得到下一代群體P(t+1)。

(7)終止條件判斷：若t≤T，則t←t+1，轉到步驟(2)；若t＞T，則以進化過程中所得到的具有最大適應度的個體作為最優(yōu)解輸出，終止運算。

從遺傳算法運算流程可以看出，進化操作過程簡單，容易理解，它給其他各種遺傳算法提供了一個基本框架。一個簡單的遺傳算法被Goldberg用來進行輪廓描述并用來舉例說明遺傳算法的基本組成。t代種群用變量P(t)表示，初始種群P(0)是隨機設計的，簡單遺傳算法的偽代碼描述如下：

procedureGA

begin

t=0;

initializeP(t);

evaluateP(t);

whilenotfinisheddo

begin

t=t+1;

selectP(t)fromP(t-1);

reproducepairsinP(t);

evaluateP(t);

end

end2.1.2遺傳算法的基本操作

遺傳算法有三個基本操作：選擇(Selection)、交叉(Crossover)和變異(Mutation)。

(1)選擇。選擇的目的是為了從當前群體中選出優(yōu)良的個體，使它們有機會作為父代為下一代繁殖子孫。根據(jù)各個個體的適應度值，按照一定的規(guī)則或方法從上一代群體中選擇出一些優(yōu)良的個體遺傳到下一代群體中。遺傳算法通過選擇運算體現(xiàn)這一思想，進行選擇的原則是適應性強的個體為下一代貢獻一個或多個后代的概率大。這樣就體現(xiàn)了達爾文的適者生存原則。

(2)交叉。交叉操作是遺傳算法中最主要的遺傳操作。通過交叉操作可以得到新一代個體，新個體組合了父輩個體的特性。將群體內的各個個體隨機搭配成對，對每一個個體，以某個概率(稱為交叉概率，CrossoverRate)交換它們之間的部分染色體。交叉體現(xiàn)了信息交換的思想。

(3)變異。變異操作首先在群體中隨機選擇一個個體，對于選中的個體以一定的概率隨機改變串結構數(shù)據(jù)中某個串的值，即對群體中的每一個個體，以某一概率(稱為變異概率，MutationRate)改變某一個或某一些基因座上的基因值為其他的等位基因。同生物界一樣，遺傳算法中變異發(fā)生的概率很低。變異為新個體的產生提供了機會。 2.2基本遺傳算法

基本遺傳算法(也稱為標準遺傳算法或簡單遺傳算法，SimpleGeneticAlgorithm，簡稱SGA)是一種群體型操作，該操作以群體中的所有個體為對象，只使用基本遺傳算子(GeneticOperator)：選擇算子(SelectionOperator)、交叉算子(CrossoverOperator)和變異算子(MutationOperator)，其遺傳進化操作過程簡單，容易理解，是其他一些遺傳算法的基礎，它不僅給各種遺傳算法提供了一個基本框架，同時也具有一定的應用價值。選擇算子、交叉算子和變異算子是遺傳算法的3個主要操作算子，它們構成了所謂的遺傳操作，使遺傳算法具有了其他傳統(tǒng)方法沒有的特點。2.2.1基本遺傳算法的數(shù)學模型

基本遺傳算法可表示為

SGA=(C,E,P0,M,Φ,Γ,Ψ,T)

式中：C——個體的編碼方法；

E——個體適應度評價函數(shù)；

P0——初始種群；

M——種群大??；

Φ——選擇算子；

?！徊嫠阕?；

Ψ——變異算子；

T——遺傳運算終止條件。(2.1)圖2.3遺傳算法的基本流程圖2.2.2基本遺傳算法的步驟

1.染色體編碼(ChromosomeCoding)與解碼(Decode)

基本遺傳算法使用固定長度的二進制符號串來表示群體中的個體，其等位基因由二值{0，1}所組成。初始群體中各個個體的基因可用均勻分布的隨機數(shù)來生成。例如，X=100111001000101101就可表示一個個體，該個體的染色體長度是n=18。

(1)編碼：設某一參數(shù)的取值范圍為［U1,U2］，我們用長度為k的二進制編碼符號來表示該參數(shù)，則它總共產生2k種不同的編碼，可使參數(shù)編碼時的對應關系為000000…0000=0→U1000000…0001=1→U1+δ000000…0010=2→U1+2δ

111111…1111=2k-1→U2

...其中，

(2)解碼：假設某一個體的編碼為bkbk-1bk-2…b2b1，則對應的解碼公式為例如：設有參數(shù)X∈［2,4］，現(xiàn)用5位二進制編碼對X進行編碼，得25=32個二進制串(染色體)：00000，00001，00010，00011，00100，00101，00110，0011101000，01001，01010，01011，01100，01101，01110，0111110000，10001，10010，10011，10100，10101，10110，1011111000，11001，11010，11011，11100，11101，11110，11111對于任一個二進制串，只要代入公式(2.2)，就可得到對應的解碼，如x22=10101，它對應的十進制數(shù)為

bi·2i-1=1+0×2+1×22+0×23+1×24=21，則對應參數(shù)X

的值為2+21×=3.3548。

2.個體適應度的檢測評估

基本遺傳算法按與個體適應度成正比的概率來決定當前群體中各個個體遺傳到下一代群體中的機會多少。為了正確估計這個概率，要求所有個體的適應度必須為非負數(shù)。所以，根據(jù)不同種類的問題，需要預先確定好由目標函數(shù)值到個體適應度之間的轉換規(guī)律，特別是要預先確定好當目標函數(shù)值為負數(shù)時的處理方法。例如，可選取一個適當大的正數(shù)c，使個體的適應度為目標函數(shù)值加上正數(shù)c。

3.遺傳算子

基本遺傳算法使用下列三種遺傳算子:

(1)選擇運算使用比例選擇算子。比例選擇因子是利用比例于各個個體適應度的概率決定其子孫的遺傳可能性。若設種群數(shù)為M，個體i的適應度為fi，則個體i被選取的概率為當個體選擇的概率給定后，產生［0，1］之間的均勻隨機數(shù)來決定哪個個體參加交配。若個體的選擇概率大，則能被多次選中，它的遺傳基因就會在種群中擴大；若個體的選擇概率小，則被淘汰。

(2)交叉運算使用單點交叉算子。只有一個交叉點位置，任意挑選經(jīng)過選擇操作后種群中兩個個體作為交叉對象，隨機產生一個交叉點位置，兩個個體在交叉點位置互換部分基因碼，形成兩個子個體，如圖2.4所示。圖2.4單點交叉示意圖(3)變異運算使用基本位變異算子或均勻變異算子。為了避免問題過早收斂，對于二進制的基因碼組成的個體種群，實現(xiàn)基因碼的小概率翻轉，即0變?yōu)?，而1變?yōu)?，如圖2.5所示。圖2.5變異操作示意圖

4.基本遺傳算法的運行參數(shù)

基本遺傳算法有下列4個運行參數(shù)需要預先設定，即M,T,Pc,Pm。

M為群體大小，即群體中所含個體的數(shù)量，一般取為20～100；

T為遺傳算法的終止進化代數(shù)，一般取為100～500；

Pc為交叉概率，一般取為0.4～0.99；

Pm為變異概率，一般取為0.0001～0.1。2.2.3遺傳算法的具體例證

下面通過具體的例子介紹遺傳算法的實際工作過程。

假設目標函數(shù)為如圖2.6所示，該函數(shù)有多個局部極值點。圖2.6目標函數(shù)的圖像下面介紹求解該優(yōu)化問題的遺傳算法的構造過程。

第一步，確定決策變量和約束條件。

式(2.4)給出，決策變量為x1,x2，約束條件為-3.0≤x1≤12.1,4.1≤x2≤5.8。

第二步，建立優(yōu)化模型。

式(2.3)已給出了問題的數(shù)學模型。

第三步，確定編碼方法。要進行編碼工作，即將變量轉換成二進制串。串的長度取決于所要求的精度。例如，變量xj的區(qū)間是［aj,bj］，要求的精度是小數(shù)點后4位，也就意味著每個變量應該被分成至少(bj-aj)×104個部分。對一個變量的二進制串位數(shù)(用mj表示)，用以下公式計算：

2mj-1＜(bj-aj)×104≤2mj-1

第四步，確定解碼方法。

從二進制串返回一個實際的值可用下面的公式來實現(xiàn)：(2.5)其中，decimal(substringj)代表變量xj的十進位值。不妨設要求的精度為小數(shù)點后4位，則目標函數(shù)的兩個變量x1和x2可以轉換為下面的串：圖2.7一個染色體二進制串對應的變量x1和x2的實值如表2.1所示。變量二進制數(shù)十進制數(shù)x10000010101001010015417x210111101111111024318初始種群可隨機生成如下：

U1=［000001010100101001101111011111110］

U2=［001110101110011000000010101001000］

U3=［111000111000001000010101001000110］

U4=［100110110100101101000000010111001］

U5=［000010111101100010001110001101000］

U6=［111110101011011000000010110011001］

U7=［110100010011111000100110011101101］

U8=［001011010100001100010110011001100］

U9=［111110001011101100011101000111101］

U10=［111101001110101010000010101101010］相對應的十進制的實際值為

U1=［x1,x2］=［-2.687969，5.361653］

U2=［x1,x2］=［0.474101，4.170144］

U3=［x1,x2

］=［10.419457，4.661461］

U4=［x1,x2

］=［6.159951，4.109598］

U5=［x1,x2

］=［-2.301286，4.477282］

U6=［x1,x2

］=［11.788084，4.174346］

U7=［x1,x2

］=［9.342067，5.121702］

U8=［x1,x2

］=［-0.330256，4.694977］

U9=［x1,x2

］=［11.671267，4.873501］

U10=［x1,x2

］=［11.446273，4.171908］

第五步，確定個體評價方法。

對一個染色體串的適應度評價由下列三個步驟組成：

(1)將染色體串進行反編碼，轉換成真實值。在本例中，意味著將二進制串轉為實際值：(2.6)

(2)評價目標函數(shù)f(xk)。

(3)將目標函數(shù)值轉為適應度。對于極大值問題，適應度就等于目標函數(shù)值，即eval(Uk)=f(xk),

k=1,2,…(2.7)在遺傳算法中，評價函數(shù)起著自然進化中環(huán)境的角色，它通過染色體的適應度對其進行評價。上述染色體的適應度值如下：eval(U1)=f(-2.687969，5.361653)=19.805119eval(U2)=f(0.474101，4.170144)=17.370896eval(U3)=f(10.419457，4.661461)=9.590546eval(U4)=f(6.159951，4.109598)=29.406122eval(U5)=f(-2.301286，4.477282)=15.686091eval(U6)=f(11.788084，4.174346)=11.900541eval(U7)=f(9.342067，5.121702)=17.958717eval(U8)=f(-0.330256，4.694977)=19.763190eval(U9)=f(11.671267，4.873501)=26.401669eval(U10)=f(11.446273，4.171908)=10.252480

由以上數(shù)據(jù)可以看出，上述染色體中最健壯的是U4，最虛弱的是U3。

第六步，設計遺傳算子和確定遺傳算法的運行參數(shù)。

(1)選擇運算使用輪盤選擇算子。

以概率的大小來構造新的種群，其步驟如下：

①計算各染色體Uk的適應度值eval(Uk)：eval(Uk)=f(xk),

k=1,2,…(2.8)②計算群體的適應度值總和：(2.9)③計算對應于每個染色體Uk的選擇概率Pk：(2.10)④計算每個染色體Uk的累計概率Qk：j=1,2,…(2.11)在實際工作中，選擇新種群的一個染色體按以下步驟完成：

①生成一個［0，1］間的隨機數(shù)r。

②如果r≤Q1，就選擇染色體U1；否則，選擇第k個染色體Uk(2≤k≤pop-size)使得Qk-1≤r≤Qk

那么，本例中種群的適應度總和為對應于每個染色體Uk(k=1，2，…，10)的選擇概率Pk如下：

P1=0.111180

P2=0.097515

P3=0.053839

P4=0.165077

P5=0.088057

P6=0.066806

P7=0.100815

P8=0.110945

P9=0.148211

P10=0.057554

對應于每個染色體Uk(k=1，2，…，10)的累計概率Qk如下：

Q1=0.111180

Q2=0.208695

Q3=0.262534

Q4=0.427611

Q5=0.515668

Q6=0.582475

Q7=0.683290

Q8=0.794234

Q9=0.942446

Q10=1.000000現(xiàn)在，我們轉動輪盤10次，每次選擇一個新種群中的染色體。假設這10次中生成的［0，1］間的隨機數(shù)如下：

0.301431

0.322062

0.766503

0.881893

0.350871

0.583392

0.1776180.343242

0.032685

0.197577

第一個隨機數(shù)r1=0.301431大于Q3，小于Q4，這樣染色體U4被選中；第二個隨機數(shù)r2=0.322062也大于Q3，小于Q4，于是染色體U4被再次選中。最終，新的種群由下列染色體組成：U1=［100110110100101101000000010111001］(U4)

U2=［100110110100101101000000010111001］(U4)

U3=［001011010100001100010110011001100］(U8)

U4=［1111100010111011000111010001111101］(U9)

U5=［100110110100101101000000010111001］(U4)

U6=［110100010011111000100110011101101］(U7)

U7=［001110101110011000000010101001000］(U2)

U8=［100110110100101101000000010111001］(U4)

U9=［000001010100101001101111011111110］(U1)

U10=［001110101110011000000010101001000］(U2)

(2)交叉運算使用單點交叉算子。

隨機選擇一個染色體串的節(jié)點，然后交換兩個父輩節(jié)點右端部分來產生子輩。假設兩個父輩染色體如下所示（節(jié)點隨機選擇在染色體串的第17位基因）：

U1=［100110110100101101000000010111001］

U2=［001011010100001100010110011001100］

假設交叉概率為P0=25%，即在平均水平上有25%的染色體進行了交叉。交叉操作的過程如下：

開始

k←0；

當k≤10時繼續(xù)

rk←［0,1］之間的隨機數(shù)；

如果rk＜0.25，則

選擇Uk為交叉的一個父輩；

結束

k←k+1；

結束

結束假設隨機數(shù)如下：

0.6257210.2668230.288644

0.295114

0.163274

0.5674610.0859400.3928650.770714

0.548656

那么，就意味著染色體U5和U7被選中作為交叉的父輩。在這里，我們隨機選擇一個［1，32］間的整數(shù)(因為33是整個染色體串的長度)作為交叉點。假設生成的整數(shù)pos為1，那么兩個染色體從第一位分割，新的子輩在第一位右端的部分互換而生成，即

U5=［100110110100101101000000010111001］

U7=［001110101110011000000010101001000］

U*5=［101110101110011000000010101001000］

U*7=［000110110100101101000000010111001］

(3)變異運算使用基本位變異算子。

假設染色體U1的第18位基因被選作變異，即如果該位基因是1，則變異后就為0。于是，染色體在變異后將是：U1=［100110110100101101000000010111001］

U*1=［100110110100101100000000010111001］將變異概率設為Pm=0.01，就是說，希望在平均水平上，種群內所有基因的1%要進行變異。在本例中，共有33×10=330個基因，希望在每一代中有3.3個變異的基因，每個基因變異的概率是相等的。因此，我們要生成一個位于［0，1］間的隨機數(shù)系列rk(k=1，2，…，330)。假設表2.2中列出的基因將進行變異。表2.2基因變異示例

基因位置染色體位置基因位數(shù)隨機數(shù)105460.0098571645320.003113199710.00094632910320.001282相對應的變量［x1,x2］的十進制值和適應度值為

f(6.159951，4.109598)=29.406122

f(6.159951，4.109598)=29.406122

f(-0.330256，4.694977)=19.763190

f(11.907206，4.873501)=5.702781

f(8.024130，4.170248)=19.91025

f(9.342067，5.11702)=17.958717

f(6.159951，4.109598)=29.406122

f(6.159951，4.109598)=29.406122

f(-2.687969，5.361653)=19.805119

f(0.474101，4.170248)=17.370896至此，完成了遺傳算法第一代操作流程。

設計終止代數(shù)為1000。在第491代，得到了最佳的染色體：

U*=［111110000000111000111101001010110］

個體隨著進化過程的進行，群體中適應度較低的一些個體被逐漸淘汰，而適應度較高的一些個體會越來越多，并且更加集中在U*附近，最終就可搜索到問題的最優(yōu)點U*。U*對應的十進制數(shù)為x1*=11.631407，x2*=5.724824，得適應度值為

eval(U*)=f(11.631407，5.724824)=38.818208

即目標函數(shù)的最大值為f(x*1,x*2)=38.818208。

2.3改進的遺傳算法

盡管遺傳算法有許多優(yōu)點，也有許多專家學者對遺傳算法進行不斷研究，但目前存在的問題依然很多，如：

（1）適應度值標定方式多種多樣，沒有一個簡潔、通用的方法，不利于遺傳算法的使用。

（2）遺傳算法的早熟現(xiàn)象（即很快收斂到局部最優(yōu)解而不是全局最優(yōu)解）是迄今為止最難處理的關鍵問題。

（3）快要接近最優(yōu)解時在最優(yōu)解附近左右擺動，收斂較慢。本節(jié)根據(jù)遺傳算法所存在的這些問題分別從適應度值函數(shù)標定和增加群體多樣性兩方面著手解決。

遺傳算法通常需要解決以下問題，如確定編碼方案，適應度函數(shù)標定，選擇遺傳操作方式及相關控制參數(shù)，停止準則確定等。相應地，為改進簡單遺傳算法的實際計算性能，很多學者的改進工作也是分別從參數(shù)編碼、初始群體設定、適應度函數(shù)標定、遺傳操作算子選擇、控制參數(shù)選擇以及遺傳算法的結構等方面提出的。自從1975年J.H.Holland系統(tǒng)提出遺傳算法的完整結構和理論以來，眾多學者一直致力于推動遺傳算法的發(fā)展，對編碼方式、控制參數(shù)的確定和交叉機理等進行了深入的研究，提出了各種變形的遺傳算法。其基本途徑概括起來主要有下面幾個方面：

(1)改進遺傳算法的組成成分或使用技術，如選用優(yōu)化控制參數(shù)、適合問題特性的編碼技術等。

(2)采用混合遺傳算法(HybridGeneticAlgorithm)。

(3)采用動態(tài)自適應技術，在進化過程中調整算法控制參數(shù)和編碼精度。

(4)采用非標準的遺傳操作算子。

(5)采用并行算法。在許多資料中都介紹了下面七種改進遺傳算法：

(1)分層遺傳算法(HierarchicGeneticAlgorithm)。

(2)CHC算法。

(3)Messy遺傳算法。

(4)自適應遺傳算法(AdaptiveGeneticAlgorithm)。

(5)基于小生境技術的遺傳算法(NichedGeneticAlgorithm，簡稱NGA)。

(6)并行遺傳算法(ParallelGeneticAlgorithm)。

(7)混合遺傳算法：

①遺傳算法與最速下降法相結合的混合遺傳算法；

②遺傳算法與模擬退火法(SimulatedAnnealing)相結合的混合遺傳算法。2.3.1改進的遺傳算法一

在改進的遺傳算法中，改進的三個算子通常是GA算法中的交叉操作，是隨機取兩個染色體進行的單點交叉操作(也可用其他的交叉操作，如多點交叉、樹交叉、部分匹配交叉等)，即在以高適應度模式為祖先的“家族”中取一點，但這種取法有其片面性。經(jīng)證明，簡單遺傳算法在任何情況下(交叉概率Pc、變異概率Pm、任意初始化、任意交叉算子、任意適應度函數(shù))都是不收斂的，即不能搜索到全局最優(yōu)解；而通過改進的遺傳算法，即在選擇作用前(或后)保留當前最優(yōu)解，則能保證收斂到全局最優(yōu)解。盡管人們證明了改進的遺傳算法最終能收斂到最優(yōu)解，但收斂到最優(yōu)解所需的時間可能是很長的。另外，早熟問題是遺傳算法中不可忽視的現(xiàn)象，其具體表現(xiàn)為：

(1)群體中所有的個體都陷于同一極值而停止進化。

(2)接近最優(yōu)解的個體總是被淘汰，進化過程不收斂。

對此可以采用以下方法來解決：

(1)動態(tài)地確定變異概率，既可防止優(yōu)良基因因為變異而遭破壞，又可在陷于局優(yōu)解時為種群引入新的基因。

(2)改進選擇方式，放棄賭輪選擇，以避免早期的高適應度個體迅速占據(jù)種群和后期的種群中因個體的適應度相差不大而導致種群停止進化；賭輪選擇方式就會使每一個個體都獲得復制一份的機會，體現(xiàn)不出好的個體的競爭力，無法實現(xiàn)遺傳算法的優(yōu)勝劣汰的原則。鑒于此，這里用一種基于種群的按個體適應度大小排序的選擇算法來代替賭輪選擇方法。其過程描述如下：

first()｛將種群中的個體按適應度大小進行排序；｝

while種群還沒有掃描完

do｛排在前面的個體復制兩份；中間的復制一份；后面的不復制；｝

擇優(yōu)交叉在解決過早收斂問題時，通常習慣于采用限制優(yōu)良個體的競爭力(高適應度個體的復制份數(shù))的方法。這樣無疑會降低算法的進化速度，增大算法的時間復雜度，降低算法的性能。由于種群的基因多樣性可以減小陷入局部最優(yōu)解的可能，而加快種群進化速度又可以提高算法的整體性能。為了解決這一對矛盾，嘗試一種在不破壞種群的基因多樣性的前提下加快種群的進化速度的方法，這一方法描述如下：在隨機選擇出父本和母本以后，按照交叉方法(單點交叉、多點交叉和一致交叉)進行ｎ次交叉，產生2n個個體，再從這2n個個體中挑選出最優(yōu)的兩個個體加入新的種群中。這樣既保存了父本和母本的基因，又在進化的過程中大大地提高了種群中個體的平均性能。

(1)在初始種群中，對所有的個體按其適應度大小進

行排序，然后計算個體的支持度和置信度；

(2)按一定的比例復制(即將當前種群中適應度最高

的兩個個體結構完整地復制到待配種群中)；

(3)按個體所處的位置確定其變異概率并變異；按

優(yōu)良個體復制4份，劣質個體不復制的原則復制個體；

(4)從復制組中隨機選擇兩個個體，對這兩個個體進行多次交叉，從所得的結果中選擇一個最優(yōu)個體存入新種群；

(5)若滿足結束條件，則停止，不然，跳轉到第(1)步，直至找到所有符合條件的規(guī)則。

該算法的優(yōu)點是在各代的每一次演化過程中，子代總是保留了父代中最好的個體，以在“高適應度模式為祖先的家族方向”搜索出更好的樣本，從而保證最終可以搜索到全局最優(yōu)解。2.3.2改進的遺傳算法二

改進的遺傳算法二的步驟如下：

(1)劃分尋優(yōu)空間。字符串中表示各個變量xi的子字符串的最高位Bnii(最左邊)可以是0或1(用b表示，下同)。據(jù)此存在一種劃分，可以把字符串劃分成對等的兩個子空間。假設有m個變量，則存在m個這種劃分方式，可以形成m對子空間，用集合表示為i=1,2,…,m;b=0,1為劃分區(qū)間，在此將個體依適應度值降序排列為

(2)設計空間退化。在演化到某一代時，如果適應值最高的前np0個(np0取群體規(guī)模的一個事先確定的比例，

這里取0.3np)個體都位于同一字符串子空間(如Abk)內：S

j

′∈Abk,

i=1,2,…,np0;b=0或1可以認為最優(yōu)點以很大概率落入Akb中，以此作為下一代的尋優(yōu)空間。對應變量為(2.12)由于在該空間內表示第i個變量的子字符串中最高位和標準遺傳算法中的最高位一樣，為提高編碼效率，提高變量表達精度，同時保證各基因位按模式定理解

釋時含義不變，將Si′中的各位基因位從左邊第二位開始，依次左移一位：j=ni-1,ni-2,…,1而最后一位由隨機數(shù)填充。為了保護最優(yōu)個體，使其在區(qū)間退化時對應變量不變，最優(yōu)個體的最后位與移動前的首位一致。由于設計空間的不斷退化，每個變量的串長ni無需太長，取4～6位即可，不影響精度。

(3)尋優(yōu)空間的移動。如果當前最優(yōu)解的某個分量xk處在當前設計空間的邊界，該變量對應的子串的各位相同，

均為0或1，則認為最優(yōu)解有可能在當前尋優(yōu)區(qū)間以外。此時，在該分量方向移動尋優(yōu)空間，以避免尋優(yōu)空間縮減而導致失去最優(yōu)解?？梢匀∫苿泳嚯x為2dk，dk為沿xk方向相

鄰兩個離散點間的距離：(2.13)移動方法是調整邊界：(2.14)

然后改變對應子串，改變方法是把該子串作為二進制數(shù)，當b=1時減2，反之加2。這樣操作保證了處在移動前后兩個空間的重疊部分的個體處在設計空間的同一位置上。當有進位或借位發(fā)生時，說明該點將被移出當前尋優(yōu)空間，略去進位或借位，就會落入新移入的那部分尋優(yōu)空間內，可以理解為隨機產生的新個體。2.3.3改進的遺傳算法三

標準遺傳算法是具有“生成+檢測”的迭代過程的搜索算法。遺傳算法采用一種群體搜索策略和群體中個體之間的信息交換、搜索，不依賴于梯度信息。但標準遺傳算法存在一些不足，下面是標準遺傳算法中存在的主要問題及解決方案。

對早熟收斂和后期搜索遲鈍的解決方案：有條件的最佳保留機制；采用遺傳—災變算法；采用適應度比例機制和個體濃度選擇機制的加權和；引入主群和屬群的概念；適應度函數(shù)動態(tài)定標；多種群并行進化及自適應調整控制參數(shù)相結合的自適應并行遺傳算法，對重要參數(shù)的選擇采用自適應變化而非固定不變。采用的具體方法如下：

(1)交叉和變異算子的改進和協(xié)調方法：

①將進化過程劃分為漸進和突變兩個不同階段；

②采用動態(tài)變異；

③運用正交設計或均勻設計方法設計新的交叉和變異算子。

(2)采用與局部搜索算法相結合的混合遺傳算法，解決局部搜索能力差的問題。

(3)采用有條件的替代父代的方法，解決單一的群體更新方式難以兼顧多樣性和收斂性的問題。

(4)收斂速度慢的解決方法：

①產生好的初始群體；

②利用小生境技術；

③使用移民技術；

④采用自適應算子；

⑤采用與局部搜索算法相結合的混合遺傳算法；

⑥對算法的參數(shù)編碼采用動態(tài)模糊控制；

⑦進行未成熟收斂判斷。

遺傳算法中包含如下5個基本要素：參數(shù)編碼、初始群體的設定、適應度函數(shù)的設計、操作設計和控制參數(shù)設定。這5個要素構成遺傳算法的核心內容。接下來將從初始群體的產生、選擇算子的改進、遺傳算法重要參數(shù)的選擇、適應度函數(shù)的選取等幾個方面對標準遺傳算法進行改進。

1.初始群體的產生

初始群體的特性對計算結果和計算效率均有重要影響。要實現(xiàn)全局最優(yōu)解，初始群體在解空間中應盡量分散。標準遺傳算法是按預定或隨機方法產生一組初始解群體，這樣可能導致初始解群體在解空間分布不均勻，從而影響算法的性能。要得到一個好的初始群體，可以將一些實驗設計方法，如均勻設計或正交設計與遺傳算法相結合。其原理為：首先根據(jù)所給出的問題構造均勻數(shù)組或正交數(shù)組，然后執(zhí)行如下算法產生初始群體：

(1)將解空間劃分為S個子空間；

(2)量化每個子空間，運用均勻數(shù)組或正交數(shù)組選擇M個染色體；

(3)從M×S個染色體中，選擇適應度函數(shù)最大的N個作為初始群體。

這樣可保證初始群體在解空間均勻分布。

另外，初始群體的各個個體之間應保持一定的距離，并定義相同長度的以某一常數(shù)為基的兩個字符串中對應位不同的數(shù)量為兩者間的廣義海明距離。要求入選群體的所有個體之間的廣義海明距離必須大于或等于某個設定值。初始群體采用這種方法產生能保證隨機產生的各個個體間有較明顯的差別，使它們能均勻分布在解空間中，從而增加獲取全局最優(yōu)解的可能。

2.選擇算子的改進

在標準遺傳算法中，常根據(jù)個體的適應度大小采用“賭輪選擇”策略。該策略雖然簡單，但容易引起“早熟收斂”和“搜索遲鈍”問題。有效的解決方法是采用有條件的最佳保留策略，即有條件地將最佳個體直接傳遞到下一代或至少等同于前一代，這樣能有效防止“早熟收斂”。

也可以使用遺傳—災變算法，即在遺傳算法的基礎上，模擬自然界的災變現(xiàn)象，提高遺傳算法的性能。當判斷連續(xù)數(shù)代最佳染色體沒有任何進化，或者各個染色體已過于近似時，即可實施災變。災變的方法很多，可以突然增大變異概率或對不同個體實施不同規(guī)模的突變，以產生不同數(shù)目的大量后代等。用災變的方法可以打破原有基因的壟斷優(yōu)勢，增加基因的多樣性，創(chuàng)造有生命力的新個體。

3.遺傳算法重要參數(shù)的選擇

遺傳算法中需要選擇的參數(shù)主要有：染色體長度l、群體規(guī)模n、交叉概率Pc和變異概率Pm等，這些參數(shù)對遺傳算法的性能影響也很大。染色體長度的選擇對二進制編碼來說取決于特定問題的精度，存在定長和變長兩種方式。群體規(guī)模通常取20～200。一般來說，求解問題的非線性越大，n的選擇就應該越大。交叉操作和變異操作是遺傳算法中兩個起重要作用的算子。通過交叉和變異，一對相互配合又相互競爭的算子使其搜索能力得到飛速提高。交叉操作的作用是組合交叉兩個個體中有價值的信息產生新的后代，它在群體進化期間大大加快了搜索速度；變異操作的作用是保持群體中基因的多樣性，偶然、次要的(交叉率取很小)起輔助作用。在遺傳算法的計算過程中，根據(jù)個體的具體情況，自適應地改變Pc、Pm的大小，將進化過程分為漸進和突變兩個不同階段：漸進階段強交叉，弱變異，強化優(yōu)勢型選擇算子；突變階段弱交叉，強變異，弱化優(yōu)勢型選擇算子。這樣對提高算法的計算速度和效率是有利的。自適應參數(shù)調整方案如下：(2.15)式中，fmax為某代中最優(yōu)個體適應度，f為此代平均適應度。

4.適應度函數(shù)的設計

遺傳算法中采用適應度函數(shù)值來評估個體性能并指導搜索，基本不用搜索空間的知識，因此，適應度函數(shù)的選取相當重要。性能不良的適應度函數(shù)往往會導致“騙”問題。適應度函數(shù)的選取標準是：規(guī)范性（單值、連續(xù)、嚴格單調）、合理性（計算量?。?、通用性。VasiliesRetridis提出在解約束優(yōu)化問題時采用變化的適應度函數(shù)的方案。將問題的約束以動態(tài)方式合并到適應度函數(shù)中，即形成一個具有變化的懲罰項的適應度函數(shù)，用來指導遺傳搜索。在那些具有許多約束條件而產生的一個復雜搜索超平面的問題中，該方案能明顯地以較大的概率找到全局最優(yōu)解。

5.進化過程中動態(tài)調整子代個體

遺傳算法要求在進行過程中保持群體規(guī)模不變。但為了防止早熟收斂，在進化過程可對群體中的個體進行調整，包括引入移民算子、過濾相似個體、動態(tài)補充子代新個體等。

移民算子是避免早熟的一種好方法。在移民的過程中不僅可以加速淘汰差的個體，而且可以增加解的多樣性。所謂的移民機制，就是在每一代進化過程中以一定的淘汰率(一般取15%～20%)將最差個體淘汰，然后用產生的新個體代替。為了加快收斂速度，可采用過濾相似個體的操作，減少基因的單一性。刪除相似個體的過濾操作為：對子代個體按適應度排序，依次計算適應度差值小于門限delta的相似個體間的廣義海明距離(相同長度的以a為基的兩個字符串中對應位不相同的數(shù)量稱為兩者間的廣義海明距離)。如果同時滿足適應度差值小于門限delta，廣義海明距離小于門限d，就過濾掉其中適應度較小的個體。delta、d應適當選取，以提高群體的多樣性。過濾操作后，需要引入新個體。從實驗測試中發(fā)現(xiàn)，如果采用直接隨機生成的方式產生新個體，適應度值都太低，而且對算法的全局搜索性能增加并不顯著(例如，對于復雜的多峰函數(shù)很難跳出局部最優(yōu)點)。

因此，可使用從優(yōu)秀的父代個體中變異產生的方法。該方法將父代中適應度較高的m個個體隨機進行若干次變異，產生出新個體，加入子代對個體中。這些新個體繼承了父代較優(yōu)個體的模式片斷，并產生新的模式，易于與其他個體結合生成新的較優(yōu)子代個體。而且增加的新個體的個數(shù)與

過濾操作刪除的數(shù)量有關。如果群體基因單一性增加，則被濾除的相似個體數(shù)目增加，補充的新個體數(shù)目隨之增加；反之，則只少量濾除相似個體，甚至不濾除，補充的新個體數(shù)目也隨之減少。這樣，就能動態(tài)解決群體由于缺乏多樣性而陷入局部解的問題。

6.小范圍競爭擇優(yōu)的交叉、變異操作

從加快收斂速度、全局搜索性能兩方面考慮，受自然界中家庭內兄弟間競爭現(xiàn)象的啟發(fā)，加入小范圍競爭、擇優(yōu)操作。其方法是，將某一對父母A、B進行n次(3～5次)交叉、變異操作，生成2n個不同的個體，選出其中一個最高適應度的個體，送入子代個體對中。反復隨機選擇父母對，直到生成設定個數(shù)的子代個體為止。這種方法實質是在相同父母的情況下，預先加入兄弟間的小范圍的競爭擇優(yōu)機制。另一方面，在標準遺傳算法中，一對父母X、Y經(jīng)遺傳算法操作后產生一對子代個體xy1、xy2、x1y、x2y，隨后都被放入子代對個體，當進行新一輪遺傳操作時，xy1、x1y可能作為新的父母對進行交叉配對，即“近親繁殖”。而加入小范圍競爭擇優(yōu)的交叉、變異操作，減少了在下一代中出現(xiàn)這一問題的幾率。2.3.4改進的遺傳算法四

1.適應度值標定

初始群體中可能存在特殊個體的適應度值超常（如很大）。為了防止其統(tǒng)治整個群體并誤導群體的發(fā)展方向而使算法收斂于局部最優(yōu)解，需限制其繁殖。在計算臨近結束，遺傳算法逐漸收斂時，由于群體中個體適應度值比較接近，繼續(xù)優(yōu)化選擇較為困難，造成在最優(yōu)解附近左右搖擺。此時應將個體適應度值加以放大，以提高選擇能力，這就是適應度值的標定。針對適應度值標定問題提出以下計算公式：(2.16)式中，f′為標定后的適應度值，f為原適應度值，fmax為適應度函數(shù)值的一個上界，fmin為適應度函數(shù)值的一個下界，δ為開區(qū)間（0，1）內的一個正實數(shù)。

若fmax未知，可用當前代或目前為止的群體中的最大值來代替。若fmin未知，可用當前代或目前為止群體中的最小值來代替。取δ的目的是防止分母為零和增加遺傳算法的隨機性。|fmin|是為了保證標定后的適應度值不出現(xiàn)負數(shù)。

由圖2.8可見，若fmax與fmin差值越大，則角度α越小，即標定后的適應度值變化范圍小，防止超常個體統(tǒng)治整個群體；反之則越大，標定后的適應度值變化范圍增大，拉開群體中個體之間的差距，避免算法在最優(yōu)解附近擺動現(xiàn)象發(fā)生。這樣就可以根據(jù)群體適應度值放大或縮小，變更選擇壓力。

2.群體多樣化

遺傳算法在求解具有多個極值點的函數(shù)時，存在一個致命的弱點——早熟，即收斂到局部最優(yōu)解而非全局最優(yōu)解，這也是遺傳算法最難解決的一個問題。遺傳算法的早熟原因是交叉算子在搜索過程中存在著嚴重的成熟化效應。在起搜索作用的同時，不可避免的是群體多樣化逐漸趨于零，從而逐漸減少了搜索范圍，引起過早收斂。圖2.9多極值函數(shù)為了解決這一問題，人們研究出很多方法：元算法、自適應遺傳算法（AGA）、改進的自適應遺傳算法（MAGA）等?？梢?，避免遺傳算法早熟的關鍵是使群體呈多樣化發(fā)展，也就是應使搜索點分布在各極值點所在的區(qū)域，如圖2.9所示的xi。

簡單遺傳算法在進行優(yōu)化計算時不是全局收斂。只有保證最優(yōu)個體復制到下一代，才能保證其收斂性，也就是說，盡管遺傳算法的基本作用對象是多個可行解且隱并行操作，仍然需要對其進行適當改進。為了增加群體的多樣性，有效地避免早熟現(xiàn)象發(fā)生，引入了相似度的概念。

定義2.1在遺傳算法進行選擇運算前，對群體中每兩個個體逐位比較。如果兩個個體中在相對應的位置上存在著相同的字符（基因），則將相同字符數(shù)量定義為相似度R。

設置值T=適應度平均值，在群體中取大于T的個體進行個體相似程度判斷。相似度低則表示這兩個個體相似性差，當相似度值R超過個體長度L/2時，即認為這兩個個體相似，如1011001和1101001的相似度值R=5，L=7，R＞L/2，所以可以認為這兩個個體具有相似性。相似性的判斷實際上是確定群體中個體是否含有相同模式。濾除相似個體，選擇不同模式的個體組成新的群體，可以增加群體的多樣性，尤其是在計算初期，經(jīng)過相似性判斷后，能夠有效避免早熟問題的產生。由此得出的改進遺傳算法的步驟如下：圖2.10“改進的遺傳算法四”的程序流程圖（1）個體按適應度值大小排序。

（2）求平均適應度值，以此作為閾值，選擇適應度值大于平均適應度值的個體。

（3）判斷相似程度，以最高適應度值為模板，去除相似個體。

（4）重復第（3）步，逐次以適應度值高的個體為模板，選擇不同模板的個體組成群體。

（5）判斷是否達到群體規(guī)模。如果是，則進行下一步交叉、變異等遺傳操作；否則重復第（4）步。如果不能得到足夠的群體規(guī)模，則濾除的個體按適應度值大小順序順次補足群體所缺數(shù)量。

（6）判斷是否滿足結束要求。如果是，則結束，否則轉到（1）。為了避免過早陷入局部最優(yōu)解，必須拓寬搜索空間，增加群體多樣性。取平均適應度值作為閾值并以高于閾值的個體作為模板進行選擇，有效鼓勵高適應度值個體的競爭力。這樣的處理，主要是為了增加群體的多樣性和高適應度值的個體的主導地位，避免統(tǒng)一模式統(tǒng)治群體，從而誤導搜索方向。當接近最優(yōu)解時，由上面的運算步驟可以盡快收斂到最優(yōu)解。這樣既不增加群體規(guī)模，避免運算時間過長，還能保證收斂到全局最優(yōu)解。

圖2.10所示為“改進的遺傳算法四”的程序流程圖。圖2.10“改進的遺傳算法四”的程序流程圖

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

2.4.1多目標優(yōu)化的概念

解決含多目標和多約束的優(yōu)化問題稱為多目標優(yōu)化(MultiobjectiveOpimization)問題。在實際應用中，工程優(yōu)化問題大多數(shù)是多目標優(yōu)化問題，有時需要使多個目標在給定區(qū)域上都可能地達到最優(yōu)的問題，目標之間一般都是互相沖突的。例如投資問題，一般我們都是希望所投入的資金量最少，風險最小，并且所獲得的收益最大。這種多于一個的數(shù)值目標的最優(yōu)化問題就是多目標優(yōu)化問題。多目標優(yōu)化問題一般的數(shù)學模型可描述為(2.17)式中，V-min表示向量極小化，即向量目標函數(shù)f(x)=［f

1(x),f2(x),…,fn(x)］T中的各個子目標函數(shù)都盡可能地達到極小化。

定義2.2設X

Rm是多目標優(yōu)化模型的約束集，f(x)∈Rn是多目標優(yōu)化時的向量目標函數(shù)，有x1∈X，x2∈X。若fk(x1)≤fk(x2),(2.18)并且fk(x1)≤fk(x2),(2.19)則稱解x1比解x2優(yōu)越