基于固定寬度直方圖的分布估計算法的一種改進

2012-08-31 09:15:44劉建軍石定元武國寧

太原城市職業技術學院學報 2012年8期

劉建軍，韓帥，石定元，武國寧

（中國石油大學理學院，北京 1 0 2 2 4 9）

劉建軍，韓帥，石定元，武國寧

（中國石油大學理學院，北京 1 0 2 2 4 9）

基于固定寬度直方圖分布的分布估計算法（F WH），提出一個改進方案，即在F WH算法中加入概率閾值的要素，不使用改變區間長度的更新方式，保證區間個數不增加，并在更新候選解步驟中加入模式搜索法（H o o k e-J e e v e s方法），構造出一種改進的優化算法（H J-F WH）。數值實驗結果表明，改進后的算法在最優解精度和收斂速度方面均有了較大的提高。

分布估計算法；模式搜索法；直方圖；概率模型

分布估計算法（E D A s:E s t i m a t i o n o f D i s t r i b u t i o n A lg o r i t h m s）是進化計算領域新近興起的一類隨機優化算法，它將傳統的遺傳算法的思想和統計學的概率模型結合起來，形成一種全新的智能優化計算模式。

分布估計算法可以按照概率模型的復雜程度進行分類，包括變量無關的P B I L、U M D A和c G A算法；雙變量相關的M I M I C、B M D A算法以及多變量相關的E CG A、F D A、B O A等算法。美國卡耐基梅隆大學的B a l u j a在1 9 9 4年提出P B I L算法，是用來解決二進制編碼的優化問題，雖然當時還沒有提出分布估計算法的概念，但是P B I L算法被公認為最早的分布估計算法模型。

直到1 9 9 6年,分布估計算法的概念才第一次提出。其中U M D A算法由德國學者M u h l e n b e i n于同年提出，它與其他算法不同在于其概率向量的更新方式。之后的M I M I C算法，是由美國M I T人工智能實驗室的D e B o n e t等人于1 9 9 7年提出的一種啟發式優化算法，此算法是最先考慮兩個變量相關。而B O A算法是由美國U I U C大學的P e l i k a n等提出的，此算法主要研究多變量相關的問題。

該文選取基于固定寬度的直方圖模型的分布估計算法（F WH算法）為基本方法，加入概率閾值的要素，防止函數早熟，同時考慮到算法效率，而不使用改變區間長度的更新方式，保證區間個數不增加，可以加快迭代速度，并在更新種群步驟中加入模式搜索法（H o o k e-J e e v e s方法），可以有效地提高逼近解的精度。

一、基于直方圖的分布估計算法

（一）基本介紹

基于直方圖的分布估計算法的模型一般分為兩種，一種是區間寬度固定的直方圖模型F WH(t h e f i x e d-w i d t h h i s t o g r a m)，另一種是區間高度固定的直方圖模型F H H(t h e f i x e d-h e i g h t h i s t o g r a m)。其中，F WH將變量的定義域劃分為寬度相同而高度不同的小塊區間，小塊的高度決定了該范圍取值的概率大小。而F H H則將變量的定義域劃分為寬度不同而高度相同的小塊區間，小塊的寬度代表了該小塊取值的概率大小。同基于高斯分布的分布估計算法相比較，F WH和F H H使用了更加簡單的均勻分布概率模型，而且通過控制每個小塊的寬度或高度，能夠有效地求得相對精度較高的結果。由于F WH和F H H都在優化連續問題時得到結果精度的大小，基本取決于在定義范圍內各維小區間劃分的個數，所以，既要保證小區間分得要細，算法迭代速度也不能太慢。該文考慮變區間算法的計算復雜性較高，故選取F WH算法作為基本算法來改進。

（二）F WH算法步驟：

S t e p 1初始化候選解，給定初始參數。

S t e p 2構造初始概率模型，現將變量的每一維進行等分，保證每個小區間初始概率相等。

S t e p 3通過隨機方式構造初始候選解，保證各點均勻分布在各個小區間上。

S t e p 4計算候選解的適應值，根據各點適應值，選擇所要的優勢候選解。

S t e p 5更新概率向量，根據優勢候選解的變量所在區間，用更新公式更新每個小區間概率向量。

S t e p 6達到給定迭代次數，輸出結果。

二、基于模式搜索法的固定寬度的直方圖分布估計算法（H J-F WH）

（一）模式搜索法

模式搜索法的基本思想，從幾何意義上講，是尋找具有較小函數值的低谷，試圖通過迭代產生序列沿山谷向極小點逼近。算法首先從初始點開始進行兩種類型的移動，即探測移動和模式移動。探測移動是依次沿個坐標軸進行，用來確定新的基點和有利于函數值下降的方向。模式移動是沿相鄰兩個基點連線方向進行，試圖沿著山谷方向使函數值更快地減小。

圖1 模式搜索法示意圖

（二）結合模式搜索法的直方圖分布估計算法

在模式搜索法結合直方圖分布估計算法（H J-F WH）中，在更新種群步驟中應用模式搜索的思想，先對種群的每一維進行探測移動，完成后再進行模式移動，找到新的基點，若無效則退回原基點，按照初始步長γ及縮減率β更新步長，再從這個基點出發，依次沿各坐標軸方向進行探測移動。如此繼續下去，直到滿足精度要求，即步長δ小于事先給定的某個小的正數ε為止。

在H J-F WH算法中的概率閾值按以下方式更新：當某一個小區間概率大于閾值時，對需要更新的變量區間的概率變為原來的，其他的每個區間的概率加上這個區間概率的。即第i個小區間的概率Pi≥G，則將這個區間的概率變為，其他區間的概率變成，（k=1，2…，i-1，i+1…，N）保證每一維小區間概率和為1。H J-F WH算法步驟：

S t e p 1初始化：對參數如候選解規模M、細分等分數N、優秀候選解規模δ（δ＜M）、概率閾值G、學習概率α、迭代次數Gen等給定初值。

S t e p 2構造概率模型：需要先對變量的連續空間進行等分。例如某一維的變量的連續空間為[a，b]，如果進行N等分，則每一份區間的長度是。因為是進行N等分，所以開始這N個區間的取值概率都是相同的，也就是對于每個變量的連續空間，進行了N等分以后，每個小區間取值的概率都是。

S t e p 3構造新解：即對每個個體的每一維變量進行賦值。一般通過產生隨機數采用輪盤賭的方式確定每個變量的取值。

S t e p 4確定新的優秀候選解：計算候選解的適應值，根據其適應值，對候選解進行排序，選擇前δ個適應值較好的解作為優秀候選解δ（k）。

S t e p 5模式搜索法更新當前最優解：將這前δ個適應值較好的解中最好的一個解采用模式搜索算法，得到一個新的最優解，完成更新。

S t e p 6更新概率向量：對于變量某一維取值的連續空間，在它的N個劃分小區間里，統計含有優秀候選解的個數，設某個小區間中含有優秀候選解的個數為ni，更新前該小區間的概率為pi，則更新后的概率為。

S t e p 7判斷概率是否超過閾值：當某個小區間的概率大于G，則將區間概率進行重新更新，否則不需要更新。

S t e p 8算法停止條件：當算法進行了一定數量的迭代次數后，算法停止，并輸出結果。