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

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

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

貪心算法，模擬退火,

蟻群算法，….)唐常杰

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

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

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

7/~tangchangjie/teach/tang_teaching.htm10/14/20222上一次

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

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

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

……

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

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

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

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

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

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

欲速不達(dá)，這里紅燈亮但有天橋這里沒有天橋，但綠燈亮10/14/202212貪心算法例子2求職時(shí)，看當(dāng)前那個(gè)給的工資高，不管以后幾年的發(fā)展SearchspaceFitnessf(x)localoptimumglobaloptimumlocaloptimumlocaloptimum0xx1x2x4x5x3瞎子爬山法：一米長(zhǎng)的探測(cè)棒，在這里發(fā)現(xiàn)往西邊走，打工工資高其實(shí)在這里打工工資才最高關(guān)鍵：探測(cè)棒太短了10/14/202213貪心算法例子2求職時(shí)，看當(dāng)前那個(gè)給的工資高，不管以后幾年的發(fā)展SearchspaceFitnessf(x)localoptimumglobaloptimumlocaloptimumlocaloptimum0xx1x2x4x5x3瞎子爬山法HillClimbing，選鄰近最好點(diǎn)，一米長(zhǎng)的探測(cè)棒，在這里發(fā)現(xiàn)往西邊走工資升高其實(shí)在這里工資才最高關(guān)鍵：探測(cè)棒太短了。目光短淺10/14/202214生活中的貪心算法初學(xué)者下象棋圍棋，常常吃子上當(dāng)，高手常棄子攻殺貪心人上當(dāng)?shù)睦印?瞎子下山、瞎子上山（最大梯度法）10/14/202215貪心算法的實(shí)現(xiàn)好寫、簡(jiǎ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();//實(shí)施追求眼前利益}}10/14/202216貪心算法廣泛地用在計(jì)算機(jī)程序中好寫、簡(jiǎn)單，容易想到和實(shí)現(xiàn)，往往成為批判對(duì)象在論文中往往處于丫環(huán)地位，用來襯托小姐程序的漂亮，對(duì)比分析時(shí)用10/14/202217貪心算法廣泛地用在計(jì)算機(jī)程序中好寫、簡(jiǎn)單，容易想到和實(shí)現(xiàn)，往往成為批判對(duì)象戲劇中常常用丫環(huán)“來襯托”小姐“的漂亮金庸。古龍的小說中也有。在論文中往往處于“丫環(huán)“地位，用來襯托”小姐程序“的漂亮，對(duì)比分析時(shí)用10/14/202218貪心算法廣泛地用在計(jì)算機(jī)程序中好寫、簡(jiǎn)單，容易想到和實(shí)現(xiàn)，往往稱為批判對(duì)象戲劇中常常用丫環(huán)“來襯托”小姐“的漂亮金庸。古龍的小說中也有。在論文中貪心算法

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

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

對(duì)貪心算法的一種批判---模擬退火算法本PPT用貪心算法來襯托模擬退火算法10/14/202221歷史沿革模擬退火（SimulatedAnnealing；SA）N.Metropolis

等

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

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

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

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

巧妙控制，巧在何處

大的冷卻趨勢(shì)中—有局部小的加熱—冷10點(diǎn)熱3點(diǎn)冷10點(diǎn)----熱3點(diǎn)----冷10點(diǎn)----熱3點(diǎn)----冷10點(diǎn)----熱3點(diǎn)----

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

巧妙控制，巧在何處

大的冷卻趨勢(shì)中—有局部小的加熱—冷10點(diǎn)熱3點(diǎn)冷10點(diǎn)----熱3點(diǎn)----冷10點(diǎn)----熱3點(diǎn)----冷10點(diǎn)----熱3點(diǎn)----

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

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

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

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

接受法則

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

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

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

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

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

策略：

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

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

10/14/202234退火參數(shù)經(jīng)驗(yàn)初始溫度為防止局部早熟，初溫

須使

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

Kirkpatrick等(1983)建議：初溫度

為10

Heragu

，

(1992)建議：初溫

999初溫

可由

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

反推

Kouvelis

以及Chiang(1992)建議初溫度

T0=Delta/ln(1/P0)10/14/202235退火參數(shù)：終止條件簡(jiǎn)單方式：

指定固定溫度

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

復(fù)雜方式：

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

是否早熟：1992年Kouvelis

與Chiang

設(shè)定N次降溫

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

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

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

以及Alfa（1992）所用

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

達(dá)成均衡

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

一般

0.5～0.9線性降溫

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

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

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