遺傳算法性能評(píng)價(jià)指標(biāo)

□文/劉曉霞 竇明鑫

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

引言

遺傳算法（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)化搜索方法。

傳統(tǒng)遺傳算法中，人們常常利用進(jìn)化代數(shù)、收斂時(shí)間和全局搜索能力等來(lái)評(píng)估算法的性能。而在進(jìn)行算法的實(shí)驗(yàn)研究過(guò)程中，我們發(fā)現(xiàn)：收斂時(shí)間、進(jìn)化代數(shù)、全局搜索概率這三個(gè)性能評(píng)價(jià)指標(biāo)在具體的評(píng)價(jià)過(guò)程中是不能同時(shí)達(dá)到最優(yōu)的。而且在研究種群規(guī)模對(duì)算法影響時(shí)發(fā)現(xiàn)：種群規(guī)模增大的過(guò)程中，三個(gè)指標(biāo)變化方向是不同的、甚至是相反的，是相互矛盾的。因此，在用進(jìn)化代數(shù)、收斂時(shí)間和全局搜索能力進(jìn)行算法性能評(píng)價(jià)時(shí)，應(yīng)該以哪一個(gè)指標(biāo)作為評(píng)價(jià)標(biāo)準(zhǔn)是需要思考的問(wèn)題，即我們需要一個(gè)參考標(biāo)準(zhǔn)。

一、實(shí)際意義

在實(shí)際問(wèn)題中，我們?cè)u(píng)價(jià)算法的好壞要具有實(shí)際的意義，對(duì)三方面評(píng)價(jià)指標(biāo)的要求也就有所不同。

有些問(wèn)題是時(shí)效性的，對(duì)算法的收斂時(shí)間要求很高，過(guò)了一定的時(shí)間限制所得到的結(jié)果是無(wú)意義的。如，鐵路的調(diào)度問(wèn)題中，最優(yōu)調(diào)度方案需要及時(shí)給出，要求在最短的時(shí)間內(nèi)得到各趟火車(chē)到站的?？柯肪€，那就對(duì)算法的收斂時(shí)間要求極高，而對(duì)算法的進(jìn)化代數(shù)以及全局搜索能力要求不高，如果給出的算法收斂時(shí)間過(guò)長(zhǎng)，在所需的時(shí)間之內(nèi)不能給出最優(yōu)解，則該結(jié)果失去了它的及時(shí)性，這樣各火車(chē)之間就有可能會(huì)產(chǎn)生不可想象的后果。

有些問(wèn)題要求全局搜索能力要很強(qiáng)，在很多精密計(jì)算中，對(duì)算法的精度要求很高，也就是對(duì)全局搜索能力要求高，必須得到確切的最優(yōu)解。如在炮彈的著陸點(diǎn)問(wèn)題中，我們要求其最優(yōu)解要非常精確，精確到一個(gè)很小的范圍內(nèi)，這樣不論是在研究炮彈的精密性，還是在實(shí)戰(zhàn)中，都有著舉足輕重的作用，而此時(shí)對(duì)算法的收斂代數(shù)、收斂時(shí)間的要求相對(duì)就較低了。

還有些問(wèn)題要求有進(jìn)化代數(shù)的限制，需要在有限的代數(shù)內(nèi)得到最優(yōu)解。在實(shí)際項(xiàng)目的完成過(guò)程中，每個(gè)結(jié)果的產(chǎn)生都需要付出一定的代價(jià)：人力、物力、財(cái)力，而為了降低成本，減少相關(guān)的支出，就需要限制進(jìn)化代數(shù)，比如就要優(yōu)化一次得到的結(jié)果，這樣進(jìn)化代數(shù)就為一，而對(duì)收斂時(shí)間和全局搜索能力的要求沒(méi)有限制。

因此，我們可以看出，在遺傳算法中常用的三個(gè)評(píng)價(jià)指標(biāo)：收斂時(shí)間、進(jìn)化代數(shù)、全局搜索能力，我們可以根據(jù)實(shí)際需要調(diào)整他們?cè)谠u(píng)價(jià)過(guò)程中的比重，進(jìn)而使得進(jìn)化性能得到更好地評(píng)價(jià)，能夠在實(shí)際應(yīng)用中發(fā)揮更重要的作用。為了比較評(píng)價(jià)不同的遺傳算法，我們提出了一種新的評(píng)價(jià)指標(biāo)來(lái)判斷不同遺傳算法的性能。

二、評(píng)價(jià)指標(biāo)

在具體的遺傳算法實(shí)驗(yàn)中，可以由使用者分別賦予收斂時(shí)間、進(jìn)化代數(shù)、全局搜索能力以不同的權(quán)重，利用加權(quán)后的值作為評(píng)價(jià)指標(biāo)。如：

其中，權(quán)值 ω1、ω2、ω3∈［0，1］，且滿(mǎn)足ω1＋ω2＋ω3＝1，T 表示算法占用的 CPU 時(shí)間，E表示進(jìn)化代數(shù)，P表示全局搜索能力。用PGA來(lái)衡量遺傳算法的性能，PGA越小遺傳算法的性能越好。

在具體應(yīng)用時(shí)，可以根據(jù)不同的要求調(diào)整權(quán)重ωi的取值，體現(xiàn)在實(shí)際問(wèn)題中其評(píng)價(jià)的重要性，從而滿(mǎn)足不同的目的。

對(duì)于時(shí)效性的問(wèn)題，可以增大ω1的取值，減小ω2、ω3的取值；對(duì)于全局搜索能力要求高的問(wèn)題中，增大ω3的取值，減小ω1、ω2的取值；而對(duì)進(jìn)化代數(shù)有的限制的問(wèn)題，增大 ω2的取值，減小 ω1、ω3的取值。類(lèi)似的，如果實(shí)際問(wèn)題中要求的不僅僅是一個(gè)方面，就可以增大其中兩個(gè)而減小另外一個(gè)，這樣可以達(dá)到利用權(quán)值來(lái)控制各個(gè)性能所占用的比重，從而更好地得到最優(yōu)解。

三、結(jié)論

本文提出了一種新的遺傳算法性能評(píng)價(jià)指標(biāo)，可以針對(duì)不同的情況，側(cè)重不同的要求來(lái)調(diào)整進(jìn)化代數(shù)、收斂時(shí)間、全局搜索概率的權(quán)重，進(jìn)而評(píng)價(jià)改進(jìn)后的遺傳算法是不是有效地滿(mǎn)足所需的指標(biāo)。

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

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

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

[4]劉剛，曹勇，李華德.幾種改進(jìn)遺傳算法的性能比較[J].微計(jì)算機(jī)信息，2007.23.

[5]徐曉華，陳崚，陳宏建.可變種群規(guī)模的遺傳算法[J].系統(tǒng)仿真學(xué)報(bào)，2006.18.