《現(xiàn)代優(yōu)化技術-靳志宏》算法收斂性ppt課件

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

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

3、new。計算新的目標函數(shù)值E(xnew) ，并計算目標函數(shù)值的增量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輸出當前最優(yōu)點，計算結束。7模擬退火算法（要素）1、狀態(tài)空間與狀態(tài)產(chǎn)生函數(shù)（鄰域函數(shù)）搜索空間也稱為狀態(tài)空間，它由經(jīng)過編碼的可行解的集合所組成。狀態(tài)產(chǎn)生函數(shù)(鄰域函數(shù))應盡可能保證產(chǎn)生的候選解能遍布全部解空間。通常由兩部分組成，即產(chǎn)生候選解的方式

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

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

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

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

8、A的單次比較方式。(5) 結合其他搜索機制的算法，如遺傳算法、混沌搜索等。(6)上述各方法的綜合應用。151 1 隨機過程的概念隨機過程的概念 隨機過程隨機過程被認為是概率論的“動力學”部分，即它的研究對象是隨時間演變的隨機現(xiàn)象，它是從多維隨機變量向一族(無限多個)隨機變量的推廣。 給定一隨機試驗 ，其樣本空間 ，將樣本空間 中的每一元作如下對應，便得到一系列結果：( ), ( ),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定義 設是概率空間, 是給定的參數(shù)集,若對每一個有一個隨機變量與之對應,則稱依賴于參數(shù) 的隨機變量族是定義在上的隨機過程。 通常指時間）（指標集稱為參數(shù)集，簡記，TTttX,( , ),tX e tetTe 注 :對 于 隨 機 過 程進 行 一 次 試 驗 ， 即 給 定 ，它 是 的 函 數(shù) ， 稱 為 隨 機 過 程 的 樣 本 函 數(shù) 。,( , )Tet X e t為參數(shù)集，對固過程定的 和稱為的狀態(tài)；( , )X e t 所有可能的值狀的全體稱為態(tài)空間；

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

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

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

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

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

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

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

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

18、名為時齊算法。下面，介紹幾個概率論中常用概念，輔助同學們理解算法收斂性的討論過程。下面，介紹幾個概率論中常用概念，輔助同學們理解算法收斂性的討論過程。52 若存在若存在n，使得，使得 ，則稱狀態(tài)，則稱狀態(tài)i可達狀態(tài)可達狀態(tài)j，記成，記成 若狀態(tài)若狀態(tài)i和狀態(tài)和狀態(tài)j滿足滿足 且且 ，則稱狀態(tài)，則稱狀態(tài)i和狀態(tài)和狀態(tà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定理：狀態(tài)定理：狀態(tài)j是常返的，則以概率是常返的，則以概率1系統(tǒng)無窮次返回狀態(tài)系統(tǒng)無窮次返回狀態(tài)j，狀態(tài)，狀態(tài)j是非常返的，則以概率是非常返的，則以概率1，系統(tǒng)只有限次返回狀態(tài)系統(tǒng)只有限次返回狀態(tài)j。記記 表示自狀態(tài)表示自狀態(tài)i出發(fā)，系統(tǒng)通過出發(fā)，系統(tǒng)通過j狀態(tài)至少狀態(tài)至少m次的概率，記次的概率，記 表示狀態(tài)表示狀態(tài)i出發(fā)出發(fā)通過通過j狀態(tài)至少

20、狀態(tài)至少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、回同一狀態(tài)，上式表明有些常返狀態(tài)的平均返回次數(shù)無窮次返回同一狀態(tài)，上式表明有些常返狀態(tài)的平均返回次數(shù)是有限的，而有些是無限的。當馬氏鏈的離散狀態(tài)均為常返且平均返回次數(shù)有限，就稱該馬是有限的，而有些是無限的。當馬氏鏈的離散狀態(tài)均為常返且平均返回次數(shù)有限，就稱該馬氏鏈是正常返的。氏鏈是正常返的。57 在模擬退火的理論中，經(jīng)常用到的一個概念是不可約，不可約中用到的一個概念是閉在模擬退火的理論中，經(jīng)常用到的一個概念是不可約，不可約中用到的一個概念是閉集。一個集合集。一個集合C是閉集的定義為：是閉集的定義為： 有有 ，這表示集合，這表示集合C是一個封閉是一個封閉的集合，的集合， i不可達到不可達到j ，

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

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

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

25、234 所對應的目標函數(shù)63近鄰一臺機器的交貨期最小遲延排序問題4 364一臺機器的交貨期最小遲延排序問題 近鄰圖1212 點與解一一對應667754357710878668554610目標函數(shù)值65探索空間（search space）與實行可能域（feasible solution field） (2) 探索空間探索空間 目標函數(shù)值(objective function value) + 懲罰函數(shù)值(penalty function value ）實行可能域?qū)嵭锌赡苡蛱剿骺臻g探索空間實行可能域?qū)嵭锌赡苡蛱剿髟u價基準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）不排斥不可行解，用懲罰函數(shù)進行處理（通常為在目標函數(shù)設置一個懲罰項，如果突）不排斥不可行解，用懲罰函數(shù)進行處理（通常為