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

2014-08-08 23:47:59李茂軍賈玲

計(jì)算技術(shù)與自動(dòng)化 2014年2期

李茂軍+賈玲

收稿日期：2013-09-18

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

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

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



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

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

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

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

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

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

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

計(jì)算技術(shù)與自動(dòng)化2014年6月

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

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

2.1 初始種群

設(shè)種群規(guī)模為N，待優(yōu)化問(wèn)題的變量有M個(gè)，則第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)化問(wèn)題的一組可行解，xij∈［αj,βj］，i=1,2,…,N，j=1,2，…,M。

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

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

本算法采用一個(gè)狀態(tài)進(jìn)化矩陣G來(lái)模擬進(jìn)化算法中的重組與變異操作過(guò)程，這使得算法操作起來(lái)非常簡(jiǎn)單,因此，狀態(tài)進(jìn)化矩陣的構(gòu)造是算法的重點(diǎn)。本文按照式（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）的值是隨機(jī)確定的，本文中G為滿足上述條件的隨機(jī)常數(shù)矩陣，具體構(gòu)造流程如圖2所示。

2.3 選種池和選擇操作

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

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

2.4 算法描述

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

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

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

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

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

3 仿真實(shí)驗(yàn)與性能分析

實(shí)驗(yàn)仿真平臺(tái)為Matlab 7.1。本實(shí)驗(yàn)采用了3個(gè)經(jīng)典測(cè)試函數(shù)，這些測(cè)試函數(shù)為高維多模函數(shù)，具有大量的局部最優(yōu)點(diǎn)，是優(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）

有多個(gè)極小值點(diǎn)，但只有一個(gè)全局最小值-186.73。

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

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

是一個(gè)具有典型欺騙問(wèn)題的函數(shù)，有1個(gè)全局極小值點(diǎn)取值近似為-837.9658，在(420.96 87,420. 9687)處，距離另一個(gè)局部最優(yōu)點(diǎn)很遠(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）

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

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

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

表1 算法對(duì)3個(gè)測(cè)試函數(shù)50次實(shí)驗(yàn)的結(jié)果

函數(shù)

全局最優(yōu)值

平均最優(yōu)值

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

平均收斂代數(shù)

f1

-186.7316

f2

-837.9658

f3

3.0000

8

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

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

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

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

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

4 結(jié) 論

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

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

參考文獻(xiàn)

［1］劉鯖潔,陳桂明,劉小方. 基于矩陣編碼的遺傳算法研究［J］.計(jì)算機(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é)報(bào)：2011,37 (9):1132-1136.

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

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

［6］陳曉峰,楊廣明,黃明.一種實(shí)數(shù)編碼的量子差分進(jìn)化算法［J］.小型微型計(jì)算機(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é)報(bào)：2011,25(2):62-67.

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

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