【正文】 進(jìn)化過(guò)程，采用人工的方式對(duì)目標(biāo)空間進(jìn)行隨機(jī)化搜索。 30城市 TSP問(wèn)題（ d*= by D B Fogel） 71 模擬退火算法的實(shí)現(xiàn)與應(yīng)用 智能優(yōu)化計(jì)算 ? 運(yùn)行過(guò)程 30城市 TSP問(wèn)題（ d*= by D B Fogel） 72 模擬退火算法的實(shí)現(xiàn)與應(yīng)用 智能優(yōu)化計(jì)算 ? 運(yùn)行過(guò)程 30城市 TSP問(wèn)題（ d*= by D B Fogel） 73 模擬退火算法的實(shí)現(xiàn)與應(yīng)用 智能優(yōu)化計(jì)算 ? 運(yùn)行過(guò)程 30城市 TSP問(wèn)題（ d*= by D B Fogel） 74 模擬退火算法的實(shí)現(xiàn)與應(yīng)用 智能優(yōu)化計(jì)算 ? 運(yùn)行過(guò)程 30城市 TSP問(wèn)題（ d*= by D B Fogel） 75 模擬退火算法的實(shí)現(xiàn)與應(yīng)用 智能優(yōu)化計(jì)算 ? 運(yùn)行過(guò)程 30城市 TSP問(wèn)題（ d*= by D B Fogel） 76 模擬退火算法的實(shí)現(xiàn)與應(yīng)用 智能優(yōu)化計(jì)算 ? 運(yùn)行結(jié)果 30城市 TSP問(wèn)題（ d*= by D B Fogel） 77 模擬退火算法的改進(jìn) 智能優(yōu)化計(jì)算 ? 改進(jìn)的可行方案 （ 1）設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù)； （ 2）設(shè)計(jì)高效的退火歷程； （ 3）避免狀態(tài)的迂回搜索； （ 4）采用并行搜索結(jié)構(gòu)； （ 5）避免陷入局部極小，改進(jìn)對(duì)溫度的控制方式； （ 6）選擇合適的初始狀態(tài)； （ 7）設(shè)計(jì)合適的算法終止準(zhǔn)則。44 35。87 76。22 60。 7 64。 62 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì) 智能優(yōu)化計(jì)算 ? 非時(shí)齊模擬退火算法 每個(gè)溫度下只產(chǎn)生一個(gè)或少量候選解 ? 時(shí)齊算法 —— 常用的 Metropolis抽樣穩(wěn)定準(zhǔn)則 （ 1）檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定； （ 2）連續(xù)若干步的目標(biāo)值變化較??； （ 3）按一定的步數(shù)抽樣。 50 ?問(wèn)題分析 51 算法描述 (解空間與目標(biāo)函數(shù) ) 52 算法描述 ? 一次迭代由三步組成 53 算法描述 54 案例講解 0 10 20 30 40 50 60 700510152025303540S u m = 4 1 2 1 7 . 8 6 455 模擬退火算法及模型 智能優(yōu)化計(jì)算 ? 基本步驟 給定初溫 t=t0，隨機(jī)產(chǎn)生初始狀態(tài) s=s0，令 k=0； Repeat Repeat 產(chǎn)生新?tīng)顟B(tài) sj=Gee(s)； if min{1,exp[(C(sj)C(s))/tk]}=randrom[0,1] s=sj。 模擬退火算法 能量最低狀態(tài) 非能量最低狀態(tài) ???????? ???TkrETZrEEP B)(ex p)(1)}({? 數(shù)學(xué)表述 44 模擬退火算法及模型 智能優(yōu)化計(jì)算 ? Metropolis準(zhǔn)則（ 1953） —— 以概率接受新?tīng)顟B(tài) 物理退火過(guò)程 固體在恒定溫度下達(dá)到熱平衡的過(guò)程可以用 Monte Carlo方法 （計(jì)算機(jī)隨機(jī)模擬方法）加以模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。 信息 1:三個(gè)小孩年齡之積為 36 只有以下 8種可能，搜索范圍減少至 8種情況 : 第一個(gè)小孩年齡 36 18 12 9 9 6 6 4 第二個(gè)小孩年齡 1 2 3 4 2 6 3 3 第三個(gè)小孩年齡 1 1 1 1 2 1 2 3 31 三個(gè)孩子的年齡 (4) 信息 2:三個(gè)小孩年齡之和等于窗戶數(shù) 第一個(gè)小孩年齡 36 18 12 9 9 6 6 4 第二個(gè)小孩年齡 1 2 3 4 2 6 3 3 第三個(gè)小孩年齡 1 1 1 1 2 1 2 3 窗戶數(shù) : 38 21 16 14 13 13 11 10 如果窗戶數(shù)為 3 2 1 1 1 10即可得出答案 B還需信息，即窗戶數(shù)為 13. 則可能為 ( 2)或 ( 1) 信息 2:大兒子眼睛是藍(lán)色的 得答案： ( 2) 32 ? 典型問(wèn)題 —— 旅行商問(wèn)題（ Traveling salesman problem, TSP） 1 2 3 4 12 1 8 10 3 2 搜索示例： TSP問(wèn)題 給定 n個(gè)城市和兩兩 城市之間的距離，要 求確定一條經(jīng)過(guò)各城 市當(dāng)且僅當(dāng)一次的最 短路線。 … A： 既然你是數(shù)學(xué)教授，那你幫我算這個(gè)題，今天是 個(gè)特殊日子：我三個(gè)兒子都在今天慶祝生日！那么你 能算出他們都有多大嗎？ B：好，但你得跟我講講他們的情況。這種算法一般具有嚴(yán)密的理論依據(jù)，而不是單純憑借專家經(jīng)驗(yàn)，理論上可以在一定的時(shí)間內(nèi)找到最優(yōu)解或近似最優(yōu)解?，F(xiàn)代優(yōu)化算法 潘克家 202288 2 目錄 ? 現(xiàn)在優(yōu)化算法概論 ? 模擬退火算法 (SA) ? 遺傳算法 (GA) 3 Part 1 概論 主要是說(shuō)明現(xiàn)代優(yōu)化算法的重要性。 23 ? 待解決的問(wèn)題 離散性、連續(xù)的、不確定性、 大規(guī)模 ? 現(xiàn)代的優(yōu)化方法 啟發(fā)式算法（ heuristic algorithm） 追求滿意（近似解） 實(shí)用性強(qiáng)（解決實(shí)際工程問(wèn)題） ? 現(xiàn)代的評(píng)價(jià)方法 算法復(fù)雜性 現(xiàn)代優(yōu)化方法 24 現(xiàn)代優(yōu)化算法的特點(diǎn) 它們的共同特點(diǎn)：都是從任一解出發(fā)，按照 某種機(jī)制，以 一定的概率 在整個(gè)求解空間中探索 最優(yōu)解。 A：好的，我給你一些提示，他們?nèi)齻€(gè)年齡之積是 36. B：很好，但我還需要更多提示。 33 ? 典型問(wèn)題 —— 旅行商問(wèn)題 城市數(shù) 24 25 26 27 28 29 30 31 計(jì)算 時(shí)間 1 sec 24 sec 10 min hour day day year 325 year TSP的搜索的困難 計(jì)算復(fù)雜度：指數(shù)災(zāi)難 34 Part 2 模擬退火法 35 36 37 模擬退火算法及模型 ? 算法的提出 模擬退火算法最早的思想由 Metropolis等（ 1953）提出，1983年 Kirkpatrick等將其應(yīng)用于組合優(yōu)化。 45 模擬退火算法及模型 智能優(yōu)化計(jì)算 否則，以概率 p=exp[(EjEi)/kBT] 接受 j 為當(dāng)前狀態(tài)。 Until 抽樣穩(wěn)定準(zhǔn)則滿足； 退溫 tk+1=update(tk)并令 k=k+1； Until 算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。 內(nèi)循環(huán)終止準(zhǔn)則 63 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì) 智能優(yōu)化計(jì)算 ? 常用方法 （ 1）設(shè)置終止溫度的閾值； （ 2）設(shè)置外循環(huán)迭代次數(shù)； （ 3）算法搜索到的最優(yōu)值連續(xù)若干步保持不變； （ 4）概率分析方法。2 99。83 46。18 40。4 50 66 67 智能優(yōu)化計(jì)算 ? 算法流程 給 給 給 給 給 給 給 給給 給 給 給 給 Si給 給 給 給 給 Sj給 給 給 給 給 給 給 s *給 給 給 給 給 給 給 給 給 給給 給m i n { 1 , e x p [ ( C ( sj) C ( si) ) / tk] } = r a n d o m [ 0 , 1 ]給 給 給 給 給 給 給 給 給 給 給 給 給 給 給 給 k = 0M e t r o p o l i s 給 給 給 給 給 給 給 給 給 給tk + 1= u p d a t e ( tk)給 k = k + 1給 S i 給 S j ， 給 給 給 給 給 給 給 給 s *給 給 給 給 給 給給 給YNYNYN68 模擬退火算法的實(shí)現(xiàn)與應(yīng)用 智能優(yōu)化計(jì)算 ? 初始溫度的計(jì)算 for i=1:100 route=randperm(CityNum)。 改進(jìn)內(nèi)容 78 模擬退火算法的改進(jìn) 智能優(yōu)化計(jì)算 ? 改進(jìn)的方式 （ 1）增加升溫或重升溫過(guò)程，避免陷入局部極??； （ 2）增加記憶功能（記憶“ Best so far”狀態(tài)）； （ 3）增加補(bǔ)充搜索過(guò)程（以最優(yōu)結(jié)果為初始解）； （ 4）對(duì)每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內(nèi)的最優(yōu)狀態(tài)； （ 5）結(jié)合其它搜索機(jī)制的算法； （ 6）上述各方法的綜合。 85 遺傳算法模擬自然選擇和自然遺傳過(guò)程中發(fā)生 的 繁殖、交叉和基因突變 現(xiàn)象，在每次迭代中 都保留一組候選解，并按某種指標(biāo)從解群中選 取較優(yōu)的個(gè)體，利用 遺傳算子 (選擇、交叉和變 異 )對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解 群，重復(fù)此過(guò)程，直到滿足某種收斂指標(biāo)為止。 1111111111111111111111 ? 2 1110000000111111000101 ? 888 = 1+3x(1110000000111111000101) 2 /(2221) = 1+3x3674053/(2221) 100 SGA實(shí)例 2 : 初始化種群、適應(yīng)函數(shù) ? 隨機(jī)初始化種群 ? 適應(yīng)函數(shù) 本實(shí)例目標(biāo)函數(shù)在定義域內(nèi)均大于 0， 且是求函數(shù)最大值，故直接引用目標(biāo)函數(shù)作為適應(yīng)函數(shù)： f(s) = f(x) 其中二進(jìn)制串 s對(duì)于變量 x的值。 ? 模擬 “ 輪盤賭 ” 算法 ： (1)r=random(0, 1)， s=0， i=0； (2)如果 s≥r， 則轉(zhuǎn) (4)； (3)s=s+p(xi)， i=i+1, 轉(zhuǎn) (2) (4)xi即為被選中的染色體 ， 輸出 I (5)結(jié)束 116 選擇 (Selection) ? 其他選擇法 ： ? 隨機(jī)遍歷抽樣 (Stochastic universal sampling) ? 局部選擇 (Local selection) ? 截?cái)噙x擇 (Truncation selection) ? 競(jìng)標(biāo)賽選擇 (Tournament selection) ? 特點(diǎn) ： 選擇操作得到的新的群體稱為 交配池 ，交配池是當(dāng)前代和下一代之間的中間群體，其規(guī)模為初始群體規(guī)模。 假如交叉概率 Pc ＝ 50%,則交配池中 50%的染色體 (一半染色體 ) 將進(jìn)行交叉操作，余下的 50%的染色體進(jìn)行選擇 (復(fù)制 )操作。以染色體適應(yīng)值的大小來(lái)確定該染色體被遺傳到下一代群體中的概率 。 (5) 按變異概率 Pm進(jìn)行 變異操作 ,生產(chǎn)新的個(gè)體 。 % crossove