模擬退火法含程序(數(shù)模講稿-資料下載頁
2024-10-04 18:36本頁面
【正文】 返回 if (rtolftol || *iter0) { //若返回，將最佳點(diǎn)和最佳位放入槽1中 swap=y[1]。y[1]=y[ilo]。y[ilo]=swap。 for (n=1。n=ndim。n++) { swap=p[1][n]。 p[1][n]=p[ilo][n]。 p[ilo][n]=swap。 } break。 }*iter = 2。 //開始新的一輪迭代，首先從高點(diǎn)通過單純形的表面，//以因子1做外插，即從離點(diǎn)對單純形進(jìn)行反射。ytry=amotsa(p,y,psum,ndim,pb,yb,funk,ihi,amp。yhi. )。if (ytry = ylo) { //得到了比最佳點(diǎn)還要好的結(jié)果，因此用因子2再做一次外推 ytry=amotsa(p,y,psum,ndim,pb,yb,funk,ihi,amp。yhi,)。} else if (ytry = ynhi ) { //反射后的點(diǎn)不如次高點(diǎn)，因此需要找一個(gè)中間的//較低點(diǎn)，即做一次一維收縮 ysave=yhi。 ytry=amotsa(p,y,psum,ndim,Pb,yb,funk, ihi,amp。yhi,)。 if (ytry = ysave) { //似乎無法擺脫高點(diǎn)，最好圍繞最低點(diǎn)也即最佳點(diǎn)進(jìn)行收縮 for (i=1。i=mpts。i++) { if (i!=ilo) { for (j=1。jndim。j++) { psum[j]= * (p[i][j]+p[ilo][j])。 p[i][j]=psum[j]。 } y[i]= (* funk) (psum)。} }*iter = ndim。GET_PSUM //重新計(jì)算psum }} else ++(*iter)。 //糾正計(jì)數(shù)器}free_vector(psum,1,ndim)。} include include extern long idum。 //在主程序中定義和初始賦值extern float tt。 //在amobsa中定義float amotsa(float **p，float y[],float psum[]，int ndim，float pb[]，float *yb，float(*funk)(float[]), int ihi，float *yhi, float fac)//從高點(diǎn)通過單純形的表面，以因子fac作外推，如果得到的新點(diǎn)較好，則用它取代高點(diǎn)。{ float ran1(long *idum)。 int j。 float fac1,fac2,yflu,ytry, *ptry。 ptry=vector(1, ndim)。 39。 facl=( fac)/ndim。 fac2=fac1fac。 for (j=1。j=ndim。j++) ptry[j] =psum[j] * fac1 p[ihi][j] * fac2。 ytry= (* funk) (ptry)。 if (ytry = *yb) { //存儲至令最好的 for(j=1。j=ndim。j++) pb[j]=ptry[j]。 *yb = ytry。 } yflu=ytrytt*log(ran1(amp。idum))。 //我們曾經(jīng)對所有的當(dāng)前頂點(diǎn)添加熱起伏運(yùn)動， if (yflu*yhi) { //但這里我們要減少熱起伏，目的是給單純形一 y[ihi]=ytry。 //個(gè)熱布朗運(yùn)動，就象接受任何提議的變化一樣 *yhi=yflu。 for (j=1。j=ndim。j++) { psum[j] += ptry[j]p[ihi][j]。 p[ihi][j]=ptry[j]。 } } free_vector(ptry,1,ndim)。 return yflu。}模擬退火法在優(yōu)化方法中將處于什么樣的地位、扮演什么樣的角色？對于這個(gè)問題目前還沒有足夠的實(shí)踐經(jīng)驗(yàn)來明確回答它。但是這種方法確有幾個(gè)極為惹人注目的特點(diǎn)，與其他優(yōu)化技術(shù)相比顯得尤其突出：首先，這種方法不象“急功近利的小人”那樣表現(xiàn)“貪婪”，也就是說，它能迅速求出某些局部極小值，但那些實(shí)際上是不利的極小值并不會讓它輕易上當(dāng)。假如給定一些足夠一般的重構(gòu)形，這種方法會在深度小于T的局部極小值之間自由地游動。當(dāng)T值降低，這些具備頻繁訪問條件的極小值的數(shù)目也將逐漸減少。第二點(diǎn)，這種方法中有關(guān)構(gòu)形的判定是趨向于以一種合乎邏輯的順序進(jìn)行的。當(dāng)控制參數(shù)T很大時(shí)，那些引起最大能量差異的諸多變化將被篩去。T減小時(shí)，這些判定就變得更恒定，相應(yīng)地，算法將注意力就更多地轉(zhuǎn)向解的較精細(xì)的改進(jìn)方面。例如，在旅行推銷員問題中，如果密西比河迂回于旅途之中，而且值很大，那么，在很高的T值下，只能做出跨河兩次的判定，而位于跨河兩岸的一些待定路徑只能在稍后的步驟中才能確定下來。以熱力學(xué)原理為借鑒的方法遠(yuǎn)不止我們所討論的這些內(nèi)容，它們還可以推廣到更廣泛的應(yīng)用領(lǐng)域，我們可以定義一些與特定熱量和熵類似的量，這些量對于監(jiān)測算法向某個(gè)可接受解逐步接近的過程是很有幫助的。關(guān)于這些內(nèi)容的討論讀者可參考[1]中的介紹。參考文獻(xiàn)和進(jìn)一步讀物：Kirkpatrick,S,Gelatt,and Vecchi,Scisaue,. [1]Kirkpatrick,Joumal of Statistical Physics,. [2]Vecchi, ,IEEE Transactions on Computer Aided Desing,PP. 215~222. [3]Otten, van Ginneken,The Annealing Aigatthm (Boston:Kluwer) [contains many references to the literature]. [4] Metropolis,Rosenbluth,M,Teller A,and Teller, of Chenical Physics, . pp. 1087~1092. [5]Lin, System Technical Joumal,~2269. [6]Vanderbilt,D,and Louie,Joumal of Computational Physics,~271. [7],Johnson,and Stein,Technometrics,~271. [8]Corana,M,Martini,C,and Ridella,S,1987,ACM Transactions on Mathematical Software, , pp. 262~280. [9]Belisle,.,and Smith,Technical Report 90~25,Department of Industrial and Operations Engineering, University of Michigan, submitted to Mathematical Programming. [1
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1