1、模擬退火算法學習及試驗分析,清華大學計算機系 李軍 2007-4,大綱,1. 介紹 2. Six-hump camel back function 試驗 3. Schwefels function 試驗對比 4. 試驗總結 5. 結論與未來工作 6. 參考,1.1 優化問題介紹,描述: 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 模擬退火算法介紹,用于解決優化問題的一種啟發式算法,理論上是一個全局最優算法. 以一定概率跳出局部極值區域從而增大了找到全局極值的概率. 偽碼描述: 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、). 注: 在簡單問題上成立的結論才有可能推廣到更復雜的問題上.,2.1 函數值分布圖,2.2 函數值分布底部區域局部,2 .3 與旅行商問題對比,2.4 主要試驗參數設置,CoolSched: (0.8*T) %溫度下降速率0.8 Generator: 生成鄰域: 從 x,y中隨機地選擇一個再加上一個隨機數R , R = randn/100; (rand符合標準正態分布N(0,1)的偽隨機數, 意味著 隨機變量落入-1,1內的概率是68.26%, 落入-2,2內的概率是 95.44% 落入-3,3內的概率是 99.72%, 除以100以后也就是大概范圍在e-3量級的小數,也就是大約以95%的

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

6、近的局部極值區域.,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 的數據比較,可見,隨著鄰域的范圍的增大, 跳出局部極小區域,最終進入全局極小區域的概率越來越大, 但是代價是總的迭代次數增加. 但是隨著鄰域范圍的增大,會出現所謂的在極值附近來回”振蕩”而無法落入極值點的現象. 可以推測,隨著鄰域范圍的進一步增大及其隨機特性,模擬退火算法將退化到隨機尋找極值并進行記錄極值的算法. 注: 當 randn*10,

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

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

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

10、一次鄰域解以95%的概率落在-700,700范圍之內, 也就得到500,500之外函數極值,所以第3個圖中的最小值明顯比第1,2個圖中的函數值要小,這說明在原定義域外存在更小的極值點 注3: 因為畫圖的原因,3個圖的縱軸的坐標是不一致的, 數值依次降低.也就是跳出了原來的局部極小區域.,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的區間內進行 Brute Force Search, 判斷搜索過程中的最小值并記錄下

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

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

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

14、,是解決問題的關鍵因素.再加上某種程度的初始解的grid式的粗遍歷并應用模擬退火或其他類似算法, 或許可以解決很多問題.,5.2 結論與未來工作2,對工程實踐的啟發性意義 先進行粗粒度的搜索, 找到一個較優的解,然后在這個解的周圍,利用設計合適的鄰域結構,進而找到比這個解更優的解. 理論中通過迭代無窮次達到平穩分布,其實也就是是相當于遍歷了所有的解空間. 某種程度的”brute force”(less bugs,no human miss)是解決當前組合優化問題的一種有效途徑. E.g., 1997年深藍(或許是當時最快的計算機)打敗世界國際象棋冠軍是暴力搜索的結果. -許豐雄,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. 刑文訓 謝金星 現代優化計算方法,附錄1. TSP的鄰域的一種構造方法示例,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. 遺傳算法特性,由于遺傳算法的交叉變異等特性,在合適的參數設置情況下,所以不存在像模擬退火那樣嚴重依賴于初始點的位置和鄰域結構.,From Slides for Introduction to Stochastic Search and Optimization (ISSO) by J. C. Spall,附錄3. 優化算法筆記(部分轉載),局部搜索，模擬退火，遺傳算法，禁忌搜索的形象比喻：為了找出地球上最高的山，一群有志氣的兔子們開始想辦法。1兔子朝著比現在高的地方跳去。他們找到了不遠處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是局部搜索，它不能保