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

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

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

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

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

5、步獲利最大（啟發(fā)性知識(shí)）人 貪心 固然 不好， 但貪心算法 有時(shí)是好用的 。不貪心的人， 在生活中 會(huì)貪心算法嗎？ 會(huì)。且看下頁(yè)。9/8/202210貪心算法例子BCAD這里有天橋這里沒(méi)有天橋，但綠燈亮這里紅燈亮下頁(yè) .9/8/202211貪心算法例子BCAD過(guò)馬路十字路口 ，擬從A到C，70%的人會(huì)用貪心算法。通常 那一個(gè)方向代價(jià)低（時(shí)間及其他資源），則先過(guò)該方向，先把看得見(jiàn)的實(shí)利（時(shí)間）搶到手。（這是一條啟發(fā)性知識(shí)）但不總是快，例如剛剛走到B, 大量救火車南北方向通行，且持續(xù)10分鐘。 欲速不達(dá)，這里紅燈亮但有天橋這里沒(méi)有天橋，但綠燈亮9/8/202212貪心算法的實(shí)現(xiàn) 好寫(xiě)、簡(jiǎ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( ); / 實(shí)施 追求眼前利益 9/8/202216貪心算法廣泛地用在計(jì)算機(jī)程序中好寫(xiě)、簡(jiǎn)單，容易想到和實(shí)現(xiàn)，往往成為批判對(duì)象在論文中往往處于丫環(huán)地位，用來(lái)襯托小姐程序的漂亮， 對(duì)比分析時(shí)用9/8/202217貪心算法廣泛地用在計(jì)算機(jī)程序中好寫(xiě)、簡(jiǎn)單，容易想到和實(shí)現(xiàn)，往往成為批判對(duì)象戲劇中 常常用丫環(huán)“來(lái)襯托 ”小姐“的漂亮金庸。古龍的小說(shuō)中也有。在論文中往往處于 “丫環(huán)“地位，用來(lái)襯托 ”小姐程序“的漂亮， 對(duì)比分析時(shí)用9/8/202218貪心算法廣泛地用在計(jì)算機(jī)程序中好寫(xiě)、簡(jiǎn)單，容易想到和實(shí)現(xiàn)，

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

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

10、讓其成準(zhǔn)液態(tài)降溫過(guò)程 巧妙控制，巧在何處 大的 冷卻趨勢(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)，9/8/202224金屬工藝學(xué)的解釋金屬加熱至一定的溫度后，分子結(jié)構(gòu)-被打散瓦解準(zhǔn)液態(tài)直接地 貪心地 一路下降溫度，可能部分緊張的結(jié)構(gòu) 冷成緊張結(jié)構(gòu)死結(jié)， 無(wú)法舒緩， 解決方法，小小地加一點(diǎn)熱。讓其成準(zhǔn)液態(tài)降溫過(guò)程 巧妙控制，巧在何處 大的 冷卻趨勢(shì)中有局部小的加熱

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

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

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

14、這個(gè)函數(shù)？否則 庶民個(gè)體會(huì)問(wèn)： 王侯將相 寧有種乎？9/8/202231 退火算法 四要素成本函數(shù)（Cost Function）：用來(lái)衡量某一系統(tǒng)狀態(tài)下之能量函數(shù) ， 類似于GEP中適應(yīng)度退火規(guī)劃（Annealing Process）： 含參數(shù)：初溫、降溫機(jī)制、冷卻率，終止溫度 策略： 溫高時(shí)（早期），多妥協(xié)，比方 爭(zhēng)99步，讓一步 溫低時(shí)（后期），少妥協(xié)，比方 爭(zhēng)999步，讓一步 9/8/202234退火參數(shù) 經(jīng)驗(yàn)初始溫度為防止局部早熟，初溫 須使 大部份的轉(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ù) ：終止條件簡(jiǎn)單方式： 指定固定溫度 降溫次數(shù)=預(yù)定值 復(fù)雜方式： 檢查解是否達(dá)標(biāo) 是否早熟： 1992 年Kouvelis 與 Chiang 設(shè)定N次降溫 無(wú)改善 退出9/8/202236退火參數(shù) 經(jīng)驗(yàn)：降溫時(shí)機(jī)降溫時(shí)機(jī)-馬可夫鏈長(zhǎng)度，同一溫度下所應(yīng)反覆進(jìn)行Metropolis 演算的次數(shù)直接方式：設(shè)固定長(zhǎng)度，與問(wèn)題規(guī)模有關(guān)，1992 年Kouvelis 與Chiang 將其設(shè)定為鄰近解個(gè)數(shù)之比率。降溫時(shí)機(jī) 為移轉(zhuǎn)接

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

17、爾升溫的 隨機(jī)（客觀或運(yùn)氣），又體現(xiàn)當(dāng)前溫度的機(jī)會(huì)函數(shù)。9/8/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 = ( Chancerate) & ( CurrT = Threshold) |-|-|- .-| 0 chance rate =1% 1溫

18、度很高的時(shí)候不需要升溫升溫機(jī)會(huì)9/8/202240模擬退火法圖隨機(jī)初始解擾動(dòng)，產(chǎn)生一個(gè)新解是否接受?修改目前解應(yīng)該降溫？減溫 中止條件?NoYesYesYesNoNo針對(duì)循環(huán)：在前解為的小鄰域中 隨機(jī)化 取解。初使化最優(yōu)解9/8/202241退火算法 偽代碼初始化：初溫T(充分大)，初解S(算法迭代起點(diǎn))， 迭代次數(shù)L While (1) for (k=1， KL,K+) ： 產(chǎn)生新解S 計(jì)算增量t=C(S)-C(S)，其中C(S)為評(píng)價(jià)函數(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)偶爾的讓