動態環境下基于近似動態規劃的分布估計算法研究

孫思雨　孫良旭　蘇曉磊　趙環宇

摘要：論文重點討論了分布估計算法的理論研究。首先，抽取出分布估計算法的核心思想，然后旨在使用EDA算法解決復雜優化問題，提出基于近似動態規劃的分布估計算法。通過Agent與環境的交互，將近似動態規劃引入到進化計算中，獲得概率模型并進行適應性的更新。測試函數使用六個經典的對比實驗，結果表明本算法的魯棒性，運行時間短并具有較強的全局搜索能力，可以作為解決函數優化問題的有效解決算法。

關鍵詞：分布估計算法；近似動態規劃；進化搜索

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2014）30-7173-04

1 分布估計算法

為克服遺傳算法由于染色體重新排列導致的鏈式問題，分布估計算法（estimation of Distribution Algorithm， EDA）不使用交叉和變異操作，而是通過從發現的信息來優化解集，并使用這些信息生成新的概率分布模型和解。概率模型使用全新的進化計算的思路，成為EDA算法的理論基礎。EDA算法[1]的概念最初在1996年提出并得到了快速發展，近年來成為智能進化領域的研究熱點。EDA算法[2-4]提出了一種全新的進化模式，通過概率模型描述候選解的空間分布，并利用概率模型隨機采樣生產新種群，實現種群的進化過程。避免盲目地重組和混合染色體的基因，能有效的增強搜索效率，快速生成高可靠性的解，這是傳統的遺傳算法無法解決的問題。

2 基于近似動態規劃的EDA算法

2.1 問題描述

分析發現現存的分布估計算法沒有較好的執行效果大多是因為概率向量通常都采用一種固定的策略來進行更新，這種方式不僅無法保證整個進化過程的策略的有效性，同時沒有考慮到進化基因位的差異。……