【正文】 010 010 011 0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011 0001 1110 100000 010110 111 100 0010110 1011011 10000 100111 0100 0001 1001110100 1100000001 1010101 0001010 010 011 第四節(jié) 遺 傳 算 法 Step6. 至下一代，適應(yīng)度計(jì)算 → 選擇 → 交叉 → 變異，直至滿足終止條件。 自然選擇過(guò)程是長(zhǎng)期的、緩慢的、連續(xù)的過(guò)程。 符號(hào)智能的特點(diǎn)是以知識(shí)為基礎(chǔ)，偏重于邏輯推理，而計(jì)算智能則是以數(shù)據(jù)為基礎(chǔ)，偏重于數(shù)值計(jì)算。它們分別從不同的角度模擬人類的智能活動(dòng)，以使計(jì)算機(jī)具有智能。 他們發(fā)現(xiàn)彼此的基本思想具有驚人的相似之處，于是提出將這類方法統(tǒng)稱為“進(jìn)化計(jì)算” ( Evolutionary Computation ) 。 第四節(jié) 遺 傳 算 法 二、幾個(gè)名詞概念 1. 進(jìn)化計(jì)算： 由于遺傳算法、進(jìn)化規(guī)劃和進(jìn)化策略是不同領(lǐng)域的研究人員分別獨(dú)立提出的，在相當(dāng)長(zhǎng)的時(shí)期里相互之間沒(méi)有正式溝通。 ? 60年代中期， 美國(guó) Michigan大學(xué)的 J. H. Holland教授 提出 借鑒生物自然遺傳的基本原理 用于自然和人工系統(tǒng)的自適應(yīng)行為研究和串編碼技術(shù)； ? 1967年，他的學(xué)生 J. D. Bagley在博士論文中首次提出“遺傳算法(Geic Algorithms)”一詞 ； ? 1975年， Holland出版了著名的“ Adaptation in Natural and Artificial Systems”，標(biāo)志遺傳算法的誕生。 ????? )()1( kxkx第三節(jié) 模 擬 退 火 算 法 ? 優(yōu)化結(jié)果 優(yōu)化目標(biāo)值 —— ＋ 06 獨(dú)立變量取值 —— t2 ℃ G1 Kg/s d1 mm S1 mm B1 m α1 弧度 L1 m d2 mm S2 mm B2 m α2 弧度 L2 m 第三節(jié) 模 擬 退 火 算 法 一、遺傳算法簡(jiǎn)介 第四節(jié) 遺 傳 算 法 ? 早在 50年代 ， 一些生物學(xué)家開始研究運(yùn)用數(shù)字計(jì)算機(jī)模擬生物的自然遺傳與自然進(jìn)化過(guò)程 ； ? 1963年，德國(guó)柏林技術(shù)大學(xué)的 I. Rechenberg和 H. P. Schwefel，做風(fēng)洞實(shí)驗(yàn)時(shí)，產(chǎn)生了進(jìn)化策略的初步思想； ? 60年代， L. J. Fogel在設(shè)計(jì)有限態(tài)自動(dòng)機(jī)時(shí)提出進(jìn)化規(guī)劃的思想。 ),()(m i n 212121212112 LLBBSSddGtfXf ???第三節(jié) 模 擬 退 火 算 法 ? 應(yīng)用模擬退火算法解決優(yōu)化設(shè)計(jì) 狀態(tài)表示 —— 12個(gè)變量的實(shí)數(shù)表示； 初始溫度 —— 100； 結(jié)束溫度 —— ； 狀態(tài)產(chǎn)生函數(shù) —— ， η為擾動(dòng)幅度參數(shù)， ξ為隨機(jī)擾動(dòng)變量，隨機(jī)擾動(dòng)可服從柯西、高斯、均勻分布。 其中， f1 (X)是兩級(jí)換熱器的初始投資， f2 (X)是兩級(jí)換熱器年維護(hù)費(fèi) (包括除垢、保養(yǎng)、維修等 )， f3 (X)是冷卻水資源費(fèi)以及管程壓降能耗費(fèi)， f4 (X)是殼程壓降能耗費(fèi)。 三、 模擬退火算法的優(yōu)缺點(diǎn) 第三節(jié) 模 擬 退 火 算 法 ? 換熱器模型 兩級(jí)管殼式換熱器組成的換熱器系統(tǒng)，數(shù)學(xué)模型高度非線性，其目標(biāo)函數(shù)通常是多峰 (谷 )的，具有很多局部最優(yōu)解。 6 外循環(huán)終止準(zhǔn)則 第三節(jié) 模 擬 退 火 算 法 ? 模擬退火算法的優(yōu)點(diǎn) 質(zhì)量高； 初值魯棒性強(qiáng)； 簡(jiǎn)單、通用、易實(shí)現(xiàn)。 10 ,0 ,1 ????? ?? ktt kk0tKkKtk??第三節(jié) 模 擬 退 火 算 法 ? 非時(shí)齊模擬退火算法 每個(gè)溫度下只產(chǎn)生一個(gè)或少量候選解 ? 時(shí)齊算法 —— 常用的 Metropolis抽樣穩(wěn)定準(zhǔn)則 （ 1）檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定； （ 2）連續(xù)若干步的目標(biāo)值變化較??； （ 3）按一定的步數(shù)抽樣。 方法 具體形式對(duì)算法影響不大， 一般采用 min[1,exp(?C/t)] 第三節(jié) 模 擬 退 火 算 法 3. 初溫 ? 收斂性分析 通過(guò)理論分析可以得到初溫的解析式，但解決實(shí)際問(wèn)題時(shí)難以得到精確的參數(shù)； 初溫應(yīng)充分大； ? 實(shí)驗(yàn)表明 初溫越大，獲得高質(zhì)量解的機(jī)率越大，但花費(fèi)較多的計(jì)算時(shí)間； 第三節(jié) 模 擬 退 火 算 法 ? 方法 (1) 均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫； (2) 隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，根據(jù)差值，利用一定的函數(shù)確定初溫； (3) 利用經(jīng)驗(yàn)公式。 若固定每一溫度，算法均計(jì)算馬氏鏈的變化直至平穩(wěn)分布，然后下降溫度，則稱為 時(shí)齊算法 ； 若無(wú)需各溫度下算法均達(dá)到平穩(wěn)分布，但溫度需按一定速率下降，則稱為 非時(shí)齊算法 。為間，為所有狀態(tài)構(gòu)成的解空令第三節(jié) 模 擬 退 火 算 法 一步轉(zhuǎn)移概率： n步轉(zhuǎn)移概率： 若解空間有限，稱馬爾可夫鏈為有限狀態(tài)； 若 ，稱馬爾可夫鏈為時(shí)齊的。 Until 抽樣穩(wěn)定準(zhǔn)則滿足； 退溫 tk+1=update(tk)并令 k=k+1； Until 算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。 Until 抽樣穩(wěn)定準(zhǔn)則滿足； 退溫 tk+1=update(tk)并令 k=k+1； Until 算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。 在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)； 在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)。 能量最低狀態(tài) 非能量最低狀態(tài) 第三節(jié) 模 擬 退 火 算 法 Metropolis準(zhǔn)則 (1953)—— 以概率接受新狀態(tài) 固體在恒定溫度下達(dá)到熱平衡的過(guò)程可以用 Monte Carlo方法 (計(jì)算機(jī)隨機(jī)模擬方法 )加以模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。為的能量，表示狀態(tài)機(jī)變量，表示分子能量的一個(gè)隨第三節(jié) 模 擬 退 火 算 法 在同一個(gè)溫度 T，選定兩個(gè)能量 E1E2， 在同一個(gè)溫度，分子停留在能量小的狀態(tài)的概率比停留在能量大的狀態(tài)的概率要大。 第三節(jié) 模 擬 退 火 算 法 物理退火過(guò)程 加溫過(guò)程 —— 增強(qiáng)粒子的熱運(yùn)動(dòng)，消除系統(tǒng)原先可能存在的非均勻態(tài)； 等溫過(guò)程 —— 對(duì)于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)； 冷卻過(guò)程 —— 使粒子熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。 2. 算法的目的 解決 NP復(fù)雜性問(wèn)題； 克服優(yōu)化過(guò)程陷入局部極小； 克服初值依賴性。在下一次的搜索中，就利用禁忌表中的信息，不再或者有選擇地搜索這些點(diǎn)，以此跳出局部最優(yōu)點(diǎn)。 其基本思想是：標(biāo)記已經(jīng)得到的局部最優(yōu)解，并在進(jìn)一步的迭代中避開這些局部最優(yōu)解。 第一節(jié) 隨 機(jī) 試 驗(yàn) 法 一、基本思想 用隨機(jī)的方法產(chǎn)生試驗(yàn)點(diǎn)，再?gòu)脑囼?yàn)點(diǎn)中選出滿足約束條件的點(diǎn)，進(jìn)而求出最優(yōu)點(diǎn)的一種方法。 啟發(fā)式算法的興起與計(jì)算 復(fù)雜性理論 的形成有密切的聯(lián)系。研究生課程 《 工程數(shù)學(xué) 》 之“ 最優(yōu)化方法 ” 現(xiàn) 代 最 優(yōu) 化 方 法 能源與動(dòng)力工程學(xué)院 College of Energy and Po