改進的乘冪適應度函數(shù)在遺傳算法中的應用

楊水清，楊加明，孫超

南昌航空大學飛行器工程學院，南昌 330063

改進的乘冪適應度函數(shù)在遺傳算法中的應用

楊水清，楊加明，孫超

南昌航空大學飛行器工程學院，南昌 330063

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）直接以待解的目標函數(shù)f(x)轉化為適應度函數(shù)Fit(f(x))，這種適應度函數(shù)簡單直觀，即

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

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

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

對于求最大值問題，做下列轉換：

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

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

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

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

2.2.3 改進的乘冪適應度函數(shù)（MGA）

改進的新適應度函數(shù)如下：

式中，F(xiàn)′是經(jīng)過乘冪變換后得到的新適應度函數(shù)；F是原適應度函數(shù)；Cmax是最大估計值，可直接取目標函數(shù)。此時k不再是一個常數(shù)，而是一個隨進化代數(shù)增加的非線性動態(tài)變化的正數(shù)。t是當前的進化代數(shù)；T是最大的遺傳代數(shù)；Favg是當代種群的平均值；ξ是適當大小的數(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)濟模式”，同時影響著現(xiàn)代城市的建設與發(fā)展，使智慧城市建設步入以大數(shù)據(jù)中心為背景的“共享時代”，同時也為智慧城市在我國的建設與發(fā)展開創(chuàng)了新局面，智慧城市在大數(shù)據(jù)平臺的支撐下，會得到更好的發(fā)展[1]。

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

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

該函數(shù)是一個復雜的二維函數(shù)，(x，y)的取值區(qū)間為[-10，10]，可以看出有很多的極大值點，由于該函數(shù)具有強烈的震蕩形態(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ù)是復雜的二維函數(shù)，具有很多的極值點，(x，y)的取值區(qū)間為[-5，5]，三維形狀如圖3所示，圖中圓圈表示各代種群搜尋到的最優(yōu)解。

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

3.2 測試結果與分析

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

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

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

下面討論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收斂波動性較大，且它們在遺傳進化的后期才收斂于最優(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。類似的結論反映在圖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)，結合圖4和圖7，可以得出結論，在收斂速度、收斂精度及收斂穩(wěn)定性方面，MGA均優(yōu)于BGA和EGA。對于測試函數(shù)f2(x，y)和f3(x，y)，分別結合圖5、圖6和圖8、圖9，可以得出如下結論，在收斂速度、收斂精度以及收斂穩(wěn)定性方面，MGA具有明顯優(yōu)勢。

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

4 結論

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

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

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

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

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

[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]孫樹棟，周明.遺傳算法原理及應用[M].北京：國防工業(yè)出版社，2002.

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

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

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

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

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

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

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

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

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

[14]史峰，王輝，郁磊，等.MATLAB智能算法30個案例分析[M].北京：北京航空航天大學出版社，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

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

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

2013-11-05

2014-02-24

1002-8331（2014）17-0040-04

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