熱動力學(xué)演化算法TDEA及其進(jìn)展課件

熱動力學(xué)演化算法及其進(jìn)展內(nèi)容提要群智能算法研究的關(guān)鍵問題熱力學(xué)與統(tǒng)計力學(xué)動力系統(tǒng)與最優(yōu)控制熱動力學(xué)算法框架自由能極小與熱力學(xué)替換規(guī)則與粒子群算法的融合總結(jié)與展望群智能算法研究的關(guān)鍵問題回顧——早期遺傳算法以及相關(guān)演化算法優(yōu)點：自組織、自適應(yīng)、普適性理論：隱含并行、基因塊（建筑塊）假設(shè)、依概率收斂—基于SGA的論證缺點：過早收斂、適應(yīng)值平臺、欺騙性問題癥結(jié)：選擇壓力與種群多樣性的關(guān)系解決方法：從線性選擇策略到非線性選擇策略適應(yīng)值變換、錦標(biāo)賽競爭選擇、Boltzmann競爭選擇、μ+λ選擇減緩選擇壓力，保持種群多樣性熱力學(xué)與統(tǒng)計力學(xué)研究對象-大量粒子組成的系統(tǒng)熱現(xiàn)象和力的宏觀關(guān)系-熱力學(xué)從粒子運(yùn)動研究宏觀關(guān)系-統(tǒng)計力學(xué)基于宏觀觀測、實驗的唯象分析基于運(yùn)動定律、假設(shè)的統(tǒng)計分析系統(tǒng)的熱力學(xué)性質(zhì)兩個方面相輔相成封閉系統(tǒng)：能量交換孤立系統(tǒng)：與世隔絕開放系統(tǒng)：充分交換基本定律熱力學(xué)第一定律系統(tǒng)內(nèi)能的變化等于其從環(huán)境傳遞的熱量與對外所作的功之差：dE=δQ-δA，或δQ=dE

+δA，即系統(tǒng)吸收的熱量等于系統(tǒng)內(nèi)能的增加與系統(tǒng)對外做功之和，對孤立系統(tǒng)dE=0，或E=恒量

——能量守恒定律熱力學(xué)第二定律不可逆性—兩個典型的現(xiàn)象——t以-t代換得到不同的方程

T-溫度，λ-熱傳導(dǎo)系數(shù)：Fourier定律

C-濃度，D-濃度擴(kuò)散系數(shù)

：Fick定律

Kelvin表述：不能從單一熱源中取熱使之完全變?yōu)橛杏玫墓Χ划a(chǎn)生任何其它影響

Clausius表述：不可能把熱從低溫物體傳到高溫物體而不產(chǎn)生其它影響不可逆性，能量的耗散特性熵與平衡態(tài)熵的概念系統(tǒng)吸收熱能除以溫度所得的商，標(biāo)志熱轉(zhuǎn)化為功的程度d

S=δQ/T，嚴(yán)格地講應(yīng)分為兩部分：d

S=diS+deSdiS≥0，稱為熵產(chǎn)生項，由系統(tǒng)內(nèi)的熱運(yùn)動決定deS可正可負(fù)，稱為熵流項，由系統(tǒng)與外界環(huán)境的相互作用決定孤立系統(tǒng)有d

S≥0，但封閉系統(tǒng)和開放系統(tǒng)則不一定熵的統(tǒng)計力學(xué)解釋

系統(tǒng)的一個宏觀態(tài)對應(yīng)著大量的微觀態(tài)，一個微觀態(tài)稱為系統(tǒng)的一種實現(xiàn)，實現(xiàn)的總數(shù)稱作容配數(shù)W，則有熵

S=klnW——著名的Boltzmann公式

k稱為Boltzmann常數(shù)系統(tǒng)的平衡態(tài)對應(yīng)的容配數(shù)W最多，熵最大信息熵自信息描述了事件集X中一個事件i出現(xiàn)給出的信息量，整個集X的平均信息量是該集所有事件自信息的統(tǒng)計平均值（數(shù)學(xué)期望），稱作集X的熵pi表示件i事發(fā)生的概率H（X）度量了集X中各個事件未出現(xiàn)時所呈現(xiàn)的平均不確定性，也度量了集X中一個事件出現(xiàn)時所給出的平均信息量自由能極小定律等溫下的封閉熱力學(xué)系統(tǒng)遵循自由能極小定律對于與周圍環(huán)境交換熱量而溫度保持不變的封閉系統(tǒng),系統(tǒng)狀態(tài)的自發(fā)變化總是朝著自由能減少的方向進(jìn)行,當(dāng)自由能達(dá)到最小值時系統(tǒng)達(dá)到平衡態(tài)系統(tǒng)的自由能

F＝E–TS能量減少與熵增加均可導(dǎo)致自由能減少,兩者均有利于系統(tǒng)的自發(fā)變化任一恒定溫度下,系統(tǒng)從非平衡態(tài)自發(fā)變化到平衡態(tài)的過程,都是能量與熵兩者競爭的結(jié)果而溫度則決定著競爭過程中能量與熵的相對權(quán)重：高溫時熵占統(tǒng)治地位；低溫時能量占統(tǒng)治地位能量溫度熵?zé)崃W(xué)系統(tǒng)與群智能算法熱力學(xué)系統(tǒng)算法若干粒子組成熱力學(xué)系統(tǒng)若干個體組成進(jìn)化種群系統(tǒng)的能量種群的負(fù)平均適應(yīng)值，與開發(fā)能力相關(guān)系統(tǒng)的熱力學(xué)熵種群的多樣性，與探索能力相關(guān)系統(tǒng)的溫度權(quán)重控制參數(shù)T能量和熵的競爭“開發(fā)能力”與“探索能力”的適當(dāng)平衡恒定溫度下系統(tǒng)朝著自由能減少的方向自發(fā)變化給定權(quán)重T下驅(qū)動種群向自由能減少的方向演化“徐徐”降溫給定權(quán)重T下種群充分演化后緩慢衰減T值TDEA通過模擬自由能極小定律實現(xiàn)種群中能量和熵之間的競爭機(jī)制，從而達(dá)到定量協(xié)調(diào)算法探索能力和開發(fā)能力之間的均衡，隨T遞減緩慢降低自由能從N個父個體和M個子個體中挑選出N個個體組成下一代種群,使其具有的自由能最小熱動力學(xué)算法框架兩個最關(guān)鍵問題如何定義熵——度量種群多樣性基因熵（Mori,1995）網(wǎng)格熵（胡婷,2005）等級熵（應(yīng)偉勤，2007）如何設(shè)計熱力學(xué)替換規(guī)則——種群自由能下降貪婪熱力學(xué)替換規(guī)則（Mori,1995）分量熱力學(xué)替換規(guī)則（應(yīng)偉勤，2007）種群的基因熵Mori在實現(xiàn)TDGA時采用基因熵來度量種群的基因多樣性，基因熵等于種群每個基因座上的信息熵的合計值優(yōu)點：很直觀，易于實現(xiàn)缺點：只適用于離散編碼；在個體編碼較長時計算開銷極大，這將會降低TDGA的計算效率…

…0…

…1…

…0…12…j…LX1X2XN種群的等級熵活躍窗口wt

：記錄了到第t代為止搜索過程已達(dá)個體的適應(yīng)度范圍在對活躍窗口劃分等級時,遵循了適應(yīng)值區(qū)域越優(yōu)分級越精細(xì)的原則…0………1……0…編碼空間目標(biāo)空間活躍窗口f(.)等級劃分示意圖等級熵度量種群中個體在適應(yīng)值空間的分散程度當(dāng)Pt中所有個體全部落入同一等級時等級熵H(wt,Pt)取最小值0,當(dāng)Pt中落入各等級的個體數(shù)都相等時,H(wt,Pt)達(dá)到最大值1.等級熵的優(yōu)點：不再依賴個體的編碼長度，計算成本較低熱力學(xué)替換規(guī)則

從父代種群Pt

=(X1,X2,…,XN)的N個個體與產(chǎn)生的M個子代種群Ot=(XN+1,XN+2,…,XN+M)，共N+M個體中挑選出N個個體組成下一代種群P(E)t+1,使其具有的自由能F(Tt,P(E)t+1)最小從N個父個體和M個子個體中挑選出N個個體生成下一代種群,使其具有的自由能最小貪婪熱力學(xué)替換規(guī)則Mori在實現(xiàn)TDGA時采用了貪婪熱力學(xué)替換規(guī)則，按照貪婪的策略逐個往下一代種群中填充使臨時種群自由能最小的個體復(fù)雜度：O(LN(N+M))貪婪熱力學(xué)替換規(guī)則的計算開銷較窮舉熱力學(xué)替換規(guī)則有很大降低,但在實際應(yīng)用中計算成本仍相當(dāng)高Pt＋1=GTR(Tt,Pt,Ot){

將子種群Ot與父種群Pt合并得到規(guī)模為N+M的中間種群Pt＋1‘,將Pt＋1置空;for(i=1;i<=N;i++)//采用貪婪策略逐次往Pt＋1中填充N個個體

{for(j=1;j<=N+M-i;j++)//在多次嘗試后找到本輪最好填充個體計算若將Pt＋1‘的第j個個體填充到Pt＋1后的自由能F(Tt,Pt＋1∪{Pt＋1‘[j]}),并記錄下本輪嘗試填充中使自由能最小的個體Xjmin;

將個體Xjmin填充到Pt＋1中,并將其從中間種群Pt＋1‘中清除出去;}

返回下一代種群Pt＋1;}分量熱力學(xué)替換規(guī)則-自由能分量貪婪替換規(guī)則計算開銷較大的主要原因在于自由能是相對于種群而言的，須首先通過嘗試填充獲得臨時種群，然后反復(fù)計算這些臨時種群的自由能為提高計算效率，引入個體的自由能分量的概念，將種群的自由能分派到其各個體上，避免反復(fù)計算種群的自由能活躍窗口wt和溫度Tt下個體Xl在種群Pt中的自由能分量

Fc(wt,Tt,Pt,Xl)=e(Xl)+TtlogK(nd/N),

其中nd表示種群Pt中與Xl處于同一等級的個體數(shù)分量熱力學(xué)替換規(guī)則基于自由能分量的分量熱力學(xué)替換規(guī)則，計算量少驅(qū)動種群自由能下降快速復(fù)雜度：O(M(N+M))，有效降低了替換規(guī)則的時間復(fù)雜度TDEA相關(guān)論文MoriN,YoshidaJ,TamakiH,KitaH,NishikawaY.Athermodynamicalselectionruleforthegeneticalgorithm.In:FogelDB,ed.Proc.oftheIEEEConf.onEvolutionaryComputation.NewYork:IEEEPress,1995.188?192.MoriN,KitaH,NishikawaY.Adaptationtoachangingenvironmentbymeansofthefeedbackthermodynamicalgeneticalgorithm.In:EibenAE,etal.,eds.Proc.oftheIEEEConf.onParallelProblemSolvingfromNature.Berlin:Springer-Verlag,1998.149?158.應(yīng)偉勤,李元香,許承瑜.熱力學(xué)遺傳算法計算效率的改進(jìn).軟件學(xué)報,2008,19(7):1613-1622WeiqinYing,YuanxiangLi,ShujuanPeng,WeiwuWang.ASteepThermodynamicalSelectionRuleforEvolutionaryAlgorithms.Proc.ofInt.Conf.onComputationalScience.Beijing,China,2007:997-1004與粒子群算法的融合根據(jù)粒子的自由能分量決定下一代種群耗散粒子群優(yōu)化算法：引入負(fù)熵自組織臨界粒子群優(yōu)化算法：引入臨界值屬性