通信市場網--中國通信市場(CTM)權威信息發布門戶網站

進化算法常用于復雜函數的求解，這些算法在函數求解中的性能是不同的，而且每種進化算法中參數的設定對算法的效果起著至關重要的作用。本文中我們比較分析了兩種進化算法: 群體爬山算法(SoHC)和遺傳群體爬山算法(GSoHCs)。每種算法都是首先對適應度附初始值，對F7函數求解，根據這兩種算法的成功率，平均函數計算次數和平均最佳適應度對其進行性能比較，并根據試驗數據分析了參數設置對結果的影響。

第2部分描述用這兩種算法要解決的問題，第3部分介紹了這兩種算

法及其實施，第4部分描述了試驗參數的設置，第5部分展示了試驗

結果，并進行了分析，第6部分將這兩種算法的效率進行了比較。

2. 問題描述

該論文中，群體爬山算法 (SoHC)和遺傳群體爬山算法（GSoHCs）

都首先將適應度附初始值(23.30923) ，然后對F7 函數進行求解：

該問題允許的最多計算次數是4000，x值和y值在區間 [-100，

100]。顯然該目標函數是非常復雜的，所以不能僅僅用梯度下降或

者分析發現法來找到最優解，應用SoHC和GSoHCs來解決該問題,并

根據它們的成功率，平均最佳適應度來對其效率進行比較。

3.算法的實施

3.1. 群體爬山算法

3.1.1算法描述

爬山算法是一種局部擇優的方法，采用啟發式方法，　從當前的節

點開始，和周圍的鄰居節點的值進行比較。如果當前節點是最大

的，那么返回當前節點，作為最大值(既山峰最高點)；反之就用最高

的鄰居節點來替換當前節點，從而實現向山峰的高處攀爬的目的。如此循環直到達到最高，,是對深度優先搜索的一種改進，它利用反饋信息幫助生成解的決策，屬于人工智能算法的一種。

群體爬山法(SoHCs)是在1997年由Sebag和Schoenauer提出，是爬山算法和進化策略算法的結合，爬山者是由進化策略生成，該算法由(m+l)-EC 和一個repoussoir 組成，repoussoir是一個可適應的外部存儲器結構，用來“推動”搜索離開已知的局部最優解[1]。在該算法中，我們總共有6個參數，分別是μ， λ， M， R， α，T。

μ 代表爬山者個數，即種群大小

λ 代表生成的后代個數

M代表要變異的位數

R 代表最差適應度的百分比，用來生成平均最差適應度AvgWorst，以更新排斥子（repeller）

α 代表R組成部分的衰退率

T 錦標賽算法中選擇染色體進行變異的位數

在以上這些參數中，唯一的對歷史群體有意義的是M。

3.1.2.算法步驟

第1步初始化：種群大小是 m，應用隨機的方法生成第一代，用二進制碼代表值，所有值在范圍 [-100，100]之內，每位排斥子最初被賦值0.5 。

第2步生成后代:生成總共l 個后代，所以每一個父代將生成l/m個后代。采用錦標賽算法來選擇M位來變異父代以生成后代。錦標賽算法描述如下：

錦標賽函數有3個參數：m， Repoussoir和 T。從父代的二進制代碼串中隨機選擇T 位i1，i2…iT; 返回ik，滿足最小。這樣選擇的位將從1翻轉為0或從0翻轉為1。變異的位是 M。

第3步父代選擇:

現在我們總共有個個體。我們從中選擇 m個最好的個體，作為我們下一代的父代。

第4步替換 Repoussoir:

爬山者擁有一些前幾代的記憶-即下一代的排斥子。當得到新一代的時候，我們需要更新這些repoussoir 。首先從m+l 個個體中，選擇R% 個最差的個體，然后計算平均最差適應度。就如一個數組存儲著每個平均最差位數作為組件。公式排斥子將用來更新新的repoussoirs。

結果見表2。

3.2.遺傳群體爬山算法

3.2.1算法描述

遺傳群體爬山算法（GSoHCs）是遺傳算法和爬山算法的結合，與SoHC的唯一區別就是所有低于平均適應度的父代將通過和最優個體進行交叉來產生后代。因此，該算法有6個參數：μ， λ， M， R， α， T，并且我們將采用錦標賽算法來選擇用來進行變異的位（bits）生成后代。

3.2.2算法步驟

第1步初始化：每個個體有一個二進制編碼的x值和y值，每個變量被解碼成表現形以計算其適應度。表現形的個體介于[-100， 100]之間，通過這種方式，生成了最初的μ個父代。

計算初始群體的平均適應度，用以產生后代。每位排斥子最初被賦值0.5。

第2步生成后代:通過變異和交叉，從μ個父代生成λ個后代。所有高于平均適應度的父代通過變異生成后代，而低于平均適應度的個體則通過交叉生成后代。每個父代生成λ/μ個后代。

爬山變異應用錦標賽算法，首先，在所有的位中選擇T位，然后計算每個位和其對應的排斥子之間的差別，差別最小的M位將用來變異，也就是說，被變異的位將從0 翻轉為1。

用交叉算法生成后代，最優的種群個體被用來和另一個選出的種群個體交叉，每個生成的后代的位或者來自于最優的父個體，或者來自于均勻交叉或者隨機選取的父個體。

第3步選擇：最優的m個個體是從m個父個體和最新生成的l個后代中選取的。

第4步生成新的排斥子：

爬山者擁有以前幾代為下一代所用的排斥子存儲器， m 個父代和l個后代中選擇R% 個最差個體，每個位的平均值被分別計算。最差個體中每個位的平均值用來更新排斥子（repeller）。計算公式如下：。新生成的排斥子repeller將用來更新新的repoussoirs。

4. 試驗設置

比較這兩種進化算法，我們采用的是同樣的參數值，最后為每一種進化算法找到了一套最優的參數系列并得到最優結果。

⒈ m (群體大小):{2，12，30，50，100}。

⒉ l (后代大小 ):{4， 24，60，100，200}。

⒊ M(生成后代要變異的位的個數): {1，2， 5}。

⒋ R (最差適應度個體的百分數，用來生成平均最差適應度，為了更新排斥子（repeller）：{0.5}。

5. α (R 的組成部分的衰退率):{0.01，0.1，1.0}

6.T (錦標賽算法中選擇染色體進行變異的位數): {2，4，6}

這兩個函數的最大求值次數是4000。對每一套參數系列，函數都將運行100次來求結果，并計算成功率，平均函數求值次數，函數求值的標準偏差，平均最佳適應度和最佳適應度的標準偏差。

5.結果分析

結果表中，除了包含μ， λ， M， R， α， T等參數外(這些參數的含義在前面的小節都有介紹)，還包含以下這些數值，其含義如下:

S.R ：成功率Success Rate (%)

A.F.E ：平均函數求值次數Average number of Function Evaluations

S. F. E ：函數求值的標準偏差Standard deviation of Function Evaluations

A.B.F ：平均最佳適應度Average Best Fitness found

5.1. 群體爬山算法

根據實驗結果表，參數設置對群體爬山算法的結果影響如下:

l 群體大小m越大越能使下一代更加多樣化，我們設群體大小 m={2，12，30，50，100}。在表1中，當u 等于 50 或者100，最大的成功率是 58%。

l 參數M，從表1可以看出M具有非常重要的作用，當M 等于1 或者 2，性能優于M 等于5。如果僅僅比較當M 等于1 或者2的情況，如果群體大小是2，12，30 ，M 等于2稍優于M 等于1 的性能。當群體大小大于30時，從表3可以看出M 等于1 的性能稍優于M 等于2的性能。

l 在該算法中，參數α 對于成功率的影響不大，我們認為如果增加變異或交叉的位數，將會起作用。

l 參數T是變異的位數。T越大越有可能從同一個父代生成2個不同的后代。但在該算法中，T對成功率的影響并不大。

l 在所有的值中， m= 30，l = 60，M = 1， R = 0.5，a =1，T =2。成功率的最大值達到59%。在這些解中參數s 比參數m作用更大。

該測試所選用的位數是10。在測試了其他一些值之后，我們發現如果設置位數是5，將得到更好的結果。幾乎所有的參數都能達到100%的成功率，見表2的結果。

5.2.遺傳群體爬山算法 (GSoHCs)

實驗結果可從4個方面分析，例如群體大小，不同的T，不同的α，以及在基因型中的位數。在表 5中可以看出，群體大小越大，解就越好，顯然，群體大小越大，生成好的后代的幾率就越大。

從表5看出， T越大成功率越高。T是指選擇用來變異的位數。T越大，從父代生成2個不同的后代的可能性越大，也就是說，每一位能變異或交叉并且變異能朝著好的方向進展，正如生命的代與代的進化一樣。

起初，所有的結果都是在假使染色體的位數是10的基礎上進行的。盡管如此，10位并沒有提供一個好的結果。取染色體的位數為5，見表2，成功率為100%，并且函數求值次數也更小。從結果表看出，不同的T是導致染色體中越少的位數卻能產生更多地改進的染色體的原因。

6. 結論

當比較SoHC 和GSoHCs 的算法結果時，我們可看出這兩種算法的結果幾乎相同。 SoHC 能達到 59% 的成功率而GSoHCs能達到 56%。實際上，二者的唯一區別是，在 GSoHCs算法中，所有的適應度低于平均適應度的個體，用和最優的個體雜交的方法生成后代，但是SoHC算法，只是用變異率來變異后代。所以 GSoHCs會有更多的機率使后代多樣化。并且，錦標賽的大小在GSoHCs算法中起的作用比在SoHC中起的作用更大，所以我們認為如果增加染色體的位數，并且增加群體的大小(即染色體的個數)， GSoHCs算法的性能會優于算法SoHC。