模擬退火算法學(xué)習(xí)及試驗分析.ppt

1、模擬退火算法學(xué)習(xí)及試驗分析,清華大學(xué)計算機系 李軍 2007-4,大綱,1. 介紹 2. Six-hump camel back function 試驗 3. Schwefels function 試驗對比 4. 試驗總結(jié) 5. 結(jié)論與未來工作 6. 參考,1.1 優(yōu)化問題介紹,描述: Find the values of a vector that minimize a scalar valued loss function L(). : the domain of allowable values for a vector 注: loss function 也被稱為: performanc

2、e measure, cost function, objective function,fitness function, or criterion etc.,1.2 模擬退火算法介紹,用于解決優(yōu)化問題的一種啟發(fā)式算法,理論上是一個全局最優(yōu)算法. 以一定概率跳出局部極值區(qū)域從而增大了找到全局極值的概率. 偽碼描述: Simulated-Annealing() Create initial solution S repeat for i=1 to iteration-length do Generate a random transition from S to Si If ( C(S) ra

3、ndom0,1) ) then S=Si Reduce Temperature t until ( no change in C(S) ) C(S): Cost or Loss function of Solution S.,2. Six-hump camel back function 試驗,The 2-D Six-hump camel back function is a global optimization test function. global minimum: f(x1,x2)=-1.0316; (x1,x2)=(-0.0898,0.7126), (0.0898,-0.7126

4、). 注: 在簡單問題上成立的結(jié)論才有可能推廣到更復(fù)雜的問題上.,2.1 函數(shù)值分布圖,2.2 函數(shù)值分布底部區(qū)域局部,2 .3 與旅行商問題對比,2.4 主要試驗參數(shù)設(shè)置,CoolSched: (0.8*T) %溫度下降速率0.8 Generator: 生成鄰域: 從 x,y中隨機地選擇一個再加上一個隨機數(shù)R , R = randn/100; (rand符合標(biāo)準(zhǔn)正態(tài)分布N(0,1)的偽隨機數(shù), 意味著 隨機變量落入-1,1內(nèi)的概率是68.26%, 落入-2,2內(nèi)的概率是 95.44% 落入-3,3內(nèi)的概率是 99.72%, 除以100以后也就是大概范圍在e-3量級的小數(shù),也就是大約以95%的

5、概率處于-0.02,0.02) InitTemp: 1 %起始溫度 MaxTries: 300 %同一溫度下的最大迭代次數(shù) StopTemp: 1e-8 %終止溫度 ,2.5 初始解的位置對最終解的影響 (R=randn/100),x1,x2分別在區(qū)間-3,3, -2,2 步長0.5進行g(shù)rid 式的初始值設(shè)置,然后用模擬退火求最小值的結(jié)果( 每一點對應(yīng)運行一次模擬退火算法之后得到的解),Six-hump camel back function 極值分布的等高線圖,可以看出, 在當(dāng)前參數(shù)設(shè)置情況下,初始解的位置與局部極值的區(qū)域基本是一一對應(yīng)的.也就是從初始解的位置出發(fā),通過鄰域搜索,往往落入最

6、近的局部極值區(qū)域.,2.6 R=randn/100的3維效果圖,2.7 R=randn/10 與 rand/1 的3維效果圖,2.8 R=randn*10 與 rand*40 的3維效果圖,2.9 R=randn/100,randn/10,randn/1 的數(shù)據(jù)比較,可見,隨著鄰域的范圍的增大, 跳出局部極小區(qū)域,最終進入全局極小區(qū)域的概率越來越大, 但是代價是總的迭代次數(shù)增加. 但是隨著鄰域范圍的增大,會出現(xiàn)所謂的在極值附近來回”振蕩”而無法落入極值點的現(xiàn)象. 可以推測,隨著鄰域范圍的進一步增大及其隨機特性,模擬退火算法將退化到隨機尋找極值并進行記錄極值的算法. 注: 當(dāng) randn*10,

7、 rand*40的時候超出我們限定的搜索范圍-3,3,-2,2的概率增大很多,與前3個試驗在某種程度上不具備可比性, 盡管如此,仍然具有啟發(fā)性的意義.,2.10 更改降溫速率后的運行結(jié)果(改為0.95),可見,隨著鄰域的范圍的增大, 效果與前一個試驗類似,區(qū)別在于 由于速率放緩, 經(jīng)歷了更多的迭代次數(shù)才達到最終解. 而且從中間的圖可以看出，進入全局極值的點的初始位置分布較散,這是因為隨著迭代次數(shù)的增多,以及鄰域結(jié)構(gòu)的隨機向外伸展性質(zhì),由初始位置導(dǎo)致陷入臨近局部極值的可能性降低,進入全局極值區(qū)域的可能性增大.,2.11 其他參數(shù)嘗試,起始溫度(提高到1000) 每個溫度時的最大迭代次數(shù)(提高到3

8、000) 限于時間,更多參數(shù)和變化形式?jīng)]有進行嘗試. 得到的試驗結(jié)論與前面基本相同,只是在初始解的臨近位置周圍略有微小的變化. 所以, 在一個合適的參數(shù)設(shè)置情況下,對尋找最優(yōu)解起主要作用的重要因素有2個: 初始解的起始位置 鄰域解的構(gòu)造結(jié)構(gòu),2.12 與Native Brute Force Search比較,x1,x2以 s的步長在-3,3,-2,2的區(qū)間內(nèi)進行 Brute Force Search, 判斷搜索過程中的最小值并記錄下來. 在解的搜索空間范圍較小時,暴力搜索的優(yōu)勢非常明顯,只需很少的迭代次數(shù)就能達到與模擬退火相當(dāng)?shù)某潭?但是隨著解空間以幾何倍數(shù)增大,需要的迭代次數(shù)也迅速增大.(

9、本試驗中達到同樣的精度是模擬退火的21倍.),降溫速率0.8時模擬退火試驗結(jié)果 暴力搜索的試驗結(jié)果,3. 2-d Schwefels function 試驗對比,Function defination:,3.1 初始解位置(step=40)與最終解值分布圖,觀察到了在 Six hump camle function 中同樣的試驗效果. 區(qū)別在于由于解空間的較多個極值區(qū)域的存在,迭代次數(shù)變化不像只有6個極值區(qū)域時為達到全局極值而明顯地增加了總的迭代次數(shù). 注1: 由于定義域范圍增大,解空間增大,所以將鄰域范圍設(shè)大,從/1到*100. 注2: 由于鄰域范圍放大之后,處于自定義域邊界的初始解生成的第

10、一次鄰域解以95%的概率落在-700,700范圍之內(nèi), 也就得到500,500之外函數(shù)極值,所以第3個圖中的最小值明顯比第1,2個圖中的函數(shù)值要小,這說明在原定義域外存在更小的極值點 注3: 因為畫圖的原因,3個圖的縱軸的坐標(biāo)是不一致的, 數(shù)值依次降低.也就是跳出了原來的局部極小區(qū)域.,Randn/1, T=0.8T Randn*40 , T=0.8T Randn*100, T=0.8T,3.2 與Native Brute Force Search比較,x1,x2以 s的步長在-500,500,-500,500的區(qū)間內(nèi)進行 Brute Force Search, 判斷搜索過程中的最小值并記錄下

11、來. 同上一個試驗結(jié)論相同, 在以非常粗的粒度進行解的搜索時,暴力搜索的優(yōu)勢非常明顯,只需很少的迭代次數(shù)就能達到與模擬退火相當(dāng)?shù)某潭?但是隨著解空間以幾何倍數(shù)增大,需要的迭代次數(shù)也迅速增大.( 本試驗中達到接近的精度所需迭代次數(shù)是模擬退火的573倍.), 進而計算時間也大大增加.,降溫速率0.8時模擬退火試驗平均結(jié)果 暴力搜索的試驗結(jié)果,3.3 3-d Schwefels function,x1,x2,x3以 80的步長在-500,500,-500,500,-500,500的區(qū)間內(nèi)進行模擬退火求極小值, randn*40, 降溫速率0.8. 由圖中可以看出,較大的解多集中在中間的球形區(qū)域,外圍

12、的值則要小一些, 這是由于變量以0為中心的區(qū)域是相對于外圍空間的局部極小值區(qū)域,所以從中間區(qū)域出發(fā)通過模擬退火找到的解也相對于外圍要大一些. 得到的結(jié)論仍同前面的試驗結(jié)果相同. 注: 這個圖同前幾個圖不同,Z軸代表變量x3, 顏色的變化代表找到的解的值的大小.,4. 試驗總結(jié),在2個toy problem 上得到的結(jié)論: 在其他參數(shù)合適的情況下,初始解的位置與鄰域結(jié)構(gòu)是2個重要因素. 初始解的位置與鄰域結(jié)構(gòu)的設(shè)計之間對于找到最優(yōu)解的問題而言存在依賴關(guān)系. 隨著鄰域的范圍的增大, 跳出局部極小區(qū)域,最終進入全局極小區(qū)域的概率越來越大, 同時也可能會產(chǎn)生振蕩,無法落入極值區(qū)域. 模擬退火本質(zhì)上也是

13、一種 暴力搜索,只不過是利用隨機的性質(zhì)和局部極值區(qū)域連續(xù)(也取決于求解問題中鄰域的結(jié)構(gòu))的特性避免了大量計算.進而在較短時間內(nèi)從某種概率上逼近局部最優(yōu)值和全局最優(yōu)值.,4.2 試驗總結(jié),問題本身解空間的性質(zhì)也會影響求解.,如果全局最優(yōu)解不在連續(xù)的空間上,(isolated point)那么將非常難以找到.,5.1 結(jié)論與未來工作1,本試驗結(jié)論能否推廣到更高維空間的問題上,對于不同性質(zhì)的問題是否有同樣的結(jié)論還有待更多的試驗及數(shù)據(jù)分析. 例如更改鄰域結(jié)構(gòu),使用tsp問題來分析,使用更高維的實際問題等. 現(xiàn)實問題是復(fù)雜的,不同問題的解空間的性質(zhì)也是仍需探索的. 對問題本身建模,以及構(gòu)造合適的鄰域結(jié)構(gòu)

14、,是解決問題的關(guān)鍵因素.再加上某種程度的初始解的grid式的粗遍歷并應(yīng)用模擬退火或其他類似算法, 或許可以解決很多問題.,5.2 結(jié)論與未來工作2,對工程實踐的啟發(fā)性意義 先進行粗粒度的搜索, 找到一個較優(yōu)的解,然后在這個解的周圍,利用設(shè)計合適的鄰域結(jié)構(gòu),進而找到比這個解更優(yōu)的解. 理論中通過迭代無窮次達到平穩(wěn)分布,其實也就是是相當(dāng)于遍歷了所有的解空間. 某種程度的”brute force”(less bugs,no human miss)是解決當(dāng)前組合優(yōu)化問題的一種有效途徑. E.g., 1997年深藍(或許是當(dāng)時最快的計算機)打敗世界國際象棋冠軍是暴力搜索的結(jié)果. -許豐雄,6. 參考,1

15、. matlab code url: 2. Minimizes a function url: 3. Steven Skiena The Algorithm Design Manual 4. James C. Spall Introduction to Stochastic Search and Optimization 5. 刑文訓(xùn) 謝金星 現(xiàn)代優(yōu)化計算方法,附錄1. TSP的鄰域的一種構(gòu)造方法示例,The Inversion, translation, and switching operations are selected randomly with probabilities 0.7

16、5, 0.125, and 0.125 Tour: 1 2 3 4 5 6 7 8 1 5 4 3 2 6 7 8 (Inversion) 1 6 2 3 4 5 7 8 (Translation) 1 5 3 4 2 6 7 8 (Switching) 2-opt Select the best from neighborhood. Neighborhood (1 2 3 4)=(1 2 3 4),(1 3 2 4),(1 4 3 2),(1 2 4 3) 返回,附錄2. 遺傳算法特性,由于遺傳算法的交叉變異等特性,在合適的參數(shù)設(shè)置情況下,所以不存在像模擬退火那樣嚴(yán)重依賴于初始點的位置和鄰域結(jié)構(gòu).,From Slides for Introduction to Stochastic Search and Optimization (ISSO) by J. C. Spall,附錄3. 優(yōu)化算法筆記(部分轉(zhuǎn)載),局部搜索，模擬退火，遺傳算法，禁忌搜索的形象比喻：為了找出地球上最高的山，一群有志氣的兔子們開始想辦法。1兔子朝著比現(xiàn)在高的地方跳去。他們找到了不遠處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是局部搜索，它不能保