分布估計算法

分布估計算法 (EDA) 是一種新興的基於統計學原理的隨機最佳化算法. EDA與遺傳算法(GA)有著明顯的區別. GA 採用交叉和變異等操作產生新個體, EDA 則通過對搜尋空間採樣和統計學習來預測搜尋的最佳區域, 進而產生優秀的新個體. 相比於 GA 基於基因的微觀層面的進化方式, EDA採用基於搜尋空間的巨觀層面的進化方法, 具備更強的全局搜尋能力和更快的收斂速度.

基本介紹

• 中文名：分布估計算法 
• 外文名：EDA

標準 EDA 及其流程

分布估計算法是一種基於統計學習理論的群體進化算法, 通過建立機率模型描述候選解在搜尋空間的分布信息, 採用統計學習手段從群體巨觀的角度建立一個描述解分布的機率模型, 然後對機率模型隨機採樣產生新的種群, 如此反覆實現種群的進化. 標準 EDA 的算法流程如下:

Step 1: 初始化種群;


Step 2: 選擇優勢群體;


Step 3: 構建機率模型;


Step 4: 隨機採樣;


Step 5: 生成新群體;


Step 6: 判斷終止條件是否滿足, 若是, 則輸出最佳化結果; 否則, 轉Step 2.


機率模型是EDA的核心, EDA通過機率模型及其更新來描述解空間分布以及種群整體進化趨勢. 按機率模型的結構及變數間的相互關係, 可分為變數無關、雙變數相關和多變數相關 EDA. PBIL(population based incremental learning)與 UMDA (univariate marginal distribution algorithm)以及 cGA (compact GA)等算法屬於變數無關 EDA. 雙變數相關 EDA 的典型代表有 MIMIC (mutual information maximiza- tion for input clustering), COMIT (combining optimiz- ers with mutual information trees), BMDA (bivariate marginal distribution algorithm)等算法. 多變數相關EDA的代表性算法有FDA (factorized tion algorithms), ECGA (extended compact distribu- GA), BOA (Bayesian optimization algorithm).

另外, 按編碼方式的不同, EDA 可分為離散 EDA 和連續 EDA. 離散 EDA 採用二進制編碼或整數編 碼, 在離散空間內搜尋問題的最優解; 連續 EDA 采 用連續的實數編碼, 求解連續域的最佳化問題. 最初 的 EDA 是基於二進制編碼的離散算法, 後來發展了 連續編碼和非二進制離散編碼的算法.

顯然, 針對不同類型的最佳化問題需要設計不同的 機率模型來描述解空間的分布. 一個合適的機率模型可以很好地描述變數之間的相互關係, 因此, EDA 在解決非線性和變數耦合的最佳化問題時能夠利用問題的結構信息, 產生更好的個體. 同時, 與其他進化算法相比, EDA 基於群體的巨觀進化方式使其可以利用解空間的全局信息和進化過程中的歷史信息, 具有更強的全局搜尋能力和更快的收斂速度. 另外, EDA 算法簡單、易於實現, 尤其是 EDA 對解空間的分布進行估計並採樣產生新個體的方法, 更容易使其作為一種手段和框架與其他算法混合, 增強尋優性能.

EDA 的改進研究

近年來, 分布估計算法的改進研究主要體現在改進機率模型、保持種群多樣性及設計混合算法等方面. 下面分別給予綜述介紹.


改進機率模型

對 EDA 機率模型改進的研究, 主要是針對連續 EDA. 連續 EDA 普遍採用高斯機率模型, 假設變數服從高斯分布. Dong 等提出了一種基於特徵分解的 EDA, 將多變數高斯模型中的協方差矩陣進行特徵分解進而調整其特徵值; 同時提出了調整特徵值的3種策略, 並基於高斯模型的極大似然估計研究了不同的特徵值調整策略對種群進化的影響; 最後指出這種改進算法可以在較小的種群規模中保證算法的搜尋效率. Ding 等提出了一種基於直方圖的EDA, 算法選取種群中的優勢群體構建機率模型, 在進化過程中通過環境效應逐漸減小優勢群體的規模, 並通過收縮策略保證最後解的精確性.

針對連續EDA易早熟收斂的缺點, Zhong等提出了一種多機率模型的 EDA. 種群由2個子種群組成, 子種群1採用直方圖模型進行粗略的全局搜尋, 子種群 2 採用高斯機率模型進行精確的細搜尋. 在進化過程中, 算法周期性地對 2 個子種群中的優勢個體進行遷徙操作, 並根據搜尋情況自適應地調整子種群的規模以提高搜尋效率. Zhang 等提出了一種基於序貫重點採樣粒子濾波的 EDA, 採用帶權粒子描述優勢群體的機率分布, 進而採樣得到下一代種群. 該算法採用的機率模型是多峰模型而不是簡單的單峰模型, 而且並不需要假設機率模型服從高斯分布. Luo 等提出了兩步訓練法改進了基於規則模型的多目標 EDA, 依次採用均值分簇法和流形分簇法進行聚類, 縮短了 EDA 的尋優時間.

對於離散EDA的機率模型改進的研究, Santana 等提出了一種近鄰傳播 EDA, 採用近鄰傳播 (AP) 算法, 基於優勢群體的互動信息矩陣進行聚類, 從而完成邊緣機率分布模型的學習和更新. 針對二進制編碼問題, Peng 等引入基於環境識別的記憶管理機制, 動態存儲或提取機率模型, 求解了動態最佳化問題, 並指出這種記憶管理機制可以在任何二進制編碼的 EDA 中使用. 另外, Li 等提出了一種子空間 EDA, 即在對機率模型採樣產生新個體時, 保留種群中優質個體的部分原有變數, 只選取另一部分變數重新採樣並更新變數值, 同時提出了3種選取變數的方式, 並比較了 3 種方式對於算法性能的影響.

種群多樣性的保持

EDA 在進化過程中對機率模型學習時, 容易對問題解空間的分布過擬合, 導致算法構建的機率模型不能準確地表達解空間的信息, 在算法若干次疊代後種群多樣性減小, 進而造成算法早熟收斂. 因此, 保持 EDA 進化過程中種群的多樣性很重要.

變異操作的本質是在算法中加入隨機因素, 這也是 GA 中保持種群多樣性的主要手段. 同樣, 在 EDA 中引入變異操作, 以一定的機率對種群中的個體或機率模型進行變異, 同樣可以改進算法的尋優能力. Cheng 等提出了一種多樣性保持的 EDA, 根據混沌運動具有的隨機性、遍歷性、初值敏感性和規律性等特點引入了混沌變異運算元, 並根據個體適應度值和種群中個體之間的距離信息自適應調整變異程度, 有效地防止了算法早熟收斂, 並提高了解的精度. 另外, EDA 是在進化一定階段之後開始失去種群多樣性的, 因此為了不影響算法的收斂速度, 可以根據算法的疊代次數有針對性地設定種群多樣性的補償程度.

Chen 等採用這種思路, 提出了一種自適應的 EDA, 解決了單機調度問題, 並指出改進機率模型的採樣方法也是保持種群多樣性的一個可行機制.

與隨機性較強的變異操作不同, delaOssa 等利用算法進化過程中獲得的其他信息構建機率模型, 進而採樣產生一部分與種群中多數個體不同的個體, 達到了增加種群多樣性的目的, 避免算法早熟收斂.

基於 EDA 的混合算法

EDA 基於機率模型的構建和採樣過程形成了一種有效的並行搜尋框架, 基於此框架很容易結合其他 方法來構造混合算法. 近幾年混合EDA算法的研究 主要集中在以下兩方面.

1) 混合其他群智慧型算法. Zhou 等將 EDA 的思想與粒子群最佳化 (PSO) 算法相結合, 使種群中的每個粒子都具有一定的自學習能力; Wang等將細菌覓食的趨化運動引入 EDA, 提高了算法的尋優能力和收斂速度; Liu等則提出了PSO-EDA算法求解置換流水線調度問題.

2) 混合其他方法. Miquelez 等將貝葉斯分類方法與 EDA 相融合, 取代機率模型中的貝葉斯網路和高斯網路, 解決了連續最佳化問題; Huang 等和 Wu 等分別在 EDA 中加入基於模擬退火算法的局部搜尋機制,以增強算法的尋優能力,避免早熟收斂. Tan 等將量子進化的思想與 EDA 相結合, 採用多量子機率模型的學習方法, 儘可能全面地描述解空間中較好的區域.

上述改進策略一方面利用了 EDA 全局搜尋能力強的優勢,另一方面通過改進機率模型、補償種群多樣性或混合其他方法等操作彌補 EDA 局部搜尋能力較弱和易早熟收斂的缺點, 算法性能測試和套用探討研究均驗證了改進策略的有效性.

EDA 理論研究

相對於算法的改進研究, 近幾年有關 EDA 的理論研究成果相對較少, 有待重點研究和發展.
Chen 等對 UMDA 的平均時間複雜度進行了分析. Wu等分析了種群規模有限的情況下EDA 的收斂性,證明了在採用比例選擇、截斷選擇和錦標賽選擇方式確定優勢種群時, 只要新一代種群的機率分布與優勢群體的機率分布的誤差在一定範圍內, EDA 便能收斂到全局最優, 並分別給出了 3 種選擇方式下允許的誤差範圍. Yu 等指出, 基於最大熵理論的 EDA 中為準確構建機率模型而需要的種群規模 為Θ (𝑚log𝑚),其中𝑚為待求解問題包含的子結構 的數量,與問題的規模有關. Ding等從貝葉斯分析的角度研究了基於多項式分布的 EDA, 並提出了 3 種實現策略, 通過引入先驗機率分布來改進算法的收斂性和種群的多樣性. Brownlee 等研究了選擇操作 對 EDA 性能的影響, 指出選擇種群中不同部分的個體構建機率模型都可以得到較好的結果; 同時, 在機率模型相對簡單的情況下, 恰當設計選擇操作可以有效地提高算法的性能.

另外, Bosman等研究了如何將離散EDA連續化, 並用於求解若干連續最佳化問題; Rastegar分析了 cGA 和 PBIL 兩種算法的最優收斂機率, 給出了算 法收斂到最優解的充分條件.

典型套用

鑒於EDA的優越性, EDA目前已在多個領域得到套用, 一些代表性套用研究如下:


1) 多目標最佳化問題. 除 Luo 等提出的採用兩步訓練法的多目標EDA外, Zhang等設計了一種基於規則模型的多目標EDA; Zhong等採用基於貝葉斯網路的機率模型, 結合非劣解分層和截斷選擇機制, 設計了有效的多目標 EDA, 並用於機翼結構最佳化設計; Zhou 等利用 EDA 在決策空間和目標空間逼近 Pareto 最優解集; Zhong 等提出了一種多機率模型 EDA, 在進化的每一代中使用多個機率模型引導算法搜尋並保持最優解集的多樣性; Marti 等指出, 對進化中產生的異常個體處理不當、種群多樣性缺失及建模運算量過大, 是影響多目標 EDA 性能的主要原因, 並由此提出了一種 MB-GNG 網路改進算法性能.

2) 調度問題. Aickelin 等針對護理調度問題設計了一種 EDA, 隨後又對算法進行了改進, 加入了智慧型的局部搜尋, 有效安排每名護士的護理計畫. 另外, 近幾年基於 EDA 的典型調度問題的研究也有很多成果, 如置換流水車間調度問題, 單機調度問題, 資源約束項目調度問題, 多模式資源約束項目調度問題, 作業車間調度問題, 柔性作業車間調度問題等.

3)生物信息學方面. Santana等套用EDA解決了蛋白質側鏈定位的問題和簡化模型中的蛋白質摺疊問題; Cano等結合EDA和主成分分析方法對基因表達的信息進行聚類分析; Armananzas等對 EDA 在生物信息學方面的套用給予了簡要綜述.

4) 其他工程套用問題. 如電磁裝置的設計, 高炮射擊體制設計, 故障綜合評判, 混沌系統控制, 路徑規劃, 物流配送中心選址, 預測控制, 多維背包問題求解, 表格排序等等. 另外, Santana 等還編寫了 Matlab 中的 EDA 工具包。