□文/劉曉霞 竇明鑫

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

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

□文/劉曉霞1竇明鑫2

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

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

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

收錄日期：2012年5月10日

引言

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

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

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

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

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

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

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

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

表4 變量個(gè)數(shù)與最小收斂代數(shù)關(guān)系

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

表7 變量個(gè)數(shù)與最小收斂代數(shù)關(guān)系

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

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

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

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

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

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

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

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

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

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

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

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

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

表10 變量個(gè)數(shù)與最小收斂代數(shù)關(guān)系

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

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

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

三、結(jié)論

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

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

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

[3]蒲若昂，李志華，宋國(guó)新.一種新的改進(jìn)遺傳算法及其應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件，2007.24.10.

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

TP3

A