劉建軍，韓 帥，石定元，武國(guó)寧

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

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

劉建軍，韓 帥，石定元，武國(guó)寧

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

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

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

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

分布估計(jì)算法可以按照概率模型的復(fù)雜程度進(jìn)行分類(lèi)，包括變量無(wú)關(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等算法。美國(guó)卡耐基梅隆大學(xué)的B a l u j a在1 9 9 4年提出P B I L算法，是用來(lái)解決二進(jìn)制編碼的優(yōu)化問(wèn)題，雖然當(dāng)時(shí)還沒(méi)有提出分布估計(jì)算法的概念，但是P B I L算法被公認(rèn)為最早的分布估計(jì)算法模型。

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

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

一、基于直方圖的分布估計(jì)算法

（一）基本介紹

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

（二）F WH算法步驟：

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

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

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

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

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

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

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

（一）模式搜索法

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

圖1 模式搜索法示意圖

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

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

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

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

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

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

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

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

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

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

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

三、數(shù)值實(shí)驗(yàn)

（一）實(shí)驗(yàn)對(duì)象及參數(shù)設(shè)置

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

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

表1 測(cè)試函數(shù)

表2 結(jié)果對(duì)比（2 0次實(shí)驗(yàn)結(jié)果的平均水平）

圖2 F WH與H J-F WH對(duì)f1的收斂圖

圖3 F WH與H J-F WH對(duì)f3的收斂圖

圖4 F WH與H J-F WH對(duì)f3的收斂圖

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

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

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

表3 區(qū)間細(xì)分等分?jǐn)?shù)N

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

表5 概率閾值G

表6 允許誤差ε

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

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

四、結(jié)論

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

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

[1]周樹(shù)德,孫增圻.分布估計(jì)算法綜述[J].自動(dòng)化學(xué)報(bào),2007，（2）:113-121.

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

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

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

[5]熊盛武，劉麟，汪洋等.基于貝葉斯網(wǎng)絡(luò)的并行分布估計(jì)算法研究[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