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

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

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

——能量守恒定律熱力學(xué)第二定律不可逆性—兩個(gè)典型的現(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)生項(xiàng)，由系統(tǒng)內(nèi)的熱運(yùn)動(dòng)決定deS可正可負(fù)，稱為熵流項(xiàng)，由系統(tǒng)與外界環(huán)境的相互作用決定孤立系統(tǒng)有d

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

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

S=klnW——著名的Boltzmann公式

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

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

…0…

…1…

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

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

從父代種群Pt

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

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

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

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

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

其中nd表示種群Pt中與Xl處于同一等級(jí)的個(gè)體數(shù)分量熱力學(xué)替換規(guī)則基于自由能分量的分量熱力學(xué)替換規(guī)則，計(jì)算量少驅(qū)動(dòng)種群自由能下降快速?gòu)?fù)雜度：O(M(N+M))，有效降低了替換規(guī)則的時(shí)間復(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ì)算效率的改進(jìn).軟件學(xué)報(bào),2008,19(7):1613-1622WeiqinYing,YuanxiangLi,ShujuanPeng,WeiwuWang.ASteepThermodynamicalSelectionRuleforEvolutionaryAlgorithms.Proc.ofInt.Conf.onComputationalScience.Beijing,China,2007:997-1004與粒子群算法的融合根據(jù)粒子的自由能分量決定下一代種群耗散粒子群優(yōu)化算法：引入負(fù)熵自組織臨界粒子群優(yōu)化算法：引入臨界值屬性