進化算法的收斂速度的影響

1、進化算法的收斂速度的影響進化算法的收斂速度的影響張彩虹（數(shù)學與信息學院數(shù)學與應(yīng)用數(shù)學00級 5班）摘 要在進化過程中，可能會出現(xiàn)過早收斂現(xiàn)象，這主要是因為種群中出現(xiàn)了超級個體，按照一定的選擇策略，該個體很快會在種群中占據(jù)絕對優(yōu)勢，從而使算法過早的收斂于一個局部的最優(yōu)解，現(xiàn)在解決的方法有對超級個體的適應(yīng)函數(shù)進行調(diào)整，從而控制該個體的選擇概率，或增加個體的變異率來增加種群的多樣性。同時，不同的群體規(guī)模和選擇策略對算法性能的影響起到舉足輕重作用。關(guān)鍵詞：進化算法；過早收斂；適應(yīng)函數(shù)；變異率；選擇策略1 引言進化算法的思想來源于達爾文的“適者生存”的理論，其最大特點是群體搜索和群體中個體之間的信息交換

2、，從而表現(xiàn)出以下優(yōu)越性：進化算法在搜索過程中不易陷入局部最優(yōu)，即使所定義的函數(shù)不連續(xù)、不規(guī)則或有噪聲時，仍能以很大概率得到全局最優(yōu)解；進化算法具有內(nèi)在的并行性；再者，進化算法采用自然進化機制來表現(xiàn)復雜現(xiàn)象，能快速可靠地解決非常困難的問題；易介入到已有模型中且易于同別的技術(shù)混合等。因此，進化算法，目前在很多領(lǐng)域得到了廣泛應(yīng)用。現(xiàn)在對進化算法的一些基本概念進行一下簡單介紹 2 。進化計算在求解問題時是從初始給定的多個解開始搜索的，這些初始解的集合稱為一個種群。適應(yīng)值函數(shù)是種群中各個個體對各自適應(yīng)環(huán)境的程度的一種量度， 它通常是用戶所提供的目標函數(shù)的一個合理的數(shù)學變換，而目標函數(shù)用能反映個體在種群中

3、優(yōu)劣程度的數(shù)學表達式表示。選擇是決定以一定的概率從種群中選取若干對個體的操作。 變異是指讓遺傳因子以一定的概率變化的操作。在通常的二進制編碼方式下，變異操作只是簡單的將因子之值取反，即將“ 0”變?yōu)椤?1”，將“ 1”變?yōu)椤?0”。進化算法是一種基于自然選擇和遺傳變異等生物進化機制的全局性概率搜索方法。它從選定的初始解出發(fā)，通過不斷迭代逐步改進當前解，直至最后搜索到最優(yōu)解或滿意解。優(yōu)化問題采用進化計算求解的一般過程包括以下幾步：1) 隨機給定一組初始解 ;2) 評價當前這組解的性能；3) 根據(jù)第二步的評價結(jié)果，從當前解中選擇一定數(shù)量的解作為基因操作的對象；4) 對所選擇的解進行基因操作例如交叉

4、或變異，得到一組新的解；5) 返回到第二步，對該組新的解進行評價；6) 若當前解滿足要求或進化過程達到一定代數(shù)，計算結(jié)束，否則轉(zhuǎn)向第三步繼續(xù)循環(huán)。1進化算法的收斂速度的影響遺傳算法自從誕生以后，已經(jīng)在各個領(lǐng)域中得到了廣泛的應(yīng)用，但是遺傳算法在應(yīng)用過程中，也暴露出了許多缺點。在進化過程中，可能會出現(xiàn)過早收斂問題，當通過染色體的交叉和變異，種群已經(jīng)很難產(chǎn)生優(yōu)于親本的子代個體時，就會發(fā)生早熟收斂。在均勻種群中經(jīng)常發(fā)生這種情況，所有標準形式的交叉簡單地重復產(chǎn)生當前的親本。進一步優(yōu)化將完全依賴于位變異而且可能非常慢。在遺傳算法中，經(jīng)常會遇到早熟收斂，因伴隨著交叉和選擇的作用，觀察到的最優(yōu)個體就會以指數(shù)速

5、度繁殖，該個體很快占據(jù)種群的大部分。對于早熟的原因，大至可以歸結(jié)如下類型1 ：2 群體規(guī)模群體規(guī)模與很多因素有關(guān)，當群體規(guī)模太小時，造成有效等位基因先天缺乏，即使采用較大概率的變異算子，生成具有競爭力的高階模式的可能性極小，況且大概率變異算子對已有模式的破壞作用顯著增大。同時，由于遺傳算子存在隨機誤差（模式采樣誤差），妨礙小群體中有效模式的正確傳播，使得群體進化不能按模式定理產(chǎn)生所預測的期望數(shù)量。根據(jù)模式理論和隱并行性，群體規(guī)模越大，遺傳算子所處理的模式就越多，生成有意義的建筑模塊并逐漸進化為最優(yōu)解的機會就越高，同時，群體規(guī)模越大，群體中個體的多樣性越好，算法陷入局部解的危險就越小，但是，群體

6、規(guī)模增大，個體適應(yīng)值計算與評估計算次數(shù)增加，計算量也隨著增加，算法效率會降低。因此，為防止過早收斂，應(yīng)該選擇合適的群體規(guī)模，在計算量許可的情況下，盡量選擇較大規(guī)模的群體，保證群體的多樣性及其進化能力，如果采用可變規(guī)模群體，初始階段應(yīng)將群體規(guī)模保持在一個較大數(shù)值。3 適應(yīng)值函數(shù) 2在我們設(shè)計的進化算法中，物種規(guī)模一般都在幾十到幾百之間，與實際物種規(guī)模相比是很小的，一方面，如果個體繁殖量調(diào)節(jié)得不好，很容易出現(xiàn)超級個體，即該個體的適應(yīng)值 fi 大大超過群體的平均適應(yīng)值f i / N ，這樣很容易導致算法過早收斂于一個局部最優(yōu)點；另一方面，在搜索的后期，群體的平均適應(yīng)值，可能會接近群體的最優(yōu)適應(yīng)值，這

7、樣群體中實際上已不存在競爭，使搜索目標難以得到改善，出現(xiàn)停滯現(xiàn)象。這些現(xiàn)象和結(jié)果不利于優(yōu)化，可能導致一些異常個體在群體中占據(jù)很大的比例，這是我們所不期望的現(xiàn)象，因為這樣可能導致未成熟的收斂現(xiàn)象。因為如果這些異常個體競爭力太突出，那么會控制選擇過程，從而影響算法的全局優(yōu)化性能。在算法運行的初始階段，群體中可能存在少數(shù)適應(yīng)值很高的個體，若使用基于適應(yīng)值的概率選擇方法，這些個體就會被大量繁殖，從而在群體中占有很大的比重。而適應(yīng)值很低的個體在群體中過早地被淘汰，造成群體多樣性急劇下降。這樣可導致群體前收斂，或者將搜索引向局部極值點。在后期階段，在采用一定的變異概率的變異算子的作用下，群體保持了相對穩(wěn)定

8、的多樣性，對于最優(yōu)解附近變化比較平緩的適應(yīng)值差異變得比較小，個體被選中的概率幾乎相同，選擇漸近為隨機過程，群體性能在很長的代數(shù)內(nèi)得不到顯著改進。因此，有必要對適應(yīng)函數(shù)進行針對性的調(diào)整，或者減少個體選擇概率的差異即降低選擇壓力，或者增大個體選擇概率的差異，即提高選擇壓力，統(tǒng)稱為適應(yīng)值標度變換。適應(yīng)值調(diào)整可以保持群體中個體間存在一定程度的競爭， 從而促進所期望的群體進化過程。適應(yīng)值調(diào)整的方法以有以下幾種：2進化算法的收斂速度的影響3.1 線性變換 1線性適應(yīng)值標度變換的一般公式為：f 'afb其中， f 為適應(yīng)函數(shù)值， f ' 為變換后適應(yīng)函數(shù)值， a, b為系數(shù)。一般要求滿足ff

9、 ，即變換前后群體的平均適應(yīng)值相等。在實際應(yīng)用中，噪聲變換后當前群體中最佳個體的適應(yīng)值設(shè)為f max'c f , c 1.2-2.0( 經(jīng)驗值 ),則由 f max'af maxb, fa fb 聯(lián)合求解得出 :a(c1)f ,bf maxc fff maxff maxf對于適應(yīng)值比較低的個體，若f '0，則取 f '0 ，那么變換后的個體選擇概率：'f j'af jbaf jbaf j bbp jmmap jf i 'af i 'nbn(a fb)n fn fi 1i1若取 cf max/ f，則 b0, a1, p'j

10、p j個體選擇概率保持不變，另外， Forrest推出了采用當前群體適應(yīng)值標準方差進行變換的方法3：ff( fc)其中， c 根據(jù)經(jīng)驗確定，使得f0，為群體適應(yīng)值標準方差。3.2冪函數(shù)變換 1冪函數(shù)變換的公式為：ffk其中， k 依賴于具體問題性質(zhì)和遺傳算法性能控制選擇變換后個體的選擇概率：f j'f jkf jk 1f jk 1f jp jp 'jnnnf maxf i'f ikk 1f if maxn 1n 1n 1顯然， pmax'pmax ，即當前群體最佳個體的選擇概率是增大。3.3 指函數(shù)變換 1指函數(shù)變換的公式為：3進化算法的收斂速度的影響fe f其

11、中，0 依賴于具體問題性質(zhì)和遺傳算法性能控制選擇，當前群體最佳個體的選擇概率隨著0 變化而變化。對于具體的適應(yīng)函數(shù)，當比較小時，當前群體最佳個體的選擇概率減少；當比較大時，當前群體最佳個體的選擇概率增大。4. 選擇算子 2選擇策略對算法性能的影響起舉足輕重的作用，不同的選擇策略將導致不同的選擇壓力，即下一代中父代個體的復制數(shù)目的不同分配關(guān)系。較大的選擇壓力使最優(yōu)個體具有較高的復制數(shù)目，從而使得算法的收斂速度較快，但容易出現(xiàn)過早收斂現(xiàn)象。相對而言，較小的選擇壓力一般能使群體保持足夠的多樣性，從而增加了算法收斂到全局最優(yōu)的概率，但算法的收斂速度較慢。所以為了防止出現(xiàn)早熟收斂的現(xiàn)象，需要選擇一種適當

12、的選擇策略。下面是幾種常用的選擇策略：4.1 基于適應(yīng)值比例的選擇適應(yīng)度比例法又稱旋輪線模型或蒙特卡羅模型 , 這個模型是利用比例于各個個體適應(yīng)度的概率決定其子孫的遺留可能性。 若某個個體 I, 以各自的選擇被選取的概率已表示為 :Nps f i /f ii1其中 , fi 為個體 I 的適應(yīng)度 .表 1 給出用適應(yīng)度比例法表示和選擇概率的例子。表中 , F 表示原適應(yīng)度 , F 2 表示調(diào)整后的適應(yīng)度 , ps 采用表示選擇概率 , 表中采用的比率 k2 。當選擇的概率約定后，產(chǎn)生 0-1 區(qū)間的隨機數(shù)， 以決定哪些個體要進行交配。 一般地，選擇概率大的個體希望多次參加交配，它的遺傳因子就會

13、在群體中擴大。表 1 適應(yīng)度比例法表示和選擇概率的示例個體FF2PS12.56.250.1821.01.000.0333.010.000.2641.21.440.0452.14.410.1360.80.640.0272.56.250.1881.31.690.054進化算法的收斂速度的影響90.90.810.02101.83.240.09適應(yīng)度比例法的一種最典型且使用最多的方法是轉(zhuǎn)盤式選擇, 實施該策略的步驟是 :a.計算個體的相對適應(yīng)值relif i；f ib.根據(jù)選擇概率 reli , I1,2,.,N 把一個圓盤分式 N 份，其中第 I 扇形的半分角為2 reli ；c.針對 i 個體計算

14、從 1 到第 i 個個體的累計相對適應(yīng)值 pi reli rel 2. reli ；d.產(chǎn)生 0 ， 1 內(nèi)的隨機數(shù)，滿足 p(i 1)pi ，則選擇個體 i ；轉(zhuǎn)盤式選擇使得種群中各個體都有機會根據(jù)其相對適應(yīng)值被選中。4.2 基于排名的選擇使用基于適應(yīng)值比例的選擇常常會出現(xiàn)過早收斂現(xiàn)象或停滯現(xiàn)象 . 避免這種現(xiàn)象的方法之一是使用基于排名的選擇策略 . 這種方法的基本思想是 :I首先根據(jù)個體i 的相對適應(yīng)值在種群中的排名來分配其選擇概率pi . 這種“分配”是基于數(shù)學方法的。II 然后再根據(jù)這個概率使用輪盤策略， 這樣個體的絕對適應(yīng)值并不直接影響后代的數(shù)量，人們可以使用各種不同的數(shù)學“分配”方

15、法來調(diào)節(jié)個體選擇概率，以達到防止或減少過早收斂和停滯的現(xiàn)象。表 2 給出了基于排名的選擇策略中適應(yīng)值和選擇概率的關(guān)系的一個例子。由此表可見，所有個體按適應(yīng)度大小排序， 因而選擇概率和適應(yīng)度無直接關(guān)系， 而僅與序號有關(guān)。這種方法的不足之外在于選擇概率和序號的關(guān)系須事先確定。此外，它和適應(yīng)度比例方法一樣都是一種基于概率的選擇，所以仍有統(tǒng)計誤差。表 2基于排序的選擇方法的示例序號個體FF 2ps133.010.000.35212.56.250.20372.56.250.15452.14.410.105101.83.240.06681.31.690.05741.21.440.045進化算法的收斂速度的

16、影響821.01.000.03990.90.810.021060.80.640.001基于排名選擇策略的優(yōu)點 : 一是可以避免出現(xiàn)過早收斂現(xiàn)象或停滯現(xiàn)象 ; 二是無論對極小化和極大化的問題 , 它都不需要進行適應(yīng)值的標準化和調(diào)整 , 可以直接使用原始適應(yīng)值進行排名選擇。4.3 基于局部競爭機制的選擇?；谶@種思想的典型選擇方法是錦標賽選擇，其基本做法是：在選擇時先隨機的在種群中選擇 k 個個體進行錦標賽式的比較，從中選出適應(yīng)值最好的個體進入下一代，復用這種方法進行直到下一代個體數(shù)為種群規(guī)模時為止。 這種方法也使得適應(yīng)值好的個體在下一代具有較大的 “生存”機會，同時它只能使用適應(yīng)值的相對值作為選

17、擇的標準，而與適應(yīng)值的數(shù)值大小不成直接比例，所以，它能較好的避免超級個體的影響，一定程度的避免過早收斂現(xiàn)象和停滯現(xiàn)象。4.4 精華保存法上述 3 種選擇法都是基于概率的選擇， 概率選擇法的優(yōu)點在于對適應(yīng)度低的個體也給予選擇的機會，能維持群體的多樣性。另一方面，即使適應(yīng)度高的個體也有被淘汰的可能，這是概率選擇的缺點。為彌補概率選擇法上述不足，常常采用精華保存法。這種方法，在現(xiàn)世代適應(yīng)度大的個體不是受交叉和突然變異的影響，而是無條件留給下一代，這種方法常被用于最優(yōu)化問題。在選擇算子后保留當前最好解的 SGA能認概率收斂到全局最優(yōu)解。Michalewicz 4 在擁擠因子模型的基礎(chǔ)上提出了一種新的選

18、擇算子。這種算子在進行選擇時需要有兩個步驟：第一步，先從種群中選擇r 個個體作為父代個體（不要求數(shù)目一定是r 個，可以小于 r 個），然后再從種群中選擇 r 個個體（要求數(shù)目一定是 r 個），將這 r 個個體從種群中剔除。選擇基于個體的適應(yīng)值：適應(yīng)值越大的個體被選擇作為父代個體的概率越大，適應(yīng)值越小的個體被選擇從種群中剔除的概率越大。在進行完第一步后，各群的個體被分三類：（1） r 個（不嚴格）作為父代的個體；（2） r 個（嚴格）被剔除的個體；（3）剩余的個體，稱為“中性”個體。第二步，生成下一代個體。下一代個體由兩部分組成，一部分是Nr 個原有的個體（上一代個體除去r 個被剔除的個體），另

19、一部分是由父代個體新生成的r 個個體。Michalewicz 把使用這種選擇算子的算法稱為modGA，圖 3 給出 modGA 的算法流程。Begint0 ；初始化 P(t)計算 P(t ) 的適應(yīng)值；While （不滿足終止條件時）6進化算法的收斂速度的影響B(tài)egintt1;從 P(t 1) 中選擇父代個體；從 P(t 1) 中選擇被剔除的個體；生成 P(t ) ；計算 P(t ) 的適應(yīng)值；endend圖 3 modGA 的算法流程從上面的描述中可以發(fā)現(xiàn)，這種選擇方法存在一個病態(tài)問題： r 個（不嚴格）作為父代的個體集合和 r 個（嚴格）被剔除的個體集合有可能出現(xiàn)相重疊的情況。 也就是說，

20、個體 p 有可能既被選作父代個體，又被選作剔除的個體。顯然，我們希望具有較高適應(yīng)值的個體被剔除的概率很小，那么，我們就可以通過修改p(t1) 的生成方法來解決這個問題：第一步：從 P(t) 中選擇 r 個（不嚴格）父代個體，每個被選擇的個體被標記為可以用于某一種固定的遺傳算子；第二步：從 P(t) 中選擇 Nr 個（嚴格）個體，將它們復制到P(t1) 中；第三步：從 r 個（不嚴格）父代個體中成生r 個（嚴格）后代；第四步：將新生成的r 個（嚴格）后代插入到P(t1) 。第一步和第二步中的選擇是根據(jù)個體的適應(yīng)值進行的。ModGA 中的選擇方法與前面所介紹的其他一些選擇方法存在一些重要的不同之處

21、。首先，父代個體和子代個體都有可能出現(xiàn)在后一代中。在第一步和第二步的選擇中，一個個體既有可能被選擇成為r 個（不嚴格）父代個體之一，又有可能被選擇成為下一代個體之一，其次，所有算子都直接作用于個體上。在第一步中，一些個體被標記為 “變異”，一些個體被標記為“交叉” 。在第四步中對標記為“變異”的個體進行變異，對標記為“交叉”的個體進行交叉。Michalewicz 證明了這種選擇方案使得模式定理仍然成立。 ModGA 的優(yōu)點在于它能夠更有效地利用存儲空間：這種算法減少了適應(yīng)值高的個體產(chǎn)生多個相同后代的概率。在 ModGA 中，一個適應(yīng)值高的個體可能會有多個后代，但每個后代都不完全相同， GA 正

22、是由于適應(yīng)值高的個體容易產(chǎn)生多個相同的后代才導致了早熟收斂，所以這種方法可以降低早熟收斂的概率。5. 變異概率7進化算法的收斂速度的影響當變異概率比較小時 ,群體多樣性下降太快 ,容易導致有效基因的迅速丟失且難以恢復 ;當變異概率比較大時 ,盡管群體的多樣性可以保持在較高水平 ,但是高階模式被破壞的概率也隨之增大 .5.1 自適應(yīng)變異率的設(shè)計在簡單遺傳算法中 ,變異率是個常數(shù)。 通常，對于變異率是一常量的情況， 經(jīng)過多次迭代后，群體的素質(zhì)會趨于一致，這樣就形成了“近親繁殖” ，但近親繁殖對后代的質(zhì)量不利。同樣，如果雙親的染色體非常接近，其后代對于雙親素質(zhì)提高也極少。因此，群體基因的多樣性變差不

23、僅會減慢進化歷程，而且可能導致進化停滯，過早收斂于非最優(yōu)解。這里提出一種 Pm 與父串間相對距離成反比、 隨迭代率（迭代次數(shù)與最大迭代次數(shù)的比值）指數(shù)下降的自適應(yīng)變化的方式。具體公式設(shè)計如下：Pmaxexp(t ) (1R ) PmPminPmt maxRmaxPmin式中： Pmin 、 Pmax 分別為最大和最小變異率；t,tmax 分別為迭代次數(shù)和最大迭代次數(shù)；R, Rmax 分別為父串間的歐式距離和最大歐式距離。這種方法在群體中各個個體過分趨于一致時，會使變異的可能性增加，從而提高群體的多樣性，增強算法維持搜索的能力； 而在群體的多樣性已經(jīng)很強時， 則減小變異率，以免破壞優(yōu)良個體。 這

24、種方法同樣能夠保證在迭代初期， 對劣質(zhì)個體賦予較大的變異率，以造成足夠的擾動， 擴大解空間，而隨著迭代次數(shù)的增加， 該變異率逐步減少至一常量，從而保證平滑收斂。這是符合優(yōu)勝劣汰規(guī)律的；同時，為了防止發(fā)生局部收斂和出現(xiàn)隨機搜索，在整個迭代過程中，將變異率控制在 0.01-0.45 之間，即選取 Pmax 0.45, Pmin 0.01。6 結(jié)束語本文通過研究影響進化算法收斂速度的因素 , 從群體規(guī)模，適應(yīng)值函數(shù)，選擇算子以及變異概率等方面找出了影響過早收斂的原因 , 并在此基礎(chǔ)上根據(jù)各個因素找到了一些解決過早收斂的方法，為將來進一步研究奠定了基礎(chǔ)。參考文獻1 李敏強 . 林丹等 . 遺傳算法的基

25、本理論與應(yīng)用 . 科學出版社， 2002.32 李陶深 . 人工智能 . 重慶大學出版社 2002.43 王正志 , 薄濤 . 進化算法 . 國防科技大學出版社， 2000.114Michalewicz,Z.,GeneticAlgorithms+DataStructure=Evolutionaryprograms,Springer-Verlag, Berlin, Heideberg, 2nd Edition,1994.8進化算法的收斂速度的影響The influence on the convergence speed of evolutionaryalgorithmsZhang caihong(Class 5, Grade 200