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

1、先進(jìn)計算模型（4）自然計算模型系列 之 模擬退火算法Simulated Annealing四川大學(xué)計算機(jī)學(xué)院2008 -2009博士生課程（粒子群-魚群算法(PSO)，遺傳算法，基因表達(dá)式編程 貪心算法， 模擬退火, 蟻群算法，.)唐常杰 四川大學(xué)計算機(jī)學(xué)院9/8/20221目錄，大致計劃第一次自然計算模型系列1：概述篇自然計算模型系列2 粒子群（ 魚群/鳥群） 算法自然計算模型系列3 基因表達(dá)式編程第二次自然計算模型系列4：模擬退火算法自然計算模型系列5：蟻群算法 自然計算模型系列6：免疫計算模型（思路和比喻）下載URL: 校園網(wǎng) 和 學(xué)院網(wǎng) /chjtang/teach/tang_teac

2、hing.htm 7/tangchangjie/teach/tang_teaching.htm9/8/20222上一次 自然計算模型 （Nature Computing)概述PSO 粒子群算法 魚群 鳥群算法GEP 基因表達(dá)式編程今天 蟻群算法 模擬退火算法 人工免疫 思想 （比喻） 歡迎同學(xué)發(fā)言 （5-30分鐘均可）（ 如 A 先講， 可跳至32頁 ）提綱9/8/20223致謝 和 參考資料 出處參考資料： 本PPT僅作和同學(xué)們在討論版內(nèi)交流之用參考了若干教科書，文獻(xiàn)和論文和報告。在末尾列出50多篇，但參考的文獻(xiàn)不只這些,主要是遺傳算法、基因表達(dá)式編程、粒子群算法 的相關(guān)作者等等，包括 國內(nèi)

3、外，校內(nèi)外專家和本實驗室成員的工作對未列出的文獻(xiàn)作者也在此一并致謝。參考文獻(xiàn)可能有遺漏，歡迎未列出的文獻(xiàn)作者及時指出，以便即時在參考文獻(xiàn)中補(bǔ)充、引用。作PPT類似于把小說改編為劇本，有重新創(chuàng)作的成分，也希望其它引用本PPT材料的標(biāo)注 本PPT9/8/20224課程計劃和特點有多位（7-8位）博士生導(dǎo)師作專題講座， 每個老師講課8小時（大約需要準(zhǔn)備 40-60小時）特點廣- N位導(dǎo)師，N=89 ,N + 個領(lǐng)域，M個課題，(MN). “N家講座” ，不敢比 百家新 -要求報告 新技術(shù)前沿淺 因為時間短，主要將思想，方法，介紹成果。不可能深入到公式和算法細(xì)節(jié)實-結(jié)合實際，結(jié)合博士生可能的選題9/8

4、/20225 這里根據(jù)情況 插講 自然計算模型PPT歡迎同學(xué) 報告、討論，發(fā)言補(bǔ)充 （5-30分鐘 均可）介紹.9/8/20226 貪心算法及其批判-模擬退火 算法Greedy Algorithm andSimulated Annealing Algorithm唐常杰川大計算機(jī)學(xué)院9/8/20227貪心算法 Greedy Algorithm貪心算法屬于自然計算嗎？ 勉強(qiáng) 算是。模擬了 部分人、在部分時間的心理社會行為人性善：理性（理想、信仰、道德） 非理性時。部分人/在部分時間 ，上述不等式 反過來了，表現(xiàn)出貪心。貪心時，目光短淺，只顧眼前最大利益，追求每步獲利最大貪心算法的基本思想：追求每一

5、步獲利最大（啟發(fā)性知識）人 貪心 固然 不好， 但貪心算法 有時是好用的 。不貪心的人， 在生活中 會貪心算法嗎？ 會。且看下頁。9/8/202210貪心算法例子BCAD這里有天橋這里沒有天橋，但綠燈亮這里紅燈亮下頁 .9/8/202211貪心算法例子BCAD過馬路十字路口 ，擬從A到C，70%的人會用貪心算法。通常 那一個方向代價低（時間及其他資源），則先過該方向，先把看得見的實利（時間）搶到手。（這是一條啟發(fā)性知識）但不總是快，例如剛剛走到B, 大量救火車南北方向通行，且持續(xù)10分鐘。 欲速不達(dá)，這里紅燈亮但有天橋這里沒有天橋，但綠燈亮9/8/202212貪心算法的實現(xiàn) 好寫、簡單Func

6、tion Find-Direction-With-Max-Score-in-One-Step( ) MaxScore=0; MaxDirection=0; for Each possible DirectionPointer, m=Get-Score-in-next-step( * DirectionPointer );/追求眼前最大利益 If (MaxScorem) . MaxScore=m; MaxDirection= DirectionPointer; return MaxDirection; ; Mian( ) While (not ok) Find-Direction-With-Ma

7、x-Score-in-One-Step( ); /眼前利益在何處？ Make-One-Step( ); / 實施 追求眼前利益 9/8/202216貪心算法廣泛地用在計算機(jī)程序中好寫、簡單，容易想到和實現(xiàn)，往往成為批判對象在論文中往往處于丫環(huán)地位，用來襯托小姐程序的漂亮， 對比分析時用9/8/202217貪心算法廣泛地用在計算機(jī)程序中好寫、簡單，容易想到和實現(xiàn)，往往成為批判對象戲劇中 常常用丫環(huán)“來襯托 ”小姐“的漂亮金庸。古龍的小說中也有。在論文中往往處于 “丫環(huán)“地位，用來襯托 ”小姐程序“的漂亮， 對比分析時用9/8/202218貪心算法廣泛地用在計算機(jī)程序中好寫、簡單，容易想到和實現(xiàn)，

8、往往稱為批判對象戲劇中 常常用丫環(huán)“ 來襯托 ”小姐“的漂亮金庸。古龍的小說中也有。在論文中 貪心算法 往往處于 “丫環(huán)“地位，用來襯托 ”小姐程序“的漂亮， 對比分析時用為什么？ 比較的需要。沒有“丫環(huán)“也要造一個（電器中也有丫環(huán)機(jī)型），貪心算法 最好造。還有點啟發(fā)性知識人生中，有時沒有選擇的權(quán)利，就盡可能做好能作的每一步，也是貪心算法，不乏成功者。慢一點，累一點不要 把人生規(guī)劃 和 計算機(jī)程序 攪混了9/8/202219 看看 工廠中的淬火和退火工藝淬火，把錐尖部分燒紅，在水中急速冷卻， 硬而脆 中國古代 鑄劍 技術(shù) 莫邪 干將 ，夫差 劍.（請 學(xué)熱處理專業(yè)的同學(xué)講）高頻淬火：利用電流趨

9、膚效應(yīng)，只加熱表面，然后急速冷卻， 表面收縮， 預(yù)應(yīng)力 或 殘應(yīng)力， 使得皮硬心韌 適合軸表面，刀刃等。（利用 預(yù)應(yīng)力 或 殘應(yīng)力）退火 - 淬火的逆向工藝， 減少應(yīng)力，是的材料舒緩，鑄件退火，金屬鑄件，日曬雨淋幾個月，在后期，氣溫區(qū)間，溫度隨氣溫有升有降，利于充分釋放應(yīng)力，如鑄造的剎車鼓，機(jī)器座等。均勻，不脆，好加 工 自然退火，先熱(粒子溫升,無序，內(nèi)能增大)，后慢冷(粒子漸趨有序內(nèi)能減為最小) 。9/8/202223金屬工藝學(xué)的解釋金屬加熱至一定的溫度后，分子結(jié)構(gòu)-被打散瓦解準(zhǔn)液態(tài)直接地 貪心地 一路下降溫度，可能部分緊張的結(jié)構(gòu) 冷成緊張結(jié)構(gòu)死結(jié)， 無法舒緩， 解決方法，小小地加一點熱。

10、讓其成準(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) 緊張，重新小加熱-，隨機(jī)地接受一個暫劣解，跳出局部優(yōu)化（早熟），有機(jī)會能達(dá)到全局最優(yōu)，9/8/202224金屬工藝學(xué)的解釋金屬加熱至一定的溫度后，分子結(jié)構(gòu)-被打散瓦解準(zhǔn)液態(tài)直接地 貪心地 一路下降溫度，可能部分緊張的結(jié)構(gòu) 冷成緊張結(jié)構(gòu)死結(jié)， 無法舒緩， 解決方法，小小地加一點熱。讓其成準(zhǔn)液態(tài)降溫過程 巧妙控制，巧在何處 大的 冷卻趨勢中有局部小的加熱

11、 冷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) 緊張，重新小加熱-，隨機(jī)地接受一個暫劣解，跳出局部優(yōu)化（早熟），有機(jī)會能達(dá)到全局最優(yōu)，9/8/202225 生活中的模擬退火- 巧妙轉(zhuǎn)達(dá)壞消息向一個心理素質(zhì)不好的人轉(zhuǎn)告壞消息（親屬受傷,Fen-Sou)可以用模擬退火算法，大趨勢：逐步降溫，發(fā)現(xiàn)其心態(tài)很差時， 偶爾升溫，避免走向極端 可防止精神緊張，防止出問題（精神錯亂，自殺，等等）使其精神狀態(tài) 從強(qiáng)烈期待和緊張，安全地轉(zhuǎn)化為 平常心，如果用瞎子下山法（貪心），降溫太快，

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

13、拘泥于 一城一池的得失9/8/202228技術(shù)要點熱力學(xué)：溫度為t，能量差所表現(xiàn)的概率P(E)=exp(-E / kt)接受法則（Accepting Rule）并行退火程序（Annealing Schedule成功關(guān)鍵：合理退火規(guī)劃9/8/202229數(shù)學(xué)建模 （符號假定和簡化）考慮搜索最優(yōu)解過程i 代表在時間k 的當(dāng)前解，成本為C(i)下一個解，成本為C(j)兩個解之間的成本差，如圖所示D E = C(j) - C(i)為搜索方向9/8/202230補(bǔ)充預(yù)備知識：通過隨機(jī) 實現(xiàn)公平設(shè)計 一個 抽簽函數(shù)(下頁） 既體現(xiàn)隨機(jī)的公平（客觀或運氣）， 又體現(xiàn)主觀努力，優(yōu)勝劣汰（適應(yīng)度 ）。為什么需要

14、這個函數(shù)？否則 庶民個體會問： 王侯將相 寧有種乎？9/8/202231 退火算法 四要素成本函數(shù)（Cost Function）：用來衡量某一系統(tǒng)狀態(tài)下之能量函數(shù) ， 類似于GEP中適應(yīng)度退火規(guī)劃（Annealing Process）： 含參數(shù)：初溫、降溫機(jī)制、冷卻率，終止溫度 策略： 溫高時（早期），多妥協(xié)，比方 爭99步，讓一步 溫低時（后期），少妥協(xié)，比方 爭999步，讓一步 9/8/202234退火參數(shù) 經(jīng)驗初始溫度為防止局部早熟，初溫 須使 大部份的轉(zhuǎn)移均可被接受 Kirkpatrick等 ( 1983 )建議：初溫度 為10 Heragu ， ( 1992 )建議： 初溫 999初

15、溫 可由 移轉(zhuǎn)接受概率 門限 P 0 反推 Kouvelis 以及 Chiang( 1992 ) 建議初溫度 T0 =Delta / ln(1/P0)9/8/202235退火參數(shù) ：終止條件簡單方式： 指定固定溫度 降溫次數(shù)=預(yù)定值 復(fù)雜方式： 檢查解是否達(dá)標(biāo) 是否早熟： 1992 年Kouvelis 與 Chiang 設(shè)定N次降溫 無改善 退出9/8/202236退火參數(shù) 經(jīng)驗：降溫時機(jī)降溫時機(jī)-馬可夫鏈長度，同一溫度下所應(yīng)反覆進(jìn)行Metropolis 演算的次數(shù)直接方式：設(shè)固定長度，與問題規(guī)模有關(guān)，1992 年Kouvelis 與Chiang 將其設(shè)定為鄰近解個數(shù)之比率。降溫時機(jī) 為移轉(zhuǎn)接

16、受次數(shù)已達(dá)一定值，Heragu 以及 Alfa（1992）所用 但當(dāng)溫降至很低時，移轉(zhuǎn)接受之機(jī)率將會很小，導(dǎo)致馬可夫鏈過長，須同時限定馬可夫鏈的長度9/8/202237退火參數(shù) 經(jīng)驗 ：溫度控制達(dá)到降溫時機(jī)時，下降多少？（比率）參數(shù)小，差距大，下一溫度 達(dá)成均衡 所需的馬可夫鏈長求解時間增加。Kirkpatrick（1983）設(shè)為0.9， 一般 0.50.9 線性降溫 Temp=Temp-x 非線性降溫 Temp=Temp*y (y : 0.50.99)9/8/202238退火算法的預(yù)備： 一個抽簽函數(shù)補(bǔ)充預(yù)備知識：通過隨機(jī) 實現(xiàn) 自然放松設(shè)計 一個 抽簽函數(shù)(下頁）設(shè)計 一個抽簽 既體現(xiàn) 偶

17、爾升溫的 隨機(jī)（客觀或運氣），又體現(xiàn)當(dāng)前溫度的機(jī)會函數(shù)。9/8/202239準(zhǔn)備一個函數(shù)：機(jī)會留給有準(zhǔn)備的對象（主觀+客觀）設(shè)計 一個 機(jī)遇函數(shù)既體現(xiàn)隨機(jī)的公平（客觀或運氣），又體現(xiàn)當(dāng)前溫度。降溫大趨勢中，按Rate = exp(-t/T)的幾率 降溫這一步 應(yīng)該 降溫嗎，擲個骰子（古人 用甲骨文占卜)：Bool GetChance( Rate, CurrT，Threshold) redomaize( ); chance=Radom(1); return = ( Chancerate) & ( CurrT = Threshold) |-|-|- .-| 0 chance rate =1% 1溫

18、度很高的時候不需要升溫升溫機(jī)會9/8/202240模擬退火法圖隨機(jī)初始解擾動，產(chǎn)生一個新解是否接受?修改目前解應(yīng)該降溫？減溫 中止條件?NoYesYesYesNoNo針對循環(huán)：在前解為的小鄰域中 隨機(jī)化 取解。初使化最優(yōu)解9/8/202241退火算法 偽代碼初始化：初溫T(充分大)，初解S(算法迭代起點)， 迭代次數(shù)L While (1) for (k=1， KL,K+) ： 產(chǎn)生新解S 計算增量t=C(S)-C(S)，其中C(S)為評價函數(shù) if (t0) 接受S作新解， else if GetChance(exp(-t/T) , CurrT，Threshold.) 接受S作為新解 if (滿足終止條件) return ( 當(dāng)前解) /作為最優(yōu)解， 按降溫規(guī)則（一般 0.50.9）降溫 這里體現(xiàn)偶爾的讓