基于遺傳算法和模擬退火算法的混合算法

1、第33卷第2期2008年4月昆明理工大學(xué)學(xué)報(bào)(理工版Journal of Kun m ing University of Science and Technol ogy (Science and Technol ogy Vol .33No 12Ap r .2008收稿日期:2007-11-01.基金項(xiàng)目:全國(guó)統(tǒng)計(jì)科學(xué)研究項(xiàng)目(項(xiàng)目編號(hào):2006C39.第一作者簡(jiǎn)介:牛向陽(yáng)(1976-,男,碩士,副教授,主要研究方向:系統(tǒng)優(yōu)化與智能計(jì)算.基于遺傳算法和模擬退火算法的混合算法牛向陽(yáng)1,倪前月1,高成修2(1.阜陽(yáng)師范學(xué)院數(shù)學(xué)系,安徽阜陽(yáng)236032;2.武漢大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,湖北武漢430072

2、摘要:結(jié)合離散時(shí)間系統(tǒng)最優(yōu)控制問題,提出一種新的混合算法.該算法是在遺傳操作中嵌入模擬退火算子,有效地結(jié)合了遺傳算法隱含并行與模擬退火算法全局尋優(yōu)的特點(diǎn),同時(shí)用罰函數(shù)方法處理約束條件,設(shè)計(jì)了專門的遺傳操作算子,構(gòu)造了相應(yīng)的適應(yīng)度函數(shù),實(shí)現(xiàn)了離散時(shí)間系統(tǒng)的最優(yōu)控制.實(shí)驗(yàn)結(jié)果表明,新算法既具有較快的收斂速度,又能夠收斂到最優(yōu)解.關(guān)鍵詞:遺傳算法;模擬退火算法;最優(yōu)控制理論;離散時(shí)間系統(tǒng)中圖分類號(hào):TP0273文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1007-855X (200802-0025-04A Hybr i d A lgor ith m Ba sed on Geneti c A lgor ithm and

3、S i m ul a ted Annea li n g A lgor ith mN I U Xi ang 2yang 1,N IQ i an 2yue 1,GAO Che ng 2xi u 2(1.Depart m ent of Mathe matics,School ofM athe matics and Computati onal Science,Fuyang Teachers College,Fuyang,Anhui 236032,China;2.School of Mathe matics and Statistics,W uhan University,W uhan 430072,

4、China Abstract:By e mbedding si m ulated annealing operat or int o genetic algorith m ,a hybrid algorith m is put f or ward,which assi m ilates advantages of both genetic algorith m and si m ulated annealing algorithm.Penalty functi on is a 2dop ted t o deal with constraint conditi ons .Specific gen

5、etic algorith m operat ors are als o designed t o construct fit 2ness functi on .The op ti m al contr ol of discrete ti m e syste m is therefore realized .It is p r oved that this algorithm can converge not only quickly but als o t o the op ti m al s oluti on .Key words:genetic algorith m;si m ulate

6、d annealing algorith m;op ti m al contr ol theory;discrete 2ti m e syste m 0引言離散時(shí)間系統(tǒng)的最優(yōu)控制是最優(yōu)控制理論的一類典型問題,在實(shí)際控制工程中應(yīng)用廣泛.此類問題的求解可歸結(jié)為數(shù)學(xué)規(guī)劃問題的求解,常用方法有古典變分法、最小值原理、動(dòng)態(tài)規(guī)劃,但這些方法需要計(jì)算目標(biāo)函數(shù)的梯度,易于陷入局部極值1.遺傳算法與模擬退火算法是最近幾年用于優(yōu)化問題的2種智能算法,基于各自不同的機(jī)理有著不同的應(yīng)用空間.模擬退火算法是模擬熱力學(xué)中物理淬火過(guò)程的一種學(xué)習(xí)規(guī)則,該算法既能向目標(biāo)函數(shù)優(yōu)化的方向迭代,又能以一定的概率接受目標(biāo)函數(shù)劣化的情況

7、,從而避免了陷入局部最優(yōu)點(diǎn),保證獲得全局最優(yōu)解的可靠性,但收斂速度較慢2.遺傳算法是模擬自然進(jìn)化過(guò)程的隨機(jī)搜索算法,能以較大的概率搜索到整體最優(yōu)解,具有全局尋優(yōu)和隱含并行性的特點(diǎn),但存在早熟收斂的缺陷3.本文結(jié)合遺傳算法和模擬退火算法各自的優(yōu)點(diǎn),提出一種收斂速度快可用離散時(shí)間系統(tǒng)最優(yōu)控制問題的混合算法.1離散時(shí)間系統(tǒng)最優(yōu)控制問題最優(yōu)控制,又稱為動(dòng)態(tài)或過(guò)程最優(yōu)化,是現(xiàn)代控制理論的一個(gè)最重要、最基本的組成部分.它所研究的中心問題是:如何根據(jù)受控系統(tǒng)的動(dòng)態(tài)特性,在滿足一定約束條件下,尋求最優(yōu)控制規(guī)律(控制策略,才能使得系統(tǒng)按照一定的技術(shù)要求進(jìn)行運(yùn)轉(zhuǎn),使其在規(guī)定的性能指標(biāo)(目標(biāo)函數(shù)下具有最優(yōu)值,即尋找

8、一個(gè)容許的控制規(guī)律使動(dòng)態(tài)系統(tǒng)(受控對(duì)象從初始狀態(tài)轉(zhuǎn)移到某種要求的終端狀態(tài),保證所規(guī)定的性能指標(biāo)達(dá)到最小(大值.離散時(shí)間系統(tǒng)的最優(yōu)控制問題可以表示成數(shù)學(xué)規(guī)劃問題,通常有狀態(tài)的時(shí)間邊界條件約束,本文考慮狀態(tài)的始端和終端均固定的情形.這種控制變量受區(qū)間約束的離散時(shí)間系統(tǒng)最優(yōu)控制的數(shù)學(xué)模型可表示為:m in f=T-1k=0L(x k,u k,k+K(x Ts1t1x k+1=A x k+B u kx0=x(0,x T=x(Tu kU k(1其中x kR m,u kR n,k=0,1,T.A為m×m實(shí)矩陣,B為m×n實(shí)矩陣,A,B非退化,并且假定nT>m n.2基于遺傳算法和

9、模擬退火算法的混合算法遺傳算法主要借用生物進(jìn)化中“適者生存”規(guī)律,首先對(duì)優(yōu)化問題的解進(jìn)行編碼,此處一個(gè)解的編碼稱為一個(gè)染色體,組成編碼的元素稱為基因.然后依據(jù)優(yōu)化問題的目標(biāo)函數(shù)構(gòu)造出相應(yīng)的適應(yīng)度函數(shù),并以適應(yīng)度函數(shù)的大小決定的概率分布來(lái)對(duì)染色體進(jìn)行優(yōu)勝劣汰,生存下來(lái)的染色體組成種群,同時(shí)再依據(jù)上述概率分布隨機(jī)產(chǎn)生雙親.接著,雙親通過(guò)編碼間的交配產(chǎn)生子代,子代以一定的概率發(fā)生變異,構(gòu)成新的種群,此時(shí)通過(guò)解碼,返回成優(yōu)化問題的解.最終給出終止規(guī)則,通過(guò)上述循環(huán),得出原問題的解.遺傳算法在對(duì)目標(biāo)函數(shù)優(yōu)化時(shí),能以較大的概率搜索到整體最優(yōu)解,具有全局尋優(yōu)和隱含并行性的特點(diǎn),但存在早熟收斂的缺陷.模擬退火

10、算法是模擬熱力學(xué)中物理淬火過(guò)程一種學(xué)習(xí)規(guī)則,其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問題之間的相似性,在某一初始溫度下,伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局優(yōu)解,即在局部最優(yōu)解中能概率性地跳出并最終趨于全局最優(yōu).該算法既能向目標(biāo)函數(shù)優(yōu)化的方向迭代,又能以一定的概率接受目標(biāo)函數(shù)劣化的情況,從而避免了陷入局部最優(yōu)點(diǎn),保證獲得全局最優(yōu)解的可靠性,但當(dāng)規(guī)模變大時(shí),學(xué)習(xí)時(shí)間加劇,收斂速度較慢.針對(duì)上述遺傳算法和模擬退火算法的各自缺陷,本文結(jié)合二者的優(yōu)點(diǎn),提出一種新的混合算法,具體過(guò)程如下:Step1給定模擬退火溫度初始值為c0,進(jìn)化代數(shù)計(jì)數(shù)器k=1.Ste

11、p2用實(shí)數(shù)編碼對(duì)各個(gè)狀態(tài)進(jìn)行編碼,隨機(jī)產(chǎn)生初始群體;Step3結(jié)合退火罰因子構(gòu)造適應(yīng)度函數(shù),對(duì)種群中的個(gè)體進(jìn)行評(píng)價(jià);Step4利用遺傳算法對(duì)初始群體進(jìn)行優(yōu)化,得到新的種群;Step5引進(jìn)最優(yōu)保留策略,對(duì)此新的種群用模擬退火算法進(jìn)行訓(xùn)練;Step6對(duì)訓(xùn)練后的種群再進(jìn)行選擇、交叉、變異等遺傳操作;Step7返回Step4,直到滿足終止條件;Step8對(duì)混合算法優(yōu)化得到的最優(yōu)解進(jìn)行解碼.3編碼方案、適應(yīng)度函數(shù)與遺傳操作311編碼方案與初始化本文采用的編碼方式是實(shí)數(shù)編碼,與二進(jìn)制編碼相比,實(shí)數(shù)編碼具有如下明顯優(yōu)點(diǎn):實(shí)數(shù)編碼不需要進(jìn)行解碼,在遺傳算法中可方便地表示范圍較大的數(shù),便于在較大空間進(jìn)行搜索,同

12、時(shí)也改善了遺傳算法的計(jì)算復(fù)雜性,提高了運(yùn)算效率;實(shí)數(shù)編碼免去了進(jìn)制轉(zhuǎn)換時(shí)引起的誤差,求解精度高,便于與經(jīng)典優(yōu)化方法混合使用.針對(duì)上述離散時(shí)間系統(tǒng)最優(yōu)控制問題,對(duì)始端和終端中的每個(gè)狀態(tài)連成一串進(jìn)行編碼,其數(shù)值是62昆明理工大學(xué)學(xué)報(bào)(理工版第33卷介于始端值和終端值之間的隨機(jī)值.而進(jìn)化代數(shù)計(jì)數(shù)k 器初始值設(shè)定為1,給定初始退火溫度設(shè)定為c 0.3.2適應(yīng)度函數(shù)由于上述離散時(shí)間系統(tǒng)最優(yōu)控制問題實(shí)質(zhì)上是求性能指標(biāo)函數(shù)的最小值問題,結(jié)合罰函數(shù)的思想,我們構(gòu)造如下的適應(yīng)度函數(shù):g =-i f (x,u (2其中,f 為性能指標(biāo)函數(shù),i 為退火懲罰因子,它是關(guān)于每個(gè)狀態(tài)的退火溫度的反比例函數(shù),隨著遺傳操作的

13、進(jìn)行,當(dāng)溫度越低時(shí),性能指標(biāo)函數(shù)越小,以逐步達(dá)到最優(yōu).313選擇、交叉與變異選擇算子其作用是從當(dāng)前群體中選擇一些比較優(yōu)良的個(gè)體,并將其復(fù)制到下一代群體中.選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的,模型的擬合殘差平方和越小,該個(gè)體被遺傳到下一代群體中的概率也就越大.本文采用比例選擇方法,目的是使適配值高的個(gè)體有更高的生存概率.該方法的基本思想是:各個(gè)個(gè)體被選擇的概率與其適應(yīng)度大小成正比.盡管比例選擇方法帶有很大的隨機(jī)性,但是由于在遺傳算法中溶入了模擬退火因子,因此可以避免由隨機(jī)性而帶來(lái)的收斂速度慢及陷入局部極值的缺陷.交叉算子作用是產(chǎn)生一些較好的新個(gè)體模式,尋優(yōu)的搜索過(guò)程主要通過(guò)它來(lái)實(shí)現(xiàn).

14、由于是實(shí)數(shù)編碼,本文采取兩點(diǎn)算術(shù)交叉:設(shè)1(t +1(11,21,n 1,2t =(12,22,n 2(3是兩個(gè)染色體,在第i 點(diǎn)至第j 點(diǎn)實(shí)施兩點(diǎn)算術(shù)交叉產(chǎn)生如下后代:1(t +1=(11,i ,j ,(j +1,n 1,2(t +1=(12,"i ,"j ,(j +12,n 2(4其中向量1(t +1中的從i 至j 間的每個(gè)元素k (i k j 由線性組合k =1k +(1-2k (5產(chǎn)生.向量2(t +1中的從"i 到"j 的每個(gè)元素"k (i k j 由"k =2k +(1-1k (6確定.變異算子目的是改善遺傳的局部搜索能力

15、,維持群體的多樣性,防止出現(xiàn)早熟現(xiàn)象.本文擾動(dòng)非均勻變異,在非均勻變異中增添一個(gè)擾動(dòng)因子退火罰函數(shù)因子,當(dāng)某狀態(tài)對(duì)應(yīng)的性能指標(biāo)函數(shù)值過(guò)大時(shí),該變異位即被淘汰,從而使變異向著有利的方向進(jìn)行.4實(shí)驗(yàn)仿真結(jié)果我們分別利用遺傳算法、模擬退火算法和混合算法求解如下動(dòng)態(tài)產(chǎn)業(yè)結(jié)構(gòu)最優(yōu)控制問題:m in f =4t =0(x (t -Q (x (t -+u (t R u (t S 1t x (t +1=x (t +u (t e 4x (t +1=1t =0,4x (0=x(0,x (5=x (t 0(7其中x (0=01312,01060,01019,01022,01010,01009,01019,01043

16、,01011,01108,01036,01102,01008,01009,01015,01066,01003,01012,01072,x (5=01302,01061,01018,01021,01011,01010,01017,01039,01012,01102,01036,01012,01006,01101,010016,01064,01003,0110,01068Q =R =1000D,D =diag (20,1,1,1為19×19矩陣,(最優(yōu)解析解為81613672第2期牛向陽(yáng),倪前月,高成修:基于遺傳算法和模擬退火算法的混合算法初始退火溫度c=400,運(yùn)行參數(shù)為p c,p m

17、,1,2=0155,0130,10-2,10-6實(shí)驗(yàn)結(jié)果如表1所示.表13種算法的性能比較Tab.1Capab ility co m pa si on of three a lgor ith m s迭代次數(shù)運(yùn)行時(shí)間/s最優(yōu)解遺傳算法40,000代3607673155模擬退火算法30,000代6862827114混合算法20,000代2306816129從上表來(lái)看,混合遺傳算法具有良好的收斂性和穩(wěn)定性,適用大規(guī)模的最優(yōu)控制問題,相對(duì)而言,模擬退火算法收斂速度最慢,遺傳算法搜索最優(yōu)解的偏差過(guò)大,陷入了局部最優(yōu),混合算法能以最短的時(shí)間、最為精確的搜索到全局最優(yōu)解.表2混合算法迭代至20000代時(shí)的最

18、優(yōu)狀態(tài)Tab.2O pti m a l st a ti on of hybr i d a lgor ith m itera ti n g to20,000steps x(0=01312,01060,01019,01022,01010,01009,01019,01043,01011,01108,01036,01102,01008,01009,01015,01066,01003,01012,01072 x(1=01262,01082,01023,01104,01063,01078,01110,01065,01009,01075,01017,01101,01076,01057,01061,01066

19、,01008,01101,01066 x(2=01166,01104,01028,01052,01074,01282,01050,01038,01032,01028,01027,01013,01036,01077,01038,01032,01034,01029,01046 x(3=01188,01082,01033,01046,01027,01058,01062,01038,01040,01056,01049,01027,01065,01026,01023,01047,01033,01030,01062 x(4=01260,01036,01050,01040,01009,01048,01120

20、,01047,01062,01046,01039,01067,01007,01029,01032,01026,01016,01006,01102 x(5=01302,01061,01018,01021,01011,01010,01017,01039,01012, 01102,01036,01102,01006,01101,010016,01064,01003,01010,010685結(jié)論本文結(jié)合遺傳算法和模擬退火算法的優(yōu)點(diǎn),提出了基于遺傳算法和模擬退火算法的混合算法,設(shè)計(jì)了專門的遺傳操作算子,構(gòu)造了相應(yīng)的適應(yīng)度函數(shù),用罰函數(shù)方法處理約束條件,實(shí)現(xiàn)了離散時(shí)間系統(tǒng)的最優(yōu)控制.通過(guò)對(duì)動(dòng)態(tài)產(chǎn)業(yè)結(jié)構(gòu)最優(yōu)

21、控制問題的優(yōu)化,驗(yàn)證了混合算法的可行性,仿真結(jié)果表明混合算法既具有較快的收斂速度,又能夠收斂到最優(yōu)解,其性能顯著優(yōu)于遺傳算法和模擬退火算法.參考文獻(xiàn):1候媛彬,張建軍.現(xiàn)代控制理論基礎(chǔ)M.北京:北京大學(xué)出版社,2005.2袁亞湘,孫文瑜.最優(yōu)化理論與方法M.北京:科學(xué)出版社,1999.3周明,孫樹棟.遺傳算法原理及其應(yīng)用M.北京:國(guó)防工業(yè)出版社,2000.4任傳祥,張海,范躍祖.混合遺傳模擬退火算法在公交智能調(diào)度中的應(yīng)用J.系統(tǒng)仿真學(xué)報(bào),2005,17(9:2075-2081.5牛向陽(yáng).基于遺傳算法和BP算法的混合算法J.河南科技大學(xué)學(xué)報(bào),2007,28(1:46-48.191-200.(上接第20頁(yè)參考文獻(xiàn):1Joglekar NR,Ford DN1Pr oduct devel opment res ource all ocati on with f oresightJ.Eur opean Journal of Operati onal Research,2005,160(1:72-87.2Abdelsala