種群規(guī)模對(duì)遺傳算法性能的影響

□文/劉曉霞 竇明鑫

（1.河北金融學(xué)院；2.中國地質(zhì)大學(xué)長(zhǎng)城學(xué)院 河北·保定）

引言

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

本文主要通過實(shí)驗(yàn)研究種群規(guī)模（PS）對(duì)遺傳算法性能:進(jìn)化代數(shù)（EGN）、收斂時(shí)間（CT）和全局搜索能力（GSC）的影響。通過四個(gè)經(jīng)典函數(shù)的測(cè)試，結(jié)果表明種群規(guī)模對(duì)遺傳算法各個(gè)性能的變化均有上升或下降的變化。

表1 測(cè)試函數(shù)定義

從直觀上看，當(dāng)種群規(guī)模增大時(shí)，算法的計(jì)算時(shí)間，也就是收斂時(shí)間將會(huì)增大；而種群規(guī)模如果增大了，那么算法收斂到最優(yōu)解的可能性就會(huì)增大，即全局搜索能力會(huì)增強(qiáng)；再者，當(dāng)種群規(guī)模增大了，在解空間中搜索時(shí)，可以在相對(duì)較少的代數(shù)中找到最優(yōu)解，那么進(jìn)化代數(shù)也隨著種群規(guī)模的增大而變小了。

一、算法步驟

Step2.利用適應(yīng)度函數(shù)來評(píng)價(jià)個(gè)體適應(yīng)度；

Step3.若滿足收斂條件，則停止迭代并給出最優(yōu)個(gè)體，否則進(jìn)行下一步；

Step4.進(jìn)行遺傳操作:

Step4.1.實(shí)行精英策略，保留本代一定比例的最優(yōu)個(gè)體至下一代；

Step4.2.利用線性排序選擇方法進(jìn)行選擇，采用兩點(diǎn)線性交叉，執(zhí)行均勻變異操作。

表2 進(jìn)化代數(shù)和種群規(guī)模的關(guān)系

二、測(cè)試函數(shù)

試驗(yàn)所用的四個(gè)函數(shù)都是要找出他們的最大值。函數(shù)定義如表1。（表1）

三、實(shí)驗(yàn)結(jié)果及分析

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

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

表3 進(jìn)化時(shí)間和種群規(guī)模關(guān)系

2、收斂時(shí)間（CT）和種群規(guī)模（PS）之間的關(guān)系如表3所示。（表3）由表3可以看出收斂時(shí)間在開始階段下降，經(jīng)過某個(gè)特定值之后，時(shí)間隨著種群規(guī)模的擴(kuò)大而增加。

3、為了測(cè)試全局搜索能力和種群規(guī)模的關(guān)系，我們把算法分別獨(dú)立運(yùn)行30次，得到全局最優(yōu)解的總次數(shù)為k，利用k/30表示全局搜索能力。全局搜索能力（GSC）和種群規(guī)模（PS）的具體關(guān)系如表4所示。（表4）從表4可以看出，隨著種群規(guī)模的擴(kuò)大全局搜索能力會(huì)增強(qiáng)，但可以看出也不是單調(diào)的。

表4 全局搜索能力和種群規(guī)模的關(guān)系

四、結(jié)論

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

[1]李敏強(qiáng)，寇紀(jì)淞，林丹等.遺傳算法的基本理論與應(yīng)用[M].北京:科學(xué)出版社，2004.

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

[3]王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社，2002.