基因表達(dá)式編程教學(xué)課件4

先進(jìn)計算模型（4）自然計算模型系列之模擬退火算法

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

貪心算法，模擬退火,

蟻群算法，….)唐常杰

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

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

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

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

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

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

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

……

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

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

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

貪心算法及其批判---模擬退火算法GreedyAlgorithmandSimulatedAnnealingAlgorithm唐常杰川大計算機學(xué)院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分鐘。

欲速不達(dá)，這里紅燈亮但有天橋這里沒有天橋，但綠燈亮2/4/202312貪心算法例子2求職時，看當(dāng)前那個給的工資高，不管以后幾年的發(fā)展SearchspaceFitnessf(x)localoptimumglobaloptimumlocaloptimumlocaloptimum0xx1x2x4x5x3瞎子爬山法：一米長的探測棒，在這里發(fā)現(xiàn)往西邊走，打工工資高其實在這里打工工資才最高關(guān)鍵：探測棒太短了2/4/202313貪心算法例子2求職時，看當(dāng)前那個給的工資高，不管以后幾年的發(fā)展SearchspaceFitnessf(x)localoptimumglobaloptimumlocaloptimumlocaloptimum0xx1x2x4x5x3瞎子爬山法HillClimbing，選鄰近最好點，一米長的探測棒，在這里發(fā)現(xiàn)往西邊走工資升高其實在這里工資才最高關(guān)鍵：探測棒太短了。目光短淺2/4/202314生活中的貪心算法初學(xué)者下象棋圍棋，常常吃子上當(dāng)，高手常棄子攻殺貪心人上當(dāng)?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ā)性知識人生中，有時沒有選擇的權(quán)利，就盡可能做好能作的每一步，也是貪心算法，不乏成功者。慢一點，累一點不要把人生規(guī)劃和計算機程序攪混了2/4/202319貪心算法廣泛地用在計算機程序中好寫、簡單，容易想到和實現(xiàn)，往往稱為批判對象戲劇中常常用丫環(huán)“地位襯托”小姐“的漂亮金庸。古龍的小說中也有。在論文中貪心算法

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

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

等

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

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

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

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

巧妙控制，巧在何處

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

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

巧妙控制，巧在何處

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

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

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

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

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

接受法則

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

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

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

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

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

策略：

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

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

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

須使

大部份的轉(zhuǎn)移均可被接受

Kirkpatrick等(1983)建議：初溫度

為10

Heragu

，

(1992)建議：初溫

999初溫

可由

移轉(zhuǎn)接受概率門限P0

反推

Kouvelis

以及Chiang(1992)建議初溫度

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

指定固定溫度

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

復(fù)雜方式：

檢查解是否達(dá)標(biāo)

是否早熟：1992年Kouvelis

與Chiang

設(shè)定N次降溫

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

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

為移轉(zhuǎn)接受次數(shù)已達(dá)一定值，Heragu

以及Alfa（1992）所用

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

達(dá)成均衡

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

一般

0.5～0.9線性降溫

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

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

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