遺傳算法的實現(xiàn)技術(shù)

第9章遺傳算法的實現(xiàn)技術(shù)

80年代以后，遺傳算法得到了廣泛的使用，在實踐過程中，人們對遺傳算法的實施提出了許多改進。本節(jié)分別予以介紹。

9.1編碼方法

[編碼的重要性]

編碼是應(yīng)用遺傳算法時要解決的首要問題，也是設(shè)計遺傳算法的一個關(guān)鍵步驟。

?編碼方法除了決定個體的染色體排列形式之外，它還決定了個體從搜索空間的基因型變換到解空間的表現(xiàn)型時的解碼方法;

?

編碼方法也影響到交叉算子、變異算子等遺傳算子的運算方法。由此可見，編碼方法在很大程度上決定了如何進行群體的遺傳進化運算以及遺傳進化運算的效率。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第1頁![編碼原則]

針對一個具體應(yīng)用問題，如何設(shè)計一種完美的編碼方案一直是遺傳算法的應(yīng)用難點之一，也是遺傳算法的一個重要研究方向?？梢哉f目前還沒有一套既嚴(yán)密又完整的指導(dǎo)理論及評價準(zhǔn)則能夠幫助我們設(shè)計編碼方案。作為參考，DeJong

曾提出了兩條操作性較強的實用編碼原則(又稱為編碼規(guī)則)：

?編碼原則一(有意義積木塊編碼原則)：應(yīng)使用能易于產(chǎn)生與所求問題相關(guān)的且具有低階、短定義長度模式的編碼方案。

?編碼原則二(最小字符集編碼原則)：應(yīng)使用能使問題得到自然表示或描述的具有最小編碼字符集的編碼方案。

由于遺傳算法應(yīng)用的廣泛性，迄今為止人們已經(jīng)提出了許多種不同的編碼方法?？偟膩碚f，這些編碼方法可以分為三大類：

二進制編碼方法浮點數(shù)編碼方法符號編碼方法遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第2頁!

9.1.1二進制編碼方法二進制編碼方法是遺傳算法中最常用的一種編碼方法，它使用的編碼符號集是由二進制符號0和1所組成的二值符號集{0，1}，它所構(gòu)成的個體基因型是一個二進制編碼符號串。

(1)編碼假設(shè)某一參數(shù)的取值范圍是[umax,umin]，我們用長度為l的二進制編碼符號串來表示該參數(shù)，則它總共能夠產(chǎn)生2l種不同的編碼，參數(shù)編碼時的對應(yīng)關(guān)系如下：

00000000…00000000＝0umin

00000000…00000001＝1umin+……11111111…11111111=2l–1umax

二進制編碼的編碼精度為：=Umax

umin2l

1遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第3頁!(2)解碼

假設(shè)某一個體的編碼是：

x：blbl-1bl-2……b2b1

則對應(yīng)的解碼公式為：

例如，對于x[0,1023]，若用10位長的二進制編碼表示該參數(shù)的話，則下述符號串：

x：0010101111就可表示一個個體，它所對應(yīng)的參數(shù)值是x＝175。編碼精度為

=1。

x=umin+(

bi·2i-1)

·

1i=lUmax

umin2l

1遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第4頁!9.1.2格雷碼編碼方法

格雷碼編碼方法是二進制編碼方法的一種變形。

(1)格雷碼編碼：其連續(xù)的兩個整數(shù)所對應(yīng)的編碼值之間僅僅只有一個碼位是不相同的，其余碼位都完全相同。如圖所示。

(2)優(yōu)點：

?便于提高遺傳算法的局部搜索能力；

?交叉、變異等遺傳操作便于實現(xiàn)；

?符合最小字符集編碼原則；

?便于利用模式定理對算法進行理論分析。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第5頁!9.1.3浮點數(shù)編碼方法

(1)二進制編碼的缺點

?二進制編碼存在著連續(xù)函數(shù)離散化時的映射誤差。個體編碼串的長度較短時，可能達(dá)不到精度要求；個體編碼串的長度較長時，雖然能提高編碼精度，但卻會使遺傳算法的搜索空間急劇擴大。

?二進制編碼不便于反映所求問題的特定知識，這樣也就不便于開發(fā)針對問題專門知識的遺傳運算算子，人們在一些經(jīng)典優(yōu)化算法的研究中所總結(jié)出的一些寶貴經(jīng)驗也就無法在這里加以利用，也不便于處理非平凡約束條件。

(2)浮點數(shù)編碼方法個體的每個基因值用某一范圍內(nèi)的一個浮點數(shù)來表示；個體的編碼長度等于其決策變量的個數(shù)。因為這種編碼方法使用的是決策變量的真實值，所以浮點數(shù)編碼方法也叫做真值編碼方法。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第6頁!(4)浮點數(shù)編碼方法的優(yōu)點：

?適合于在遺傳算法中表示范圍較大的數(shù)；

?適合于精度要求較高的遺傳算法；

?便于較大空間的遺傳搜索；

?改善了遺傳算法的計算復(fù)雜性，提高了運算效率；

?便于遺傳算法與經(jīng)典優(yōu)化方法的混合使用；

?便于設(shè)計針對問題的專門知識的知識型遺傳算子；

?便于處理復(fù)雜的決策變量約束條件。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第7頁!

(2)符號編碼的主要優(yōu)點：

?符合有意義積木塊編碼原則。

?便于在遺傳算法中利用所求解問題的專門知識。

?便于遺傳算法與相關(guān)近似算法之間的混合使用。但對于使用符號編碼方法的遺傳算法，一般需要認(rèn)真設(shè)計交叉、變異等遺傳運算的操作方法，以滿足問題的各種約束要求，這樣才能提高算法的搜索性能。9.1.5多參數(shù)級聯(lián)編碼方法9.1.5多參數(shù)交叉編碼方法遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第8頁!?對于求最小值問題，變換如下：F(X)=Cmax-f(X)

iff(X)Cmax0

iff(X)

Cmax9.2.2適應(yīng)度尺度變換

(1)適應(yīng)度尺度變換的原因在遺傳算法中，各個個體被遺傳到下一代群體中的概率是由該個體的適應(yīng)度來確定的，應(yīng)用實踐表明，僅使用以上兩式來計算個體適應(yīng)度時，有些遺傳算法會收斂得很快，也有些遺傳算法會收斂得很慢。

?

在遺傳算法運行的初期階段

群體中可能會有少數(shù)幾個個體的適應(yīng)度相對其他個體來說非常高。若按照常用的比例選擇算子來確定個體的遺傳數(shù)量時，則這幾個相對較好的個體將在下一代群體中占有很高的比例，在極端情況下或當(dāng)群體現(xiàn)模較小時，新的群體甚至完全由這樣的少數(shù)幾個個體所組成。這時產(chǎn)生新個體作用較大的交叉算子就起不了什么作用，因為相同的兩個個體不論在何處進行交叉操作都永遠(yuǎn)不會產(chǎn)生出新的個體，如下所示：遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第9頁!(2)適應(yīng)度尺度變換定義在遺傳算法運行的不同階段，有時需要對個體的適應(yīng)度進行適當(dāng)?shù)臄U大或縮小。這種對個體適應(yīng)度所做的擴大或縮小變換就稱為適應(yīng)度尺度變換。(3)適應(yīng)度尺度變換方法目前常用的個體適應(yīng)度尺度變換方法主要有三種：線性尺度變換、乘冪尺度變換和指數(shù)尺度變換。

Ⅰ.線性尺度變換。線性尺度變換的公式如下:F’=aF+b

式中F——原適應(yīng)度；

F’——變換后的新適應(yīng)度；

a,b——系數(shù)。系數(shù)a,b直接影響到這個尺度變換的大小，所以對其選取有一定的要求，一般希望它們滿足下面兩個條件:遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第10頁!遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第11頁!

綜上所述，參數(shù)a,b的計算方法如下：

(1)計算適應(yīng)度非負(fù)判別式：Fmin>C·Favg-FmaxC-1

若不等式滿足，則執(zhí)行(2)，否則執(zhí)行(3)。

(2)正常情況下的縮放：C-1a

=Fmax-FavgFavgFmax-C·Favgb

=Fmax-FavgFavg(3)負(fù)適應(yīng)度時的縮放：a

=FavgFavg-Fminb

=Favg·FminFavg-Fmin遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第12頁!9.2.3約束條件的處理方法實際應(yīng)用中的優(yōu)化問題一般都含有一定的約束條件，它們的描述形式各種各樣。在遺傳算法的應(yīng)用中，必須對這些約束條件進行處理，而目前還未找到一種能夠處理各種約束條件的一般化方法。所以對約束條件進行處理時，只能是針對具體應(yīng)用問題及約束條件的特征，再考慮遺傳算法中遺傳算子的運行能力，選用不同的處理方法。在構(gòu)造遺傳算法時，處理約束條件的常用方法主要有如下三種：

搜索空間限定法罰函數(shù)法可行解變換法

(1)搜索空間限定法

[基本思想]

對遺傳算法的搜索空間的大小加以限制，使得搜索空間中表示一個個體的點與解空間中表示一個可行解的點有一一對應(yīng)的關(guān)系。此時的搜索空間與解空間的對應(yīng)關(guān)系如圖所示。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第13頁!

[對一些比較簡單的約束條件(如a<x＜b之類)]

在個體染色體的編碼方法上著手，就能夠達(dá)到這種搜索空間與解空間之間的對應(yīng)的要求。

?用這種處理方法能夠在遺傳算法中設(shè)置最小的搜索空間，所以它能夠提高遺傳算法的搜索效率。

?但需要注意的是：除了在編碼方法上想辦法之外，也必須保證經(jīng)過交叉、變異等遺傳其子作用之后所產(chǎn)生出的新個體在解空間中也要有確定的對應(yīng)解，而不會產(chǎn)生無效解。

[處理方法]

方法一：用編碼方法來保證總是能夠產(chǎn)生出在解空間中有對應(yīng)可行解的染色體。這個實現(xiàn)方法要求我們設(shè)計出一種比較好的個體編碼方案。如前面我們講到的二進制編碼方案即可實現(xiàn)上述要求。方法二：用程序來保證直到產(chǎn)生出在解空間中有對應(yīng)可行解的染色體之前，一直進行交叉運算和變異運算。雖然這個實現(xiàn)方法對編碼方法的要求不高，但它有可能需要反復(fù)地進行交叉運算和變異運算才能產(chǎn)生出一個滿足約束條件的可行解，這樣就有可能會降低遺傳算法的運行效率。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第14頁!max

式中——懲罰函數(shù)；

——懲罰系數(shù)。

Ⅰ.最簡單的懲罰函數(shù)形式是平方法，即：Ⅱ.也有人建議采用松緊法。在遺傳算法初期，懲罰輕一些；到了后期，則懲罰重一些。具體的新目標(biāo)函數(shù)F為：加入罰函數(shù)后，原來的問題變?yōu)橄率鲆粋€新的目標(biāo)函數(shù)：遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第15頁!(3)可行解變換法

[基本思想]

在由個體基因型到個體表現(xiàn)型的變換中，增加使其滿足約束條件的處理過程。即尋找出一種個體基因型和個體表現(xiàn)型之間的多對一的變換關(guān)系，使進化過程中所產(chǎn)生的個體總能夠通過這個變換而轉(zhuǎn)化成解空間中滿足約束條件的一個可行解。下圖為該方法的示意圖。

[優(yōu)劣]

這種處理方法雖然對個體的編碼方法、交叉運算、變異運算等沒有附加的要求，但它卻是以擴大搜索空間為代價的，所以一般會使得遺傳算法的運行效率有所下降。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第16頁!

[特點]

適應(yīng)度越高的個體被選中的概率也越大，適應(yīng)度越低的個體被選中的概率也越小。

[缺點]

由于是隨機操作的原因，這種選擇方法的選擇誤差比較大，有時甚至連適應(yīng)度較高的個體也選擇不上。9.3.2分級選擇(rankingselecton)（或稱排序選擇）

(1)產(chǎn)生原因遺傳算法中個體適應(yīng)度數(shù)值上的差別有時會很大，尤其是在算法的早期這種差別更是懸殊。因此，個別特優(yōu)個體會多次被選中進行復(fù)制，經(jīng)過幾代后它們在群體中數(shù)目愈來愈多，沖淡了群體的多樣性。因此，人們提出分級的概念，用連續(xù)漸變的分級代替數(shù)值懸殊的適應(yīng)度。

(2)方法

?設(shè)群體中有m個個體，將它們按降序方法依次排序，規(guī)定個體優(yōu)劣的等級依次為：1，2，3，…，i，…，M。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第17頁!下面按兩種情況討論：

Ⅰ.所有個體按相同概率選取，即d=0，得：

q=1/MⅡ.令最壞（最后）個體的的選取概率為0，即q–(M-1)d=0，帶入①式，得：

q=2/M

于是，q可在這兩種極端情況下選取，即：

1/M≤q≤2/M

有了q，由①式，可得：(3)優(yōu)缺點優(yōu)點：消除個體適應(yīng)度差別懸殊時的影響，代替適應(yīng)度的縮放技術(shù)。缺點：抹殺個體適應(yīng)度的實際差別，未能充分運用遺傳信息。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第18頁!9.3.4最優(yōu)保存策略（Elitistselection)

在遺傳算法的運行過程中．通過對個體進行交叉、變異等遺傳操作而不斷地產(chǎn)生出新的個體。雖然隨著群體的進化過程會產(chǎn)生出越來越多的優(yōu)良個體，但由于選擇、交叉、變異等遺傳操作的隨機性，它們也有可能破壞掉當(dāng)前群體中適應(yīng)度最好的個體。我們希望適應(yīng)度最好的個體要盡可能地保留到下一代群體中。為達(dá)到這個目的，可以使用最優(yōu)保存策略進化模型來進行優(yōu)勝劣汰操作。

(1)基本思想當(dāng)前群體中適應(yīng)度最高的個體不參與交叉運算和變異運算，而是用它來替換掉本代群體中經(jīng)過交叉、變異等遺傳操作后所產(chǎn)生的適應(yīng)度最低的個體。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第19頁!9.3.5確定式采樣選擇(DeterministicSamplingselection)

(1)基本思想：按照一種確定的方式來進行選擇操作

(2)具體操作過程：

Ⅰ.

計算群體中各個個體在下一代群體中的期望生存數(shù)目Ni：

Ⅱ.

用Ni

的整數(shù)部分Ni確定各個對應(yīng)個體在下一代群體中的生存數(shù)目

(x表示下取值，取不大于x的最大整數(shù)。)

Ⅲ.按照Ni的小數(shù)部分對個體進行降序排序，順序取前M個個體加入到下一代群體中。至此可完全確定出下一代群體中的M個個體。

(3)特點：這種選擇操作方法可保證適應(yīng)度較大的一些個體一定能夠被保留在下一代群體中，并且操作也比較簡單。MNii=1i=1,2,…M遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第20頁!

9.4.1單點交叉(One-pointCrossover)

(1)單點交叉：又稱為簡單交叉，它是指在個體編碼串中只隨機設(shè)置一個交叉點，然后在該點相互交換兩個配對個體的部分染色體。

(2)特點：若鄰接基因座之間的關(guān)系能提供較好的個體性狀和較高的個體適應(yīng)度的話，則這種單點交叉操作破壞這種個體性狀和降低個體適應(yīng)度的可能性最小。9.4.2雙點交叉與多點交叉

(1)

雙點交叉(Two-pointCrossover)：指在個體編碼串中隨機設(shè)置了二個交叉點，然后再進行部分基因交換。

(2)雙點交叉的具體操作過程

Ⅰ.

在相互配對的兩個個體編碼串中隨機設(shè)置兩個交叉點。

Ⅱ.

交換兩個個體在所設(shè)定的兩個交叉點之間的部分染色體。例如：遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第21頁!

9.4.3均勻交叉(UniformCrossover)

(1)均勻交叉：指兩個配對個體的每一個基因座上的基因都以相同的交叉概率進行交換，從而形成兩個新的個體。均勻交叉實際上可歸屬于多點交叉的范圍。

(2)操作過程：

Ⅰ.

隨機產(chǎn)生一個與個體編碼串長度等長的屏蔽字

W=w1w2…wi…wl

,其中l(wèi)為個體編碼串長度。

Ⅱ.

由下述規(guī)則從A、B兩個父代個體中產(chǎn)生出兩個新的子代個體A’、B’:

?若wi=0，則A’在第i個基因座上的基因值繼承A的對應(yīng)基因值，B’

在第i個基因座上的基因值繼承B的對應(yīng)基因值；

?若wi＝l，則A’

在第i個基因座上的基因值繼承B的對應(yīng)基因值，B’

在第i個基因座上的基因值繼承A的對應(yīng)基因值。

例如，均勻交叉操作的示例如下:遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第22頁!9.5變異算子

(1)從遺傳運算過程中產(chǎn)生新個體的能力方面來說:

?交叉運算是產(chǎn)生新個體的主要方法，它決定了遺傳算法的全局搜索能力；

?

而變異運算只是產(chǎn)生新個體的輔助方法，但它也是必不可少的一個運算步驟，因為它決定了遺傳算法的局部搜索能力。

?

交叉算子與變異算子的相互配合，共同完成對搜索空間的全局搜索和局部搜索，從而使得遺傳算法能夠以良好的搜索性能完成最優(yōu)化問題的尋優(yōu)過程。

(2)在遺傳算法中使用變異算子主要有以下兩個目的：

(1)改善遺傳算法的局部搜索能力；

(2)維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。

(3)變異算子的設(shè)計包括如下兩方面的內(nèi)容：

?如何確定變異點的位置?

?如何進行基因值替換?

下面介紹其中較常用的幾種變異操作方法，它們適合于二進制編碼的個體和浮點數(shù)編碼的個體。

9.5.1基本位變異(SimpleMutation)遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第23頁!

9.5.3邊界變異(Boundarymutation)

(1)邊界變異均勻變異操作的一個變形算法。在進行邊界變異操作時，隨機地取基因座的二個對應(yīng)邊界基因值之一去替代原有基因值。

(2)舉例假設(shè)有一個體為X=x1x2…xk…xn,若xk為變異點，其取值范圍為[Ukmin,Ukmax],

在該點對個體X進行邊界變異操作后，可得到一個新的個體X=x1x2…xk’…xn,

其中變異點的新基因值是：Ukmin,ifrandom(0,1)=0Ukmax,ifrandom(0,1)=1xk’=式中，random(0,1)表示以均等的概率從0,1中任取其一。(3)適用范圍當(dāng)變量的取值范圍特別寬，并且無其他約束條件時，邊界變異會帶來不好的作用。但它特別適用于最優(yōu)點位于或接近于可行解的邊界時的一類問題。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第24頁!9.5.5高斯變異(Gaussianmutation)(1)高斯變異是改進遺傳算法對重點搜索區(qū)域的局部搜索性能的另一種變異操作方法。所謂高斯變異操作是指進行變異操作時，用符合均值為、方差為2

的正態(tài)分布的一個隨機數(shù)來替換原有基因值。

(2)操作

?

高斯變異的具體操作過程與均勻變異類似。

?

具體實現(xiàn)高斯變異時，符合正態(tài)分布的隨機數(shù)Q可由一些符合均勻分布的隨機數(shù)利用公式來近似產(chǎn)生。例：

?假定有12個在[0,1]范圍內(nèi)均勻分布的隨機數(shù)ri(i=1,2,…,12)，則符合N(,2)

正態(tài)分布的一個隨機數(shù)Q可由下式求得：遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第25頁!9.6終止遺傳算法是一個反復(fù)迭代的過程，每次選代期間，要執(zhí)行適應(yīng)度計算、復(fù)制、交叉、變異等操作，直至滿足終止條件。

使遺傳算法終止的方法有三種：

(1)規(guī)定最大選代次數(shù)T。一旦遺傳算法的迭代次數(shù)達(dá)到T，則停止操作，輸出結(jié)果。通常T取200一500次。由于遺傳算法中有許多隨機因素影響，最后一代的結(jié)果不一定含有最優(yōu)個體。為此，要經(jīng)常記錄每代的最優(yōu)個體以便查詢比較。

(2)規(guī)定最小的偏差。對于適應(yīng)度目標(biāo)已知的遺傳算法，如用方差作為適應(yīng)度計算的曲線擬合問題，可用最小的偏差制定終止條件，即：

|fmax–f*|≤

式中f*——已知的適應(yīng)度目標(biāo)；

fmax——每代最大的適應(yīng)廢。

(3)觀察適應(yīng)度的變化趨勢。在遺傳算法的初期，最優(yōu)個體的適應(yīng)度以及群體的平均適應(yīng)度都較小，以后隨著復(fù)制、交叉、變異等操作，適應(yīng)度值增加。到了遺傳算法后期，這種增加已趨緩和或停止．一旦這種增加停止，即中止遺傳算法。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第26頁!

(3)二進制編碼方法的優(yōu)點：

Ⅰ.編碼、解碼操作簡單易行；

Ⅱ.

交叉、變異等遺傳操作便于實現(xiàn)；

Ⅲ.

符合最小字符集編碼原則（使用能使問題得到自然表示或描述的具有最小編碼字符集的編碼方案。）；

Ⅳ.

便于利用模式定理對算法進行理論分析。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第27頁!4遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第28頁!

例如，如果一個優(yōu)化問題含有5個變量xi(i＝1,2,…,5)，每個變量都有其對應(yīng)的上下限[Uimin,Uimax]，則：5.806.903.503.805.00x:

表示一個體的基因型，其對應(yīng)的表現(xiàn)型是：x：[5.80，6.90，3.50，3.80，5.00]T。(3)注意事項：

?

在浮點數(shù)編碼方法中:

必須保證基因值在給定的區(qū)間限制范圍內(nèi)；遺傳算法中所使用的交叉、變異等遺傳算子也必須保證其運算結(jié)果所產(chǎn)生的新個體的基因值也在這個區(qū)間限制范圍內(nèi)。

?當(dāng)用多個字節(jié)來表示一個基因值時，交叉運算必須在兩個基因的分界字節(jié)處進行，而不能在某個基因的中間字節(jié)分隔處進行。

遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第29頁!9.1.4符號編碼方法

(1)編碼方法個體染色體編碼串中的基因值取自一個無數(shù)值含義、而只有代碼含義的符號集。這個符號集可以是一個字母表，如{A,B,C,D,…}；也可以是一個數(shù)宇序號表，如{1,2,3,4,5,…}；還可以是一個代碼表，如{Al,A2,A3,A4,A5,…}等等。

例如：對于旅行商問題，假設(shè)有n個城市分別記為C1,C2,…,Cn

，將各個城市的代號按其被訪問的順序連接在一起，就可構(gòu)成一個表示旅行路線的個體，如：

X：[C1,C2,…,Cn]

若將各個城市按其代號的下標(biāo)進行編號，則這個個體也可表示為：

X：[1，2，…，n][旅行商問題(TravelingSalesmanProblem，簡稱TSP)可描述為；已知n個城市之間的相互距離。現(xiàn)有一推銷員必須遍訪這n個城市，并且每個城市只能訪問一次，最后又必須返回出發(fā)城市。如何安排他對這些城市的訪問次序，可使其旅行路線的總長度最短?]遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第30頁!9.2適應(yīng)度函數(shù)

?

在研究自然界生物的遺傳和進化現(xiàn)象時，生物學(xué)家使用適應(yīng)度這個術(shù)語來度量某個物種對于其生存環(huán)境的適應(yīng)程度。

?與此相類似，遺傳算法中也使用適應(yīng)度這個概念來度量群體中各個個體在優(yōu)化計算中有可能達(dá)到或接近于或有助于找到最優(yōu)解的優(yōu)良程度。

度量個體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)。9.2.1目標(biāo)函數(shù)與適應(yīng)度函數(shù)遺傳算法的一個特點是它僅使用所求問題的目標(biāo)函數(shù)值就可以得到下一步的有關(guān)搜索信息。

最優(yōu)化問題可分為兩大類，一類為求目標(biāo)函數(shù)的全局最大值，另一類為求目標(biāo)函數(shù)的全局最小值。對于這兩類優(yōu)化問題，第二章中已經(jīng)介紹過由解空間中某一點的目標(biāo)函數(shù)值f(x)到搜索空間中對應(yīng)個體的適應(yīng)度函數(shù)值F(x)的轉(zhuǎn)換方法：

?對于求最大值的問題，作下述轉(zhuǎn)換：F(X)=f(X)+Cminiff(X)+Cmin>00

iff(X)+Cmin≤0遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第31頁!A:101010101010101010101010B:101010101010101010101010單點交叉

這樣就會使群體的多樣性降低，容易導(dǎo)致遺傳算法發(fā)生早熟現(xiàn)象（或稱早期收斂)，使遺傳算法所求到的解停留在某一局部最優(yōu)點上。

因此，我們希望在遺傳算法運行的初期階段，算法能夠?qū)σ恍┻m應(yīng)度較高的個體進行控制，降低其適應(yīng)度與其他個體適應(yīng)度之間的差異程度，從而限制其復(fù)制數(shù)量，以維護群體的多樣性。

?

在遺傳算法運行的后期階段

群體中所有個體的平均適應(yīng)度可能會接近于群體中最佳個體的適應(yīng)度。也就是說，大部分個體的適應(yīng)度和最佳個體的適應(yīng)度差異不大，它們之間無競爭力，都會有以相接近的概率被遺傳到下一代的可能性，從而使得進化過程無競爭性可言，只是一種隨機的選擇過程。這將導(dǎo)致無法對某些重點區(qū)域進行重點搜索，從而影響遺傳算法的運行效率。

因此，我們希望在遺傳算法運行的后期階段，算法能夠?qū)€體的適應(yīng)度進行適當(dāng)?shù)姆糯?，擴大最佳個體適應(yīng)度與其他個體適應(yīng)度之間的差異程度，以提高個體之間的競爭性。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第32頁!條件1：尺度變換后全部個體的新適應(yīng)度的平均值F’avg要等于其原適應(yīng)度平均值Favg

即：F’avg=Favg

這條要求是為了保證群體中適應(yīng)度接近于平均適應(yīng)度的個體能夠有期待的數(shù)量被遺傳到下一代群體中。

條件2：尺度變換后群體中新的最大適應(yīng)度F’max要等于其原平均適應(yīng)度Favg

的指定

倍數(shù)。即：F’max=CFavg

式中，C為最佳個體的期望復(fù)制數(shù)量，對于群體規(guī)模大小為50~100個個體的情況，一般取C=1.2~2。這條要求是為了保證群體中最好的個體能夠期望復(fù)制C倍到新一代群體中。如下圖所示。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第33頁!

最小適應(yīng)度為負(fù)時的處理：在遺傳算法執(zhí)行的后期，個別劣質(zhì)個體的適應(yīng)度遠(yuǎn)遠(yuǎn)小于群體平均適應(yīng)度及最大適應(yīng)度，并且后兩者比較接近。這時按上述方法縮放適應(yīng)度會使低適應(yīng)度變成負(fù)值，如圖所示。這將會給后面的處理過程帶來不便，必須避免這種情況的發(fā)生，解決這個問題的方法是：把原最小適應(yīng)度Fmin映射為Fmin=0，并且保持原平均適應(yīng)度Favg與新的平均適應(yīng)度F’avg相等。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第34頁!Ⅱ.乘冪尺度變換乘冪尺度變換的公式為：

F’=Fk

即新的適應(yīng)度是原有適應(yīng)度的某個指定乘冪。冪指數(shù)k與所求解的問題有關(guān)，并且在算法的執(zhí)行過程中需要不斷對其進行修正才能使尺度變換滿足一定的伸縮要求。

Ⅲ.指數(shù)尺度變換

指數(shù)尺度變換的公式為：

F’＝exp(-F)

即新的適應(yīng)度是原有適應(yīng)度的某個指數(shù)。式中系數(shù)決定了選擇的強制性，

越小，原有適應(yīng)度較高的個體的新適應(yīng)度就越與其他個體的新適應(yīng)度相差較大，亦即越增加了選擇該個體的強制性。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第35頁!遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第36頁!(2)罰函數(shù)法

[基本思想]

對在解空間中無對應(yīng)可行解的個體，計算其適應(yīng)度時，處以一個罰函數(shù)，從而降低該個體適應(yīng)度，使該個體被遺傳到下一代群體中的機會減少。即用下式來對個體的適應(yīng)度進行調(diào)整：F(X)X滿足約束條件時F(X)–P(X)X不滿足約束條件時F’(X)=

式中，F(xiàn)(X)為原適應(yīng)度;F’(x)為考慮了罰函數(shù)之后的新適應(yīng)度;P(x)為罰函數(shù)。[懲罰函數(shù)]

設(shè)有優(yōu)化問題的目標(biāo)函數(shù)：maxF(x1,x2,…,xn)S.t.Hi(x1,x2,…,xn)i=1,2,…,m遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第37頁!

其中：K——系數(shù)，可取1/m；

t——當(dāng)前的迭代代次；

T——終止迭代次數(shù)；

——系數(shù)，1左右；

f——個體適應(yīng)度的平均值；

di——違背約束i的程度，視問題的不同而定義。[難點]

如何確定合理的罰函數(shù)是這種處理方法的難點之所在，因為這時既要考慮如何度量解對約束條件不滿足的程度，又要考慮遺傳算法在計算效率上的要求。

?罰函數(shù)的強度太小的話，部分個體仍有可能破壞約束條件，所以保證不了遺傳運算所得到的個體一定是滿足約束條件的一個可行解；

?罰函數(shù)的強度太大的話，又有可能使個體的適應(yīng)度差異不大，降低了個體之間的競爭力，從而影響遺傳算法的運行效率。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第38頁!9.3選擇算子在生物的遺傳和自然進化過程中，對生存環(huán)境適應(yīng)程度較高的物種將有更多的機會遺傳到下一代；

遺傳算法中的選擇操作用來確定如何從父代群體中按某種方法選取哪些個體遺傳到下一代群體中的一種遺傳運算。選擇操作建立在對個體的適應(yīng)度進行評價的基礎(chǔ)上。最常用的選擇算子是基本遺傳算法中的比例選擇算子。但對于各種不同的問題，比例選擇算子并不是最合適的一種選擇算子，所以人們提出了其他一些選擇算于。下面介紹幾種常用選擇算子的操作方法。

9.3.1比例選擇(Fitnessproportionalselection)[基本思想]

各個個體被選中的概率與其適應(yīng)度大小成正比。設(shè)群體大小為M，個體i的適應(yīng)度為Fi，則個體i被選中的概率pis為：M

pis=Fi/Fii=1i=1,2,…M遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第39頁!

?采用線性分級，使各個個體被選中的可能性有如下線性關(guān)系：

p(i)=q-(i-1)d

其中，q

——最優(yōu)個體被選中的概率；

d——相鄰個體被選中概率之差。上述線性關(guān)系使p(i)構(gòu)成等差級數(shù)，即：

q，q-d，q–2d，…，

q-id，…，q–(M-1)d

由于概率定義要求，按級數(shù)求和，有：即：①遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第40頁!

9.3.3競技選擇法(tournamentselection)

(1)方法簡介

這種選擇法通過相互競爭，優(yōu)勝者成為下一代的個體。在每一代群體中，每次都隨機選擇k個個體構(gòu)成一個小群體，然后從這k個個體中確定性地取適應(yīng)度最大的個體復(fù)制，進入下一代群體。被復(fù)制后的個體仍返回父代群體中，參加下一次k個個體的隨機選擇。這種隨機選擇重復(fù)M次，產(chǎn)生M個下一代個體．

(2)具體操作步驟

Ⅰ.從第t代群體中隨機選擇k個個體；

Ⅱ.比較k個個體的適應(yīng)度，復(fù)制適應(yīng)度最大者進入第t+1代，被復(fù)制的個體仍保留在第t代；

Ⅲ.重復(fù)執(zhí)行Ⅰ、ⅡM次，直至產(chǎn)生同t代一樣的個體數(shù)目。

(3)特點競技選擇法中，選擇的力度取決于k值的大小。k值愈大，每次選出的優(yōu)勝者具有很高的適應(yīng)度。反之，k值愈小，優(yōu)勝者的適應(yīng)度或高或低，隨機性很強。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第41頁!

(2)最優(yōu)保存策略進化模型的具體操作過程

Ⅰ.

找出當(dāng)前群體中適應(yīng)度最高的個體和適應(yīng)度最低的個體。

Ⅱ.

若當(dāng)前群體中最佳個體的適應(yīng)度比總的迄今為止的最好個體的適應(yīng)度還要高，則以當(dāng)前群體中的最佳個體作為新的迄今為止的最好個體。

Ⅲ.

用迄今為止的最好個體替換掉當(dāng)前群體中的最差個體。

(3)特點：最優(yōu)保存策略可視為選擇操作的一部分。該策略的實施可保證迄今為止所得到的最優(yōu)個體不會被交叉、變異等遺傳運算所破壞，它是遺傳算法收斂性的一個重要保證條件。

缺點：它容易使得某個局部最優(yōu)個體不易被淘汰掉反而快速擴散，從而使得算法的全局搜索能力不強。

(4)使用方法：該方法一般要與其他一些選擇操作方法配合起來使用，方可有良好的效果。另外，最優(yōu)保存策略還可加以推廣，即在每一代的進化過程中保留多個最優(yōu)個體不參加交叉、變異等遺傳運算，而直接將它們復(fù)制到下一代群體中。這種選擇方法也稱為穩(wěn)態(tài)復(fù)制。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第42頁!9.4交叉算子在生物的自然進化過程中，兩個同源染色體通過交配而重組，形成新的染色體，從而產(chǎn)生出新的個體或物種。交配重組是生物遺傳和進化過程中的一個主要環(huán)節(jié)。模仿這個環(huán)節(jié)，在遺傳算法中也使用交叉算子來產(chǎn)生新的個體。遺傳算法中的所謂交叉運算，是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉算子的設(shè)計和實現(xiàn)與所研究的問題密切相關(guān)，一般要求它既不要太多地破壞個體編碼串中表示優(yōu)良性狀的優(yōu)良模式，又要能夠有效地產(chǎn)生出一些較好的新個體模式。另外，交叉算子的設(shè)計要和個體編碼設(shè)計統(tǒng)一考慮。交叉算子的設(shè)計包括以下兩方面的內(nèi)容:(1)如何確定交叉點的位置?(2)如何進行部分基因交換?

遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第43頁!(3)多點交叉(Multi-pointCrossover)：指在個體編碼串中隨機設(shè)置多個交叉點，然后進行基因交換。多點交叉又稱為廣義交叉。(4)操作過程：與單點交叉和雙點交叉相類似。

例如，三個交叉點時的交叉操作示例：(5)說明：

一般不大使用多點交叉算子，因為它有可能破壞一些好的模式。事實上，隨著交叉點數(shù)的增多，個體的結(jié)構(gòu)被破壞的可能性也逐漸增大。遺傳算法的實現(xiàn)技術(shù)共49頁，您現(xiàn)在瀏覽的是第44頁!9.4.4算術(shù)交叉(ArithmeticCrossover)

(1)算術(shù)交叉：