第三章 遺傳算法的理論基礎

#被淘汰，有害的基因可能被保留。引起群體結(jié)構(gòu)發(fā)生變化的主要因素是隨機波動的——遺傳漂移，它也是產(chǎn)生未成熟收斂的一個主要原因。對此可以采用增大群體容量的方法來減緩遺傳漂移，但這樣做可能導致算法效率的降低。上述三個方面都有可能產(chǎn)生未成熟收斂現(xiàn)象，即群體中個體的多樣性過早地丟失，從而使算法陷入局部最優(yōu)點。在遺傳算法處理過程的每個環(huán)節(jié)都有可能導入未成熟收斂的因素。遺傳算法未成熟收斂產(chǎn)生的主要原因是，在迭代過程中，未得到最優(yōu)解或滿意解以前，群體就失去了多樣性。具體表現(xiàn)在以下幾個方面：在進化初始階段，生成了具有很高適應度的個體X。在基于適應度比例的選擇下，其它個體被淘汰，大部分個體與X一致。相同的兩個個體進行交叉，從而未能生成新個體。通過變異所生成的個體適應度高但數(shù)量少，所以被淘汰的概率很大。群體中的大部分個體都處于與X一致的狀態(tài)。3.4.2未成熟收斂的防止在分析了未成熟收斂產(chǎn)生的原因后，下面要解決的是如何防止該現(xiàn)象的發(fā)生，即如何維持群體多樣性以保證在尋找到最優(yōu)解或滿意解以前，不會發(fā)生未成熟收斂現(xiàn)象。解決的方法有以下幾種。1．重新啟動法這是實際應用中最早出現(xiàn)的方法之一。在遺傳算法搜索中碰到未成熟收斂問題而不能繼續(xù)時，則隨機選擇一組初始值重新進行遺傳算法操作。假設每次執(zhí)行遺傳算法后陷入不成熟收斂的概率為Q(0冬Q<1)，那么做n次獨立的遺傳算法操作后，可避免未成熟收斂的概率為F(n)二1-Qn，隨著n的增大，F(xiàn)(n)將趨于1。但是，對于Q較大的情況，如果優(yōu)化對象很復雜以及每次執(zhí)行時間都很長的情況，采用該辦法顯然是不合適的。配對策略(MatingStrategies)為了維持群體的多樣性，可以有目的地選擇配對個體。一般情況下，在物種的形成過程中要考慮配對策略，以防止根本不相似的個體進行配對。因為在生物界，不同種族之間一般是不會雜交的，這是因為它們的基因結(jié)構(gòu)不同，會發(fā)生互斥作用，同時雜交后會使種族失去其優(yōu)良特性。因此，配對受到限制，即大多數(shù)是同種或近種相配，以使一個種族的優(yōu)良特性得以保存和發(fā)揚。然而，這里所說的匹配策略有不同的目的。其目的是，由不同的父輩產(chǎn)生的個體試圖比其父輩更具有多樣性，Goldberg的共享函數(shù)(SharingFunction)就是一種間接匹配策略。該策略對生物種(Species)內(nèi)的相互匹配或至少對占統(tǒng)治地位的物種內(nèi)的相互匹配有一定限制。Eshelman提出了一種可以更直接地防止相似個體交配的方法——防止亂倫機制(IncestPreventionMechanism)。參與交配的個體是隨機配對的，但只有當參與配對的個體間的海明距離超過一定閾值時，才允許它們進行交配。最初的閾值可采用初始群體海明距離的期望平均值，隨著迭代過程的發(fā)展，閾值可以逐步減小。盡管Eshelman的方法并不能明顯地阻止同輩或相似父輩之間進行交配，但只要個體相似，它就有一定的影響。匹配策略是對具有一定差異的個體進行配對，這在某種程度上可以維持群體的多樣性。但它同時也具有一定的副作用，即交叉操作會使較多的模板遭到破壞，只有較少的共享模板得以保留。重組策略(RecombinationStrategies)重組策略就是使用交叉算子。在某種程度上，交叉操作試圖產(chǎn)生與其父輩不同的個體，從而使產(chǎn)生的群體更具多樣性。能使交叉操作更具有活力的最簡單的方法就是，增加其使用的頻率和使用動態(tài)改變適應度函數(shù)的方法，如共享函數(shù)方法。另一種方法是把交叉點選在個體的具有不同值的位上。只要父輩個體至少有兩位不同，所產(chǎn)生的子代個體就會與其父輩不相同。維持群體多樣性的更基本的方法是，使用更具有破壞性的交叉算子，如均勻交叉算子。該算子試圖交叉近一半的不同位，因而保留的模板比單點或兩點交叉所保留的模板要少得多?？傊?，重組策略主要是從使用頻率和交叉點兩方面考慮，來維持群體的多樣性。這對采用隨機選擇配對個體進行交叉操作可能有特定的意義，但對成比例選擇方式，其效果則不一定明顯。4替代策略(ReplacementStrategies)匹配策略和重組策略分別是在選擇、交叉階段，通過某種策略來維持群體的多樣性。而替代策略是確定在選擇、交叉產(chǎn)生的個體中，選擇哪一個個體進入新一代群體。DeJong采用排擠(Crowding)模式，用新產(chǎn)生的個體去替換父輩中類似的個體。Syscuda和Whiteley也采用類似的方法，他們僅把與父輩各個個體均不相似的新個體添加到群體中。這種替換策略僅從維持群體的多樣性出發(fā)，存在一定的負面影響，即交叉操作會破壞較多模板，但這種影響比前兩種策略的要少。性能評估遺傳算法的實現(xiàn)涉及到它的五個要素：參數(shù)編碼、初始群體的設定、適應度函數(shù)的設計、遺傳操作設計和控制參數(shù)設定，而每個要素又對應不同的環(huán)境，存在各種相應的設計策略和方法。不同的策略和方法決定了各自的遺傳算法具有不同的性能或特征。因此，評估遺傳算法的性能對于研究和應用遺傳算法是十分重要的。目前，遺傳算法的評估指標大多采用適應度值。特別在沒有具體要求的情況下，一般采用各代中最優(yōu)個體的適應度值和群體的平均適應度值。以此為依據(jù)，DeJong提出了兩個用于定量分析遺傳算法的測度:離線性能(Off-linePerformance)測度和在線性能(On-linePerformance)測度，得到兩個評估準則。1．在線性能評估準則定義3?8設X(s)為環(huán)境e下策略s的在線性能，f(t)為時刻t或第t代中相應于環(huán)境eee的目標函數(shù)或平均適應度函數(shù)，則X(s)可以表示為eX(s)二1丈f(t)(3.9)eTet=1式(3.9)表明，在線性能可以用從第一代到當前的優(yōu)化進程的平均值來表示。2．離線性能評估準則定義3?9設X*(s)為環(huán)境e下策略s的離線性能，則有e1TX*(s)=工f*(t)(3.10)eTet=1式中，f*(t)=best{f(1),f(2),f(t)}。eeee式(3.10)表明，離線性能是特定時刻或特定代的最佳性能的累積平均。具體地說，在進化過程中，每進化一代就統(tǒng)計目前為止的各代中的最佳適應度或最佳平均適應度，并計算對進化代數(shù)的平均值。DeJong指出：離線性能用于測量算法的收斂性，在應用時，優(yōu)化問題的求解可以得到模

擬，在一定的優(yōu)化進程停止準則下，當前最好的解可以被保存和利用；而在線性能用于測量算法的動態(tài)性能，在應用時，優(yōu)化問題的求解必須通過真實的實驗在線實現(xiàn)，可以迅速得到較好的優(yōu)化結(jié)果。但是，從遺傳算法的運行機理可知，在遺傳算子的作用下，群體的平均適應度呈現(xiàn)增長的趨勢，因此，定義3.8和定義3.9中的f(t)和f*(t)相差不大，它們所反映ee的性質(zhì)也基本一樣。下面以最優(yōu)化方法的收斂速度和收斂準則來討論遺傳算法的性能。一般優(yōu)化問題可描述為求x二(x,x,,x)t，使/(x)達到最小(或最大)。最優(yōu)化方法12n通常采用迭代方法求它的最優(yōu)解，其基本思想為：給定一個初始點x，按照某一迭代規(guī)則產(chǎn)0生一個點列｛x｝，使得當｛x｝為有窮點列時，其最后一個點是最優(yōu)化問題的最優(yōu)解。當｛x｝是iii無窮點列時，它有極限點，且其極限點是最優(yōu)化問題的最優(yōu)解。一個好的優(yōu)化算法為：當x能i穩(wěn)定地接近全局極小點(或極大點)的鄰域時，迅速收斂于x*，當滿足給定的收斂準則時，迭代終止。假設一算法產(chǎn)生的迭代點列｛x｝在某種范數(shù)意義下收斂，即ilim卜-x=0(3.11)is1式中，x=x+a，a為步長因子。i+1iii若存在實數(shù)a>0及一個與迭代次數(shù)無關(guān)的常數(shù)q>0，使得limis(3.12)limis(3.12)則稱此算法產(chǎn)生的迭代點列｛x｝具有q-a階收斂速度(a為迭代步長因子)。因為||x-x||ii+1i是代-x*||的一個估計，所以在實際中，一般用比+]-x||代替卜廠x*||，作為迭代終止判決條件。當a=1，q>0時，稱｛x｝具有q線性收斂速度。i當1<a<2，q>0或1，q=0時，稱｛x｝具有q超線性收斂速度。i當a=2時，稱｛x｝具有q二階收斂速度。i具有超線性收斂速度和二階收斂速度的迭代算法的收斂速度比較快。關(guān)于算法的終止準則，實際應用中可以使用各種不同的方法進行確定。Himmeblau提出了下面的終止準則。當||x』>e和|f(x」>e時，采用

x-xx-x—i+1iXi<￡(3.13)否則采用|x-X|<￡或If(X)-f(X)|<￡(3.14)i+1ii+1i式中，￡為根據(jù)實際問題要求精度給出的適當小的正數(shù)。根據(jù)以上Himmeblau提出的終止準則，實際中可以用各代適應度函數(shù)的均值之差來衡量遺傳算法的收斂特性。定義收斂性測量函數(shù)為：C(s)二[￡[f(t+1)-f(t)](3.15)eTeet=1式中，f'(t)為時刻t或第t代中相應于環(huán)境e的目標函數(shù)或平均適應度函數(shù)。e從優(yōu)化問題中尋找最優(yōu)解或最優(yōu)解組的角度考慮，可以定義部分在線特性：f(s)=1丈f'e(t)(3.16)nTet=1式中，f'e(t)為群體中對應于最優(yōu)解或最優(yōu)解組的個體適應度的均值。小生境技術(shù)和共享函數(shù)Cavicchio提出只有在子串的適應度超過父代的情況下，子串才能替代父串進入下一代群體的預選擇機制，該機制趨向于替換與其本身相似的個體，能夠維持群體的分布特性，并且不斷地以優(yōu)秀個體來更新種群，使種群不斷被優(yōu)化。DeJong提出基于排擠的機制，其思想來源于一個有趣的生物現(xiàn)象：在一個有限的生存空間中，各種不同的生物為了延續(xù)生存，必須相互競爭各種有限的生存資源。差別較大的個體由于生活習性不同而很少競爭。處于平衡狀態(tài)的大小固定的種群，新生個體將代替與之相似的舊個體。排擠機制可以維護當前種群的多樣性，排擠機制用海明距離來度量個體之間的相似性。這就是小生境技術(shù)。Glodberg和Richardson利用共享函數(shù)來度量兩個個體