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

熱動(dòng)力學(xué)演化算法及其進(jìn)展第一頁，共二十九頁，編輯于2023年，星期三內(nèi)容提要群智能算法研究的關(guān)鍵問題熱力學(xué)與統(tǒng)計(jì)力學(xué)動(dòng)力系統(tǒng)與最優(yōu)控制熱動(dòng)力學(xué)算法框架自由能極小與熱力學(xué)替換規(guī)則與粒子群算法的融合總結(jié)與展望第二頁，共二十九頁，編輯于2023年，星期三群智能算法研究的關(guān)鍵問題回顧——早期遺傳算法以及相關(guān)演化算法優(yōu)點(diǎn)：自組織、自適應(yīng)、普適性理論：隱含并行、基因塊（建筑塊）假設(shè)、依概率收斂—基于SGA的論證缺點(diǎn)：過早收斂、適應(yīng)值平臺(tái)、欺騙性問題癥結(jié)：選擇壓力與種群多樣性的關(guān)系解決方法：從線性選擇策略到非線性選擇策略適應(yīng)值變換、錦標(biāo)賽競(jìng)爭(zhēng)選擇、Boltzmann競(jìng)爭(zhēng)選擇、μ+λ選擇減緩選擇壓力，保持種群多樣性第三頁，共二十九頁，編輯于2023年，星期三現(xiàn)代——啟發(fā)式群智能算法：粒子群優(yōu)化、差分進(jìn)化、分布估計(jì)算法優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單、普適性強(qiáng)、快速收斂、精度高理論：動(dòng)力學(xué)分析方法缺點(diǎn)：過早收斂、局部搜索癥結(jié)：種群多樣性與局部搜索、廣域探測(cè)與局部開采解決方法：2E（Exploration&Exploitation)權(quán)衡

增強(qiáng)搜索潛力，保持種群多樣性第四頁，共二十九頁，編輯于2023年，星期三熱力學(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)：與世隔絕開放系統(tǒng)：充分交換第五頁，共二十九頁，編輯于2023年，星期三基本定律熱力學(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)生其它影響不可逆性，能量的耗散特性第六頁，共二十九頁，編輯于2023年，星期三熵與平衡態(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)和開放系統(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最多，熵最大第七頁，共二十九頁，編輯于2023年，星期三熵與序孤立系統(tǒng)的自發(fā)過程是熵增加的過程，最終發(fā)展到一個(gè)宏觀靜止的平衡態(tài)，熵達(dá)到最大值平衡態(tài)是一個(gè)最無序的狀態(tài)系統(tǒng)的熵值反映系統(tǒng)的有序程度，系統(tǒng)的熵值越小，它越是有序，呈現(xiàn)某種結(jié)構(gòu)；系統(tǒng)的熵值越大，它越是無序，難以發(fā)現(xiàn)其結(jié)構(gòu)系統(tǒng)總是力圖自發(fā)地從熵值較小的狀態(tài)向熵值較大（即從有序走向無序）的狀態(tài)轉(zhuǎn)變，即孤立系統(tǒng)的“熵值增大原理”第八頁，共二十九頁，編輯于2023年，星期三信息熵自信息描述了事件集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í)所給出的平均信息量第九頁，共二十九頁，編輯于2023年，星期三自由能極小定律等溫下的封閉熱力學(xué)系統(tǒng)遵循自由能極小定律對(duì)于與周圍環(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)的過程,都是能量與熵兩者競(jìng)爭(zhēng)的結(jié)果而溫度則決定著競(jìng)爭(zhēng)過程中能量與熵的相對(duì)權(quán)重：高溫時(shí)熵占統(tǒng)治地位；低溫時(shí)能量占統(tǒng)治地位能量溫度熵第十頁，共二十九頁，編輯于2023年，星期三熱力學(xué)系統(tǒng)與群智能算法熱力學(xué)系統(tǒng)算法若干粒子組成熱力學(xué)系統(tǒng)若干個(gè)體組成進(jìn)化種群系統(tǒng)的能量種群的負(fù)平均適應(yīng)值，與開發(fā)能力相關(guān)系統(tǒng)的熱力學(xué)熵種群的多樣性，與探索能力相關(guān)系統(tǒng)的溫度權(quán)重控制參數(shù)T能量和熵的競(jìng)爭(zhēng)“開發(fā)能力”與“探索能力”的適當(dāng)平衡恒定溫度下系統(tǒng)朝著自由能減少的方向自發(fā)變化給定權(quán)重T下驅(qū)動(dòng)種群向自由能減少的方向演化“徐徐”降溫給定權(quán)重T下種群充分演化后緩慢衰減T值第十一頁，共二十九頁，編輯于2023年，星期三動(dòng)力系統(tǒng)與最優(yōu)控制第十二頁，共二十九頁，編輯于2023年，星期三TDEA通過模擬自由能極小定律實(shí)現(xiàn)種群中能量和熵之間的競(jìng)爭(zhēng)機(jī)制，從而達(dá)到定量協(xié)調(diào)算法探索能力和開發(fā)能力之間的均衡，隨T遞減緩慢降低自由能從N個(gè)父?jìng)€(gè)體和M個(gè)子個(gè)體中挑選出N個(gè)個(gè)體組成下一代種群,使其具有的自由能最小熱動(dòng)力學(xué)算法框架第十三頁，共二十九頁，編輯于2023年，星期三兩個(gè)最關(guān)鍵問題如何定義熵——度量種群多樣性基因熵（Mori,1995）網(wǎng)格熵（胡婷,2005）等級(jí)熵（應(yīng)偉勤，2007）如何設(shè)計(jì)熱力學(xué)替換規(guī)則——種群自由能下降貪婪熱力學(xué)替換規(guī)則（Mori,1995）分量熱力學(xué)替換規(guī)則（應(yīng)偉勤，2007）第十四頁，共二十九頁，編輯于2023年，星期三種群的基因熵Mori在實(shí)現(xiàn)TDGA時(shí)采用基因熵來度量種群的基因多樣性，基因熵等于種群每個(gè)基因座上的信息熵的合計(jì)值優(yōu)點(diǎn)：很直觀，易于實(shí)現(xiàn)缺點(diǎn)：只適用于離散編碼；在個(gè)體編碼較長(zhǎng)時(shí)計(jì)算開銷極大，這將會(huì)降低TDGA的計(jì)算效率…

…0…

…1…

…0…12…j…LX1X2XN第十五頁，共二十九頁，編輯于2023年，星期三種群的網(wǎng)格熵由于基因熵?zé)o法應(yīng)用于實(shí)數(shù)編碼，胡婷提出了一種網(wǎng)格熵，將定義域劃分為若干網(wǎng)格，計(jì)算個(gè)體在網(wǎng)格中分布的信息熵x1x2G1G2GM………第十六頁，共二十九頁，編輯于2023年，星期三種群的等級(jí)熵活躍窗口wt

：記錄了到第t代為止搜索過程已達(dá)個(gè)體的適應(yīng)度范圍在對(duì)活躍窗口劃分等級(jí)時(shí),遵循了適應(yīng)值區(qū)域越優(yōu)分級(jí)越精細(xì)的原則…0………1……0…編碼空間目標(biāo)空間活躍窗口f(.)等級(jí)劃分示意圖第十七頁，共二十九頁，編輯于2023年，星期三等級(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ì)算成本較低第十八頁，共二十九頁，編輯于2023年，星期三熱力學(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è)體生成下一代種群,使其具有的自由能最小第十九頁，共二十九頁，編輯于2023年，星期三窮舉熱力學(xué)替換規(guī)則精確地最小化所有可能的下一代種群的自由能本身是一個(gè)頗難的組合優(yōu)化問題窮舉熱力學(xué)替換規(guī)則：使用窮舉法計(jì)算所有可能組合成的臨時(shí)種群的自由能，最小的那個(gè)種群即為下一代窮舉熱力學(xué)替換規(guī)則的復(fù)雜度為O(LNCNN+M),因此Mori指出窮舉熱力學(xué)替換規(guī)則在實(shí)際應(yīng)用中是不可行的第二十頁，共二十九頁，編輯于2023年，星期三貪婪熱力學(xué)替換規(guī)則Mori在實(shí)現(xiàn)TDGA時(shí)采用了貪婪熱力學(xué)替換規(guī)則，按照貪婪的策略逐個(gè)往下一代種群中填充使臨時(shí)種群自由能最小的個(gè)體復(fù)雜度：O(LN(N+M))貪婪熱力學(xué)替換規(guī)則的計(jì)算開銷較窮舉熱力學(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;}第二十一頁，共二十九頁，編輯于2023年，星期三分量熱力學(xué)替換規(guī)則-自由能分量貪婪替換規(guī)則計(jì)算開銷較大的主要原因在于自由能是相對(duì)于種群而言的，須首先通過嘗試填充獲得臨時(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ù)第二十二頁，共二十九頁，編輯于2023年，星期三分量熱力學(xué)替換規(guī)則基于自由能分量的分量熱力學(xué)替換規(guī)則，計(jì)算量少驅(qū)動(dòng)種群自由能下降快速復(fù)雜度：O(M(N+M))，有效降低了替換規(guī)則的時(shí)間復(fù)雜度第二十三頁，共二十九頁，編輯于2023年，星期三分量熱力學(xué)替換規(guī)則(CTR)的性質(zhì)在兩個(gè)引理的基礎(chǔ)上，運(yùn)用極限夾逼準(zhǔn)則可從理論上完整地證明CTR規(guī)則除了具有較低時(shí)間復(fù)雜度之外，還具有驅(qū)動(dòng)種群自由能近似最速下降的良好性質(zhì)(極限夾逼準(zhǔn)則，數(shù)學(xué)歸納法，自然對(duì)數(shù)性質(zhì)ln(x)<=x-1)第二十四頁，共二十九頁，編輯于2023年，星期三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.Bei