無(wú)約束條件的模擬退火算法

無(wú)約束條件的模擬退火算法.實(shí)驗(yàn)?zāi)康模菏褂媚M退火算法解決連續(xù)函數(shù)優(yōu)化問(wèn)題。使用C或C++語(yǔ)言編程環(huán)境實(shí)現(xiàn)模擬退火算法，并運(yùn)行函數(shù)4得出函數(shù)的極值和極值點(diǎn)位置。maxf3,j,z)=50-(5x-2j)2+(%-7j2+2z)4二?模擬退火算法介紹:模擬退火算法是1982年,KirkPatrick將退火思想引入組合優(yōu)化領(lǐng)域，提出的一種解大規(guī)模組合優(yōu)化問(wèn)題的算法，對(duì)NP完全組合優(yōu)化問(wèn)題尤其有效。它以優(yōu)化問(wèn)題的求解與物理系統(tǒng)的退火過(guò)程的相似性為基礎(chǔ)，利用Metropolis算法并適當(dāng)控制溫度的下降過(guò)程式項(xiàng)模擬退火，從而達(dá)到求解全局優(yōu)化問(wèn)題的目的。模擬退火算法在搜索策略上與傳統(tǒng)的隨機(jī)搜索方法不同，它不僅引入了適當(dāng)?shù)碾S機(jī)因素，而且還引入了物理系統(tǒng)退火過(guò)程的自然機(jī)理。這種自然機(jī)理的引入使模擬退火算法在迭代過(guò)程中不僅接受使目標(biāo)函數(shù)值變好的試探點(diǎn)，而且還能夠以一定的概率接受使目標(biāo)函數(shù)值變差的試探點(diǎn)，接受概率隨著溫度的下降逐漸減少。模擬退火算法的這種搜索策略有利于避免搜索過(guò)程因陷入局部最優(yōu)解而無(wú)法自拔的弊病，有利于提高求得全局最優(yōu)解的可靠性。無(wú)約束條件的模擬退火算法：給定初始解%0eRn和初始溫度T0>0，給定產(chǎn)生隨機(jī)向量的概率密度函數(shù)和控制溫度下降過(guò)程的溫度更新函數(shù)，給定常數(shù) P>0。計(jì)算f(%)，置X0=%0，X.=%0，f.=f(%0)，k=0根據(jù)給定的概率密度函數(shù)產(chǎn)生一個(gè)隨機(jī)向量Zk，利用當(dāng)前迭代點(diǎn)Xk和隨機(jī)向量Zk產(chǎn)生一個(gè)新的試探點(diǎn)，即Yk=Xk+Zk計(jì)算f(yk)產(chǎn)生一個(gè)在(0，1)上均勻分布的隨機(jī)數(shù)門(mén)，計(jì)算在給定當(dāng)前迭代點(diǎn)Xk和溫度二下接受試探點(diǎn)Yk的概率P(yk|Xk,T)，即:pTkP(Yk|Xk,“)=min(1,exp(一'f()-f(")|))pTk如果n<P(yk|Xk,T)，則置Xk+1=yk,f(Xk+1)=f(yk)；否則置Xk+1=Xk,f(Xk+1)=f(Xk)。如果f(Xk+1)<f.,則置X.=Xk+1,f.=f(Xk+1)。如果滿足迭代終止條件，則算法結(jié)束，Xmin就作為近似的全局最優(yōu)解，fmin為相應(yīng)的最優(yōu)值；否則繼續(xù)步驟6。根據(jù)給定的溫度更新函數(shù)產(chǎn)生一個(gè)新的溫度《,置k=k+1,轉(zhuǎn)步驟2。核心問(wèn)題：冷卻參數(shù)表、領(lǐng)域結(jié)構(gòu)和新解產(chǎn)生器、接受準(zhǔn)則和隨機(jī)數(shù)產(chǎn)生器(即Metropolis算法)為退火算法過(guò)程的三大支柱。冷卻參數(shù)即&的選取，新解產(chǎn)生器即由司機(jī)函數(shù)產(chǎn)生下一個(gè)解的一個(gè)變換，接受準(zhǔn)則即為概率接受準(zhǔn)則和隨機(jī)數(shù)產(chǎn)生器(Metropolis算法)，這里我們選取p=0.96;新解產(chǎn)生器為：x_next=x+-x*(rand()% 10000) /10100.00y_next=y+-y*(rand()% 10000) /10100.00z_next=z+-z*(rand()% 10000) /10100.00隨機(jī)數(shù)產(chǎn)生器：r_rand=0.01*(rand()+500)/33000.00;接受準(zhǔn)則為：P(YkIXk,T「=min(1,exp(-頃(X^.爭(zhēng)宙)|))kr_rand<P時(shí)，接受下一個(gè)解，否則，繼續(xù)尋找。程序流程圖：

J、&E:\文檔、陳鵬濤\shuxueshiyan\chenpengtao\moni\Debu...xy2?：2030-25hsz=-6-40136e+014x_next=9.61188Lnext=22.8891E_next=-4.72277hsz_next=-1.70431e+014r_i'and=0-00267667最大值為:-1.70431e+014皆職潺最大值時(shí)CK_niax=9.61188Lnax=22-8891z_niax=-4_?227?hsz=-1-70431e+014x_next=4-61941Lnext=17.463?z_next=-0.892183hsz_next=-2.05316e+013r_i'and=0-0026?667最大值為:-2-05316e+013

49.74070.002733880.0560898-0.00134393=49.99030.00111667最終結(jié)果:49.9903當(dāng)取得最美值時(shí)七max=50,這時(shí)X_max(2.44036e-009,1?09176e-006,-3?95199e-010)最終結(jié)果:49.9903當(dāng)取得最美值時(shí)七.實(shí)驗(yàn)心得：通過(guò)本次實(shí)驗(yàn)，了解了無(wú)約束模擬退火算法的思想，算法原理，結(jié)果流程，并實(shí)現(xiàn)了用所寫(xiě)的程序求解全局最優(yōu)解，求得了實(shí)驗(yàn)函數(shù)的最大值。在編寫(xiě)程序的過(guò)程中，由于起初對(duì)算法有一定的誤解，沒(méi)能理解其實(shí)質(zhì)，后來(lái)查資料，明白了其原理，經(jīng)過(guò)認(rèn)真地考慮，實(shí)現(xiàn)了算法。但是，由于原本的模擬退火算法有兩層循環(huán)，在這里，我們簡(jiǎn)化了只有一層循環(huán)。在實(shí)驗(yàn)中，對(duì)參數(shù)的設(shè)置有較高的要求，需要經(jīng)過(guò)多次的嘗試，才能調(diào)到比較合適的結(jié)果。附錄：(源程序)#include<iostream>#include<cmath>#include<ctime>#include<cstdlib>usingnamespacestd;constdoubleb=0.9;doubleu=0;doubleIfunc(doublex,doubley,doublez){doublehsz=0.0;hsz=50-pow(5*x-2*y,2)-pow(x-7*y*y+2*z*z,4);returnhsz;}doubleglfunc(doublew1,doublew2,doubleT){doublep;doubleu=0;doublew3=-1.00*abs(w1-w2);u=exp(w3/(b*T));if(u<1)p=u;elsep=1;returnp;}voidmain(){doublex=0,y=0,z=0,x_next=0,y_next=0,z_next=0,hsz=0,hsz_next=0,hsz_max=0;doublex_max,y_max,z_max;cout<<”請(qǐng)輸入xyz值：";cin>>x>>y>>z;cout<<endl;doubleT=20000;hsz_max=Ifunc(x,y,z);do{hsz=Ifunc(x,y,z);cout<<"hsz="<<hsz<<endl;//計(jì)算初始值srand(static_cast<unsigned>(time(static_cast<time_t*>(NULL))));〃進(jìn)彳亍y=x+z變換x_next=x+-x*(rand()%10000)/10100.00;

y_next=y+-y*(rand()%10000)/10100.00;z_next=z+-z*(rand()%10000)/10100.00;cout<<"x_next="<<x_next<<endl;cout<<"y_next="<<y_next<<endl;cout<<"z_next="<<z_next<<endl;hsz_next=Ifunc(x_next,y_next,z_next);cout<<"hsz_next="<<hsz_next<<endl;〃隨機(jī)選取數(shù)r_randdoubler_rand=0.01*(rand()+500)/33000.00;cout<<"r_rand="<<r_rand<<endl;doublep=glfunc(hsz,hsz_next,T);///概率接受檢驗(yàn)if(r_rand<=p){x=x_next;y=y_nextz=z_next;hsz=hsz_next;}else{x_next=x;y_next=y;z_next=z;hsz_next=hsz;}if(hsz_next>hsz_max){x_max=x_next;y_max=y_next;z_max=z_next;hsz_max=hsz_next;T=T*b;}cout