基因表達式編程教學課件4

先進計算模型（4）自然計算模型系列之模擬退火算法

SimulatedAnnealing四川大學計算機學院2008-2009博士生課程（粒子群-魚群算法(PSO)，遺傳算法，基因表達式編程

貪心算法，模擬退火,

蟻群算法，….)唐常杰

四川大學計算機學院2/4/20231目錄，大致計劃第一次自然計算模型系列1：概述篇自然計算模型系列2粒子群（

魚群/鳥群）算法自然計算模型系列3基因表達式編程第二次自然計算模型系列4：模擬退火算法自然計算模型系列5：蟻群算法自然計算模型系列6：免疫計算模型（思路和比喻）下載URL:校園網(wǎng)和學院網(wǎng)

http:///~chjtang/teach/tang_teaching.htm

7/~tangchangjie/teach/tang_teaching.htm2/4/20232上一次

自然計算模型（NatureComputing)概述PSO

粒子群算法魚群鳥群算法GEP基因表達式編程今天

蟻群算法模擬退火算法人工免疫思想（比喻）

……

歡迎同學發(fā)言（5-30分鐘均可）（如A先講，可跳至32頁）提綱2/4/20233致謝和參考資料出處參考資料：本PPT僅作和同學們在討論版內交流之用參考了若干教科書，文獻和論文和報告。在末尾列出50多篇，但參考的文獻不只這些,主要是遺傳算法、基因表達式編程、粒子群算法的相關作者等等，包括國內外，校內外專家和本實驗室成員的工作對未列出的文獻作者也在此一并致謝。參考文獻可能有遺漏，歡迎未列出的文獻作者及時指出，以便即時在參考文獻中補充、引用。作PPT類似于把小說改編為劇本，有重新創(chuàng)作的成分，也希望其它引用本PPT材料的標注本PPT2/4/20234課程計劃和特點有多位（7-8位）博士生導師作專題講座，每個老師講課8小時（大約需要準備40--60小時）特點廣---N位導師，N=8~9,N+

個領域，M個課題，(M>N).“N家講座”，不敢比百家…新---要求報告新技術前沿淺–因為時間短，主要將思想，方法，介紹成果。不可能深入到公式和算法細節(jié)實---結合實際，結合博士生可能的選題2/4/20235

這里根據(jù)情況插講自然計算模型PPT歡迎同學報告、討論，發(fā)言補充（5-30分鐘均可）介紹…..2/4/20236

貪心算法及其批判---模擬退火算法GreedyAlgorithmandSimulatedAnnealingAlgorithm唐常杰川大計算機學院2/4/20237貪心算法GreedyAlgorithm貪心算法屬于自然計算嗎？勉強算是。模擬了部分人、在部分時間的心理社會行為人性善：理性（理想、信仰、道德）>非理性時。部分人/在部分時間，上述不等式反過來了，表現(xiàn)出貪心。貪心時，目光短淺，只顧眼前最大利益，追求每步獲利最大貪心算法的基本思想：追求每一步獲利最大人貪心固然不好，但貪心算法有時是好用的。不貪心的人，在生活中會貪心算法嗎？會。且看下頁。2/4/20238貪心算法GreedyAlgorithm貪心算法屬于自然計算嗎？勉強算是。模擬了部分人、在部分時間的心理社會行為人性善：理性（理想、信仰、道德）>非理性時。部分人/在部分時間，上述不等式反過來了，表現(xiàn)出貪心。貪心時，目光短淺，只顧眼前最大利益，追求每步獲利最大貪心算法的基本思想：追求每一步獲利最大人貪心固然不好，但貪心算法有時是好用的。不貪心的人，在生活中會用貪心算法嗎？

會。且看下頁。2/4/20239貪心算法GreedyAlgorithm貪心算法屬于自然計算嗎？勉強算是。模擬了部分人、在部分時間的心理社會行為人性善：理性（理想、信仰、道德）>非理性時。部分人/在部分時間，上述不等式反過來了，表現(xiàn)出貪心。貪心時，目光短淺，只顧眼前最大利益，追求每步獲利最大貪心算法的基本思想：追求每一步獲利最大（啟發(fā)性知識）人貪心固然不好，但貪心算法有時是好用的。不貪心的人，在生活中會貪心算法嗎？

會。且看下頁。2/4/202310貪心算法例子BCAD這里有天橋這里沒有天橋，但綠燈亮這里紅燈亮下頁…..2/4/202311貪心算法例子BCAD過馬路十字路口，擬從A到C，70%的人會用貪心算法。通常那一個方向代價低（時間及其他資源），則先過該方向，先把看得見的實利（時間）搶到手。（這是一條啟發(fā)性知識）但不總是快，例如剛剛走到B,大量救火車南北方向通行，且持續(xù)10分鐘。

欲速不達，這里紅燈亮但有天橋這里沒有天橋，但綠燈亮2/4/202312貪心算法例子2求職時，看當前那個給的工資高，不管以后幾年的發(fā)展SearchspaceFitnessf(x)localoptimumglobaloptimumlocaloptimumlocaloptimum0xx1x2x4x5x3瞎子爬山法：一米長的探測棒，在這里發(fā)現(xiàn)往西邊走，打工工資高其實在這里打工工資才最高關鍵：探測棒太短了2/4/202313貪心算法例子2求職時，看當前那個給的工資高，不管以后幾年的發(fā)展SearchspaceFitnessf(x)localoptimumglobaloptimumlocaloptimumlocaloptimum0xx1x2x4x5x3瞎子爬山法HillClimbing，選鄰近最好點，一米長的探測棒，在這里發(fā)現(xiàn)往西邊走工資升高其實在這里工資才最高關鍵：探測棒太短了。目光短淺2/4/202314生活中的貪心算法初學者下象棋圍棋，常常吃子上當，高手常棄子攻殺貪心人上當?shù)睦印?瞎子下山、瞎子上山（最大梯度法）2/4/202315貪心算法的實現(xiàn)好寫、簡單FunctionFind-Direction-With-Max-Score-in-One-Step(){MaxScore=0;MaxDirection=0;forEachpossibleDirectionPointer,{m=Get-Score-in-next-step(*DirectionPointer

);//追求眼前最大利益If(MaxScore<m){.MaxScore=m;MaxDirection=DirectionPointer;}returnMaxDirection;}};

Mian(){While(notok){Find-Direction-With-Max-Score-in-One-Step();//眼前利益在何處？Make-One-Step();//實施追求眼前利益}}2/4/202316貪心算法廣泛地用在計算機程序中好寫、簡單，容易想到和實現(xiàn)，往往成為批判對象在論文中往往處于丫環(huán)地位，用來襯托小姐程序的漂亮，對比分析時用2/4/202317貪心算法廣泛地用在計算機程序中好寫、簡單，容易想到和實現(xiàn)，往往成為批判對象戲劇中常常用丫環(huán)“來襯托”小姐“的漂亮金庸。古龍的小說中也有。在論文中往往處于“丫環(huán)“地位，用來襯托”小姐程序“的漂亮，對比分析時用2/4/202318貪心算法廣泛地用在計算機程序中好寫、簡單，容易想到和實現(xiàn)，往往稱為批判對象戲劇中常常用丫環(huán)“來襯托”小姐“的漂亮金庸。古龍的小說中也有。在論文中貪心算法

往往處于“丫環(huán)“地位，用來襯托”小姐程序“的漂亮，對比分析時用為什么？比較的需要。沒有“丫環(huán)“也要造一個（電器中也有丫環(huán)機型），貪心算法最好造。還有點啟發(fā)性知識人生中，有時沒有選擇的權利，就盡可能做好能作的每一步，也是貪心算法，不乏成功者。慢一點，累一點不要把人生規(guī)劃和計算機程序攪混了2/4/202319貪心算法廣泛地用在計算機程序中好寫、簡單，容易想到和實現(xiàn)，往往稱為批判對象戲劇中常常用丫環(huán)“地位襯托”小姐“的漂亮金庸。古龍的小說中也有。在論文中貪心算法

往往處于“丫環(huán)“地位，用來襯托”小姐程序“的漂亮，對比分析時用為什么？比較的需要。沒有“丫環(huán)“也要造一個（電器中也有丫環(huán)機型），貪心算法最好造。還有點啟發(fā)性知識人生中，有時沒有選擇的權利，就盡可能做好能作的每一步，說來也是貪心算法，但不乏成功者，慢一點。不要把人生規(guī)劃和計算機程序攪混了2/4/202320

對貪心算法的一種批判---模擬退火算法本PPT用貪心算法來襯托模擬退火算法2/4/202321歷史沿革模擬退火（SimulatedAnnealing；SA）N.Metropolis

等

1953年所提出，被忽略1983年，Kirkpatricketal.提出蒙特卡羅模擬法（MonteCarloSimulated）的隨機搜尋技巧，求解的組合最佳化問題時人們才重新想起模擬退火。

科學歷史上類似事情很多2/4/202322看看工廠中的淬火和退火工藝淬火，把錐尖部分燒紅，在水中急速冷卻，硬而脆中國古代鑄劍技術莫邪干將，夫差劍….（請學熱處理專業(yè)的同學講）高頻淬火：利用電流趨膚效應，只加熱表面，然后急速冷卻，表面收縮，預應力或殘應力，使得皮硬心韌適合軸表面，刀刃等。（利用預應力或殘應力）退火---淬火的逆向工藝，減少應力，是的材料舒緩，鑄件退火，金屬鑄件，日曬雨淋幾個月，在后期，氣溫區(qū)間，溫度隨氣溫有升有降，利于充分釋放應力，如鑄造的剎車鼓，機器座等。均勻，不脆，好加工

自然退火，先熱(粒子溫升,無序，內能增大)，后慢冷(粒子漸趨有序內能減為最小)

。2/4/202323金屬工藝學的解釋金屬加熱至一定的溫度后，分子結構--被打散瓦解—準液態(tài)直接地貪心地一路下降溫度，可能部分緊張的結構冷成緊張結構死結，無法舒緩，解決方法，小小地加一點熱。讓其成準液態(tài)降溫過程

巧妙控制，巧在何處

大的冷卻趨勢中—有局部小的加熱—冷10點熱3點冷10點----熱3點----冷10點----熱3點----冷10點----熱3點----

使其分子在液態(tài)結構轉變?yōu)楣腆w結構時，重新排列成我們所預期的穩(wěn)定狀態(tài)當冷進行得不好時，晶粒結構緊張，重新小加熱--，隨機地接受一個暫劣解，跳出局部優(yōu)化（早熟），有機會能達到全局最優(yōu)，2/4/202324金屬工藝學的解釋金屬加熱至一定的溫度后，分子結構--被打散瓦解—準液態(tài)直接地貪心地一路下降溫度，可能部分緊張的結構冷成緊張結構死結，無法舒緩，解決方法，小小地加一點熱。讓其成準液態(tài)降溫過程

巧妙控制，巧在何處

大的冷卻趨勢中—有局部小的加熱—冷10點熱3點冷10點----熱3點----冷10點----熱3點----冷10點----熱3點----

使其分子在液態(tài)結構轉變?yōu)楣腆w結構時，重新排列成我們所預期的穩(wěn)定狀態(tài)當冷進行得不好時，晶粒結構緊張，重新小加熱--，隨機地接受一個暫劣解，跳出局部優(yōu)化（早熟），有機會能達到全局最優(yōu)，2/4/202325

生活中的模擬退火--巧妙轉達壞消息向一個心理素質不好的人轉告壞消息（親屬受傷…,Fen-Sou)可以用模擬退火算法，大趨勢：逐步降溫，發(fā)現(xiàn)其心態(tài)很差時，偶爾升溫，避免走向極端可防止精神緊張，防止出問題（精神錯亂，自殺，等等）使其精神狀態(tài)從強烈期待和緊張，安全地轉化為平常心，如果用瞎子下山法（貪心），降溫太快，可能導致精神崩潰2/4/202326

生活中的模擬退火--巧妙轉達壞消息向一個心理素質不好的人轉告壞消息，可以用模擬退火算法，大趨勢：逐步降溫，發(fā)現(xiàn)其心態(tài)很差時，偶爾升溫，避免走向極端可防止精神緊張，防止出問題（精神錯論，自殺等等）使其精神狀態(tài)從強烈期待和緊張，安全地轉化為平常心，如果用瞎子下山法（貪心），降溫太快，可能導致精神崩潰2/4/202327比喻弛中有張，慢功細活有堅定的信念，允許暫時的失敗。是對貪心算法的一種批判

貪心算法是對部分人性的模擬。思想：弛中有張，爭中有讓，可能是99%的弛，1%的張大趨勢是弛（降溫，釋放應力）爭99步，不放讓一步戰(zhàn)爭中不拘泥于一城一池的得失2/4/202328技術要點熱力學：溫度為t，能量差所表現(xiàn)的概率P(ΔE)=exp(-ΔE/kt)接受法則（AcceptingRule）并行退火程序（AnnealingSchedule成功關鍵：合理退火規(guī)劃2/4/202329數(shù)學建模（符號假定和簡化）考慮搜索最優(yōu)解過程i代表在時間k的當前解，成本為C(i)下一個解，成本為C(j)兩個解之間的成本差，如圖所示DE=C(j)-C(i)為搜索方向2/4/202330補充預備知識：通過隨機實現(xiàn)公平設計一個抽簽函數(shù)(下頁）既體現(xiàn)隨機的公平（客觀或運氣），又體現(xiàn)主觀努力，優(yōu)勝劣汰（適應度）。為什么需要這個函數(shù)？否則庶民個體會問：王侯將相寧有種乎？2/4/202331數(shù)學建模（符號假定和簡化）遇到困難j的成本大于i時，擲骰子，隨機定是否接受j來取代i成新解（按概率允許小的失?。├щy時要妥協(xié)以下按概率決定是否妥協(xié)，退步。SAMetrolopis

接受法則

+退火計劃，溫度漸降，擲骰子定是否接受較差新解，當溫度越低時（即越接近勝利），越少妥協(xié)

弛中有張，可能是99%的弛，1%的張，大趨勢是弛（降溫，釋放應力），爭99步，讓一步2/4/202332退火算法四要點系統(tǒng)狀態(tài)或配置（Configuration）：三元組（溫度，初始解，作當前解）搜索（干預）規(guī)則：

退火過程中，系統(tǒng)狀態(tài)經(jīng)—干預---跳至另一種狀態(tài)常用方法

梯度法（GradientType）迭代法（IterativeImprovement）2/4/202333退火算法四要素成本函數(shù)（CostFunction）：用來衡量某一系統(tǒng)狀態(tài)下之能量函數(shù)，類似于GEP中適應度退火規(guī)劃（AnnealingProcess）：

含參數(shù)：初溫、降溫機制、冷卻率，終止溫度

策略：

溫高時（早期），多妥協(xié)，比方爭99步，讓一步

溫低時（后期），少妥協(xié)，比方爭999步，讓一步

2/4/202334退火參數(shù)經(jīng)驗初始溫度為防止局部早熟，初溫

須使

大部份的轉移均可被接受

Kirkpatrick等(1983)建議：初溫度

為10

Heragu

，

(1992)建議：初溫

999初溫

可由

移轉接受概率門限P0

反推

Kouvelis

以及Chiang(1992)建議初溫度

T0=Delta/ln(1/P0)2/4/202335退火參數(shù)：終止條件簡單方式：

指定固定溫度

降溫次數(shù)=預定值

復雜方式：

檢查解是否達標

是否早熟：1992年Kouvelis

與Chiang

設定N次降溫

無改善退出2/4/202336退火參數(shù)經(jīng)驗：降溫時機降溫時機---馬可夫鏈長度，同一溫度下所應反覆進行Metropolis演算的次數(shù)直接方式：設固定長度，與問題規(guī)模有關，1992年Kouvelis

與Chiang將其設定為鄰近解個數(shù)之比率。降溫時機

為移轉接受次數(shù)已達一定值，Heragu

以及Alfa（1992）所用

但當溫降至很低時，移轉接受之機率將會很小，導致馬可夫鏈過長，須同時限定馬可夫鏈的長度2/4/202337退火參數(shù)經(jīng)驗：溫度控制達到降溫時機時，下降多少？（比率）參數(shù)小，差距大，下一溫度

達成均衡

所需的馬可夫鏈長求解時間增加。Kirkpatrick（1983）設為0.9，

一般

0.5～0.9線性降溫

Temp=Temp-x非線性降溫Temp=Temp*y

(y:0.5~0.99)2/4/202338退火算法的預備：一個抽簽函數(shù)補充預備知識：通過隨機實現(xiàn)自然放松設計一個抽簽函數(shù)(下頁）設計一個抽簽既體現(xiàn)偶爾升溫的隨機（客觀或運氣），又體現(xiàn)當前溫度的機會函數(shù)。2/4/202339準備一個函數(shù)：機會留給有準備的對象（主觀+客觀）設計一個機遇函數(shù)既體現(xiàn)隨機的公平（客觀或運氣），又體現(xiàn)當前溫度。降溫大趨勢中，按Rate=exp(-Δt′/T)的幾率降溫這一步應該降溫嗎，擲個骰子（古人用甲骨文占卜)：Bool

GetChance(Rate,CurrT，Threshold){redomaize();chance=Radom(1);return=(Chance<rate)&&(CurrT<=Threshold)}|-----|-----------|------……..------------------------------------|0chan