變量數目與種群規模的關系
2012-03-05 07:24:28劉曉霞竇明鑫
合作經濟與科技 2012年14期
□文/劉曉霞 竇明鑫
（1.河北金融學院；2.中國地質大學長城學院 河北·保定）
變量數目與種群規模的關系
□文/劉曉霞1竇明鑫2
（1.河北金融學院；2.中國地質大學長城學院 河北·保定）
在遺傳算法的參數選擇中，種群規模是一個重要的參數。本文通過實驗取收斂時間和收斂代數的平均值作為評價指標來研究在確定遺傳算法參數時，種群規模跟決策變量個數n有著一定的關系，通過經典函數的測試表明：比較合適的種群規模應控制在4n到6n之間。
遺傳算法；種群規模；決策變量個數；收斂代數；收斂時間
收錄日期：2012年5月10日
引言
遺傳算法（GA）由美國Michigan大學的Holland教授于1975年首先提出，后經De Jong、GoldBerg等人改進推廣，廣泛應用于各類問題。它是一種模擬自然界生物進化過程與機制的全局概率優化搜索方法。
在遺傳算法的參數選擇中，種群規模（PS）是一個重要的參數，如何選擇合適的種群規模至今沒有確定的指導思想。種群規模選擇過大會增加計算負擔，收斂時間會顯著增加，過小則降低種群的個體多樣性，容易早熟，可能難以搜索到全局最優解。因此，我們希望找到種群規模與變量個數之間的對應關系，能夠根據所給出函數的變量個數來選取相對合適的種群規模，使得算法的性能達到更好。
下面選擇三個典型的測試函數，利用不同的種群規模和不同的變量個數進行試驗，期望找到變量個數與種群規模之間的最佳關系。
一、測試函數
為了研究變量個數與種群規模對GA性能的影響，我們選擇了以下三個函數。試驗時每個函數的變量個數從10依次增加到20分別進行試驗。（表1）
二、實驗結果及分析
表1 測試函數的定義
表3 函數f1的PS與EGN測試結果
表4 變量個數與最小收斂代數關系
表6 函數f2的PS與EGN測試結果
表7 變量個數與最小收斂代數關系
在以下試驗中，進化參數設置如下：對每個種群設置收斂精度為ε＝0.01，選擇概率為 PS＝0.25，交叉概率為 PC＝0.7，變異概率為Pm＝0.05，進化代數為2000。種群規模從n依次增加到8n。每種規模的種群獨立運行30次。取收斂時間（CT）和收斂代數（EGN）的平均值作為評價指標，函數收斂性能指標利用收斂時間（T）、進化代數（E）、全局搜索能力（P）加權后的值PGA=ω1T＋ω2E＋ω3（1-P）作為評價指標。
表 2 函數f1的PS與CT測試結果
表5 函數f2的PS與CT測試結果
表8 函數f3的PS與CT測試結果
1、函數f1的試驗結果如表2所示。（表 2、圖 1）
圖1表現了函數f1收斂時間與種群規模的關系，函數的曲線隨著種群規模的擴大一致地呈現了幾乎直線上升的狀態，說明種群規模對GA計算時間的影響十分明顯。（表 3、表 4）
從表4可以看出，最小收斂代數有1次 n，2 次 4n，2 次 5n，3 次 6n，1 次 7n，1次8n。
2、函數f1的試驗結果如表5所示。（表 5、圖 2）
圖2表現了函數f2收斂時間與種群規模的關系，函數的曲線隨著種群規模的擴大一致的呈現了幾乎直線上升的狀態，說明種群規模對GA計算時間的影響十分明顯。（表 6、表 7）
從表7可以看出，最小收斂代數有1次 3n，1次 4n，3次 5n，5次 6n，1次 7n。
3、函數f3的試驗結果如表8所示。（表 8、圖 3）
圖3表現了函數f3收斂時間與種群規模的關系，函數的曲線隨著種群規模的擴大一致的呈現了幾乎直線上升的狀態，說明種群規模對GA計算時間的影響十分明顯。（表 9、表 10）
表9 函數f3的PS與EGN測試結果
表10 變量個數與最小收斂代數關系
從表10可以看出，最小收斂代數有4次 4n，5次 5n，1次 6n，1次 7n。
從以上圖表及分析可以看出，種群規模的擴大對GA的搜索收斂時間有很大的影響，因此如果要想在較短時間內得到最優解，就不應該選取過大的種群規模。
對于三個測試函數來說，在變量個數一定的情況下，收斂代數最小的種群規模在 4n到6n之間，因此在確定遺傳算法種群規模參數時，可以選擇在4n到6n之間。
三、結論
在確定遺傳算法參數時，種群規模的確定與決策變量個數n有著一定的關系，比較合適的種群規模應該控制著4n到6n之間。而且，推薦選用比較小的種群規模去進行計算，這樣會節約大量的計算時間。
[1]李敏強，寇紀淞，林丹等.遺傳算法的基本理論與應用[M].北京：科學出版社，2004.
[2]王小平，曹立明.遺傳算法——理論、應用與軟件實現[M].西安：西安交通大學出版社，2002.
[3]蒲若昂，李志華，宋國新.一種新的改進遺傳算法及其應用[J].計算機應用與軟件，2007.24.10.
[4]王力，侯燕玲.基于遺傳算法通用試題庫系統研究 [J].微計算機信息，2008.5.3.
TP3
A
