生物學(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ù)。基于這種小生境的遺傳算法（Niched Genetic Algorithms，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è)體，故它能夠有效的維持群體的多樣性，并造就小生境的進(jìn)化環(huán)境。De Jong在1975年提出基于排擠機(jī)制的選擇策略，其基本思想源于在一個(gè)有限的生存環(huán)境中，各種不同的生物為了能夠延續(xù)生存，他們之間必須相互競爭各種有限的生存資源。因此，在算法中設(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年提出了基于共享機(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ù)（Sharing Function）是表示群體中兩個(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è)體之間比較相似時(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è)算法的基本思想是：首先兩兩比較群體中各個(gè)個(gè)體之間的距離，若這個(gè)距離在預(yù)先的距離L 之內(nèi)的話，在比較兩者之間的適應(yīng)度大小，并對其中適應(yīng)值較低的個(gè)體施加一個(gè)較強(qiáng)的罰函數(shù)，極大地降低其適應(yīng)度，這樣，對于在預(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（t），并求出各個(gè)個(gè)體的適應(yīng)度F （i=1，2，M）。（2） 依據(jù)各個(gè)個(gè)體的適應(yīng)度對其進(jìn)行降序排列，記憶前N個(gè)個(gè)體（N<M）.(3) 選擇算法。對群體P（t）進(jìn)行比例選擇運(yùn)算，得到P （t）。（4）交叉選擇。對選擇的個(gè)體集合P （t） 作單點(diǎn)交叉運(yùn)算，得到P （t）。（5）變異運(yùn)算。對P （t）作均勻變異運(yùn)算，得到P （t）。（6）小生境淘汰運(yùn)算。將第（5）步得到的M個(gè)個(gè)體和第（2）步所記憶的N個(gè)個(gè)體合并在一起，得到一個(gè)含有M+N 個(gè)個(gè)體的新群體；對著M+N個(gè)個(gè)體，按照下式得到兩個(gè)個(gè)體x 和x 之間的海明距離：|| x - x ||= ( )當(dāng)|| x - x ||<L時(shí)，比較個(gè)體x 和個(gè)體x 的適應(yīng)度大小，并對其中適應(yīng)度較低的個(gè)體處以罰函數(shù)： Fmin(x ，x )=Penalty（7）依據(jù)這M+N個(gè)個(gè)體的新適應(yīng)度對各個(gè)個(gè)體進(jìn)行降序排列，記憶前N個(gè)個(gè)體。（8）終止條件判斷。若不滿足終止條件，則：更新進(jìn)化代數(shù)記憶器t t+1， 并將第（7）步排列中的前M個(gè)個(gè)體作為新的下一代群體P(t),然后轉(zhuǎn)到第（3）步：若滿足終止條件，則：輸出計(jì)算結(jié)果，算法結(jié)束。
[例] Shubert 函數(shù)的全局最優(yōu)化計(jì)算。
min f(x , x )={ } { }
s.t. -10 x 10（i=1，2）
上述函數(shù)共有760個(gè)局部最優(yōu)點(diǎn)，其中有18個(gè)是全局最優(yōu)點(diǎn)，全局最優(yōu)點(diǎn)處的目標(biāo)函數(shù)值是f （x ， x ）=-186.731。
用上述小生境遺傳算法求解該例題時(shí)，可用下式進(jìn)行目標(biāo)函數(shù)值到個(gè)體適應(yīng)度的變換處理：
F（x ， x ）=
L=202（二進(jìn)制編碼串長度，其中每個(gè)變量用10位二進(jìn)制編碼來表示）
M=50
T=500
p =0.1
p =0.1
L=0.5(小生境之間的距離參數(shù))
Penlty=10 （罰函數(shù)）
使用上述參數(shù)進(jìn)行了50次，試算，每次都可得到許多全局最優(yōu)解下表為其中一次運(yùn)算所得到的最好的18個(gè)個(gè)體。從該表可以看出，從小生境的角度來數(shù)，該算法得到了一個(gè)較好的結(jié)果。上述算法的特點(diǎn)保證了在一個(gè)函數(shù)峰內(nèi)只存在一個(gè)較優(yōu)的個(gè)體，這樣每一個(gè)函數(shù)峰就是一個(gè)小生境。
基于小生境遺傳算法的Shubert函數(shù)優(yōu)化算法計(jì)算結(jié)果
個(gè)體標(biāo)號(hào)??x? ?x? ?f（x ， x ）
1??5.4828??4.8581??-186.731
2??5.4830??-7.7083? ?-186.731
3??4.8581??5.4831? ?-186.731
4??4.8581??-7.0838??-186.731
5??-4.4252??-7.4983??-186.731
6??-7.0832??-7.0838??-186.731
7??5.4827??-1.4249??-186.731
8??0.8580??5.4831??-186.731
9??4.8580??-0.8009??-186.730
10??-0.8009??-7.7084??-186.730
11??-0.8009??4.8581??-186.730
12??-7.7088??-0.7999??-186.730
13??-7.7088??-7.0831??-186.730
14??-1.4256??-0.8009??-186.730
15??-0.8011??-1.4252??-186.730
16??-7.7075??5.4834??-186.730
17??-7.7088??4.8579??-186.730
18??-7.0825??-1.4249??-186.730
下面再介紹一種隔離小生境技術(shù)的遺傳算法
隔離小生境技術(shù)的基本概念及進(jìn)化策略依照自然界的地理隔離技術(shù),將遺傳算法的初始群體分為幾個(gè)子群體,子群體之間獨(dú)立進(jìn)化,各個(gè)子群體的進(jìn)化快慢及規(guī)模取決于各個(gè)子群體的平均適應(yīng)水平.由于隔離后的子群體彼此獨(dú)立,界限分明,可以對各個(gè)子群體的進(jìn)化過程靈活控制。生物界中,競爭不僅存在于個(gè)體之間,種群作為整體同樣存在著競爭,適者生存的法則在種群這一層次上同樣適用.在基于隔離的小生境技術(shù)中,是通過將種群的規(guī)模同種群個(gè)體平均適應(yīng)值相聯(lián)系來實(shí)現(xiàn)優(yōu)勝劣汰、適者生存這一機(jī)制的.子群體平均適應(yīng)值高,則其群體規(guī)模就大,反之,群體規(guī)模就小.生物界在進(jìn)化過程中,適應(yīng)環(huán)境的物種能得到更多的繁殖機(jī)會(huì),其后代不斷地增多,但這種增加不是無限制的,否則就會(huì)引起生態(tài)環(huán)境的失衡.在遺傳算法中,群體的總體規(guī)模是一定的,為了保證群體中物種的多樣性,就必須限制某些子群體的規(guī)模,稱子群體中所允許的最大規(guī)模為子群體最大允許規(guī)模(maximum allowed scale),記為S .生物界中同樣會(huì)出現(xiàn)某些物種因不適應(yīng)環(huán)境數(shù)量逐漸減少,直至滅絕的現(xiàn)象.在隔離小生境機(jī)制中,為了保持群體的多樣性,有時(shí)需要有意識(shí)地保護(hù)某些子群體,使之不會(huì)過早地被淘汰,并保持一定的進(jìn)化能力.子群體的進(jìn)化能力是和子群體的規(guī)模相聯(lián)系的,要保證子群體的進(jìn)化能力,必須規(guī)定每一子群體生存的最小規(guī)模,稱為子群體最小生存規(guī)模(minimum live scale),記為S .在群體進(jìn)化過程中,如果某一子群體在規(guī)定的代數(shù)內(nèi),持續(xù)表現(xiàn)最差,應(yīng)該使這個(gè)子群體滅絕,代之以搜索空間的新解,這一最劣子群體滅絕的機(jī)制,定義為劣種不活(the worst die).子群體在進(jìn)化過程中,如果出現(xiàn)兩個(gè)子群體相似或相同的現(xiàn)象,則去掉其中的一個(gè),代之以搜索空間的新解,這種策略稱為同種互斥或種內(nèi)競爭(intraspecific competition).解群中出現(xiàn)的新的子群體,在進(jìn)化的初期往往無法同已經(jīng)得到進(jìn)化的其它子群體相競爭,如果不對此施加保護(hù),這些新解往往在進(jìn)化的初期就被淘汰掉,這顯然是我們所不希望的.為了解決這個(gè)問題,必須對新產(chǎn)生的解加以保護(hù),這種保護(hù)新解的策略叫幼弱保護(hù)(immature protection).子群體在進(jìn)化過程中,如果收斂到或接近局部最優(yōu)解,會(huì)出現(xiàn)進(jìn)化停滯的現(xiàn)象,此時(shí)應(yīng)當(dāng)以某種概率將該子群體去掉,代之以搜索空間的新解,此種策略稱為新老更替(the new superseding the old).在進(jìn)化過程中,表現(xiàn)最優(yōu)的個(gè)體進(jìn)化為最優(yōu)解的概率最大,應(yīng)當(dāng)使它充分進(jìn)化,故新老更替策略不能用于最優(yōu)子群體,這種做法稱為優(yōu)種保留(the best live).優(yōu)種保留可以作用于最好的一個(gè)子群體,也可以作用于最好的幾個(gè)子群體.
基于隔離小生境技術(shù)的遺傳算法步驟
1)編碼:針對具體問題,選擇合適的編碼方案,完成問題解空間向遺傳算法解空間的轉(zhuǎn)化.
2)產(chǎn)生初始群體:隨機(jī)產(chǎn)生N個(gè)初始個(gè)體.
3)初始群體隔離:將N個(gè)初始個(gè)體均分給K個(gè)子群體,每個(gè)子群體含有的個(gè)體數(shù)均為N/K.
4)計(jì)算適應(yīng)值:計(jì)算群體中所有個(gè)體的適應(yīng)值.并保存適應(yīng)值最高的個(gè)體.
5)確定子群體規(guī)模:子群體的規(guī)模同子群體的平均適應(yīng)值相關(guān),子群體的平均適應(yīng)值越大,其在下一代中擁有的個(gè)體就越多;反之,在下一代中擁有的個(gè)體就少.但數(shù)目必須滿足最大允許規(guī)模和最小保護(hù)規(guī)模的限制,即第t+1代第k個(gè)子群體的規(guī)模n (t+1)滿足S ≤n (t+1) ≤S .
確定子群體規(guī)模的具體方法如下,首先給每個(gè)子群體都預(yù)分配S 個(gè)個(gè)體,剩下的個(gè)體根據(jù)子群體的平均適應(yīng)值利用賭輪法選擇,直到總的群體數(shù)量達(dá)到N為止.子群體的平均適應(yīng)值一般可簡單取為f (t)= (1)
式中f (t)為t代第k個(gè)子群體的平均適應(yīng)值;f (t)為t代第k個(gè)子群體中第i個(gè)個(gè)體的適應(yīng)值; n (t+1)為t代第k個(gè)子群體的規(guī)模.子群體k第t+1代的規(guī)模n (t+1)為：
n (t+1)=N . f (t)/ （2）
子群體規(guī)模的確定也可以根據(jù)其平均適應(yīng)水平用賭輪法確定.
6)保護(hù)解除判定:對群體中施加保護(hù)的群體,進(jìn)行保護(hù)解除判定,對滿足保護(hù)解除條件的,撤除保護(hù).
7)劣種不活判定:對解群中沒有保護(hù)而連續(xù)幾代表現(xiàn)又最差的群體,予以剔除并產(chǎn)生等規(guī)模的新子群體.
8)同種互斥判定:隨機(jī)挑選出兩個(gè)子群體,依據(jù)某種原則判定其相似程度,對滿足相似條件的兩個(gè)子群體,去掉其中的一個(gè),產(chǎn)生同等規(guī)模的新解.
9)新老更替判定:判定解群中是否存在已經(jīng)進(jìn)化停滯的子群體,如果有,進(jìn)行新老更替,產(chǎn)生同等規(guī)模的新解,但對包含最優(yōu)個(gè)體的子群體要保留(最優(yōu)保留機(jī)制).
10)重新計(jì)算適應(yīng)值:對新產(chǎn)生的子群體計(jì)算適應(yīng)性值,并施加幼弱保護(hù)措施.
11)子群體進(jìn)化:由于子群體的規(guī)模同其在群體中的平均表現(xiàn)水平相聯(lián)系,故子群體的規(guī)模是不斷變化的.
根據(jù)公式(2)確定的規(guī)模,選擇出子群體的繁殖個(gè)體,利用交叉和變異算子產(chǎn)生下一代解群.
12)收斂性判定,如果滿足收斂性條件,或已經(jīng)進(jìn)化了規(guī)定的代數(shù),則結(jié)束進(jìn)化過程;否則返回第4步。
除了上面的還有下面幾種常用的的小生境算法：
1 確定性擁擠算法
確定性擁擠（Deterministic crowding, DC）算法由Mahfoud 提出。該算法屬于擁擠算法范疇，采用子個(gè)體與父個(gè)體直接進(jìn)行競爭的模式，競爭的內(nèi)容包括適應(yīng)值和個(gè)體之間的距離。算法的過程如下：
確定性擁擠算法（重復(fù)G 代）
重復(fù)下列步驟N/2次：
（1）用放回的方式隨機(jī)選擇兩個(gè)父個(gè)體p 和p 。
（2）對其進(jìn)行雜交和變異，產(chǎn)生兩個(gè)個(gè)體c 和c 。
（3）如果[d(p ，c )+d(p ，c )] [d(p ，c )+d(p ，c )]，則
如果f（c ）>f（p ）,則用c 代替p ，否則保留p 。
如果f（c ）>f（p ），則用c 替換p ，否則保留p 。
如果f（c ）>f（p ），則用c 替換p ，否則保留p 。
如果f（c ）>f（p ），則用c 替換p ，否則保留p 。
其中，N 是種群規(guī)模，的d（i，j）是個(gè)體i 和個(gè)體j 之間的距離。
2 限制錦標(biāo)賽算法
限制錦標(biāo)賽選擇（Restricted tournament selection RTS）算法由Harik 提出。該算法屬于擁擠算法范疇，采用了個(gè)體與種群中其它個(gè)體進(jìn)行競爭的模式，競爭的內(nèi)容包括適應(yīng)值和個(gè)體之間的距離。該算法的過程如下：
限制錦標(biāo)賽算法（重復(fù)G代）
重復(fù)下列步驟N/2次：
（1）??用有放回的方式隨機(jī)選擇兩個(gè)父個(gè)體p 和p 。
（2）??對其進(jìn)行雜夾和變異，產(chǎn)生兩個(gè)子個(gè)體c 和才c 。
（3）??分別為c 和c從當(dāng)前的種群中隨機(jī)的選擇出w個(gè)個(gè)體。
（4） 不失一般性，設(shè)d 和d 分別是w個(gè)個(gè)體的中與c 和c 距離最近的兩個(gè)個(gè)體。
（5） 如果f（c ）>f（d ），則用c 替d 換，否則保留d 。
如果f（c ）>f（d ），則用c 替換d ，否則保留d 。
3多小生境擁擠算法
多小生境擁擠算法（Multi-niche crowding，MNC）由Cedeno提出。該算法屬擁擠算法的范疇，采用種群中的若干個(gè)體相互競爭的模式，競爭的內(nèi)容包括適應(yīng)值和個(gè)體之間的距離。競爭選擇出的老個(gè)體被新個(gè)體產(chǎn)生的子個(gè)體替換。算法的過程如下：
多小生境擁擠算法（重復(fù)G 代）
重復(fù)下列步驟N/2次：
（1）??用有放回的方式隨機(jī)選父個(gè)體p 。
（2）??從種群中隨機(jī)選擇C 個(gè)體作為p 的交配候選集，從中選出與p 最接近的個(gè)體p 。
（3）??對p 和p 進(jìn)行雜交和變異，產(chǎn)生兩個(gè)個(gè)體c 和c 。
（4）??分別為c 和c 從中當(dāng)前種群中各隨機(jī)選擇出C 群個(gè)體，每群個(gè)體包含w個(gè)個(gè)體。
（5）??每一群個(gè)體都選出一個(gè)與對應(yīng)字個(gè)體距離最近的個(gè)體。這樣就為每個(gè)個(gè)體產(chǎn)生了C 個(gè)替換候選個(gè)體。
（6）??不失一般性，設(shè)d 和d 是兩個(gè)替換候選集中適應(yīng)值最低的個(gè)體。
（7）??用c 替換d ，用c 替換d 。
Cedeno 還給出了C ，w和C 的最優(yōu)參數(shù)值。C 應(yīng)該在區(qū)間[2，4]內(nèi)，C 和w至少應(yīng)該兩倍于用戶希望找到的全局峰個(gè)數(shù)。該算法的步驟2提出了一中基于試探性的方法的限制交配策略。
4 標(biāo)準(zhǔn)適應(yīng)值共享算法
標(biāo)準(zhǔn)適應(yīng)值共享算法（Standard fitness sharing SH）由Goldberg 和Richardson 提出。該算法屬于適應(yīng)值共享算法范疇，事先需要給出解空間中小生境的半徑，并假設(shè)解空間中峰半徑均相同。算法的過程如下：
標(biāo)準(zhǔn)的適應(yīng)值共享算法（重復(fù)G 代）
（1）??計(jì)算種群中個(gè)體之間的共享函數(shù)值sh（d ）
sh（d ）=
其中， 是事先給出的峰半徑，d 是個(gè)體i和個(gè)體j之間的距離， 是控制共享函數(shù)形狀的參數(shù)，一般取 =1（線形共享函數(shù)）。兩個(gè)個(gè)體之間共享函數(shù)值越大，則兩個(gè)個(gè)體越接近。
（2）??計(jì)算種群中個(gè)體的小生境數(shù)m
m =
其中，N 是種群規(guī)模。個(gè)體的小生境數(shù)越大，則該個(gè)體周圍繞著越多其它個(gè)體。
（3）??計(jì)算種群中個(gè)體共享后的適應(yīng)值f
f =f / m
（4）??用個(gè)體共享后的適應(yīng)值進(jìn)行選擇，雜交和變異出新的個(gè)體，生成新一代種群。
Deb和Goldberg 在假設(shè)解空間中峰均勻分布并且峰半徑相同的前提下，提出計(jì)算峰半徑的計(jì)算公式。此外它們還提供了一種基于峰半徑的限制交配策略，從而保證所有的雜交均在同一物種進(jìn)行，確保了后代和父母的均屬于同一小生境。標(biāo)準(zhǔn)適應(yīng)值共享算法計(jì)算距離的時(shí)間復(fù)雜度為O（N ）。
5 清除算法
清除（Clearing）算法由Petrowski 提出。該算法屬于適應(yīng)值共性算法范疇，事先需要給出解空間的小生境半徑 （重要參數(shù)）和小生境的容量 （次要參數(shù)），并假設(shè)解空間中峰值半徑均相同。算法的過程如下：
清除算法（G）
（1）??按照適應(yīng)值對個(gè)體進(jìn)行降序排列。
（2）??將第一個(gè)體指定為第一個(gè)小生境中心。
（3）??從第二個(gè)個(gè)體開始順序執(zhí)行下列步驟到最后一個(gè)個(gè)體：
（3.1）如果當(dāng)前個(gè)體到所有已指定小生境中心的距離均大于，則該個(gè)體被指定為一個(gè)新的小生境中心。該個(gè)成為優(yōu)勝者。
（3.2）如果當(dāng)前個(gè)體到某個(gè)已指定的小生境中心的距離小于，并且該小生境個(gè)數(shù)小于，則該個(gè)體加入到該小生境中去，該小生境的個(gè)體總數(shù)增加1。該個(gè)體成為優(yōu)勝者。
（3.3）其它個(gè)體均為失敗者。
（3.4）維持所有優(yōu)勝者的適應(yīng)度不變，將所有失敗者的適應(yīng)值置為0。
（4）用個(gè)體修改后的適應(yīng)值進(jìn)行選擇，雜交和變異出新個(gè)體，生成新一代種群。
清除算法計(jì)算距離的時(shí)間復(fù)雜度為O（kN），其中k是該算法維持的小生境數(shù)量。如果將優(yōu)勝者的小生境數(shù)看為一，而將失敗者的小生境看作無窮大，則清除算法也可看作標(biāo)準(zhǔn)適應(yīng)值共享算法的改進(jìn)。
6 結(jié)合適應(yīng)值共享的自適應(yīng)k均值聚類算法
結(jié)合適應(yīng)值共享的自適應(yīng)算法k均值聚類算法（Adaptive k-mean clustering with fitness sharing）算法由Yin 和German提出。該算法屬于適應(yīng)值共性算法范疇，事先需要給出解空間中小生境中新建的最小距離 和小生境中的個(gè)體到該小生境中心之間的最大距離 。解空間中峰半徑可能不相同。算法的過程如下：結(jié)合適應(yīng)值共享的自適應(yīng)k均值均類算法（重復(fù)G代）
（1）??按照適應(yīng)值對個(gè)體進(jìn)行降序排列。
（2）? ?產(chǎn)生在[1，N]之間的隨機(jī)整數(shù)k（初始小生境個(gè)數(shù)）。
（3）??將前k個(gè)個(gè)體分別放入不同的小生境中并成為小生境中心。確保所有 小生境中心間距離大于 ，如果不能滿足這一條件，則合并小生境，新的小生境中心就是該小生境中所有個(gè)體的中心。
（4）??對于其它N-k個(gè)個(gè)體中的每一個(gè)，計(jì)算其與當(dāng)前所有想生境中心之間 的距離。如果距離大于 ，則生成新的小生境，該個(gè)體成為新小生境的中心。否則將該個(gè)體安排到距離最近的小生境中去。據(jù)需要確保所有小生境中心間的距離均大于 ，如果不能滿足這一條件，則需要合并小生境。
（5）??所有個(gè)體均被安置完畢后，固定小生境的中心，將所有個(gè)體按照最小
距離原則安排到最近的小生境中去。
（6）??計(jì)算計(jì)算種群個(gè)體的小生境數(shù)m
m =n - n （d /2 ） 若x C
其中，n 是第c個(gè)小生境中包含個(gè)個(gè)體總數(shù)，d 是個(gè)體i與它歸屬的小生境中心之間的距離，x 是第i個(gè)個(gè)體，C 第c 個(gè)小生境的個(gè)體基， 是控制函數(shù)形狀的參數(shù)，通常 =1。
（7）??用公式計(jì)算個(gè)體共享后的適應(yīng)值。
（8）??用個(gè)體共享后的適應(yīng)值進(jìn)行選擇，雜交和變異出新的個(gè)體，生成新一 代個(gè)體種群。
結(jié)合適應(yīng)值共享的自適應(yīng)性k均值聚類算法計(jì)算距離的時(shí)間復(fù)雜度為O（Kn）。
7 動(dòng)態(tài)小生境共享算法
動(dòng)態(tài)小生境共享算方法（Dynamic niche sharing）是由Miller和Shaw 提出。該算法屬于適應(yīng)值共享算法范疇，事先需要給出解空間中小生境的半徑 和小生境的數(shù)量k。算法的過程如下；
動(dòng)態(tài)小生境共享算法（重復(fù)G代）
（1）??按照適應(yīng)值對個(gè)體進(jìn)行降序排列。
（2）??將第一個(gè)個(gè)體指定為第一個(gè)小生境中心。
（3）??從第二個(gè)個(gè)體開始順序執(zhí)行下列步驟到最后一個(gè)個(gè)體：
（3.1）如果當(dāng)前個(gè)體與所有已指定的小生境中心之間的距離大于 ，而且已指定的小生境數(shù)量小于k，則形成一個(gè)新的小生境，該個(gè)體成為新小生境的中心。
（3.2）如果當(dāng)前個(gè)體與所有小生境中心之間的距離均大于 ，而且已指定的小生境數(shù)量不小于k，則該個(gè)體成為獨(dú)立個(gè)體。
（4） 對于那些屬于某個(gè)小生境的個(gè)體，其小生境數(shù)就是它所屬的小生境中個(gè)體的數(shù)量。對于那些獨(dú)立個(gè)體，采用公式計(jì)算小生境數(shù)。
（5） 用公式計(jì)算個(gè)體共享后的適應(yīng)值。
（6） 用共享后的適應(yīng)值進(jìn)行選擇，雜交和變異出新的個(gè)體，生成新一代種群。動(dòng)態(tài)小生境共享算法計(jì)算距離的時(shí)間復(fù)雜度為O（Kn）。
8 自適應(yīng)小生境算法
自適應(yīng)小生境算法（Adaptive nicking）由Goldberg 和 Wang 提出。該算法屬于適應(yīng)值共享算法范疇，事先需要給出解空間中小生境的半徑 和小生境的數(shù)量k。算法包含兩個(gè)分別被稱為顧客和商家的個(gè)體群，利用這兩個(gè)個(gè)體群的共同演化實(shí)現(xiàn)多峰優(yōu)化的目的。顧客群類似于其它適應(yīng)值共享算法中的種群，而商家群則代表搜索空間中峰的集合。商家群的個(gè)體數(shù)量k略大于其它適應(yīng)值共享算法中的小生境樹立功能。顧客群中的個(gè)體的適應(yīng)值與其它適應(yīng)值共享算法中個(gè)體的適應(yīng)值相同，而商家群中的個(gè)體的適應(yīng)值是屬于該商家所有顧客的適應(yīng)值之和。
算法需要首先在搜索空間中隨機(jī)放置商家群的個(gè)體，其余的過程如下；
自適應(yīng)小生境算法（重復(fù)G 代）
（1）??將每一個(gè)顧客群中的個(gè)體都安排到最近的商家中去。
（2）??計(jì)算所有顧客的小生境數(shù)（其歸屬的商家所擁有的顧客數(shù)量）。
（3）??用公式計(jì)算顧客群的個(gè)體共享后的適應(yīng)值。
（4）??用顧客群中個(gè)體共享后的適應(yīng)值盡心選擇，雜交和變異出新的個(gè)體，生成新一代顧客群。
（5）??順序選擇每一個(gè)商家群中的個(gè)體并對其進(jìn)行變異操作以產(chǎn)生新的商家。如果新商家的適應(yīng)值比老商家的適應(yīng)高，而且與其它商家之間的距離均小于，則新商家代替老商家。否則進(jìn)行另外一次變異操作，直到產(chǎn)生可以替換的新商家或變異操作的次數(shù)超過指定的最大變異為止。
自適應(yīng)小生境算法計(jì)算距離的時(shí)間的復(fù)雜度為O(Kn).
from:
http://qbwh.com/viewthread_123913.html