模擬退火算法及其應(yīng)用研究畢業(yè)論文(編輯修改稿)
2025-07-25 21:55 本頁面
【文章內(nèi)容簡介】 能量最低態(tài)控制參數(shù)的下降冷卻設(shè)定初始溫度熔解過程目標(biāo)函數(shù)能量眾所周知，處于熱平衡的物理系統(tǒng)的各種可能狀態(tài)服從波茲曼(80ltzmann)概率分布，即如式(2)所示.這里先研究由式(2)所確定的函數(shù)隨T的變化趨勢，選定兩個能量EE，在同一溫度T下，有： P()P() = (6)式（6）中恒存在exp(因此式(6)大于零總成立.在同一溫度下，(6)，(2)式的概率分布使得每個狀態(tài)的概率基本相同，= (7)當(dāng)r為狀態(tài)D中能量最低的狀態(tài)時，有:所以，P{}： 其中，有R= （8）亦有P{}.可見，當(dāng)溫度趨于0時，式(2)決定的概率漸進(jìn)1／|D|.據(jù)此可以得到，在此溫度趨于0時，分子在能量最低的狀態(tài)的概率變化可以由圖1(a)，由式(3)和分子在能量最小狀態(tài)的概率是單調(diào)減小可知，在溫度較高時，分子處于這些狀態(tài)的概率在l／|D|：附近，依賴于狀念的不同，可能超過1／|D |.由式(7)和(8)可知存在一個溫度t，使式(7)決定的概率在(0，1)使單調(diào)升的：再出式(7)可知，當(dāng)溫度趨于O時式(2)定義的概率趨進(jìn)于0.概率變化曲線圖見圖1(b).由上面的討論可知，在溫度很低時{TO}，只有能量最低的點(diǎn)概率不為零.(a)能量在最低狀態(tài) (b)在非能量最低狀態(tài) 圖 1 波茲曼函數(shù)曲線 整體最優(yōu)解，鄰域結(jié)構(gòu)與局部最優(yōu)解：設(shè)(S，f)是組合優(yōu)化問題的一個實(shí)例，iS，若(i)≤，對所有i∈S成立，稱i為最小化問題min，i∈S的整體最優(yōu)解.：設(shè)(s，f)是組合優(yōu)化問題的一個實(shí)例，則一個領(lǐng)域結(jié)構(gòu)是一個映射N：S2，其中2表示S的所有子集組成的集合，其涵義是，對每一個解i∈S，有一個解的集合SS，這些解在種意義上是“鄰近”i的，每個J∈S，稱為i的一個鄰近解.：設(shè)(S，f)是組合優(yōu)化問題的一個實(shí)例，而N是一個鄰域結(jié)構(gòu)，i∈，稱i為最小化問題min，i∈S，,對所有j∈S，成立4 局部搜索算法局部搜索算法是一種通用的近似算法，其基本法則是在鄰近解中迭代，使目標(biāo)函數(shù)逐步優(yōu)化，、簡便，能求解多種組臺優(yōu)化問題，并能給出較好的近似解. 局部搜索算法的算法描述局部搜索算法從一個初始解∈S開始，然后運(yùn)用一個產(chǎn)生器，持續(xù)的在解i(稱為當(dāng)前解)的鄰域S中搜索比i更優(yōu)的解，若找到比i更優(yōu)的解，就用這個解取代i成為當(dāng)前解，再對當(dāng)前解的領(lǐng)域繼續(xù)搜索：直至滿足算法終止條件，.LOCAL—SEARCH(){INITALIZE(i.，)：i=i.：do{for(i=j)j∈Sif(f(J)f(i))i=j：}while(S內(nèi)還有解未被搜索到)：} 局部搜索算法的算法的特點(diǎn)由算法描述可知，局部算法具有以下特點(diǎn)：(1)通用性：只要給定組合優(yōu)化問題的實(shí)例(s，f)，產(chǎn)生器和鄰域結(jié)構(gòu)，就能實(shí)現(xiàn)算法；(2)靈活性：可以選用不同機(jī)制的產(chǎn)生器，設(shè)定不同復(fù)雜程度的鄰域結(jié)構(gòu)：(3)最終解可能是某個局部最優(yōu)解：在大多數(shù)情況下，無法設(shè)定恰當(dāng)?shù)泥徲蚪Y(jié)構(gòu)，所以不能保證最終解的質(zhì)量；(4)最終解的質(zhì)量依賴初始解的選擇：對大多數(shù)組合優(yōu)化問題來說，不存在選擇初始解的準(zhǔn)則，算法執(zhí)行時的初始解常常是隨機(jī)選取，這可能導(dǎo)致較差的最終解. 改善局部搜索算法性能的途徑在保持局部搜索算法通用性和靈活性的前提百，以下方案有利于提高最終解的質(zhì)量：(1)對大量初始解執(zhí)行算法，從中選優(yōu)；(2)引入更復(fù)雜的鄰域結(jié)構(gòu)，使算法能對解空間的更大范圍進(jìn)行搜索：(3)改變局部搜索算法只能接受優(yōu)化解迭代的準(zhǔn)則，不可能對所有解施行，因而最終解仍然可能是某個局部最優(yōu)解；第二種方案需要對求解問題的透徹了解，而專注于某類問題又將使局部搜索算法失去通用性而成為一種專用算法；——模擬退火算法(SA).5 貨郎擔(dān)問題的模擬退火算法的實(shí)現(xiàn) 貨郎擔(dān)問題的描述貨郎擔(dān)問題，是威廉哈密爾頓爵士和英國數(shù)學(xué)家克克曼()于19世紀(jì)初提出的一個數(shù)學(xué)問題，：一名商人要到若干城市去推銷商品，已知城市個數(shù)和各城市間的路程（或旅費(fèi)），要求找到一條從城市1出發(fā)，經(jīng)過所有城市且每個城市只能訪問一次，最后回到城市1的路線，使總的路程（或旅費(fèi)），易于為人們所理解，而其計算復(fù)雜性卻是問題的輸入規(guī)模的指數(shù)函數(shù)，：假設(shè)有n個城市，并分別編號，給定一個完全無向圖G=(V,E),V={1，2，……，n}，n(i,j)E有一非負(fù)整數(shù)耗費(fèi)C(即上的權(quán)記為C,i,j V).并設(shè) = (9).人們在考慮解決這個問題時，一般首先想到的最原始的一種方法就是:列出每一條可供選擇的路線(即對給定的城市進(jìn)行排列組合)，計算出每條路線的總里程，、B、C和D，各城市之間的耗費(fèi)為己知數(shù)，A如圖CBDDBCDBDCCBDAA圖2 定點(diǎn)帶權(quán)圖 圖 3 TSP問題解空間樹從圖中不難看出，可供選擇的路線共有6條，從中很快可以選出一條總耗費(fèi)最短的路線：頂點(diǎn)序列為（A,C,B,D,A）.由此推算，若設(shè)城市數(shù)目為n時，那么組合路徑數(shù)則為(n1)!.很顯然，當(dāng)城市數(shù)目不多時要找到最短距離的路線并不難，但隨著城市數(shù)目的不斷增大，組合路線數(shù)將呈指數(shù)級數(shù)規(guī)律急劇增長，以至達(dá)到無法計算的地步，這就是所謂的“組合爆炸問題”.假設(shè)現(xiàn)在城市的數(shù)目增為20個，組合路徑數(shù)則為(201)!≈1017，如此龐大的組合數(shù)目，若計算機(jī)以每秒檢索1000萬條路線的速度計算，也需要花上386年的時間[6].TSP是最有代表性的優(yōu)化組合問題之一，比如飛機(jī)航線安排、送郵件、快遞服務(wù)、如在VLSI芯片設(shè)計、電路板布局、機(jī)器人控制、車輛選路、物流配送等方面，下面舉幾個實(shí)例.，在一電路板上打成百上千個孔，轉(zhuǎn)頭在這些孔之間移動，孔相當(dāng)于城市，轉(zhuǎn)頭從一個孔移到另一個孔所耗的時間相當(dāng)于TSP中的旅費(fèi).，就構(gòu)成TSP問題，在這個問題中，車輛從源點(diǎn)出發(fā)訪問多個目的地并且最后回到源點(diǎn).，DNA片斷作為城市，.更重要的是，比如背包問題、分配問題、車間調(diào)度問題，和TSP同屬NP
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1