遺傳算法的基本原理學習培訓課件

1、第四章 遺傳算法的基本原理 4.1 遺傳算法的基本描述 4.2 遺傳算法的模式理論4.3 遺傳算法與其他搜索算法的比較4.4 遺傳算法的高級實現(xiàn)4.1.1 標準遺傳算法流程：1編碼2初始群體的生成3適應度評估檢測4WHILE DO1. 選擇2. 交叉3. 變異4. 適應度評估檢測5END DO 4.1 遺傳算法的基本描述選擇交叉當前代中間代下一代4.1 遺傳算法的基本描述4.1.3 遺傳編碼定義：由問題空間向GA編碼空間的映射稱為編碼，而由編碼空間向問題空間的映射成為譯碼。問題編碼一般應滿足以下三個原則：1）完備性（completeness）：問題空間中的所有點都能能成為GA編碼空間中的點的表

2、現(xiàn)型2）健全性（soundness）：GA編碼空間中的染色體位串必須對應問題空間中的某一潛在解。3）非冗余性（non-redundancy）：染色體和潛在解必須一一對應。4.1 遺傳算法的基本描述4.1.3 遺傳編碼根據(jù)模式定理，De Jong進一步提出了較為客觀明確的編碼評估準則，稱之為編碼原理。具體可以概括為兩條規(guī)則：1）有意義積木塊編碼規(guī)則：編碼應易于生成與所求問題相關(guān)的短距和低階的積木塊。2）最小字符集編碼規(guī)則：編碼應采用最小字符集，以使問題得到自然、簡單的表示和描述。4.1 遺傳算法的基本描述1二進制編碼1）連續(xù)實函數(shù)的二進制編碼設一維連續(xù)實函數(shù) 采用長度維L的二進制字符串進行定長編

3、碼，建立位串空間：k=1,2,K; l=1,2,L; K=2L表示精度為 。將個體又從位串空間轉(zhuǎn)換到問題空間的譯碼函數(shù)的公式定義為：4.1 遺傳算法的基本描述對于n維連續(xù)函數(shù) ，各維變量的二進制編碼位串的長度為li,那么x的編碼從左到右依次構(gòu)成總長度為 的二進制編碼位串。相應的GA編碼空間為：，K=2L該空間上的個體位串結(jié)構(gòu)為對于給定的二進制編碼位串sk,位段譯碼函數(shù)的形式為 ， i = 1,2,n 4.1 遺傳算法的基本描述2其他編碼1) 大字符集編碼（相對于二進制編碼）2) 序列編碼（TSP）3) 實數(shù)編碼4) 樹編碼5) 自適應編碼6) 亂序編碼 4.1 遺傳算法的基本描述4.1.4 群

4、體設定 1。初始群體的設定一般來講，初始群體的設定可以采用如下的策略：根據(jù)問題固有知識，設法把握最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此分布范圍內(nèi)設定初始群體。先隨機生成一定數(shù)目的個體，然后從中挑出最好的個體加入到初始群體中。這一過程不斷重復，直到初始群體中個體數(shù)達到了預定的規(guī)模。4.1 遺傳算法的基本描述4.1.4 群體設定 2。群體規(guī)模的設定 根據(jù)模式定理，若群體規(guī)模為M，則遺傳操作可從這M個個體中生成和檢測O(M3)個模式，并在此基礎上不斷形成和優(yōu)化積木塊，直到找到最優(yōu)解。群體規(guī)模N，模式階i，被采樣的模式數(shù)量的期望Mi (i = 1, 2, , )之間滿足如下關(guān)系：群體規(guī)模

5、一般不隨迭代而變化，但也不絕對。4.1 遺傳算法的基本描述4.1.5 適應度函數(shù)（評價函數(shù)） 1。目標函數(shù)映射成適應度函數(shù) 2。適應度函數(shù)定標 1）線性定標（linear scaling）f = af + b2）截斷（sigma truncation）3） 乘冪標f = fK4） 指數(shù)定標f = exp(-bf)4.1 遺傳算法的基本描述4.1.6 遺傳算子 包括三個基本遺傳算子（genetic operator）：選擇，交叉和變異。這三個遺傳算子具有一些特點：（1）這三個算子的操作都是隨機化操作，因此，群體中個體向最優(yōu)解遷移的規(guī)則是隨機的。需要強調(diào)的是，這種隨機化操作和傳統(tǒng)的隨機搜索方法是有

6、區(qū)別的。遺傳操作進行的是高效有向的搜索，而不是如一般隨機搜索方法所進行的無向搜索。（2）遺傳操作的效果和所取的操作概率、編碼方法、群體大小，以及適應度函數(shù)的設定密切相關(guān)。（3）三個基本算子的操作方法和操作策略隨具體求解問題的不同而異?；蛘哒f，是和個體的編碼方式直接相關(guān)。 4.1.6 遺傳算子一、選擇（selection）算子 從群體中選擇優(yōu)勝個體，淘汰劣質(zhì)個體的操作叫選擇。選擇算子有時又稱為再生算子（reproduction operator）。選擇即從當前群體中選擇適應度值高的個體以生成配對池（mating pool）的過程。 4.1.6 遺傳算子一、選擇（selection）算子 1、適應

7、度比例選擇首先計算每個個體的適應度值，然后計算出此適應度值在群體適應度值總和中所占的比例，表示該個體在選擇過程中被選中的概率。選擇過程體現(xiàn)了生物進化過程中“適者生存，優(yōu)勝劣汰”的思想。 對于給定的規(guī)模為n的群體 ，個體 的適應度值為 ，其選擇概率為： 問題：易出現(xiàn)未成熟收斂4.1.6 遺傳算子一、選擇（selection）算子 2、Boltzmann選擇在群體進化過程中，不同階段需要不同地選擇壓力。早期階段選擇壓力較小，我們希望較差地個體也又一定地生存機會，使得群體保持較高地多樣性；后期階段，選擇壓力較大，我們希望GA縮小搜索鄰域，加快當前最優(yōu)解的改善速度。為了動態(tài)調(diào)整群體進化過程中的選擇壓力

8、，Goldberg設計了Boltzmann選擇方法。個體選擇概率為： 4.1.6 遺傳算子一、選擇（selection）算子 3、排序選擇 排序選擇方法是將群體中個體按其適應度值由大到小的順序排成一個序列，然后將事先設計好的序列概率分配給每個個體。排序選擇不利用個體適應度值絕對值的信息，可以避免群體進化過程中的適應度標度變換。4.1.6 遺傳算子一、選擇（selection）算子 3、排序選擇 對于給定的規(guī)模為n的群體 ，并且滿足個體適應度值降序排列 。假設當前群體最佳個體a1在選擇操作后的期望數(shù)量為 ，即；最差個體an在選擇操作后的期望數(shù)量為 。其它個體的期望數(shù)量按等差序列計算， ，故現(xiàn)在排

9、序選擇概率為 4.1.6 遺傳算子一、選擇（selection）算子 4、聯(lián)賽選擇（tournament selection）基本思想：從當前群體中隨機選擇一定數(shù)量的個體（放回或者不放回），將其中適應值最大的個體放入配對池中。反復執(zhí)行這一過程，直到配對池中的個體數(shù)量達到設定的值。聯(lián)賽規(guī)模用q表示，也稱q-聯(lián)賽選擇。聯(lián)賽選擇與個體的適應度值由間接關(guān)系，注重適應度值大小的比較。聯(lián)賽規(guī)模一般取q=2。4.1.6 遺傳算子一、選擇（selection）算子 5、精英選擇 如果下一代群體的最佳個體適應度值小于當前群體最佳個體的適應度值，則將當前群體最佳個體或者適應度值大于下一代最佳個體適應度值的多個個體

10、直接復制到下一代，隨機替代和替代最差的下一代群體中的相應數(shù)量的個體。 精英選擇是群體收斂到全局最優(yōu)解的一種基本保障。 4.1.6 遺傳算子一、選擇（selection）算子 6、穩(wěn)態(tài)選擇 穩(wěn)態(tài)選擇操作中，僅有少量個體按適應度值比例選擇方法被選擇，通過遺傳操作生成新的個體。新個體放回到群體中時，隨機替代等量的舊個體，或者替代等量的最差的舊個體。 Holland將穩(wěn)態(tài)選擇方法應用于分類器規(guī)則學習中，最大程度繼承已獲得的規(guī)則，實現(xiàn)增量學習。 De Jong將下一代群體中生成的與上一代不同的新個體所占的比例稱為“代溝”（generation gap）。代溝越大，說明新個體的生成比例越高，群體搜索新的編

11、碼空間的能力（探索）越強。4.1.6 遺傳算子二、交叉（Crossover）算子 交叉算子是模仿自然界有性繁殖的基因重組過程，其作用在于將已有的優(yōu)良基因遺傳給下一代個體，并生成包含更復雜基因結(jié)構(gòu)的新個體。交叉操作一般分為以下幾個步驟：1）從配對池中隨機取出要交配的一對個體；2）根據(jù)位串長度L，對要交叉的一對個體，隨機選取1, L-1中一個或多個整數(shù)k作為交叉位置；3）根據(jù)交叉概率實施交叉操作，配對個體在交叉位置處，相互交換各自的部分內(nèi)容，從而形成新的一對個體。4.1.6 遺傳算子二、交叉（Crossover）算子 1、一點交叉（one-point crossover）位串A： 1 1 0 1

12、| 1 0 1 0位串B： 1 0 1 1 | 0 1 0 1位串A：1 1 0 1 | 0 1 0 1位串B：1 0 1 1 | 1 0 1 0 4.1.6 遺傳算子二、交叉（Crossover）算子 1、兩點交叉（two-point crossover）位串A： 1 1 | 0 1 1 | 0 1 0位串B： 1 0 | 1 1 0 | 1 0 1位串A：1 1 | 1 1 0 | 0 1 0位串B：1 0 | 0 1 1 | 1 0 1 4.1.6 遺傳算子二、交叉（Crossover）算子 1、多點交叉（multi-point crossover）位串A： 1 1 | 0 1 | 1

13、0 | 1 0位串B： 1 0 | 1 1 | 0 1 | 0 1位串A：1 1 | 1 1 | 1 0 | 0 1位串B：1 0 | 0 1 | 0 1 | 1 04.1.6 遺傳算子二、交叉（Crossover）算子 1、一致交叉一致交叉即染色體位串上的每一位按相同概率進行隨機均勻交叉。一致交叉算子生成的新個體位：操作描述如下： ：，x是取值為0，1上符合均勻分布的隨機變量。4.1.6 遺傳算子三、變異（Mutation）算子 變異操作模擬自然界生物體進化中染色體上某位基因發(fā)生的突變現(xiàn)象，從而改變?nèi)旧w的結(jié)構(gòu)和物理性狀。在標準遺傳算法中，變異算子通過按變異概率pm隨機反轉(zhuǎn)某位等位基因的二進

14、制字符值來實現(xiàn)。對于給定的染色體位串 ，具體如下：生成新的個體 。其中，xi是對應于每一個基因位產(chǎn)生的均勻隨機變量， 。 4.1.6 遺傳算子四、逆轉(zhuǎn)（Inversion Operator）算子 逆轉(zhuǎn)操作首先在個體位串上隨機地選擇兩個點，位串染色體被這兩個點分成三段，將中間段的左右順序倒轉(zhuǎn)過來與另兩段相連，形成新的個體位串。例如：長度為10的二進制位串，其中下劃線標示的等位基因為重要基因：1011101101（是倒位位置）經(jīng)倒位后變?yōu)?011011101。新的位串中重要基因更為靠近，被單點交叉算子分離的可能性大大降低了。4.1.6 遺傳算子四、換位（Swap Operator）算子換位操作首先

15、在個體位串上隨機地選擇兩個基因，將這兩個基因的位置互換，形成新的個體位串。例如：長度為10的二進制位串，其中下劃線標示的為隨機選中的基因：1011101101經(jīng)換位后變?yōu)?111101100 4.1.7 迭代終止條件一般采用設定最大代數(shù)的方法。其次，可以根據(jù)群體的收斂程度來判斷，通過計算種群中的基因多樣性測度，即所有基因位的相似性程度來進行控制。第三，根據(jù)算法的離線性能和在線性能的變化進行判定。最后，在采用精英保留選擇策略的情況下，按每代最佳個體的適應值的變化情況確定。 4.1.8 控制參數(shù)1）位串長度L：位串長度L的選擇取決于特定問題解的精度。要求的精度越高，位串越長，但需要更多的計算時間。

16、為提高運算效率，變長度位串或者在當前所達到的較小可行域內(nèi)重新編碼，是一種可行的方法，并顯示了良好性能。2）群體規(guī)模n：大群體含有較多模式，為遺傳算法提供了足夠的模式采樣容量，可以改進GA搜索的質(zhì)量，防止成熟前收斂。但大群體增加了個體適應性評價的計算量，從而使收斂速度降低。一般情況下建議n20200。4.1.8 控制參數(shù)3）交叉概率Pc：交叉概率控制著交叉算子的應用頻率，在每一代新的群體中，需要對Pcn個個體的染色體結(jié)構(gòu)進行交叉操作。交叉概率越高，群體中新結(jié)構(gòu)的引人愈快，已獲得的優(yōu)良基因結(jié)構(gòu)的丟失速度也相應升高。而交叉概率太低則可能導致搜索阻滯。一般取Pc=0.601.00。4）變異概率Pm：變

17、異操作是保持群體多樣性的有效手段，交叉結(jié)束后，交配池中的全部個體位串上的每位等位基因按變異率Pm隨機改變，因此每代中大約發(fā)生PmnL次變異。變異概率太小，可能使某些基因位過早丟失的信息無法恢復；而變異概率過高，則遺傳搜索將變成隨機搜索。一般取Pm = 0.0050.01。 4.1.8 控制參數(shù)從理論上來講，不存在一組適用于所有問題的最佳參數(shù)值，隨著問題特征的變化，有效參數(shù)的差異往往非常顯著。 4.1.9 GA的性能評估 關(guān)于搜索類算法的性能評估，一般可以歸納為算法的求解效率和求解質(zhì)量兩個方面。算法的求解效率是比較獲得同樣的可行解所需要的計算時間。算法的求解質(zhì)量是在規(guī)定的時間（或者時間相關(guān)指標）

18、內(nèi)所獲得的可行解的優(yōu)劣。4.1.9 GA的性能評估 1適應值函數(shù)計算次數(shù)該指標是指發(fā)現(xiàn)同樣適應性的個體，或者找到同樣質(zhì)量的可行解，所需要的關(guān)于個體評價的適應值函數(shù)的計算次數(shù)（function evaluations）。顯然，該值越小說明相應GA的搜索效率越高。 該指標不僅可以用于不同參數(shù)設置GA的性能比較，也可以用于GA與其他搜索算法的比較。 4.1.9 GA的性能評估 2在線和離線性能函數(shù) 1）在線性能函數(shù)（on-line performance）：設GA的遺傳策略為s（包括L，n，Pc，Pm，算子形式等），該策略的在線性能：即在線性能反映了群體平均適應值經(jīng)平滑處理后的變化情況，描述了群體的

19、整體性狀和進化能力。4.1.9 GA的性能評估 2在線和離線性能函數(shù) 2）離線性能函數(shù)（offline performance）：對于GA遺傳策略s，其離線性能其中，f(a*，t)maxf(al, t)，f(a2, t)，f(an, t)，即當前群體中最佳個體的適應值。該指標反映了群體中最佳個體適應值經(jīng)平滑處理后的變化情況，描述了個體的進化能力和GA的搜索能力。4.1.9 GA的性能評估 3最優(yōu)解搜索性能 GA用于函數(shù)優(yōu)化的目的就是發(fā)現(xiàn)問題的全局最優(yōu)解，所以通常采用當前群體發(fā)現(xiàn)的最佳可行解的改善情況作為度量GA搜索能力的基本指標。 4.2 遺傳算法的模式理論4.21 模式與模式空間位串上的某些

20、等位基因的聯(lián)結(jié)與適應值函數(shù)之間存在著某種聯(lián)系，這種聯(lián)系提供了尋優(yōu)過程的指導信息，引導著群體在位串空間中的移動方向。采用字符集K=0，1對問題參數(shù)進行二進制編碼，位串空間表示為SL1,0L，該空間的大小為|SL|2L。擴展字符集K0,1,*，其中*是通配符或無關(guān)符（wild cards，or“dont cares”），即可和0或 1匹配。擴展位串空間表示為SeL1,0,*L，該空間的大小為| SeL |3L，則稱SeL為SL的模式空間。顯然，包含2L個位串的位串空間，對應于3L個模式位串的模式空間。4.2 遺傳算法的模式理論4.21 模式與模式空間定義：擴展位串空間SeL0,1,*L中的任何一個

21、點H，稱為對應于位串空間 SL1,0L的一個模式（Schema）： 其中a(al，a2，aL)，H(H1，H2，HL)， ，i = 1，2，L； ， 例如：0 * * 1 0，1 * 1 * *，0 * * * *4.2 遺傳算法的模式理論4.21 模式與模式空間模式是由SL中具有共同特征的位串所組成的集合（對應于位串空間的子空間），它描述了該集合中位串上共同的基因特征。集合的大小N由模式中*的個數(shù)k決定，N=2k。例如：模式0 0 * *表示位串長度為4，兩個高位基因為00的位串集合，即0000，0001，0010，0011如果包含這一模式的所有位串都具有較好的適應度，則該模式可能是一個重要

22、的模式。Goldberg將模式稱為“超平面”（hyper plane），指出了模式在編碼空間上的幾何意義，模式包含的位串是編碼空間相應超平面上的點。模式 H1 = 1 * * * *表示函數(shù)解空間的右半?yún)^(qū)域模式 H2 = 0 * * * *表示函數(shù)解空間的左半?yún)^(qū)域Y = X2模式 H3 = * * * * 1表示函數(shù)解空間的陰影區(qū)域（奇數(shù)位串）模式 H4 = * * * * 0表示函數(shù)解空間的空白區(qū)域（偶數(shù)位串）模式 H5 = * * * 1 *表示函數(shù)解空間的陰影區(qū)域模式 H6 = * * * 0 *表示函數(shù)解空間的空白區(qū)域模式 H7 = 1 0 * * * 的表示域，代表了1/4的解空間模

23、式 H8 = * * 1 * 1 的表示域，代表了1/4的解空間4.2 遺傳算法的模式理論4.21 模式與模式空間模式的階（schema order）是指模式中所含有0、1確定基因位的個數(shù)，記作O(H)。模式的定義距（defining length）是指模式中從左到右第一個非 * 位和最后一位非 * 位之間的距離，記作模式的維數(shù)（schema dimension）是指模式中所包含的位串的個數(shù)，也稱為模式的容量，記作D(H)，D(H)=2L-O(H)。4.2 遺傳算法的模式理論4.21 模式與模式空間令m = m(H，t)為模式H在第t代群體中所含位串數(shù)量，模式在t代群體中包含的個體位串為a1,

24、 a2, ,am，稱為模式H在群體中的生存數(shù)量（survivals）或者采樣樣本（samples），(j = 1，2，m)，則模式H在第 t代群體中的適應值估計為即模式的適應值估計（簡稱模式的適應值）是群體中其所包含的全部個體的適應值的平均值。4.2 遺傳算法的模式理論4.21 模式與模式空間從編碼空間來看，m（H，t）是當前群體中包含屬于模式H的個體數(shù)量，反映了所對應的模式空間的分布情況，該數(shù)量越大說明群體搜索越集中于模式H代表的子空間。從模式空間來看，m（H，t）是模式H在當前群體中的個體采樣數(shù)量，反映了所對應的編碼空間的分布情況。該數(shù)量越大說明群體中的個體越趨向相似和一致，在編碼空間的搜

25、索范圍越小。 一個模式H由位串長度L、階O(H)、定義距 、容量D(H)和適應值f(H，t)等五個指標來描述。模式的引入為在一個有限字符集上定義的有限長度的位串之間的相似性度量和理論分析提供了有力的工具。4.2 遺傳算法的模式理論4.22 模式定理和積木塊假設 在選擇算子作用下，對于平均適應度高于群體平均適應度的模式，其樣本數(shù)將呈指數(shù)級增長：而對于平均適應度低于群體平均適應度的模式，其樣本數(shù)將呈指數(shù)級減少。在選擇和交叉算子作用下，模式定義距越小，則群體中該模式個體數(shù)量越容易呈指數(shù)級增長；模式定義距越大，則群體中該模式個體數(shù)量越不容易呈指數(shù)級增長。在變異算子作用下，階數(shù)越小模式H越易于生存；階數(shù)

26、越大，模式H越易于被破壞。 4.2 遺傳算法的模式理論4.22 模式定理和積木塊假設 模式定理：在遺傳算子選擇、交叉、變異的作用下，那些低階、定義距短的、超過群體平均適應度值的模式的生存數(shù)量，將隨著迭代次數(shù)的增加以指數(shù)規(guī)律增長。 模式定理的意義：統(tǒng)計決策中的雙臂賭機問題表明：按指數(shù)規(guī)律提高將硬幣投往平均支付高的賭機的概率，可以獲得最大的累積支付。應用到優(yōu)化問題則是：要獲得最優(yōu)的可行解，則必須保證較優(yōu)解的樣本數(shù)呈指數(shù)級增長。而模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的樣本數(shù)呈指數(shù)級增長，從而給出了遺傳算法的理論基礎。 4.2 遺傳算法的模式理論4.22 模式定理和積木塊假設 定義：具有低階、

27、短定義距以及高適應度的模式稱作積木塊。積木塊假設（building block hypothesis）：低階、短距高平均適應度的模式（積木塊）在遺傳算子作用下，相互結(jié)合，能生成高階、長距、高平均適應度的模式，并可最終生成全局最優(yōu)解。 4.2 遺傳算法的模式理論4.22 模式定理和積木塊假設 模式定理和積木塊假設比較準確地模擬了自然界的物種競爭和遺傳法則，其中模式定理描述了GA群體中模式之間的競爭關(guān)系，積木塊假設說明了有效基因之間的繼承與重組。因此，模式定理和積木塊假設構(gòu)成了關(guān)于GA進化過程能夠發(fā)現(xiàn)最優(yōu)解的一個解釋，被認為是解釋遺傳算法尋優(yōu)原理的較系統(tǒng)的理論，統(tǒng)稱為模式理論（schema the

28、ory）。它們也是GA進化動力學的基本理論，盡管還存在著不完善之處，但是它為深入研究遺傳算法的運行機理奠定了基礎。 4.2 遺傳算法的模式理論4.22 模式定理和積木塊假設 模式定理在一定程度上證明了標準遺傳算法的有效性，但它仍有以下的缺點：（1）模式定理只對二進制編碼適用，對其他編碼方案尚沒有相應的結(jié)論成立。（2）模式定理只給出了在下一代包含模式H的個體數(shù)的下限。我們無法據(jù)此推斷算法的收斂性。（3）模式定理沒有解決算法設計中控制參數(shù)選取等問題。4.2 遺傳算法的模式理論4.22 模式定理和積木塊假設 Bethke采用Walsh函數(shù)和一種巧妙的模式變換，提出了一種采用Walsh系數(shù)計算模式平均

29、適應度的有效分析方法，這使得在一些特定的適應度函數(shù)和編碼方式下，可以判定積木塊通過相互組合是否會產(chǎn)生最優(yōu)解或接近最優(yōu)解。Holland把Bethke的方法推廣到了當群體非均勻分布時的模式平均適應度分析上。 4.2 遺傳算法的模式理論4.3 騙問題 騙問題（deceptive Problem），即構(gòu)造一個問題，給定一些帶欺騙性質(zhì)的初始條件，“迷惑”遺傳算法，使其偏離全局最優(yōu)解。為此，要最大限度地違背積木塊假設，即使得低階、短距高于平均適應度的模式生成局部最優(yōu)點。由模式理論，一個問題能否用遺傳算法有效地求解，取決于問題編碼是否滿足積木塊假設，滿足者用遺傳算法求解效率較高，不滿足者效率 較低、甚至找

30、不到滿意解。 4.4 遺傳算法的高級實現(xiàn) 4.4.1 小生境遺傳算法生物總是傾向于與自己特征、性狀相類似的生物(同類)生活在一起，一般總是與同類交配繁衍后代。這種正選型交配方式在生物遺傳進化過程中是有其積極的作用的。生物學上，小生境(Niche)是指特定環(huán)境中一種組織(organism)的功能，而把有共同特性的組織稱作物種(species)。 4.4.1 小生境遺傳算法 4.4.1 小生境遺傳算法1基于預選擇機制的小生境技術(shù)1970年，Cavicchio率先在遺傳算法中引入了基于預選擇機制的小生境技術(shù)。只有在子串的適應度超過其父串的情況下，子串才能替換其父串，進入下一代群體。由于這種方式趨向于

31、替換與其本身相似的個體(父與子之間的性狀遺傳)，因而能夠較好地維持群體的分布特性。Cavicchio聲稱使用這種方法可以在群體規(guī)模相對較小的情況下維持較高的群體分布特性。4.4 小生境遺傳算法2基于排擠機制的小生境技術(shù)（ De Jong，1975年）(1)初始化;（建立初始群體，確定遺傳參數(shù)，設定排擠因子CF）(2)計算個體的適應度；(3)遺傳操作(選擇、交叉和變異)；(4)從當前群體中隨機選取群體規(guī)模的1CF個個體組成排擠因子成員(5)比較新產(chǎn)生的個體與排擠因子成員之間的相似性；(6)用新產(chǎn)生的個體去替換排擠因子成員中最相似的個體，形成新的當前群體；(7)如未滿足算法終止條件則返回第(2)步

32、，否則算法終止。 4.4 小生境遺傳算法3基于共享(sharing)機制的小生境技術(shù)（ Goldberg和Richardson， 1987年）定義了共享函數(shù)(sharing function)，用來確定每個個體在群體中的共享度。一個個體的共享度等于該個體與群體內(nèi)的各個其它個體之間的共享函數(shù)值的總和。共享函數(shù)是關(guān)于兩個體之間的關(guān)系密切程度(基因型的相似性或表現(xiàn)型的相似性)的函數(shù)，當個體間關(guān)系比較密切時，共享函數(shù)值較大，反之，則共享函數(shù)值較小。 4.4 小生境遺傳算法設dij表示個體i和個體j之間的關(guān)系密切程度，S為共享函數(shù)，Si表示個體i在群體中的共享度，則有： 在計算了各個體的共享度后，個體的適應度f(i)依據(jù)