《MATLAB遺傳算法工具箱及應(yīng)用》課件第2章

第二章基本遺傳算法及改進(jìn) 2.1遺傳算法的運(yùn)行過程

2.1.1完整的遺傳算法運(yùn)算流程

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

完整的遺傳算法運(yùn)算流程可以用圖2.2來描述。

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

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

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

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

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

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

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

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

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

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

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遺傳算法的基本操作

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

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

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

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

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

基本遺傳算法可表示為

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

式中：C——個(gè)體的編碼方法；

E——個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)；

P0——初始種群；

M——種群大?。?/p>

Φ——選擇算子；

Γ——交叉算子；

Ψ——變異算子；

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

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

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

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

111111…1111=2k-1→U2

...其中，

(2)解碼：假設(shè)某一個(gè)體的編碼為bkbk-1bk-2…b2b1，則對(duì)應(yīng)的解碼公式為例如：設(shè)有參數(shù)X∈［2,4］，現(xiàn)用5位二進(jìn)制編碼對(duì)X進(jìn)行編碼，得25=32個(gè)二進(jìn)制串(染色體)：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對(duì)于任一個(gè)二進(jìn)制串，只要代入公式(2.2)，就可得到對(duì)應(yīng)的解碼，如x22=10101，它對(duì)應(yīng)的十進(jìn)制數(shù)為

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

的值為2+21×=3.3548。

2.個(gè)體適應(yīng)度的檢測(cè)評(píng)估

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

3.遺傳算子

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第四步，確定解碼方法。

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

U1=［000001010100101001101111011111110］

U2=［001110101110011000000010101001000］

U3=［111000111000001000010101001000110］

U4=［100110110100101101000000010111001］

U5=［000010111101100010001110001101000］

U6=［111110101011011000000010110011001］

U7=［110100010011111000100110011101101］

U8=［001011010100001100010110011001100］

U9=［111110001011101100011101000111101］

U10=［111101001110101010000010101101010］相對(duì)應(yīng)的十進(jìn)制的實(shí)際值為

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］

第五步，確定個(gè)體評(píng)價(jià)方法。

對(duì)一個(gè)染色體串的適應(yīng)度評(píng)價(jià)由下列三個(gè)步驟組成：

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

(2)評(píng)價(jià)目標(biāo)函數(shù)f(xk)。

(3)將目標(biāo)函數(shù)值轉(zhuǎn)為適應(yīng)度。對(duì)于極大值問題，適應(yīng)度就等于目標(biāo)函數(shù)值，即eval(Uk)=f(xk),

k=1,2,…(2.7)在遺傳算法中，評(píng)價(jià)函數(shù)起著自然進(jìn)化中環(huán)境的角色，它通過染色體的適應(yīng)度對(duì)其進(jìn)行評(píng)價(jià)。上述染色體的適應(yīng)度值如下：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è)計(jì)遺傳算子和確定遺傳算法的運(yùn)行參數(shù)。

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

以概率的大小來構(gòu)造新的種群，其步驟如下：

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

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

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

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

那么，本例中種群的適應(yīng)度總和為對(duì)應(yīng)于每個(gè)染色體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

對(duì)應(yīng)于每個(gè)染色體Uk(k=1，2，…，10)的累計(jì)概率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)在，我們轉(zhuǎn)動(dòng)輪盤10次，每次選擇一個(gè)新種群中的染色體。假設(shè)這10次中生成的［0，1］間的隨機(jī)數(shù)如下：

0.301431

0.322062

0.766503

0.881893

0.350871

0.583392

0.1776180.343242

0.032685

0.197577

第一個(gè)隨機(jī)數(shù)r1=0.301431大于Q3，小于Q4，這樣染色體U4被選中；第二個(gè)隨機(jī)數(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)交叉運(yùn)算使用單點(diǎn)交叉算子。

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

U1=［100110110100101101000000010111001］

U2=［001011010100001100010110011001100］

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

開始

k←0；

當(dāng)k≤10時(shí)繼續(xù)

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

如果rk＜0.25，則

選擇Uk為交叉的一個(gè)父輩；

結(jié)束

k←k+1；

結(jié)束

結(jié)束假設(shè)隨機(jī)數(shù)如下：

0.6257210.2668230.288644

0.295114

0.163274

0.5674610.0859400.3928650.770714

0.548656

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

U5=［100110110100101101000000010111001］

U7=［001110101110011000000010101001000］

U*5=［101110101110011000000010101001000］

U*7=［000110110100101101000000010111001］

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

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

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

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

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è)計(jì)終止代數(shù)為1000。在第491代，得到了最佳的染色體：

U*=［111110000000111000111101001010110］

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

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

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

2.3改進(jìn)的遺傳算法

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

（1）適應(yīng)度值標(biāo)定方式多種多樣，沒有一個(gè)簡(jiǎn)潔、通用的方法，不利于遺傳算法的使用。

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

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

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

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

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

(3)采用動(dòng)態(tài)自適應(yīng)技術(shù)，在進(jìn)化過程中調(diào)整算法控制參數(shù)和編碼精度。

(4)采用非標(biāo)準(zhǔn)的遺傳操作算子。

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

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

(2)CHC算法。

(3)Messy遺傳算法。

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

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

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

(7)混合遺傳算法：

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

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

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

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

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

對(duì)此可以采用以下方法來解決：

(1)動(dòng)態(tài)地確定變異概率，既可防止優(yōu)良基因因?yàn)樽儺惗馄茐?，又可在陷于局?yōu)解時(shí)為種群引入新的基因。

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

first()｛將種群中的個(gè)體按適應(yīng)度大小進(jìn)行排序；｝

while種群還沒有掃描完

do｛排在前面的個(gè)體復(fù)制兩份；中間的復(fù)制一份；后面的不復(fù)制；｝

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

(1)在初始種群中，對(duì)所有的個(gè)體按其適應(yīng)度大小進(jìn)

行排序，然后計(jì)算個(gè)體的支持度和置信度；

(2)按一定的比例復(fù)制(即將當(dāng)前種群中適應(yīng)度最高

的兩個(gè)個(gè)體結(jié)構(gòu)完整地復(fù)制到待配種群中)；

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

優(yōu)良個(gè)體復(fù)制4份，劣質(zhì)個(gè)體不復(fù)制的原則復(fù)制個(gè)體；

(4)從復(fù)制組中隨機(jī)選擇兩個(gè)個(gè)體，對(duì)這兩個(gè)個(gè)體進(jìn)行多次交叉，從所得的結(jié)果中選擇一個(gè)最優(yōu)個(gè)體存入新種群；

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

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

改進(jìn)的遺傳算法二的步驟如下：

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

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

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

j

′∈Abk,

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

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

(3)尋優(yōu)空間的移動(dòng)。如果當(dāng)前最優(yōu)解的某個(gè)分量xk處在當(dāng)前設(shè)計(jì)空間的邊界，該變量對(duì)應(yīng)的子串的各位相同，

均為0或1，則認(rèn)為最優(yōu)解有可能在當(dāng)前尋優(yōu)區(qū)間以外。此時(shí)，在該分量方向移動(dòng)尋優(yōu)空間，以避免尋優(yōu)空間縮減而導(dǎo)致失去最優(yōu)解?？梢匀∫苿?dòng)距離為2dk，dk為沿xk方向相

鄰兩個(gè)離散點(diǎn)間的距離：(2.13)移動(dòng)方法是調(diào)整邊界：(2.14)

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

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

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

(1)交叉和變異算子的改進(jìn)和協(xié)調(diào)方法：

①將進(jìn)化過程劃分為漸進(jìn)和突變兩個(gè)不同階段；

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

③運(yùn)用正交設(shè)計(jì)或均勻設(shè)計(jì)方法設(shè)計(jì)新的交叉和變異算子。

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

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

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

①產(chǎn)生好的初始群體；

②利用小生境技術(shù)；

③使用移民技術(shù)；

④采用自適應(yīng)算子；

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

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

⑦進(jìn)行未成熟收斂判斷。

遺傳算法中包含如下5個(gè)基本要素：參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、操作設(shè)計(jì)和控制參數(shù)設(shè)定。這5個(gè)要素構(gòu)成遺傳算法的核心內(nèi)容。接下來將從初始群體的產(chǎn)生、選擇算子的改進(jìn)、遺傳算法重要參數(shù)的選擇、適應(yīng)度函數(shù)的選取等幾個(gè)方面對(duì)標(biāo)準(zhǔn)遺傳算法進(jìn)行改進(jìn)。

1.初始群體的產(chǎn)生

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

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

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

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

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

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

2.選擇算子的改進(jìn)

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

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

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

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

4.適應(yīng)度函數(shù)的設(shè)計(jì)

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

5.進(jìn)化過程中動(dòng)態(tài)調(diào)整子代個(gè)體

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

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

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

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

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

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

1.適應(yīng)度值標(biāo)定

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

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

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

2.群體多樣化

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

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

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

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

（2）求平均適應(yīng)度值，以此作為閾值，選擇適應(yīng)度值大于平均適應(yīng)度值的個(gè)體。

（3）判斷相似程度，以最高適應(yīng)度值為模板，去除相似個(gè)體。

（4）重復(fù)第（3）步，逐次以適應(yīng)度值高的個(gè)體為模板，選擇不同模板的個(gè)體組成群體。

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

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

圖2.10所示為“改進(jìn)的遺傳算法四”的程序流程圖。圖2.10“改進(jìn)的遺傳算法四”的程序流程圖

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

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

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

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

定義2.2設(shè)X

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