遺傳算法性能評價指標(biāo)

□文/劉曉霞 竇明鑫

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

引言

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

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

一、實際意義

在實際問題中，我們評價算法的好壞要具有實際的意義，對三方面評價指標(biāo)的要求也就有所不同。

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

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

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

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

二、評價指標(biāo)

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

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

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

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

三、結(jié)論

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

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

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

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

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

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