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

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

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

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

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

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

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

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

分布估計算法（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）是進化計算領(lǐng)域新近興起的一類隨機優(yōu)化算法，它將傳統(tǒng)的遺傳算法的思想和統(tǒng)計學(xué)的概率模型結(jié)合起來，形成一種全新的智能優(yōu)化計算模式。

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

直到1 9 9 6年,分布估計算法的概念才第一次提出。其中U M D A算法由德國學(xué)者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年提出的一種啟發(fā)式優(yōu)化算法，此算法是最先考慮兩個變量相關(guān)。而B O A算法是由美國U I U C大學(xué)的P e l i k a n等提出的，此算法主要研究多變量相關(guān)的問題。

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

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

（一）基本介紹

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

（二）F WH算法步驟：

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

S t e p 2構(gòu)造初始概率模型，現(xiàn)將變量的每一維進行等分，保證每個小區(qū)間初始概率相等。

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

S t e p 4計算候選解的適應(yīng)值，根據(jù)各點適應(yīng)值，選擇所要的優(yōu)勢候選解。

S t e p 5更新概率向量，根據(jù)優(yōu)勢候選解的變量所在區(qū)間，用更新公式更新每個小區(qū)間概率向量。

S t e p 6達到給定迭代次數(shù)，輸出結(jié)果。

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

（一）模式搜索法

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

圖1 模式搜索法示意圖

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

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

在H J-F WH算法中的概率閾值按以下方式更新：當(dāng)某一個小區(qū)間概率大于閾值時，對需要更新的變量區(qū)間的概率變?yōu)樵瓉淼?，其他的每個區(qū)間的概率加上這個區(qū)間概率的。即第i個小區(qū)間的概率Pi≥G，則將這個區(qū)間的概率變?yōu)椋渌麉^(qū)間的概率變成，（k=1，2…，i-1，i+1…，N）保證每一維小區(qū)間概率和為1。H J-F WH算法步驟：

S t e p 1初始化：對參數(shù)如候選解規(guī)模M、細分等分數(shù)N、優(yōu)秀候選解規(guī)模δ（δ＜M）、概率閾值G、學(xué)習(xí)概率α、迭代次數(shù)Gen等給定初值。

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

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

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

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

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

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

S t e p 8算法停止條件：當(dāng)算法進行了一定數(shù)量的迭代次數(shù)后，算法停止，并輸出結(jié)果。

三、數(shù)值實驗

（一）實驗對象及參數(shù)設(shè)置

選取三個連續(xù)優(yōu)化問題的經(jīng)典函數(shù)作為測試函數(shù)進行數(shù)值實驗，實驗中候選解規(guī)模M=1 0 0 0，優(yōu)秀候選解規(guī)模δ=1 5 0，區(qū)間細分等分數(shù) N=1 5 0，學(xué)習(xí)概率α=0.5，概率閾值 G=0.8，最大迭代次數(shù)Gen=2 0 0，初始步長γ=0.5，加速因子λ=1，縮減率β=0.5。

表1給出了三個函數(shù)的表達式、定義范圍及維數(shù)、最優(yōu)解和最優(yōu)值，表2列出了F WH算法與H J-F WH算法針對各函數(shù)的數(shù)值實驗比較結(jié)果。

表1 測試函數(shù)

表2 結(jié)果對比（2 0次實驗結(jié)果的平均水平）

圖2 F WH與H J-F WH對f1的收斂圖

圖3 F WH與H J-F WH對f3的收斂圖

圖4 F WH與H J-F WH對f3的收斂圖

通過上面的圖表可以明顯看出，改進后的H J-F WH算法的最優(yōu)解精度有大幅的提高，而且比起F WH算法逼近最優(yōu)解的收斂速度要快，改進效果比較明顯。

（二）參數(shù)調(diào)整

一般來說，參數(shù)的選取對算法的性能影響很大，下面對H J-F WH算法中的參數(shù)進行數(shù)值比較，這里采用控制變量法，即每次只改變一個變量。表3、表4、表5和表6分別只列出了在H J-F WH算法中解的取值區(qū)間細分等分數(shù)N、優(yōu)秀候選解規(guī)模、概率閾值G和允許誤差分別對算法獲得最優(yōu)值的影響。

表3 區(qū)間細分等分數(shù)N

表4 優(yōu)秀候選解規(guī)模δ

表5 概率閾值G

表6 允許誤差ε

對于H J-F WH算法，通過以上參數(shù)調(diào)整的實驗結(jié)果表明，只有允許誤差的影響對于解的精度影響較大，即ε越小解精度越高，而其他參數(shù)對于解的精度影響較小。而對于F WH算法區(qū)間細分等分數(shù)N、優(yōu)秀候選解規(guī)模δ、概率閾值G等參數(shù)對于解的精度相對來說影響較大，尤其是細分等分數(shù)N，這里不做詳述。

通過上述幾組數(shù)值實驗結(jié)果表明，改進后的H J-F WH算法比起改進前在解的精度和收斂速度方面有明顯提高，而且對于部分高維問題（低于1 0維）效果也有一定程度的提升。

四、結(jié)論

論文通過對于固定寬度的直方圖模型的分布估計算法加入概率閾值的要素，可以防止函數(shù)早熟，使用固定區(qū)間寬度提高算法的運行速度，在更新種群步驟中加入模式搜索法，可以有效地提高逼近解的精度。

針對更高維的問題如何找到一些好的改進方法以及如何進一步提高最優(yōu)值的精度，都需要繼續(xù)深入研究。

[1]周樹德,孫增圻.分布估計算法綜述[J].自動化學(xué)報,2007，（2）:113-121.

[2]陳寶林.最優(yōu)化理論與算法(第二版)[M].北京：清華大學(xué)出版社，2009:332-336.

[3]嚴宇平.運用改進直方圖模型的分布估計算法求解連續(xù)空間優(yōu)化問題[D].中山大學(xué)碩士學(xué)位論文，2010.

[4]張慶彬，吳惕華，劉波.自適應(yīng)實值分布估計算法[J].清華大學(xué)學(xué)報（自然科學(xué)版），2008，(S2):1859-1862.

[5]熊盛武，劉麟，汪洋等.基于貝葉斯網(wǎng)絡(luò)的并行分布估計算法研究[D].武漢理工大學(xué)碩士學(xué)位論文，2005.

O

A

1 6 7 3-0 0 4 6（2 0 1 2）8-0 1 4 7-0 3