李茂軍+賈玲

收稿日期：2013-09-18

作者簡介：李茂軍（1964—），男，湖南寧鄉(xiāng)人，教授，博士，研究方向：智能控制與智能計算。

文章編號：1003-6199(2014)02-0085-04

摘 要：傳統(tǒng)進(jìn)化算法主要通過選擇、重組和變異這三種遺傳操作實現(xiàn)種群的進(jìn)化。在進(jìn)化過程中通常需要設(shè)定群體規(guī)模、交叉概率和變異概率等參數(shù)，而且它們的值會直接影響計算結(jié)果及精度。為了簡化操作過程，設(shè)計一種基于離散系統(tǒng)狀態(tài)空間模型的進(jìn)化算法，這種算法采用實數(shù)編碼方式，構(gòu)造一個狀態(tài)進(jìn)化矩陣來實現(xiàn)重組和變異的功能，提高算法的可操作性和可靠性。并將該算法應(yīng)用于求解無約束全局優(yōu)化問題，對幾種典型的測試函數(shù)進(jìn)行仿真，結(jié)果表明：這種新的進(jìn)化算法具有搜索能力強、收斂速度快、計算精度高、操作簡單等優(yōu)點，對相關(guān)研究有參考作用。



關(guān)鍵詞：進(jìn)化算法；狀態(tài)空間模型；實數(shù)編碼；狀態(tài)進(jìn)化矩陣

中圖分類號：TP301.6文獻(xiàn)標(biāo)識碼：A



An Evolutionary Algorithm Based on StatespaceModel



LI Maojun,JIA Ling

(College of Electrical and Information Engineering, Changsha University of Science & Technology, Changsha,Hunan 410114,China)

Abstract:The traditional evolutionary algorithm primarily through three genetic operators: selection, recombination and mutation operations, to achieve the evolution of the population. In the process of evolution, it usually needs to set the crossover probability and mutation probability, which will directly affect the results and precision. In order to simplify the procedure, we design a new evolutionary algorithm, which based on discrete state-space model system and using real-encoding method. The algorithm constructs a state evolution matrix to achieve the function of recombination and mutation, and improve the operability and reliability of the algorithm. We do some simulation based on several typical test functions, the results shows that: this new evolutionary algorithm has many advantages, such as strong search capability, rapid convergence, high precision, simple operation, etc. It has useful reference for relevant studies.



Key words:evolutionary algorithm; state-space model ; real-encoding; state evolution matrix



1 引 言

進(jìn)化算法(EA)是一類模擬生物進(jìn)化機制的智能優(yōu)化方法，如遺傳算法（GA）［1］、蟻群算法（ACO）［2］、模擬退火算法（SA）［3］等。同傳統(tǒng)的梯度法、牛頓法、窮舉法等優(yōu)化算法相比，進(jìn)化計算具有自組織、自適應(yīng)、自學(xué)習(xí)、不受問題性質(zhì)限制的優(yōu)點，因此進(jìn)化算法常用來解決復(fù)雜的工程優(yōu)化問題［4］。隨著科學(xué)的發(fā)展和應(yīng)用需求的增加，傳統(tǒng)進(jìn)化算法已不能滿足工程應(yīng)用需要。幾十年來，許多學(xué)者嘗試了很多方法來更好地解決優(yōu)化問題，如對傳統(tǒng)進(jìn)化算法進(jìn)行改進(jìn)、引入新的理論、結(jié)合兩種或兩種以上進(jìn)化算法等來處理優(yōu)化問題，取得了一定的效果［5-7］。

文獻(xiàn)［8］提出一種改進(jìn)的遺傳算法，為了避免連續(xù)函數(shù)優(yōu)化過程中的早熟收斂和搜索遲鈍，在簡單遺傳算法基礎(chǔ)上提出了劃分尋優(yōu)區(qū)間、基于排序和最佳保留的輪盤賭選擇算子, 并采用擇優(yōu)交叉算子和二元變異算子，提高了算法的運行效率和收斂速度，并可避免陷入局部最優(yōu)；文獻(xiàn)［9］ 針對粒子群算法（PSO）算法存在進(jìn)化后期收斂速度慢、易陷入局部最優(yōu)點的缺點，提出了一種多向?qū)W習(xí)型的粒子群優(yōu)化算法，該算法中粒子通過同時追隨自己找到的最優(yōu)解、隨機的其他粒子同維度的最優(yōu)解和整個群的最優(yōu)解來完成速度更新，通過判別區(qū)域邊界來完成位置優(yōu)化更新，通過對全局最優(yōu)位置進(jìn)行小范圍擾動，以增強算法跳出局部最優(yōu)的能力。明顯改善了全局搜索能力，并且能夠有效避免早熟收斂問題。文獻(xiàn)［10］提出了一種結(jié)合免疫克隆算子的量子遺傳算法（QGA），采用免疫克隆操作及交叉策略提高抗體成熟力及親和性，增強抗體群分布的多樣性及穩(wěn)定性，有效克服了量子遺傳算法容易陷于局部最優(yōu)及計算緩慢的不足。

傳統(tǒng)進(jìn)化算法存在的問題有：一、編程過程比較復(fù)雜，算法開始要先對所求問題進(jìn)行編碼，最后對找到最優(yōu)解還要進(jìn)行解碼；二、遺傳算子和初始種群的選擇對解的品質(zhì)影響很大，大部分需要依靠經(jīng)驗來選擇；三、搜索速度比較慢，要得到精確度高的解需要花很長時間；四、容易出現(xiàn)早熟收斂現(xiàn)象，陷入局部最優(yōu)解而無法跳出。

針對傳統(tǒng)進(jìn)化算法的存在的問題，本文提出一種基于狀態(tài)空間模型的進(jìn)化算法（SEA），這種算法采用實數(shù)編碼方式，構(gòu)造一個狀態(tài)進(jìn)化矩陣來實現(xiàn)種群進(jìn)化，并通過選種池中的選擇操作實現(xiàn)優(yōu)勝劣汰的自然選擇機制。通過對幾種典型函數(shù)的測試結(jié)果表明,該算法具有很強的搜索能力和很高的搜索精度，能快速地找到問題的全局最優(yōu)解。

2 基于狀態(tài)空間模型的進(jìn)化算法

算法基于離散系統(tǒng)狀態(tài)空間模型，引入進(jìn)化計算的基本思想，構(gòu)造一種基于狀態(tài)空間模型X'(k+1)=GX(k)（其中X(k)為第k個采樣時刻的狀態(tài)向量，G為狀態(tài)進(jìn)化矩陣）的進(jìn)化算法。在這種算法中，進(jìn)化算法的群體表示為狀態(tài)向量X(k)，X(k)表示第k代群體，狀態(tài)向量X(k)包含N個分量，每個分量均表示1個個體（這里的個體是按傳統(tǒng)進(jìn)化算法中的實數(shù)編碼方法而得到的），每個個體包含M個變量。在這里，狀態(tài)向量X(k)實際上是一個N×M矩陣，該矩陣的每一行表示一個個體，每一個元素是變量的實數(shù)值。群體進(jìn)化通過狀態(tài)進(jìn)化矩陣G實現(xiàn)，G是一個N×N的矩陣?？苫谶M(jìn)化算法中群體進(jìn)化的基本方法來構(gòu)造狀態(tài)進(jìn)化矩陣G，也可以通過其它途徑來構(gòu)造狀態(tài)進(jìn)化矩陣G。本文主要基于進(jìn)化計算中群體進(jìn)化的基本思想來構(gòu)造狀態(tài)進(jìn)化矩陣G。其計算模型如圖1所示。

計算技術(shù)與自動化2014年6月

第33卷第2期李茂軍等:一種基于狀態(tài)空間模型的進(jìn)化算法

圖1 基于狀態(tài)空間模型的進(jìn)化算法計算模型

2.1 初始種群

設(shè)種群規(guī)模為N，待優(yōu)化問題的變量有M個，則第k代群體X(k)為

X(k)=x11x12…x1Mx21x22…x2M…xN1xN2…xNM （1） 

其中Xi=(xi1,xi2,…,xiM)，i=1,2,…,N為優(yōu)化問題的一組可行解，xij∈［αj,βj］，i=1,2,…,N，j=1,2，…,M。

在算法初始化階段，用隨機函數(shù)產(chǎn)生N組、每組M個分別在αj,βj(j=1,2，…,M)上服從均勻分布的實數(shù)構(gòu)成初始種群X0。

2.2 狀態(tài)進(jìn)化矩陣

本算法采用一個狀態(tài)進(jìn)化矩陣G來模擬進(jìn)化算法中的重組與變異操作過程，這使得算法操作起來非常簡單,因此，狀態(tài)進(jìn)化矩陣的構(gòu)造是算法的重點。本文按照式（2）構(gòu)造狀態(tài)進(jìn)化矩陣G

G=g11g12…g1Ng21g22…g2N…gN1gN2…gNN （2）

其中0≤gij≤1,i,j=1,2,…,N，且∑nj=1gij≤1 ，矩陣G中元素gij（i,j=1,2,…,N）的值是隨機確定的，本文中G為滿足上述條件的隨機常數(shù)矩陣，具體構(gòu)造流程如圖2所示。

2.3 選種池和選擇操作

同傳統(tǒng)進(jìn)化算法類似，選擇操作是一個擇優(yōu)的過程，體現(xiàn)了優(yōu)勝劣汰的進(jìn)化思想，本文按最小化優(yōu)化問題尋優(yōu)。如圖1所示，從初始群體X(0)開始，按照X'(k+1)=GX(k)迭代，可依次得到一系列群體X'(1),X'(2),X'(3),……。群體X'(k+1)和X(k)(k= 0,1,2,…)同時進(jìn)入選種池，按照適應(yīng)度函數(shù)f()計算選種池中每個群體的適應(yīng)度值Y(k)，按照從小到大排列，選擇前N個個體組成新一代群體X(k+1)，如此反復(fù)，直到算法滿足停機條件。

圖2 狀態(tài)進(jìn)化矩陣構(gòu)造流程圖

2.4 算法描述

Step 1. 初始化種群 X(0),并計算初始種群的適應(yīng)度值；

Step 2. 根據(jù)圖2流程得到狀態(tài)進(jìn)化矩陣G；

Step 3. 進(jìn)行進(jìn)化操作，X'(k+1)=G?X(k)，并計算種群X'(k+1)適應(yīng)度值；

Step 4. 將種群X(k)，X'(k+1)同時放入選種池，按適應(yīng)度值從小到大排列，選擇前N個個體作為新一代的群體X(k+1)；

Step 5. 是否滿足終止條件：若是，則結(jié)束；否則，轉(zhuǎn)到Step 3。

3 仿真實驗與性能分析

實驗仿真平臺為Matlab 7.1。本實驗采用了3個經(jīng)典測試函數(shù)，這些測試函數(shù)為高維多模函數(shù)，具有大量的局部最優(yōu)點，是優(yōu)化領(lǐng)域中公認(rèn)的較難優(yōu)化的函數(shù)。

1)Shubert函數(shù)

f1=∑5i=1icos ［(i+1)x+i］?

∑5i=1icos ［(i+1)y+i］－10≤x,y≤10 （3）

有多個極小值點，但只有一個全局最小值-186.73。

2)Schwefel's函數(shù)

f2=－xsin (x)－ysin (y)－500≤x,y≤500（4）

是一個具有典型欺騙問題的函數(shù)，有1個全局極小值點取值近似為-837.9658，在(420.96 87,420. 9687)處，距離另一個局部最優(yōu)點很遠(yuǎn)，因此如果陷入局部最優(yōu)就很難跳出。

(3)GoldsteinPrice函數(shù)

f3=［1+(x+y+1)2(19－14x+3x2－14y+6xy+3y2)］?［30+(2x－3y)2(18－32x+12x2+48y－36xy+27y2)］－2≤x,y≤2（5）

這是一個多模函數(shù)，有多個極小值點，但只有一個全局最小值3，極小值點為(0,-1)。

在測試中，將種群大小設(shè)置為500，每次運行代數(shù)為60代，每個測試函數(shù)運行測試50次。表1顯示了函數(shù)f1~f3運行50次的實驗結(jié)果，包括平均最優(yōu)值、標(biāo)準(zhǔn)差和平均收斂代數(shù)。全局最優(yōu)值為f1~f3理論最優(yōu)值，平均最優(yōu)值fmav按照公式（6）計算得到（其中fmi為第i次運用本算法求解f1~f3優(yōu)化問題得到的最優(yōu)解對應(yīng)的適應(yīng)度函數(shù)值），標(biāo)準(zhǔn)差為平均最優(yōu)值與全局最優(yōu)值之差，平均收斂代數(shù)為每次實驗找到最優(yōu)解所需要的最少代數(shù)的平均值。

fmav=∑50i=1fmi/50，i=1,2,…,50（6）

表1 算法對3個測試函數(shù)50次實驗的結(jié)果

函數(shù)

全局最優(yōu)值

平均最優(yōu)值

標(biāo)準(zhǔn)差

平均收斂代數(shù)

f1

-186.7316

-186.7316

0

9

f2

-837.9658

-837.9658

0

12

f3

3.0000

3.0000

0

8

圖3~5分別顯示了運用本算法求解函數(shù)f1~f3優(yōu)化問題所得到的最優(yōu)解對應(yīng)的適應(yīng)度函數(shù)值隨進(jìn)化代數(shù)變化曲線。

圖3 算法求解f1優(yōu)化問題適應(yīng)度函數(shù)值變化曲線 

圖4 算法求解f2優(yōu)化問題適應(yīng)度函數(shù)值變化曲線

圖5 算法求解f3優(yōu)化問題適應(yīng)度函數(shù)值變化曲線

從表1和圖3~5可以看出，本文提出的算法在3個函數(shù)優(yōu)化中取得了良好的效果，找到最優(yōu)解的成功率高，收斂速度快。通過50次實驗結(jié)果可以看出，基于狀態(tài)空間模型的進(jìn)化算法穩(wěn)定性好，成功率高。

4 結(jié) 論

本文設(shè)計了一種基于離散系統(tǒng)狀態(tài)空間模型的進(jìn)化算法，以基本進(jìn)化算法的思想為基礎(chǔ)，借鑒矩陣?yán)碚摵蛯崝?shù)編碼方法，通過構(gòu)造一個狀態(tài)進(jìn)化矩陣，來實現(xiàn)種群的進(jìn)化，提高了算法的可操作性和可靠性。通過對3個經(jīng)典優(yōu)化測試函數(shù)進(jìn)行優(yōu)化實驗，結(jié)果表明：本文提出的算法增強了防止陷入局部最優(yōu)的能力，能夠較大地提高收斂速度和精度，而且穩(wěn)定性能很好。

雖然算法的仿真結(jié)果是令人滿意的，但是由于實驗條件的局限性和實驗次數(shù)的有限性，算法收斂性和遍歷性還需要通過進(jìn)一步的數(shù)學(xué)證明。如何構(gòu)造更好的狀態(tài)進(jìn)化矩陣，是需要進(jìn)一步研究的問題。

參考文獻(xiàn)

［1］ 劉鯖潔,陳桂明,劉小方. 基于矩陣編碼的遺傳算法研究［J］.計算機工程：2011, 37(13):160-162.

［2］ IRINA CIORNEI, ELIAS KYRIAKIDES. Hybrid Ant Colony-Genetic Algorithm (GAAPI) for Global Continuous Optimization ［J］. Systems, Man, and Cybernetics, part B, 2012, 42(1), 34-245.

［3］ 董麗麗,龔光紅,李妮,等.基于云模型的自適應(yīng)并行模擬退火遺傳算法［J］.北京航空航天大學(xué)學(xué)報：2011,37 (9):1132-1136.

［4］ 劉正龍,楊艷梅.基于遺傳算法的數(shù)值優(yōu)化約束問題的研究［J］.計算機系統(tǒng)應(yīng)用：2013,22(5):139-142.

［5］ 王巍,趙文紅,王宇平.一種有效的解無約束全局優(yōu)化的進(jìn)化算法［J］.控制理論與應(yīng)用：2010,27 (5):570-574.

［6］ 陳曉峰,楊廣明,黃明.一種實數(shù)編碼的量子差分進(jìn)化算法［J］.小型微型計算機系統(tǒng)：2013,34(5):1141-1146.

［7］ YUSUKE T,YOSHIFUMIO,SHINJIW, et al. BinaryBased Topology Optimization of Magnetostatic Shielding by a Hybrid Evolutionary Algorithm Combining Genetic Algorithm and ExtendedCompact Genetic Algorithm ［J］. Magnetics:2013,49 (5) :2093-2096.

［8］ 王越,許全文,黃麗豐.基于改進(jìn)遺傳算法的連續(xù)函數(shù)優(yōu)化［J］.重慶理工大學(xué)學(xué)報：2011,25(2):62-67.

［9］ 闞超豪.多向?qū)W習(xí)自適應(yīng)的粒子群算法［J］.計算機工程與應(yīng)用：2013,49(6):23-28.

［10］徐雪松,王四春.基于免疫量子遺傳算法的多峰函數(shù)尋優(yōu)［J］.計算機應(yīng)用：2012，32(6):1674-1677.

計算技術(shù)與自動化2014年6月

第33卷第2期李茂軍等:一種基于狀態(tài)空間模型的進(jìn)化算法

圖1 基于狀態(tài)空間模型的進(jìn)化算法計算模型

2.1 初始種群

設(shè)種群規(guī)模為N，待優(yōu)化問題的變量有M個，則第k代群體X(k)為

X(k)=x11x12…x1Mx21x22…x2M…xN1xN2…xNM （1） 

其中Xi=(xi1,xi2,…,xiM)，i=1,2,…,N為優(yōu)化問題的一組可行解，xij∈［αj,βj］，i=1,2,…,N，j=1,2，…,M。

在算法初始化階段，用隨機函數(shù)產(chǎn)生N組、每組M個分別在αj,βj(j=1,2，…,M)上服從均勻分布的實數(shù)構(gòu)成初始種群X0。

2.2 狀態(tài)進(jìn)化矩陣

本算法采用一個狀態(tài)進(jìn)化矩陣G來模擬進(jìn)化算法中的重組與變異操作過程，這使得算法操作起來非常簡單,因此，狀態(tài)進(jìn)化矩陣的構(gòu)造是算法的重點。本文按照式（2）構(gòu)造狀態(tài)進(jìn)化矩陣G

G=g11g12…g1Ng21g22…g2N…gN1gN2…gNN （2）

其中0≤gij≤1,i,j=1,2,…,N，且∑nj=1gij≤1 ，矩陣G中元素gij（i,j=1,2,…,N）的值是隨機確定的，本文中G為滿足上述條件的隨機常數(shù)矩陣，具體構(gòu)造流程如圖2所示。

2.3 選種池和選擇操作

同傳統(tǒng)進(jìn)化算法類似，選擇操作是一個擇優(yōu)的過程，體現(xiàn)了優(yōu)勝劣汰的進(jìn)化思想，本文按最小化優(yōu)化問題尋優(yōu)。如圖1所示，從初始群體X(0)開始，按照X'(k+1)=GX(k)迭代，可依次得到一系列群體X'(1),X'(2),X'(3),……。群體X'(k+1)和X(k)(k= 0,1,2,…)同時進(jìn)入選種池，按照適應(yīng)度函數(shù)f()計算選種池中每個群體的適應(yīng)度值Y(k)，按照從小到大排列，選擇前N個個體組成新一代群體X(k+1)，如此反復(fù)，直到算法滿足停機條件。

圖2 狀態(tài)進(jìn)化矩陣構(gòu)造流程圖

2.4 算法描述

Step 1. 初始化種群 X(0),并計算初始種群的適應(yīng)度值；

Step 2. 根據(jù)圖2流程得到狀態(tài)進(jìn)化矩陣G；

Step 3. 進(jìn)行進(jìn)化操作，X'(k+1)=G?X(k)，并計算種群X'(k+1)適應(yīng)度值；

Step 4. 將種群X(k)，X'(k+1)同時放入選種池，按適應(yīng)度值從小到大排列，選擇前N個個體作為新一代的群體X(k+1)；

Step 5. 是否滿足終止條件：若是，則結(jié)束；否則，轉(zhuǎn)到Step 3。

3 仿真實驗與性能分析

實驗仿真平臺為Matlab 7.1。本實驗采用了3個經(jīng)典測試函數(shù)，這些測試函數(shù)為高維多模函數(shù)，具有大量的局部最優(yōu)點，是優(yōu)化領(lǐng)域中公認(rèn)的較難優(yōu)化的函數(shù)。

1)Shubert函數(shù)

f1=∑5i=1icos ［(i+1)x+i］?

∑5i=1icos ［(i+1)y+i］－10≤x,y≤10 （3）

有多個極小值點，但只有一個全局最小值-186.73。

2)Schwefel's函數(shù)

f2=－xsin (x)－ysin (y)－500≤x,y≤500（4）

是一個具有典型欺騙問題的函數(shù)，有1個全局極小值點取值近似為-837.9658，在(420.96 87,420. 9687)處，距離另一個局部最優(yōu)點很遠(yuǎn)，因此如果陷入局部最優(yōu)就很難跳出。

(3)GoldsteinPrice函數(shù)

f3=［1+(x+y+1)2(19－14x+3x2－14y+6xy+3y2)］?［30+(2x－3y)2(18－32x+12x2+48y－36xy+27y2)］－2≤x,y≤2（5）

這是一個多模函數(shù)，有多個極小值點，但只有一個全局最小值3，極小值點為(0,-1)。

在測試中，將種群大小設(shè)置為500，每次運行代數(shù)為60代，每個測試函數(shù)運行測試50次。表1顯示了函數(shù)f1~f3運行50次的實驗結(jié)果，包括平均最優(yōu)值、標(biāo)準(zhǔn)差和平均收斂代數(shù)。全局最優(yōu)值為f1~f3理論最優(yōu)值，平均最優(yōu)值fmav按照公式（6）計算得到（其中fmi為第i次運用本算法求解f1~f3優(yōu)化問題得到的最優(yōu)解對應(yīng)的適應(yīng)度函數(shù)值），標(biāo)準(zhǔn)差為平均最優(yōu)值與全局最優(yōu)值之差，平均收斂代數(shù)為每次實驗找到最優(yōu)解所需要的最少代數(shù)的平均值。

fmav=∑50i=1fmi/50，i=1,2,…,50（6）

表1 算法對3個測試函數(shù)50次實驗的結(jié)果

函數(shù)

全局最優(yōu)值

平均最優(yōu)值

標(biāo)準(zhǔn)差

平均收斂代數(shù)

f1

-186.7316

-186.7316

0

9

f2

-837.9658

-837.9658

0

12

f3

3.0000

3.0000

0

8

圖3~5分別顯示了運用本算法求解函數(shù)f1~f3優(yōu)化問題所得到的最優(yōu)解對應(yīng)的適應(yīng)度函數(shù)值隨進(jìn)化代數(shù)變化曲線。

圖3 算法求解f1優(yōu)化問題適應(yīng)度函數(shù)值變化曲線 

圖4 算法求解f2優(yōu)化問題適應(yīng)度函數(shù)值變化曲線

圖5 算法求解f3優(yōu)化問題適應(yīng)度函數(shù)值變化曲線

從表1和圖3~5可以看出，本文提出的算法在3個函數(shù)優(yōu)化中取得了良好的效果，找到最優(yōu)解的成功率高，收斂速度快。通過50次實驗結(jié)果可以看出，基于狀態(tài)空間模型的進(jìn)化算法穩(wěn)定性好，成功率高。

4 結(jié) 論

本文設(shè)計了一種基于離散系統(tǒng)狀態(tài)空間模型的進(jìn)化算法，以基本進(jìn)化算法的思想為基礎(chǔ)，借鑒矩陣?yán)碚摵蛯崝?shù)編碼方法，通過構(gòu)造一個狀態(tài)進(jìn)化矩陣，來實現(xiàn)種群的進(jìn)化，提高了算法的可操作性和可靠性。通過對3個經(jīng)典優(yōu)化測試函數(shù)進(jìn)行優(yōu)化實驗，結(jié)果表明：本文提出的算法增強了防止陷入局部最優(yōu)的能力，能夠較大地提高收斂速度和精度，而且穩(wěn)定性能很好。

雖然算法的仿真結(jié)果是令人滿意的，但是由于實驗條件的局限性和實驗次數(shù)的有限性，算法收斂性和遍歷性還需要通過進(jìn)一步的數(shù)學(xué)證明。如何構(gòu)造更好的狀態(tài)進(jìn)化矩陣，是需要進(jìn)一步研究的問題。

參考文獻(xiàn)

［1］ 劉鯖潔,陳桂明,劉小方. 基于矩陣編碼的遺傳算法研究［J］.計算機工程：2011, 37(13):160-162.

［2］ IRINA CIORNEI, ELIAS KYRIAKIDES. Hybrid Ant Colony-Genetic Algorithm (GAAPI) for Global Continuous Optimization ［J］. Systems, Man, and Cybernetics, part B, 2012, 42(1), 34-245.

［3］ 董麗麗,龔光紅,李妮,等.基于云模型的自適應(yīng)并行模擬退火遺傳算法［J］.北京航空航天大學(xué)學(xué)報：2011,37 (9):1132-1136.

［4］ 劉正龍,楊艷梅.基于遺傳算法的數(shù)值優(yōu)化約束問題的研究［J］.計算機系統(tǒng)應(yīng)用：2013,22(5):139-142.

［5］ 王巍,趙文紅,王宇平.一種有效的解無約束全局優(yōu)化的進(jìn)化算法［J］.控制理論與應(yīng)用：2010,27 (5):570-574.

［6］ 陳曉峰,楊廣明,黃明.一種實數(shù)編碼的量子差分進(jìn)化算法［J］.小型微型計算機系統(tǒng)：2013,34(5):1141-1146.

［7］ YUSUKE T,YOSHIFUMIO,SHINJIW, et al. BinaryBased Topology Optimization of Magnetostatic Shielding by a Hybrid Evolutionary Algorithm Combining Genetic Algorithm and ExtendedCompact Genetic Algorithm ［J］. Magnetics:2013,49 (5) :2093-2096.

［8］ 王越,許全文,黃麗豐.基于改進(jìn)遺傳算法的連續(xù)函數(shù)優(yōu)化［J］.重慶理工大學(xué)學(xué)報：2011,25(2):62-67.

［9］ 闞超豪.多向?qū)W習(xí)自適應(yīng)的粒子群算法［J］.計算機工程與應(yīng)用：2013,49(6):23-28.

［10］徐雪松,王四春.基于免疫量子遺傳算法的多峰函數(shù)尋優(yōu)［J］.計算機應(yīng)用：2012，32(6):1674-1677.

計算技術(shù)與自動化2014年6月

第33卷第2期李茂軍等:一種基于狀態(tài)空間模型的進(jìn)化算法

圖1 基于狀態(tài)空間模型的進(jìn)化算法計算模型

2.1 初始種群

設(shè)種群規(guī)模為N，待優(yōu)化問題的變量有M個，則第k代群體X(k)為

X(k)=x11x12…x1Mx21x22…x2M…xN1xN2…xNM （1） 

其中Xi=(xi1,xi2,…,xiM)，i=1,2,…,N為優(yōu)化問題的一組可行解，xij∈［αj,βj］，i=1,2,…,N，j=1,2，…,M。

在算法初始化階段，用隨機函數(shù)產(chǎn)生N組、每組M個分別在αj,βj(j=1,2，…,M)上服從均勻分布的實數(shù)構(gòu)成初始種群X0。

2.2 狀態(tài)進(jìn)化矩陣

本算法采用一個狀態(tài)進(jìn)化矩陣G來模擬進(jìn)化算法中的重組與變異操作過程，這使得算法操作起來非常簡單,因此，狀態(tài)進(jìn)化矩陣的構(gòu)造是算法的重點。本文按照式（2）構(gòu)造狀態(tài)進(jìn)化矩陣G

G=g11g12…g1Ng21g22…g2N…gN1gN2…gNN （2）

其中0≤gij≤1,i,j=1,2,…,N，且∑nj=1gij≤1 ，矩陣G中元素gij（i,j=1,2,…,N）的值是隨機確定的，本文中G為滿足上述條件的隨機常數(shù)矩陣，具體構(gòu)造流程如圖2所示。

2.3 選種池和選擇操作

同傳統(tǒng)進(jìn)化算法類似，選擇操作是一個擇優(yōu)的過程，體現(xiàn)了優(yōu)勝劣汰的進(jìn)化思想，本文按最小化優(yōu)化問題尋優(yōu)。如圖1所示，從初始群體X(0)開始，按照X'(k+1)=GX(k)迭代，可依次得到一系列群體X'(1),X'(2),X'(3),……。群體X'(k+1)和X(k)(k= 0,1,2,…)同時進(jìn)入選種池，按照適應(yīng)度函數(shù)f()計算選種池中每個群體的適應(yīng)度值Y(k)，按照從小到大排列，選擇前N個個體組成新一代群體X(k+1)，如此反復(fù)，直到算法滿足停機條件。

圖2 狀態(tài)進(jìn)化矩陣構(gòu)造流程圖

2.4 算法描述

Step 1. 初始化種群 X(0),并計算初始種群的適應(yīng)度值；

Step 2. 根據(jù)圖2流程得到狀態(tài)進(jìn)化矩陣G；

Step 3. 進(jìn)行進(jìn)化操作，X'(k+1)=G?X(k)，并計算種群X'(k+1)適應(yīng)度值；

Step 4. 將種群X(k)，X'(k+1)同時放入選種池，按適應(yīng)度值從小到大排列，選擇前N個個體作為新一代的群體X(k+1)；

Step 5. 是否滿足終止條件：若是，則結(jié)束；否則，轉(zhuǎn)到Step 3。

3 仿真實驗與性能分析

實驗仿真平臺為Matlab 7.1。本實驗采用了3個經(jīng)典測試函數(shù)，這些測試函數(shù)為高維多模函數(shù)，具有大量的局部最優(yōu)點，是優(yōu)化領(lǐng)域中公認(rèn)的較難優(yōu)化的函數(shù)。

1)Shubert函數(shù)

f1=∑5i=1icos ［(i+1)x+i］?

∑5i=1icos ［(i+1)y+i］－10≤x,y≤10 （3）

有多個極小值點，但只有一個全局最小值-186.73。

2)Schwefel's函數(shù)

f2=－xsin (x)－ysin (y)－500≤x,y≤500（4）

是一個具有典型欺騙問題的函數(shù)，有1個全局極小值點取值近似為-837.9658，在(420.96 87,420. 9687)處，距離另一個局部最優(yōu)點很遠(yuǎn)，因此如果陷入局部最優(yōu)就很難跳出。

(3)GoldsteinPrice函數(shù)

f3=［1+(x+y+1)2(19－14x+3x2－14y+6xy+3y2)］?［30+(2x－3y)2(18－32x+12x2+48y－36xy+27y2)］－2≤x,y≤2（5）

這是一個多模函數(shù)，有多個極小值點，但只有一個全局最小值3，極小值點為(0,-1)。

在測試中，將種群大小設(shè)置為500，每次運行代數(shù)為60代，每個測試函數(shù)運行測試50次。表1顯示了函數(shù)f1~f3運行50次的實驗結(jié)果，包括平均最優(yōu)值、標(biāo)準(zhǔn)差和平均收斂代數(shù)。全局最優(yōu)值為f1~f3理論最優(yōu)值，平均最優(yōu)值fmav按照公式（6）計算得到（其中fmi為第i次運用本算法求解f1~f3優(yōu)化問題得到的最優(yōu)解對應(yīng)的適應(yīng)度函數(shù)值），標(biāo)準(zhǔn)差為平均最優(yōu)值與全局最優(yōu)值之差，平均收斂代數(shù)為每次實驗找到最優(yōu)解所需要的最少代數(shù)的平均值。

fmav=∑50i=1fmi/50，i=1,2,…,50（6）

表1 算法對3個測試函數(shù)50次實驗的結(jié)果

函數(shù)

全局最優(yōu)值

平均最優(yōu)值

標(biāo)準(zhǔn)差

平均收斂代數(shù)

f1

-186.7316

-186.7316

0

9

f2

-837.9658

-837.9658

0

12

f3

3.0000

3.0000

0

8

圖3~5分別顯示了運用本算法求解函數(shù)f1~f3優(yōu)化問題所得到的最優(yōu)解對應(yīng)的適應(yīng)度函數(shù)值隨進(jìn)化代數(shù)變化曲線。

圖3 算法求解f1優(yōu)化問題適應(yīng)度函數(shù)值變化曲線 

圖4 算法求解f2優(yōu)化問題適應(yīng)度函數(shù)值變化曲線

圖5 算法求解f3優(yōu)化問題適應(yīng)度函數(shù)值變化曲線

從表1和圖3~5可以看出，本文提出的算法在3個函數(shù)優(yōu)化中取得了良好的效果，找到最優(yōu)解的成功率高，收斂速度快。通過50次實驗結(jié)果可以看出，基于狀態(tài)空間模型的進(jìn)化算法穩(wěn)定性好，成功率高。

4 結(jié) 論

本文設(shè)計了一種基于離散系統(tǒng)狀態(tài)空間模型的進(jìn)化算法，以基本進(jìn)化算法的思想為基礎(chǔ)，借鑒矩陣?yán)碚摵蛯崝?shù)編碼方法，通過構(gòu)造一個狀態(tài)進(jìn)化矩陣，來實現(xiàn)種群的進(jìn)化，提高了算法的可操作性和可靠性。通過對3個經(jīng)典優(yōu)化測試函數(shù)進(jìn)行優(yōu)化實驗，結(jié)果表明：本文提出的算法增強了防止陷入局部最優(yōu)的能力，能夠較大地提高收斂速度和精度，而且穩(wěn)定性能很好。

雖然算法的仿真結(jié)果是令人滿意的，但是由于實驗條件的局限性和實驗次數(shù)的有限性，算法收斂性和遍歷性還需要通過進(jìn)一步的數(shù)學(xué)證明。如何構(gòu)造更好的狀態(tài)進(jìn)化矩陣，是需要進(jìn)一步研究的問題。

參考文獻(xiàn)

［1］ 劉鯖潔,陳桂明,劉小方. 基于矩陣編碼的遺傳算法研究［J］.計算機工程：2011, 37(13):160-162.

［2］ IRINA CIORNEI, ELIAS KYRIAKIDES. Hybrid Ant Colony-Genetic Algorithm (GAAPI) for Global Continuous Optimization ［J］. Systems, Man, and Cybernetics, part B, 2012, 42(1), 34-245.

［3］ 董麗麗,龔光紅,李妮,等.基于云模型的自適應(yīng)并行模擬退火遺傳算法［J］.北京航空航天大學(xué)學(xué)報：2011,37 (9):1132-1136.

［4］ 劉正龍,楊艷梅.基于遺傳算法的數(shù)值優(yōu)化約束問題的研究［J］.計算機系統(tǒng)應(yīng)用：2013,22(5):139-142.

［5］ 王巍,趙文紅,王宇平.一種有效的解無約束全局優(yōu)化的進(jìn)化算法［J］.控制理論與應(yīng)用：2010,27 (5):570-574.

［6］ 陳曉峰,楊廣明,黃明.一種實數(shù)編碼的量子差分進(jìn)化算法［J］.小型微型計算機系統(tǒng)：2013,34(5):1141-1146.

［7］ YUSUKE T,YOSHIFUMIO,SHINJIW, et al. BinaryBased Topology Optimization of Magnetostatic Shielding by a Hybrid Evolutionary Algorithm Combining Genetic Algorithm and ExtendedCompact Genetic Algorithm ［J］. Magnetics:2013,49 (5) :2093-2096.

［8］ 王越,許全文,黃麗豐.基于改進(jìn)遺傳算法的連續(xù)函數(shù)優(yōu)化［J］.重慶理工大學(xué)學(xué)報：2011,25(2):62-67.

［9］ 闞超豪.多向?qū)W習(xí)自適應(yīng)的粒子群算法［J］.計算機工程與應(yīng)用：2013,49(6):23-28.

［10］徐雪松,王四春.基于免疫量子遺傳算法的多峰函數(shù)尋優(yōu)［J］.計算機應(yīng)用：2012，32(6):1674-1677.