種群規模對遺傳算法性能的影響

□文/劉曉霞 竇明鑫

（1.河北金融學院；2.中國地質大學長城學院 河北·保定）

引言

遺傳算法（GA）由美國Michigan大學的Holland教授于1975年首先提出，后經De Jong、GoldBerg等人改進推廣，廣泛應用于各類問題。它是一種模擬自然界生物進化過程與機制的全局概率優化搜索方法。在經典的遺傳算法中，種群的規模始終是固定不變的，這與實際的生物進化過程不符。在人類或其他生物進化的過程中，種群的規模的發展是有其一定的規律的，不可能固定不變。隨著人類或其他生物對環境的適應度的提高，種群的規模也在逐步調整。經典的遺傳算法采用固定的種群規模，使得種群不能根據其總體適應度來動態地調節其規模，不能很好解決全局收斂和收斂速度間的突出矛盾，在很大程度上影響了遺傳算法的收斂速度和解的質量。

本文主要通過實驗研究種群規模（PS）對遺傳算法性能:進化代數（EGN）、收斂時間（CT）和全局搜索能力（GSC）的影響。通過四個經典函數的測試，結果表明種群規模對遺傳算法各個性能的變化均有上升或下降的變化。

表1 測試函數定義

從直觀上看，當種群規模增大時，算法的計算時間，也就是收斂時間將會增大；而種群規模如果增大了，那么算法收斂到最優解的可能性就會增大，即全局搜索能力會增強；再者，當種群規模增大了，在解空間中搜索時，可以在相對較少的代數中找到最優解，那么進化代數也隨著種群規模的增大而變小了。

一、算法步驟

Step2.利用適應度函數來評價個體適應度；

Step3.若滿足收斂條件，則停止迭代并給出最優個體，否則進行下一步；

Step4.進行遺傳操作:

Step4.1.實行精英策略，保留本代一定比例的最優個體至下一代；

Step4.2.利用線性排序選擇方法進行選擇，采用兩點線性交叉，執行均勻變異操作。

表2 進化代數和種群規模的關系

二、測試函數

試驗所用的四個函數都是要找出他們的最大值。函數定義如表1。（表1）

三、實驗結果及分析

在以下試驗中，進化參數設置如下:對每個種群設置收斂精度為ε＝0.001，選擇概率為 Ps＝0.25，交叉概率為 Pc＝0.7，變異概率為 Pm＝0.05，f1、f3進化代數為 800，f2、f4最大進化代數為 2000。

1、收斂代數（EGN）和種群規模（PS）之間的關系如表2所示。（表2、圖1）從表2中可以看出進化代數隨著種群規模的增加而降低，但不同的函數具有不同的下降速率曲線，并且呈波動型下降，而不是單調的下降。尤其是對Rosenbrock函數f4來說，它的收斂代數波動幅度最大。

表3 進化時間和種群規模關系

2、收斂時間（CT）和種群規模（PS）之間的關系如表3所示。（表3）由表3可以看出收斂時間在開始階段下降，經過某個特定值之后，時間隨著種群規模的擴大而增加。

3、為了測試全局搜索能力和種群規模的關系，我們把算法分別獨立運行30次，得到全局最優解的總次數為k，利用k/30表示全局搜索能力。全局搜索能力（GSC）和種群規模（PS）的具體關系如表4所示。（表4）從表4可以看出，隨著種群規模的擴大全局搜索能力會增強，但可以看出也不是單調的。

表4 全局搜索能力和種群規模的關系

四、結論

在研究了種群規模對GA的進化代數（EGN）、收斂時間（CT）、全局搜索能力（GPS）的影響之后，我們可以得到如下結論:（1）當種群規模增大時，進化代數降低；（2）當種群規模增大時，全局搜索能力增強；（3）當種群規模增大時，收斂時間在初始階段會下降，而當種群達到某個規模后，收斂時間又會增加。同時，上述變化都不是單調增加或者減少的，而是隨著種群規模的增大，改變是波動或震蕩的；（4）對于四個不同的函數，各個性能的變化率都不相同，有不同的上升或下降速率，也就是說種群規模對算法性能影響的大小跟函數的選取也有關。

[1]李敏強，寇紀淞，林丹等.遺傳算法的基本理論與應用[M].北京:科學出版社，2004.

[2]王力，侯燕玲.基于遺傳算法通用試題庫系統研究 [J].微計算機信息，2008.5.3.

[3]王小平，曹立明.遺傳算法——理論、應用與軟件實現[M].西安:西安交通大學出版社，2002.