1、現代優化技術現代優化技術第第1313講：算法收斂性淺析講：算法收斂性淺析1;.2一、模擬退火算法的基本思想啟發注意到一個自然規則：物質總是趨于最低的能態物質總是趨于最低的能態。水總是向低處流。電子總是向最低能級的軌道排布。最低能態是最穩定的狀態。物質會物質會”自動自動”地趨向的最低能態。地趨向的最低能態。3模擬退火算法（起源）物理退火原理4模擬退火算法與物理退火過程的相似關系模擬退火模擬退火物理退火物理退火解解粒子狀態粒子狀態最優解最優解能量最低態能量最低態設定初溫設定初溫熔解過程熔解過程Metropolis采樣過程采樣過程等溫過程等溫過程控制參數的下降控制參數的下降冷卻冷卻目標函數目標函數能

2、量能量5模擬退火算法（Metropolis準則）Metropolis準則假設在狀態xold時，系統受到某種擾動而使其狀態變為xnew。與此相對應，系統的能量也從E(xold)變成E(xnew)，系統由狀態xold變為狀態xnew的接受概率p：)()()()(exp()()(1oldnewoldnewoldnewxExEifTxExExExEifp6模擬退火算法（流程）隨機產生一個初始解x0，令xbest x0 ，并計算目標函數值E(x0);設置初始溫度T(0)=To;Do while T Tmin /降溫過程for j = 1k /等溫過程對當前最優解xbest按照某一鄰域函數，產生一新的解x

3、new。計算新的目標函數值E(xnew) ，并計算目標函數值的增量E = E(xnew) - E(xbest) 。如果E 0，則xbest = xnew；如果E 0，則p = exp(- E /T(i);如果c = random0,1 p， xbest = xnew; 否則 xbest = xbest。End for按照溫度控制策略更新T；End Do輸出當前最優點，計算結束。7模擬退火算法（要素）1、狀態空間與狀態產生函數（鄰域函數）搜索空間也稱為狀態空間，它由經過編碼的可行解的集合所組成。狀態產生函數(鄰域函數)應盡可能保證產生的候選解能遍布全部解空間。通常由兩部分組成，即產生候選解的方式

4、和候選解產生的概率分布。候選解一般按照某一概率分布對解空間進行隨機采樣來獲得。概率分布可以是均勻分布、正態分布、指數分布等等。8模擬退火算法（要素）2、狀態轉移概率（接受概率） p狀態轉移概率是指從一個狀態xold(一個可行解)向另一個狀態xnew(另一個可行解)的轉移概率;通俗的理解是接受一個新解為當前解的概率;它與當前的溫度參數T有關，隨溫度下降而減小。一般采用Metropolis準則)()()()(exp()()(1oldnewoldnewoldnewxExEifTxExExExEifp9模擬退火算法（要素）3、冷卻進度表T(t)冷卻進度表是指從某一高溫狀態To向低溫狀態冷卻時的降溫管理

5、表。假設時刻t的溫度用T(t)來表示，則經典模擬退火算法的降溫方式為：而快速模擬退火算法的降溫方式為：這兩種方式都能夠使得模擬退火算法收斂于全局最小點。)1lg()(0tTtTtTtT1)(01002004006008001000204060801001201400200400600800100005101520253035404550)1lg()(0tTtTtTtT1)(011模擬退火算法（要素）4、初始溫度T0實驗表明，初溫越大，獲得高質量解的幾率越大，但花費的計算時間將增加。因此，初溫的確定應折衷考慮優化質量和優化效率，常用方法包括：(1) 均勻抽樣一組狀態，以各狀態目標值的方差為初溫。

6、(2) 隨機產生一組狀態，確定兩兩狀態間的最大目標值差|max|，然后依據差值，利用一定的函數確定初溫。比如，t0=max/pr ，其中pr為初始接受概率。(3) 利用經驗公式給出。12模擬退火算法（要素）5、內循環終止準則或稱Metropolis抽樣穩定準則，用于決定在各溫度下產生候選解的數目。常用的抽樣穩定準則包括：(1) 檢驗目標函數的均值是否穩定；(2) 連續若干步的目標值變化較小；(3) 按一定的步數抽樣。13模擬退火算法（要素）6、外循環終止準則即算法終止準則，常用的包括：(1) 設置終止溫度的閾值；(2) 設置外循環迭代次數；(3) 算法搜索到的最優值連續若干步保持不變；(4)

7、檢驗系統熵是否穩定。14模擬退火算法的改進也可通過增加某些環節而實現對模擬退火算法的改進。主要的改進方式包括：(1) 增加升溫或重升溫過程。在算法進程的適當時機，將溫度適當提高，從而可激活各狀態的接受概率，以調整搜索進程中的當前狀態，避免算法在局部極小解處停滯不前。(2) 增加記憶功能。為避免搜索過程中由于執行概率接受環節而遺失當前遇到的最優解，可通過增加存儲環節，將“Best So Far”的狀態記憶下來。(3) 增加補充搜索過程。即在退火過程結束后，以搜索到的最優解為初始狀態，再次執行模擬退火過程或局部性搜索。(4) 對每一當前狀態，采用多次搜索策略，以概率接受區域內的最優狀態，而非標準S

8、A的單次比較方式。(5) 結合其他搜索機制的算法，如遺傳算法、混沌搜索等。(6)上述各方法的綜合應用。151 1 隨機過程的概念隨機過程的概念 隨機過程隨機過程被認為是概率論的“動力學”部分，即它的研究對象是隨時間演變的隨機現象，它是從多維隨機變量向一族(無限多個)隨機變量的推廣。 給定一隨機試驗 ，其樣本空間 ，將樣本空間 中的每一元作如下對應，便得到一系列結果：( ), ( ),eX e Y e12( ),( ),( ),neX e XeXe12( ),( ),),eX e Xe( ),eX e( , ) (,),eX e tt X一維即隨機變量(, )X Y即二維隨機變量12(,)XX

9、即隨機序列12(,)nXXXn維即隨機變量( ),(,)X t t 即隨機過程E16,F PTtTX e ttX e ttTF P定義 設是概率空間, 是給定的參數集,若對每一個有一個隨機變量與之對應,則稱依賴于參數 的隨機變量族是定義在上的隨機過程。 通常指時間）（指標集稱為參數集，簡記，TTttX,( , ),tX e tetTe 注 :對 于 隨 機 過 程進 行 一 次 試 驗 ， 即 給 定 ，它 是 的 函 數 ， 稱 為 隨 機 過 程 的 樣 本 函 數 。,( , )Tet X e t為參數集，對固過程定的 和稱為的狀態；( , )X e t 所有可能的值狀的全體稱為態空間；

10、( , )( )X e tX t今后將簡記為17 例1：拋擲一枚硬幣的試驗，樣本空間是 ，現定義： 1( ) ,()( )2 ( ),cos tHX ttP HP TtTX t t 當出現，其中當出現則是一隨機過程。,( )t X tcos tt解：對任意固定的是隨機變量，取值為和1234( )X t1( )X t2( )X tt1( )( )2P X tcos tP X tt12( ),( )X tcos t Xtt此隨機過程的樣本函數只有兩個，即,H T 182 ( )(),(0,2 )X tcostt 例 ：考慮式中 和 是 正常數, 是在上服從均勻分布的隨機變量, 這是一個隨機過程。,

11、( )(),t X tcost 對每一固定的時刻是隨機變量 的函數,從而也是隨機變量。它的狀態空間是-.(0,2 ),( )(),x tcost在內隨機取一數相應的就得到一個樣本函數這族樣本函數的差異在于它們相位 的不同,故這一隨機相位過程稱為正弦波。193( ) , 0,1( )X tVcos ttVX t 例 ：設其中 是常數；在上服從均勻分布,則是一個隨機過程。 ( )0,1( ).tX tVcos tVcos tvx tvcos t對每一固定的 ，是隨機變量 乘以常數，故也是隨機變量,對上隨機變量取一 值,就得到相應的一個樣本函數204120( )0,0( )( ),00,1,2,.X

12、 tttX tX t t例 ：設某城市的急救中心電話臺遲早會接到用戶的呼叫。 以表示時間間隔內接到的呼叫次數， 它是一個隨機變量，且對于不同的，是不同 的隨機變量，于是是一隨機過程，且它的 狀態空間是1t2t3t4t1t2t4t3t14231( )x t2( )x t( )x tt21例5：考慮拋擲一顆骰子的試驗：16(1)(1)1,2, (),1,.,6,1nnnnXnnnXP XiiXn 設是第 次拋擲的點數，對于的不同值，是隨機變量，服從相同的分布， 因而構成一隨機過程，稱為伯努利過程或伯努利隨機序列,它的狀態空間為 1,2,3,4,5,6 。(2) ,11,2,3,4,5,6nnYnY

13、n 設是前 次拋擲中出現的最大點數,也是 一隨機過程，它的狀態空間仍是。 下面分別給出它們的一條樣本函數：n87654321nx321654nx(1)(2)n87654321ny321654ny22隨機過程的分類：隨機過程的分類： 隨機過程可根據參數集T和任一時刻的狀態分為四類，參數集T可分為離散集和連續集兩種情況，任一時刻的狀態分別為離散型隨機變量和連續型隨機變量兩種：連續參數連續型的隨機過程，如例2，例3連續參數離散型的隨機過程，如例1，例4離散參數離散型的隨機過程，如例51.離散參數連續型的隨機過程，如下例12,2,( ),()nnTttn tX tXXXXX n t 對于隨機相位正弦波

14、，若只在時間集上觀察，就得到隨機序列是連續型隨機變量。Markov鏈鏈24 擬用擬用黑妹牙膏黑妹牙膏中華牙膏中華牙膏現用現用黑妹牙膏黑妹牙膏6040中華牙膏中華牙膏30702526272829 擬用擬用黑妹牙膏黑妹牙膏中華牙膏中華牙膏現用現用黑妹牙膏黑妹牙膏6040中華牙膏中華牙膏307030312 轉移概率矩陣及柯爾莫哥洛夫定理轉移概率矩陣及柯爾莫哥洛夫定理323334例例1 某計算機機房的一臺計算機經常出故障，研究者每隔某計算機機房的一臺計算機經常出故障，研究者每隔15min觀察一次計算機的運觀察一次計算機的運行狀態，收集了行狀態，收集了24h的數據（共作的數據（共作97次觀察）。用次觀察

15、）。用1表示正常狀態，用表示正常狀態，用0表示不正常狀表示不正常狀態，所得的數據序列如下：態，所得的數據序列如下：111111111111111001113536373839404142434445464748近鄰探索過程 全局全局最最優優解解局局部部最最優優解解2 2局局部最優部最優解解1 1鄰域鄰域目目標函數標函數値値49模擬退火算法的數學模型可以描述為，在給定鄰域結構后，模擬退火過程是從模擬退火算法的數學模型可以描述為，在給定鄰域結構后，模擬退火過程是從一個狀態到另一個狀態不斷地隨機游動，我們可以用馬爾科夫鏈描述這一過程，一個狀態到另一個狀態不斷地隨機游動，我們可以用馬爾科夫鏈描述這一過

16、程，對給定的溫度對給定的溫度t，兩個狀態的轉移概率定義為：，兩個狀態的轉移概率定義為：| |1,( )( ),( )1( )( ),ijijDijijijij iG t A tjip tG t A tji 50 稱為從稱為從i到到j的產生概率（的產生概率（generation probability），）， 表示在狀態表示在狀態i時，時，j狀狀態被選取的概率，比較容易理解的是態被選取的概率，比較容易理解的是j為為i的鄰居，如果在鄰域中等概率選取，則的鄰居，如果在鄰域中等概率選取，則j被選中被選中的概率為：的概率為：1/ |( )|,( )( )0,( )ijN ijN iG tjN i ( )

17、ijG t 稱為接受概率（稱為接受概率（acceptance probability），表示產生狀態），表示產生狀態j后，后，j狀態被接受的概率，狀態被接受的概率，在模擬退火算法中常見的是：在模擬退火算法中常見的是：( )ijA t1,( )( )( )exp(/ ),( )( )ijf if jA tftf if j51 由上面三組公式可以看出，一步轉移概率只同狀態由上面三組公式可以看出，一步轉移概率只同狀態i轉移到狀態轉移到狀態j有關，同第幾次迭代有關，同第幾次迭代無關，因此，馬氏鏈是時齊的，正是這個原因，將這一類算法取名為時齊算法。無關，因此，馬氏鏈是時齊的，正是這個原因，將這一類算法取

18、名為時齊算法。下面，介紹幾個概率論中常用概念，輔助同學們理解算法收斂性的討論過程。下面，介紹幾個概率論中常用概念，輔助同學們理解算法收斂性的討論過程。52 若存在若存在n，使得，使得 ，則稱狀態，則稱狀態i可達狀態可達狀態j，記成，記成 若狀態若狀態i和狀態和狀態j滿足滿足 且且 ，則稱狀態，則稱狀態i和狀態和狀態j相通，記成相通，記成 。有如下定理：。有如下定理： 定理：若定理：若 且且 則有則有 。 ( )0nijpijijjiijijjkik53 定義從定義從i到達到達j的首達時刻的隨機變量為：的首達時刻的隨機變量為：min |(0),( ),1ijTn Xi X nj n 其概率定義為

19、：其概率定義為：( )|(0)nijijfP Tn Xi( ),( ),1,2,1|(0)P X nj X mj mnXi 遲早到達概率定義為：遲早到達概率定義為：( )1nijijnff 定理：定理： 的充分必要條件是的充分必要條件是ij0ijf 54定理：狀態定理：狀態j是常返的，則以概率是常返的，則以概率1系統無窮次返回狀態系統無窮次返回狀態j，狀態，狀態j是非常返的，則以概率是非常返的，則以概率1，系統只有限次返回狀態系統只有限次返回狀態j。記記 表示自狀態表示自狀態i出發，系統通過出發，系統通過j狀態至少狀態至少m次的概率，記次的概率，記 表示狀態表示狀態i出發出發通過通過j狀態至少

20、狀態至少m次的時間。次的時間。 ( )ijA m( )ijY m1(1)( )| |(0)ijjjijijlA mP YmTl P Tl Xi1( )ljjijlAm f55 于是，有于是，有 ，進而，進而，所以，所以，( )(0)()()mmjjjjjjijAmAff(1)()mijijijA mff1,1( )0,1jjjjjjfAmmf 常返的含義常返的含義56 常返中的一種特殊情況為正常返，定義：常返中的一種特殊情況為正常返，定義：( )1niiinunf 當當 時為正常返，當時為正常返，當 時為零常返。時為零常返。iu iu 常返定理表明常返是以概率常返定理表明常返是以概率1無窮次返

21、回同一狀態，上式表明有些常返狀態的平均返回次數無窮次返回同一狀態，上式表明有些常返狀態的平均返回次數是有限的，而有些是無限的。當馬氏鏈的離散狀態均為常返且平均返回次數有限，就稱該馬是有限的，而有些是無限的。當馬氏鏈的離散狀態均為常返且平均返回次數有限，就稱該馬氏鏈是正常返的。氏鏈是正常返的。57 在模擬退火的理論中，經常用到的一個概念是不可約，不可約中用到的一個概念是閉在模擬退火的理論中，經常用到的一個概念是不可約，不可約中用到的一個概念是閉集。一個集合集。一個集合C是閉集的定義為：是閉集的定義為： 有有 ，這表示集合，這表示集合C是一個封閉是一個封閉的集合，的集合， i不可達到不可達到j ，

22、對任意，對任意n成立。除整個狀態空間外，沒有別的閉成立。除整個狀態空間外，沒有別的閉集的馬氏鏈成為不可約的馬氏鏈。集的馬氏鏈成為不可約的馬氏鏈。,iC jC 0ijp ,iC jC 58定理定理1：不可約、有限狀態且時齊的馬氏鏈是正常返的。：不可約、有限狀態且時齊的馬氏鏈是正常返的。定理定理2：非周期、不可約且時齊的馬氏鏈是正常返的充分必要條件：存在唯一平：非周期、不可約且時齊的馬氏鏈是正常返的充分必要條件：存在唯一平穩分布穩分布 ，滿足，滿足|1,2,jvj ( )11njiijiijiivv pv p( )lim0njijnvp59模擬退火算法的時齊算法，當具有以下條件成立時，則可以認為該

23、模擬退火算模擬退火算法的時齊算法，當具有以下條件成立時，則可以認為該模擬退火算法收斂全局最優解：法收斂全局最優解：（1）在每一個給定的溫度）在每一個給定的溫度t，給出算法一步轉移概率，給出算法一步轉移概率 的一些限定條件，使的一些限定條件，使得定理得定理2成立，由此得到平穩分布概率。成立，由此得到平穩分布概率。（2）給出平穩分布應該滿足的條件，使得當溫度漸進達到）給出平穩分布應該滿足的條件，使得當溫度漸進達到0度時，平穩分布的度時，平穩分布的極限存在，即要求極限存在，即要求（3）進一步要求平穩分布的極限具有全局最優性條件：）進一步要求平穩分布的極限具有全局最優性條件：其中其中 是最優狀態集合。

24、是最優狀態集合。( )ijp t( )( )lim( )lim( , )|(0, )0njijnnv tptP X n tj Xti0lim( )jjtv t1|0OPTOPTjOPTjDDjD D OPTD60探索空間（search space）與實行可能域（feasible solution field） (1)探索空間探索空間 = = 實行可能域實行可能域目標函數值 探索評價基準61近鄰例一臺機器的交貨期最小遲延排序問題工件的集合 1,2,3,4工件 i 1 2 3 4加工時間 pi 1 2 3 4交貨期 di 5 9 6 462目標函數一臺機器的交貨期最小遲延排序問題可行解（順列） 1

25、234 所對應的目標函數63近鄰一臺機器的交貨期最小遲延排序問題4 364一臺機器的交貨期最小遲延排序問題 近鄰圖1212 點與解一一對應667754357710878668554610目標函數值65探索空間（search space）與實行可能域（feasible solution field） (2) 探索空間探索空間 目標函數值(objective function value) + 懲罰函數值(penalty function value ）實行可能域實行可能域探索空間探索空間實行可能域實行可能域探索評價基準66帶有時間窗約束的帶有時間窗約束的VRP問題：問題：序號坐標時間窗1(16,2)40,702(6,2)60,903(11,11)70,1004(14,16)90,1205(18,19)100,1306(20,3)120,1507(11,12)120,1508(3,10)150,1809(3,1)190,22010(6,7)190,220鄰域交換不能隨意進行，因為需要滿足客鄰域交換不能隨意進行，因為需要滿足客戶時間窗的硬性要求戶時間窗的硬性要求67處理辦法有兩種：處理辦法有兩種：（1）不排斥不可行解，用懲罰函數進行處理（通常為在目標函數設置一個懲罰項，如果突）不排斥不可行解，用懲罰函數進行處理（通常為