變量數(shù)目與種群規(guī)模的關系

□文/劉曉霞 竇明鑫

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

變量數(shù)目與種群規(guī)模的關系

□文/劉曉霞1竇明鑫2

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

在遺傳算法的參數(shù)選擇中，種群規(guī)模是一個重要的參數(shù)。本文通過實驗取收斂時間和收斂代數(shù)的平均值作為評價指標來研究在確定遺傳算法參數(shù)時，種群規(guī)模跟決策變量個數(shù)n有著一定的關系，通過經典函數(shù)的測試表明：比較合適的種群規(guī)模應控制在4n到6n之間。

遺傳算法；種群規(guī)模；決策變量個數(shù)；收斂代數(shù)；收斂時間

收錄日期：2012年5月10日

引言

遺傳算法（GA）由美國Michigan大學的Holland教授于1975年首先提出，后經De Jong、GoldBerg等人改進推廣，廣泛應用于各類問題。它是一種模擬自然界生物進化過程與機制的全局概率優(yōu)化搜索方法。

在遺傳算法的參數(shù)選擇中，種群規(guī)模（PS）是一個重要的參數(shù)，如何選擇合適的種群規(guī)模至今沒有確定的指導思想。種群規(guī)模選擇過大會增加計算負擔，收斂時間會顯著增加，過小則降低種群的個體多樣性，容易早熟，可能難以搜索到全局最優(yōu)解。因此，我們希望找到種群規(guī)模與變量個數(shù)之間的對應關系，能夠根據所給出函數(shù)的變量個數(shù)來選取相對合適的種群規(guī)模，使得算法的性能達到更好。

下面選擇三個典型的測試函數(shù)，利用不同的種群規(guī)模和不同的變量個數(shù)進行試驗，期望找到變量個數(shù)與種群規(guī)模之間的最佳關系。

一、測試函數(shù)

為了研究變量個數(shù)與種群規(guī)模對GA性能的影響，我們選擇了以下三個函數(shù)。試驗時每個函數(shù)的變量個數(shù)從10依次增加到20分別進行試驗。（表1）

二、實驗結果及分析

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

表3 函數(shù)f1的PS與EGN測試結果

表4 變量個數(shù)與最小收斂代數(shù)關系

表6 函數(shù)f2的PS與EGN測試結果

表7 變量個數(shù)與最小收斂代數(shù)關系

在以下試驗中，進化參數(shù)設置如下：對每個種群設置收斂精度為ε＝0.01，選擇概率為 PS＝0.25，交叉概率為 PC＝0.7，變異概率為Pm＝0.05，進化代數(shù)為2000。種群規(guī)模從n依次增加到8n。每種規(guī)模的種群獨立運行30次。取收斂時間（CT）和收斂代數(shù)（EGN）的平均值作為評價指標，函數(shù)收斂性能指標利用收斂時間（T）、進化代數(shù)（E）、全局搜索能力（P）加權后的值PGA=ω1T＋ω2E＋ω3（1-P）作為評價指標。

表 2 函數(shù)f1的PS與CT測試結果

表5 函數(shù)f2的PS與CT測試結果

表8 函數(shù)f3的PS與CT測試結果

1、函數(shù)f1的試驗結果如表2所示。（表 2、圖 1）

圖1表現(xiàn)了函數(shù)f1收斂時間與種群規(guī)模的關系，函數(shù)的曲線隨著種群規(guī)模的擴大一致地呈現(xiàn)了幾乎直線上升的狀態(tài)，說明種群規(guī)模對GA計算時間的影響十分明顯。（表 3、表 4）

從表4可以看出，最小收斂代數(shù)有1次 n，2 次 4n，2 次 5n，3 次 6n，1 次 7n，1次8n。

2、函數(shù)f1的試驗結果如表5所示。（表 5、圖 2）

圖2表現(xiàn)了函數(shù)f2收斂時間與種群規(guī)模的關系，函數(shù)的曲線隨著種群規(guī)模的擴大一致的呈現(xiàn)了幾乎直線上升的狀態(tài)，說明種群規(guī)模對GA計算時間的影響十分明顯。（表 6、表 7）

從表7可以看出，最小收斂代數(shù)有1次 3n，1次 4n，3次 5n，5次 6n，1次 7n。

3、函數(shù)f3的試驗結果如表8所示。（表 8、圖 3）

圖3表現(xiàn)了函數(shù)f3收斂時間與種群規(guī)模的關系，函數(shù)的曲線隨著種群規(guī)模的擴大一致的呈現(xiàn)了幾乎直線上升的狀態(tài)，說明種群規(guī)模對GA計算時間的影響十分明顯。（表 9、表 10）

表9 函數(shù)f3的PS與EGN測試結果

表10 變量個數(shù)與最小收斂代數(shù)關系

從表10可以看出，最小收斂代數(shù)有4次 4n，5次 5n，1次 6n，1次 7n。

從以上圖表及分析可以看出，種群規(guī)模的擴大對GA的搜索收斂時間有很大的影響，因此如果要想在較短時間內得到最優(yōu)解，就不應該選取過大的種群規(guī)模。

對于三個測試函數(shù)來說，在變量個數(shù)一定的情況下，收斂代數(shù)最小的種群規(guī)模在 4n到6n之間，因此在確定遺傳算法種群規(guī)模參數(shù)時，可以選擇在4n到6n之間。

三、結論

在確定遺傳算法參數(shù)時，種群規(guī)模的確定與決策變量個數(shù)n有著一定的關系，比較合適的種群規(guī)模應該控制著4n到6n之間。而且，推薦選用比較小的種群規(guī)模去進行計算，這樣會節(jié)約大量的計算時間。

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

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

[3]蒲若昂，李志華，宋國新.一種新的改進遺傳算法及其應用[J].計算機應用與軟件，2007.24.10.

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

TP3

A