楊水清，楊加明，孫超

南昌航空大學(xué)飛行器工程學(xué)院，南昌 330063

改進(jìn)的乘冪適應(yīng)度函數(shù)在遺傳算法中的應(yīng)用

楊水清，楊加明，孫超

南昌航空大學(xué)飛行器工程學(xué)院，南昌 330063

在遺傳算法優(yōu)化過程中，引導(dǎo)搜索的主要依據(jù)是適應(yīng)度函數(shù)。通過評估常見的幾種適應(yīng)度函數(shù)，兼顧保持種群的多樣性和算法的收斂性，由乘冪尺度變換，提出了一種改進(jìn)的乘冪適應(yīng)度函數(shù)。以三個典型的測試函數(shù)為例，在相同遺傳操作和參數(shù)情況下，分別采用常見的與改進(jìn)的適應(yīng)度函數(shù)進(jìn)行優(yōu)化比較。結(jié)果表明，所改進(jìn)的乘冪適應(yīng)度函數(shù)能明顯提高算法的收斂精度、收斂速度和收斂穩(wěn)定性，對提高遺傳算法的整體性能有重要的意義。

遺傳算法；適應(yīng)度函數(shù)；測試函數(shù)；優(yōu)化計算

1 引言

求解復(fù)雜函數(shù)的最優(yōu)問題是遺傳算法（Genetic A lgorithms，GA）的一個重要研究方向。Holstien[1]首先在純數(shù)學(xué)優(yōu)化領(lǐng)域應(yīng)用GA。De Jong[2]在函數(shù)優(yōu)化方面進(jìn)行了深入研究，并對一些具有代表性的測試函數(shù)進(jìn)行了算法優(yōu)化實驗。20世紀(jì)80年代末，Goldberg[3]對適應(yīng)度函數(shù)做了進(jìn)一步分析，發(fā)現(xiàn)目標(biāo)函數(shù)經(jīng)過線性變換后，可作為一種較好形式的適應(yīng)度函數(shù)。

在遺傳算法中，適應(yīng)度（Fitness）用來度量群體中的個體在優(yōu)化計算中達(dá)到或接近于最優(yōu)解的優(yōu)良程度[4]。適應(yīng)度較高的個體遺傳到下一代的概率就較大；而較低的個體遺傳到下一代的概率就相對小一些。遺傳算法引導(dǎo)搜索的主要依據(jù)就是個體的適應(yīng)度值。也就是說，遺傳算法依靠選擇操作來引導(dǎo)算法的搜索方向。選擇操作是以個體的適應(yīng)度作為確定性指標(biāo)，從當(dāng)前群體中選擇適應(yīng)度值高的個體進(jìn)行交叉和變異，尋找最優(yōu)解。

如果適應(yīng)度函數(shù)選擇不當(dāng)，可能會造成遺傳算法的欺騙現(xiàn)象[5]，因此適應(yīng)度函數(shù)的選取至關(guān)重要，它直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。遺傳算法的多數(shù)改進(jìn)方案主要針對適應(yīng)度函數(shù)、遺傳操作算子、控制參數(shù)的選擇及編碼。文獻(xiàn)[6]提出的自適應(yīng)遺傳算法對交叉概率pc和變異概率pm進(jìn)行自適應(yīng)調(diào)整，其方案建立在個體適應(yīng)度的基礎(chǔ)之上。

已有研究[7-13]表明，適應(yīng)度函數(shù)的改進(jìn)對遺傳算法優(yōu)化有積極影響。本文以函數(shù)最優(yōu)化問題為背景，在現(xiàn)有研究的基礎(chǔ)上對適應(yīng)度函數(shù)作進(jìn)一步改進(jìn)，利用乘冪變換法的特點，結(jié)合適應(yīng)度線性尺度變換，提出了基于乘冪變換的非線性動態(tài)適應(yīng)度函數(shù)，用典型的遺傳算法測試函數(shù)[14]驗證本文提出的適應(yīng)度函數(shù)的有效性與可行性。

2 適應(yīng)度函數(shù)的選擇

2.1 適應(yīng)度函數(shù)的作用

對遺傳算法進(jìn)行選擇操作時，往往會出現(xiàn)兩個遺傳算法的欺騙問題：

（1）在遺傳進(jìn)化的初期，通常會產(chǎn)生一些超常的個體，若按照比例選擇法，這些超常個體會因競爭力突出而控制選擇過程，影響算法的全局優(yōu)化性能。

（2）在遺傳進(jìn)化的后期，即算法接近收斂時，由于種群中個體適應(yīng)度差異較小，繼續(xù)優(yōu)化的潛能降低，可能獲得某個局部最優(yōu)解。

如果適應(yīng)度函數(shù)設(shè)計不當(dāng)，有可能造成這兩種問題的出現(xiàn)，所以適應(yīng)度函數(shù)的設(shè)計是遺傳算法設(shè)計的一個重要內(nèi)容。

2.2 適應(yīng)度函數(shù)的分析

適應(yīng)度函數(shù)的設(shè)計應(yīng)盡量滿足如下條件：

（1）單值、連續(xù)、非負(fù)、最大化。

（2）合理、一致性，要求適應(yīng)度值反映對應(yīng)解的優(yōu)劣程度。

（3）計算量小。適應(yīng)度函數(shù)設(shè)計應(yīng)盡量簡單，這樣可以減少計算時間和算法的復(fù)雜性。

（4）通用性較強(qiáng)。適應(yīng)度對某類具體的問題，應(yīng)盡可能通用，最好無需改變適應(yīng)度函數(shù)中的參數(shù)。

2.2.1 基本適應(yīng)度函數(shù)（BGA）

（1）直接以待解的目標(biāo)函數(shù)f(x)轉(zhuǎn)化為適應(yīng)度函數(shù)Fit(f(x))，這種適應(yīng)度函數(shù)簡單直觀，即

其中，f(x)為目標(biāo)函數(shù)最大化問題；-f(x)為目標(biāo)函數(shù)最小化問題。但有可能出現(xiàn)兩種現(xiàn)象：一是不能滿足常用的賭盤選擇中概率非負(fù)的要求；二是某些待解函數(shù)在函數(shù)值分布上相差很大，由此得到的平均適應(yīng)度不利于體現(xiàn)種群的平均性能，從而影響算法的性能。

（2）對于求最小值問題，可以做下列轉(zhuǎn)換：

式中，Cmax為一個適當(dāng)?shù)南鄬^大的數(shù)，它是f(x)的最大估計值。

對于求最大值問題，做下列轉(zhuǎn)換：

式中，Cmin為f(x)最小估計值，它可以是一個合適的輸入值。這種方法是第一種方法的改進(jìn)，可以稱為“界限改造法”，但這種方法有時存在界限值預(yù)先估計困難，導(dǎo)致計算結(jié)果不精確。

2.2.2 乘冪適應(yīng)度函數(shù)（EGA）

乘冪尺度變換是指新的適應(yīng)度為原來適應(yīng)度的某個指定乘冪，其乘冪尺度變換的公式為：

式中，F(xiàn)′是經(jīng)過乘冪變換后得到的新適應(yīng)度函數(shù)；F是原適應(yīng)度函數(shù)，可直接取目標(biāo)函數(shù)。冪指數(shù)k與所求的問題有關(guān)，在算法的執(zhí)行過程中需要不斷對其進(jìn)行修正，才能使尺度變換滿足一定的伸縮要求。

2.2.3 改進(jìn)的乘冪適應(yīng)度函數(shù)（MGA）

改進(jìn)的新適應(yīng)度函數(shù)如下：

式中，F(xiàn)′是經(jīng)過乘冪變換后得到的新適應(yīng)度函數(shù)；F是原適應(yīng)度函數(shù)；Cmax是最大估計值，可直接取目標(biāo)函數(shù)。此時k不再是一個常數(shù)，而是一個隨進(jìn)化代數(shù)增加的非線性動態(tài)變化的正數(shù)。t是當(dāng)前的進(jìn)化代數(shù)；T是最大的遺傳代數(shù)；Favg是當(dāng)代種群的平均值；ξ是適當(dāng)大小的數(shù)。

3 測試與分析

3.1 測試函數(shù)

函數(shù)1定義為：

該函數(shù)是一個非線性、不對稱、不可分離的多峰函數(shù)，其中x，y的區(qū)間均為[-2，2]。全局有多個極值點，較難找到最優(yōu)點。其三維形狀如圖1所示，圖中的圓圈表示各代種群搜尋到的最優(yōu)解。

互聯(lián)網(wǎng)大數(shù)據(jù)支持下的“共享經(jīng)濟(jì)模式”，同時影響著現(xiàn)代城市的建設(shè)與發(fā)展，使智慧城市建設(shè)步入以大數(shù)據(jù)中心為背景的“共享時代”，同時也為智慧城市在我國的建設(shè)與發(fā)展開創(chuàng)了新局面，智慧城市在大數(shù)據(jù)平臺的支撐下，會得到更好的發(fā)展[1]。

圖1 函數(shù)1的分布圖

函數(shù)2又稱為Shubert函數(shù)，定義為：

該函數(shù)是一個復(fù)雜的二維函數(shù)，(x，y)的取值區(qū)間為[-10，10]，可以看出有很多的極大值點，由于該函數(shù)具有強(qiáng)烈的震蕩形態(tài)，所以找到全局極大值有一定的困難。其三維形狀如圖2所示，圖中圓圈表示各代種群搜尋到的最優(yōu)解。

圖2 函數(shù)2的分布圖

函數(shù)3又稱為Rastrigrin函數(shù)，定義為：

f3(x，y)=20+x2-10 cos(2πx)+y2-10 cos(2πy)（10）

該函數(shù)是復(fù)雜的二維函數(shù)，具有很多的極值點，(x，y)的取值區(qū)間為[-5，5]，三維形狀如圖3所示，圖中圓圈表示各代種群搜尋到的最優(yōu)解。

圖3 函數(shù)3的分布圖

3.2 測試結(jié)果與分析

為了便于比較各算法搜索的性能，選取同樣的測試參數(shù)比較。本文選擇種群規(guī)模為100；進(jìn)化代數(shù)為60；交叉概率為0.7；變異概率為0.01；代溝（GGAP）為0.95，采用進(jìn)化代數(shù)固定的終止策略。對每個適應(yīng)度函數(shù)算法分別運行50次，實驗測試的結(jié)果保留四位有效數(shù)。為了驗證MGA的有效性和可行性，將其與BGA以及EGA進(jìn)行了對比。

圖4 函數(shù)f1(x，y)在不同算法下解的變化對比

表1 測試實驗的最優(yōu)結(jié)果

下面討論MGA、EGA和BGA之間的收斂速度、收斂精度和收斂穩(wěn)定性的優(yōu)劣。

圖4、圖5和圖6分別為函數(shù)f1(x，y)、f2(x，y)和f3(x，y)在不同算法下解的變化對比，從圖4可以看出，雖然BGA、EGA和MGA最后都能收斂到最優(yōu)解，但MGA的收斂速度要明顯快于BGA和EGA。由圖5及圖6知道，MGA很快收斂到最優(yōu)解；而EGA和BGA收斂波動性較大，且它們在遺傳進(jìn)化的后期才收斂于最優(yōu)解。

圖7、圖8和圖9分別為函數(shù)f1(x，y)、f2(x，y)和f3(x，y)在不同算法下運行50次得到的最優(yōu)解變動對比。從圖7中可以看出，BGA和EGA算法每次運行得到的最優(yōu)解變動非常大，尤其是BGA；而且它們的最優(yōu)解的精確度不高。故在收斂精度和收斂穩(wěn)定性方面，EGA要優(yōu)于BGA；MGA要優(yōu)于BGA和EGA。類似的結(jié)論反映在圖8和圖9上，MGA算法每次運行所得的最優(yōu)解幾乎在一條直線上，而EGA和BGA的變動較大。

圖5 函數(shù)f2(x，y)在不同算法下解的變化對比

圖6 函數(shù)f3(x，y)在不同算法下解的變化對比

圖7 函數(shù)f1(x，y)在不同算法下最優(yōu)解的變動對比

圖8 函數(shù)f2(x，y)在不同算法下最優(yōu)解的變動對比

圖9 函數(shù)f(x，y)在不同算法下最優(yōu)解的變動對比

對于測試函數(shù)f1(x，y)，結(jié)合圖4和圖7，可以得出結(jié)論，在收斂速度、收斂精度及收斂穩(wěn)定性方面，MGA均優(yōu)于BGA和EGA。對于測試函數(shù)f2(x，y)和f3(x，y)，分別結(jié)合圖5、圖6和圖8、圖9，可以得出如下結(jié)論，在收斂速度、收斂精度以及收斂穩(wěn)定性方面，MGA具有明顯優(yōu)勢。

需要特別指出的是，圖7和圖9相對于圖8而言，其最優(yōu)解的變動明顯較大，可能的原因有：（1）測試函數(shù)f2(x，y)的局部極大值點太多，且極值相差不大，故對一般的適應(yīng)度函數(shù)較容易找出局部最優(yōu)解。從圖1和圖3可以看出，圖中極值點相對較少，且差距明顯，故設(shè)計更好的適應(yīng)度函數(shù)會更容易找到最優(yōu)解。（2）乘冪變換法對于冪指數(shù)及一些相關(guān)參數(shù)有一定的選擇要求，這就需要在程序執(zhí)行過程中通過分析選取不同的冪指數(shù)。

4 結(jié)論

尋到較精確最優(yōu)解；在收斂速度方面，MGA算法明顯提高。

（2）對每種算法運行50次，MGA算法運行所得的最優(yōu)解變動很小，而BGA和EGA算法得到的最優(yōu)解變動幅度明顯，說明在收斂精度和收斂穩(wěn)定性方面，MGA算法優(yōu)勢明顯。

（3）適應(yīng)度函數(shù)標(biāo)定只是遺傳算法優(yōu)化問題的改進(jìn)措施之一，還須注重編碼方案、遺傳操作方式及相關(guān)控制參數(shù)等。

本文用三種測試函數(shù)對改進(jìn)的遺傳算法的性能進(jìn)行測試，以一般適應(yīng)度函數(shù)（BGA、EGA）遺傳算法和改進(jìn)的乘冪適應(yīng)度函數(shù)（MGA）遺傳算法進(jìn)行性能比較，得到以下結(jié)論：

（1）對三種測試函數(shù)，MGA算法很快地找到了精確最優(yōu)解，而BGA和EGA算法基本是在遺傳進(jìn)化后期搜

[1]Holstien R B.Artificial genetic adaptation in computer control systems[D].Ann Arbor：Department of Computer and Communication Sciences，University of Michigan，1971.

[2]De Jong K A.Analysis of the behavior of a class of genetic adaptive systems[D].Ann Arbor：Department of Computer and Communication Sciences，University of Michigan，1975.

[3]Goldberg D E.Genetic algorithms in search，optimization and machine learning[M].Boston，MA，USA：Addison Wesley Publishing Company，1989：117-121.

[4]孫樹棟，周明.遺傳算法原理及應(yīng)用[M].北京：國防工業(yè)出版社，2002.

[5]雷英杰，張善文，李續(xù)武，等.MATLAB遺傳算法工具箱及應(yīng)用[M].西安：西安電子科技大學(xué)出版社，2005.

[6]鄧洋春，梁昔明.一種改進(jìn)操作算子的加速收斂遺傳算法[J].現(xiàn)代電子技術(shù)，2009（2）：36-38.

[7]郭曉原.遺傳算法中適應(yīng)度尺度變換與操作算子的比較研究[D].北京：華北電力大學(xué)，2012.

[8]金芬，孫春華.遺傳算法中適應(yīng)度函數(shù)的改進(jìn)[D].江蘇蘇州：蘇州大學(xué)，2010.

[9]張思才，張方曉.一種遺傳算法適應(yīng)度函數(shù)的改進(jìn)方法[J].計算機(jī)應(yīng)用與軟件，2006，23（2）：146-150.

[10]伊丹丹，姜淑娟，張艷梅.多路徑覆蓋測試數(shù)據(jù)生成適應(yīng)度函數(shù)設(shè)計方法[J].計算機(jī)工程與應(yīng)用，2012，48（22）：79-83.

[11]代才，王宇平.基于新的適應(yīng)度函數(shù)的多目標(biāo)進(jìn)化算法[J].華中科技大學(xué)學(xué)報，2013，41（7）：56-60.

[12]施澤波.圖像增強(qiáng)中優(yōu)化算法適應(yīng)度函數(shù)設(shè)計[J].電光與控制，2010，20（5）：113-117.

[13]王偉，軒紅.基于AHP方法的遺傳算法適應(yīng)度函數(shù)設(shè)計與應(yīng)用[J].河南科學(xué)，2010，28（9）：59-64.

[14]史峰，王輝，郁磊，等.MATLAB智能算法30個案例分析[M].北京：北京航空航天大學(xué)出版社，2011.

YANG Shuiqing, YANG Jiaming, SUN Chao

School of Aircraft Engineering, Nanchang Hangkong University, Nanchang 330063, China

It is the main factors for fitness functions to guide the search of the genetic algorithm optimization process. The exponential fitness functions are improved by exponentiation scale transformation.They are used to evaluate several common fitness functions to keep their diversity of population and convergence of the algorithm s.The optimal computation is compared for the usual and the improved fitness functions under the same conditions of genetic manipulation and their parameters in using three typical test functions.Numerical results show that it is significant for the new fitness functions of a power optimal algorithm to improve the overall performance including the accuracy,convergence speed,and convergence stability of the ameliorated genetic algorithm s.

genetic algorithm s;fitness functions;testing functions;optimal computation

YANG Shuiqing, YANG Jiaming, SUN Chao. Improved exponentiation scale transformation in application of genetic algorithm. Computer Engineering and Applications, 2014, 50（17）：40-43.

A

TP18

10.3778/j.issn.1002-8331.1311-0047

航空科學(xué)基金（No.2012ZA 56001）；江西省自然科學(xué)基金（No.20114BAB202010）。

楊水清（1988—），男，碩士，主要研究方向為數(shù)值分析與計算；楊加明（1963—），男，博士，教授，主要研究方向為復(fù)合材料結(jié)構(gòu)分析與設(shè)計；孫超（1988—），男，碩士，主要研究方向為復(fù)合材料結(jié)構(gòu)分析。E-mail：happyeveryday1115@163.com

2013-11-05

2014-02-24

1002-8331（2014）17-0040-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-04-01,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1311-0047.htm l