遺傳算法小生境技術(shù)簡介

《遺傳算法小生境技術(shù)簡介》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、遺傳算法小生境技術(shù)簡介生物學(xué)上，小生境是指特定環(huán)境下的一種組織結(jié)構(gòu)。在自然界中，往往特征，形狀相似的物種相聚在一起，并在同類中交配繁衍后代。在SGA中，交配完全是隨機(jī)的，在進(jìn)化的后期，大量的個(gè)體集中于某一極值點(diǎn)上，在用遺傳算法求解多峰值問題時(shí)，經(jīng)常只能找到個(gè)別的幾個(gè)最優(yōu)值，甚至往往得到是局部最優(yōu)解。利用小生境我們可以找到全部最優(yōu)解。小生境技術(shù)就是將每一代個(gè)體劃分為若干類，每個(gè)類中選出若干適應(yīng)度較大的個(gè)體作為一個(gè)類的優(yōu)秀代表組成一個(gè)群，再在種群中，以及不同種群中之間，雜交，變異產(chǎn)生新一代個(gè)體群。同時(shí)采用預(yù)選擇機(jī)制和排擠機(jī)制或分享機(jī)制完成任務(wù)。基

2、于這種小生境的遺傳算法（NichedGeneticAlgorithms，NGA），可以更好的保持解的多樣性，同時(shí)具有很高的全局尋優(yōu)能力和收斂速度，特別適合于復(fù)雜多峰函數(shù)的優(yōu)化問題。模擬小生境技術(shù)主要建立在常規(guī)選擇操作的改進(jìn)之上。Cavichio在1970年提出了基于預(yù)選擇機(jī)制的選擇策略，其基本做法是：當(dāng)新產(chǎn)生的子代個(gè)體的適應(yīng)度超過其父代個(gè)體的適應(yīng)度時(shí)，所產(chǎn)生的子代才能代替其父代而遺傳到下一代群體中去，否則父代個(gè)體仍保留在下一代群體中。由于子代個(gè)體和父代個(gè)體之間編碼結(jié)構(gòu)的相似性，所以替換掉的只是一些編碼結(jié)構(gòu)相似的個(gè)體，故它能夠有效的維持群體的多

3、樣性，并造就小生境的進(jìn)化環(huán)境。DeJong在1975年提出基于排擠機(jī)制的選擇策略，其基本思想源于在一個(gè)有限的生存環(huán)境中，各種不同的生物為了能夠延續(xù)生存，他們之間必須相互競(jìng)爭各種有限的生存資源。因此，在算法中設(shè)置一個(gè)排擠因子CF（一般取CF=2或3），由群體中隨機(jī)選取的1/CF個(gè)個(gè)體組成排擠成員，然后依據(jù)新產(chǎn)生的的個(gè)體與排擠成員的相似性來排擠一些與預(yù)排擠成員相類似的個(gè)體，個(gè)體之間的相似性可用個(gè)體編碼之間的海明距離來度量。隨著排擠過程的進(jìn)行，群體中的個(gè)體逐漸被分類，從而形成一個(gè)個(gè)小的生成環(huán)境，并維持群體的多樣性。??Goldberg等在1987年

4、提出了基于共享機(jī)制（Sharing）的小生境實(shí)現(xiàn)方法。這種實(shí)現(xiàn)方法的基本思想是：通過反映個(gè)體之間的相似程度的共享函數(shù)來調(diào)節(jié)群體中各個(gè)個(gè)體的適應(yīng)度，從而在這以后的群體進(jìn)化過程中，算法能夠依據(jù)這個(gè)調(diào)整后的新適應(yīng)度來進(jìn)行選擇運(yùn)算，以維持群體的多樣性，創(chuàng)造出小生境的進(jìn)化環(huán)境。共享函數(shù)（SharingFunction）是表示群體中兩個(gè)個(gè)體之間密切關(guān)系程度的一個(gè)函數(shù)，可記為S（d）其中表示個(gè)體i和j之間的關(guān)系。例如，個(gè)體基因型之間的海明距離就可以為一種共享函數(shù)。這里，個(gè)體之間的密切程度主要體現(xiàn)為個(gè)體基因型的相似性或個(gè)體表現(xiàn)型的相似性上。當(dāng)個(gè)體之間比較相似

5、時(shí)，其共享函數(shù)值就比較大；反之，當(dāng)個(gè)體之間不太相似時(shí)，其共享函數(shù)值比較小。共享度是某個(gè)個(gè)體在群體中共享程度的一中度量，它定義為該個(gè)體與群體內(nèi)其它各個(gè)個(gè)體之間的共享函數(shù)值之和，用S表示：S=（i=1，，M）在計(jì)算出了群體中各個(gè)個(gè)體的共享度之后，依據(jù)下式來調(diào)整各個(gè)個(gè)體的適應(yīng)度：F（X）=F（X）/S（i=1，，M）由于每個(gè)個(gè)體的遺傳概率是由其適應(yīng)度大小來控制的，所以這種調(diào)整適應(yīng)度的方法就能夠限制群體中個(gè)別個(gè)體的大量增加，從而維護(hù)了群體的多樣性，并造就了一種小生境的進(jìn)化環(huán)境。下面介紹一個(gè)基于小生境概念的遺傳算法。這個(gè)算法的基本思想是：首先兩兩比較群

6、體中各個(gè)個(gè)體之間的距離，若這個(gè)距離在預(yù)先的距離L之內(nèi)的話，在比較兩者之間的適應(yīng)度大小，并對(duì)其中適應(yīng)值較低的個(gè)體施加一個(gè)較強(qiáng)的罰函數(shù)，極大地降低其適應(yīng)度，這樣，對(duì)于在預(yù)先指定的某一距離L之內(nèi)的兩個(gè)個(gè)體，其中較差的個(gè)體經(jīng)處理后其適應(yīng)度變得更差，他在后面的進(jìn)化過程被淘汰的概率就極大。也就是說，在距離L內(nèi)將只存在一個(gè)優(yōu)良個(gè)體，從而既維護(hù)了群體的多樣性，又使得各個(gè)個(gè)體之間保持一定的距離，并使得個(gè)體能夠在整個(gè)約束的空間中分散開來，這樣就實(shí)現(xiàn)了一種小生境遺傳算法。這個(gè)小生境算法的描述如下：算法NicheGA（1）設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器；隨機(jī)生成M個(gè)初始群體P（

7、t），并求出各個(gè)個(gè)體的適應(yīng)度F（i=1，2，M）。（2）依據(jù)各個(gè)個(gè)體的適應(yīng)度對(duì)其進(jìn)行降序排列，記憶前N個(gè)個(gè)體（N

8、

9、x-x

10、

11、=()當(dāng)

12、

13、x-x

14、

15、

16、體x的適應(yīng)度大小，并對(duì)其中適應(yīng)度較低的個(gè)體處以罰函數(shù)：Fmin(x，x)=Penalty（7）依據(jù)這M+N個(gè)個(gè)體的新適應(yīng)度對(duì)各個(gè)個(gè)體進(jìn)行降序排列，記憶前N個(gè)個(gè)體。（