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

1、熱動(dòng)力學(xué)演化算法及其進(jìn)展,李元香,內(nèi)容提要,群智能算法研究的關(guān)鍵問題 熱力學(xué)與統(tǒng)計(jì)力學(xué) 動(dòng)力系統(tǒng)與最優(yōu)控制 熱動(dòng)力學(xué)算法框架 自由能極小與熱力學(xué)替換規(guī)則 與粒子群算法的融合 總結(jié)與展望,群智能算法研究的關(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)選擇、+選擇 減緩選擇壓力，保持種群多樣性,現(xiàn)代啟發(fā)式群智能算法：粒子群優(yōu)化、差分進(jìn)化、分布

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

3、貪婪替換規(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ù),分量熱力學(xué)替換規(guī)則,基于自由能分量的分量熱力學(xué)替換規(guī)則，計(jì)算量少驅(qū)動(dòng)種群自由能下降快速 復(fù)雜度：O(M(N+M)，有效降低了替換規(guī)則的時(shí)間復(fù)雜度,分量熱力學(xué)替換規(guī)則(CTR)的性質(zhì),在兩

4、個(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),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、計(jì)算效率的改進(jìn). 軟件學(xué)報(bào), 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)化算法：引入負(fù)熵 自組織臨界粒子群優(yōu)化算法：引入臨界值屬性 引入分子熱運(yùn)動(dòng)中分子力、布朗運(yùn)動(dòng)和擴(kuò)散現(xiàn)象 分別從三個(gè)不同層面模擬熱力學(xué)機(jī)制改進(jìn)粒子群優(yōu)化算法,TD-PSO算法,按PSO算法中的位置更新公式隨機(jī)選擇M個(gè)粒子生成子種群,1.合并父、子種群 2.在新種群中計(jì)算M個(gè)父粒子和子粒子的自由能分量 3.保留父、子粒子中自由能分量較小者,分子力、布朗運(yùn)動(dòng)、擴(kuò)散,微觀,介觀,宏觀,模擬的角度,熱運(yùn)動(dòng)機(jī)制,斥力引力,布朗運(yùn)動(dòng),擴(kuò)散現(xiàn)象,總結(jié)與展望,熱力學(xué)與統(tǒng)計(jì)力學(xué)的顯著特點(diǎn)是普適性，在少數(shù)幾個(gè)一般原理和假設(shè)的基礎(chǔ)上，其結(jié)論可應(yīng)用于完全不同的物質(zhì)組成的系統(tǒng)，甚至社會(huì)科學(xué)和宇宙學(xué)。因此，在算法