熱動力學(xué)演化算法TDEA及其進展-PPT課件

1、熱動力學(xué)演化算法及其進展,李元香,內(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)值變換、錦標賽競爭選擇、Boltzmann競爭選擇、+選擇 減緩選擇壓力，保持種群多樣性,現(xiàn)代啟發(fā)式群智能算法：粒子群優(yōu)化、差分進化、分布

2、估計算法 優(yōu)點：實現(xiàn)簡單、普適性強、快速收斂、精度高 理論：動力學(xué)分析方法 缺點：過早收斂、局部搜索 癥結(jié)：種群多樣性與局部搜索、廣域探測與局部開采 解決方法：2E（Exploration for(i=1;i=N;i+) /采用貪婪策略逐次往Pt1中填充N個個體 for(j=1;j=N+M-i;j+) /在多次嘗試后找到本輪最好填充個體 計算若將Pt1的第j個個體填充到Pt1后的自由能F(Tt ,Pt1Pt1j),并記 錄下本輪嘗試填充中使自由能最小的個體Xjmin; 將個體Xjmin填充到Pt1中,并將其從中間種群Pt1中清除出去; 返回下一代種群Pt1; ,分量熱力學(xué)替換規(guī)則-自由能分量,

3、貪婪替換規(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ù)雜度,分量熱力學(xué)替換規(guī)則(CTR)的性質(zhì),在兩

4、個引理的基礎(chǔ)上，運用極限夾逼準則可從理論上完整地證明CTR規(guī)則除了具有較低時間復(fù)雜度之外，還具有驅(qū)動種群自由能近似最速下降的良好性質(zhì)(極限夾逼準則，數(shù)學(xué)歸納法，自然對數(shù)性質(zhì)ln(x)=x-1),TDEA相關(guān)論文,Mori N, Yoshida J, Tamaki H, Kita H, Nishikawa Y. A thermodynamical selection rule for the genetic algorithm. In: Fogel DB, ed.Proc. of the IEEE Conf. on Evolutionary Computation. New York: IEEE

5、 Press, 1995. 188192. Mori N, Kita H, Nishikawa Y. Adaptation to a changing environment by means of the feedback thermodynamical genetic algorithm. In: Eiben AE, et al., eds. Proc. of the IEEE Conf. on Parallel Problem Solving from Nature. Berlin: Springer-Verlag, 1998.149158. 應(yīng)偉勤, 李元香, 許承瑜. 熱力學(xué)遺傳算法

6、計算效率的改進. 軟件學(xué)報, 2008, 19(7):1613-1622 Weiqin Ying, Yuanxiang Li, Shujuan Peng, Weiwu Wang. A Steep Thermodynamical Selection Rule for Evolutionary Algorithms. Proc. of Int. Conf. on Computational Science. Beijing, China, 2007: 997-1004,與粒子群算法的融合,根據(jù)粒子的自由能分量決定下一代種群 耗散粒子群優(yōu)化算法：引入負熵 自組織臨界粒子群優(yōu)化算法：引入臨界值屬性 引入分子熱運動中分子力、布朗運動和擴散現(xiàn)象 分別從三個不同層面模擬熱力學(xué)機制改進粒子群優(yōu)化算法,TD-PSO算法,按PSO算法中的位置更新公式隨機選擇M個粒子生成子種群,1.合并父、子種群 2.在新種群中計算M個父粒子和子粒子的自由能分量 3.保留父、子粒子中自由能分量較小者,分子力、布朗運動、擴散,微觀,介觀,宏觀,模擬的角度,熱運動機制,斥力引力,布朗運動,擴散現(xiàn)象,總結(jié)與展望,熱力學(xué)與統(tǒng)計力學(xué)的顯著特點是普適性，在少數(shù)幾個一般原理和假設(shè)的基礎(chǔ)上，其結(jié)論可應(yīng)用于完全不同的物質(zhì)組成的系統(tǒng)，甚至社會科學(xué)和宇宙學(xué)。因此，在算法