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