一種混合粒子群算法的貝葉斯網(wǎng)絡優(yōu)化模型

摘 要： 傳統(tǒng)的粒子群優(yōu)化算法通過群體中粒子間的合作和競爭進行群體智能指導優(yōu)化搜索，算法收斂速度快，但較易陷入局部較優(yōu)值，進入早熟狀態(tài)。為了解決這個問題，提出了一種混合粒子群算法的貝葉斯網(wǎng)絡優(yōu)化模型，它可以通過當前所選擇的較優(yōu)解群構造一個貝葉斯網(wǎng)絡和聯(lián)合概率分布模型，利用這個模型進行采樣得到更優(yōu)解，用其可隨機替換掉PSO中的一些粒子或個體最優(yōu)解；同時利用粒子群算法對當前選擇出的較優(yōu)解群進行深度搜索，并將得到的最優(yōu)解融入到較優(yōu)解群中。分析可知，該方法可以提高算法有效性和可靠性。

關鍵詞： 粒子群優(yōu)化算法； 貝葉斯網(wǎng)絡； 較優(yōu)解群； 深度搜索

中圖分類號：TP393 文獻標志碼：A 文章編號：1006-8228（2014）09-31-02

A Bayesian network optimization model mixed particle swarm optimization algorithm

Chu Lingwei， Xu Yanwei

（Shanghai National Engineering Research Center for Broadband Networks Applications， Shanghai 200336， China）

Abstract： Traditional particle swarm optimization algorithms search through cooperation and competition among the particles in the swarm. It has a fast convergence rate， however， easy to fall into local optimal. In order to solve this problem， a Bayesian network optimization model based on mixed particle swarm optimization algorithm is proposed. It can use current optimal solutions that may come from PSO to construct a Bayesian network and joint probability distribution. It will use this distribution samples and get some better solutions， which will be integrated into Particle Swarm Optimization （PSO） algorithm to increase diversity.

Key words： particle swarm optimization algorithm； Bayesian network； better solution group； deep search

0 引言

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是一種有效的群體智能優(yōu)化算法[1]。它最核心的思想來源于Eberhart博士和kennedy博士在1995 年對鳥群覓食行為的研究所提出的，主要是在深入研究其集群活動的規(guī)律性啟發(fā)后所建立的一個群體智能模型。與其他進化算法相比，PSO主要是通過粒子間的協(xié)作和競爭，在充分保證群體中的個體對信息進行共享的同時，可使得整個群體在問題求解空間中進行從無序到有序的運動演化過程，從而搜索到最優(yōu)解。

PSO算法是一種基于迭代的優(yōu)化算法。它同時具有進化計算和群體智能算法的特點。基本流程如下述所：首先在初始時刻它生成一組隨機解，然后通過粒子在解空間中追隨它自己的個體最優(yōu)值（pbest）和種群的最優(yōu)值（gbest）進行搜索，最后逐步迭代搜尋到最優(yōu)值。PSO的優(yōu)勢主要集中在于其結構和規(guī)則簡單，易于實現(xiàn)，搜索速度快、效率高[2]。

但是，粒子群算法在實際使用中也面臨著一個嚴重的問題，即它容易發(fā)生早熟收斂（尤其是在處理復雜的多峰搜索問題時），局部尋優(yōu)能力較差，易陷入局部最優(yōu)。

為了解決這個問題，本文提出了一種混合粒子群算法的貝葉斯網(wǎng)絡優(yōu)化模型（A Bayesian network optimization model mixed particle swarm optimization algorithm， BNOM），它首先通過當前所選擇的較優(yōu)解群構造一個貝葉斯網(wǎng)絡和聯(lián)合概率分布模型，并利用這個模型進行采樣，進而得到更優(yōu)的解，相當于全局搜索；且同時利用粒子群算法對當前選擇出的較優(yōu)的解群進行深度搜索，并得到更優(yōu)的解，相當于局部搜索。本模型最大的特點是通過在貝葉斯網(wǎng)絡模型中引入粒子群算法，使得貝葉斯網(wǎng)絡既能充分利用已建立的貝葉斯網(wǎng)絡概率模型進行全局推理采樣的同時，還能利用粒子群算法對當前的局部較優(yōu)區(qū)域進行深度探索，通過分析可知，這個模型可以通過全局搜索和局部搜索提高算法的有效性和可靠性。

1 貝葉斯網(wǎng)絡模型

貝葉斯網(wǎng)絡是一種有向非循環(huán)網(wǎng)絡[3]，主要是由節(jié)點、有向弧線和條件概率分布表（CPT）所組成的[8]。CPT可以分解為隨機變量邊緣分布的乘積，即：

⑴

式⑴中，B表示一個貝葉斯網(wǎng)絡，x1，x2，…，x∞表示網(wǎng)絡中的結點，即問題隨機變量；A={x1，x2，…，x∞}表示問題的隨機變量集合，πi：i=1，2，…∞，表示貝葉斯網(wǎng)絡的某個隨機變量i對應的的父結點集。

本文采用貝葉斯信息準則（BIC）作為評分函數(shù)，它是最小描述長度原理（MDL：minimal description length）中的一類[4]。

2 粒子群優(yōu)化算法

粒子群優(yōu)化算法（Particle Swarm Optimization， PSO）中的一個粒子對應于解空間中的一個可行解，并由目標函數(shù)作為其適應度值來評價其優(yōu)劣程度。粒子在解空間中的運動方向和距離是由速度來決定的。具體可描述為：

假設粒子群算法當前搜索的是一個n維的問題空間，粒子的數(shù)量是N個。表示為：X={xi1，xi2，…，xN}，其中第i個粒子所處的位置為X={xi1，xi2，…，xiN}。粒子通過pbest和gbest不斷地更新調(diào)整自己的位置來搜索新的解位置。當前的粒子將把自己的最優(yōu)值pbest記錄下來，記為pid，且整個粒子群經(jīng)歷過的最好的位置gbest也將被記錄下來，記為pgd。下面將描述粒子的速度更新公式：

3 混合粒子群算法的貝葉斯網(wǎng)絡優(yōu)化模型

本文提出一種混合粒子群算法的貝葉斯網(wǎng)絡優(yōu)化模型，其可準確反映網(wǎng)絡參數(shù)間層次和粒度關聯(lián)關系，既能充分利用已建立的貝葉斯網(wǎng)絡概率模型進行全局推理采樣，又能在當前的較優(yōu)解群空間中利用粒子群算法進行深度的挖掘和搜索，具有很高的有效性和可靠性。

為實現(xiàn)上述目的，我們利用貝葉斯網(wǎng)絡在評估和推理方面的優(yōu)勢對當前的較優(yōu)解群進行建模，但是僅僅利用貝葉斯網(wǎng)絡自身的推理解，可能會過于局限和隨機。此時，為了增加較優(yōu)解的性能，考慮利用PSO算法也對當前的種群進行搜索，這樣就可以在一個局部的解空間中快速搜索到一些更優(yōu)的解，并將這些解融入到貝葉斯網(wǎng)絡需要建模的較優(yōu)解群中，可以增加較優(yōu)解群的質量。接下來，為了解決PSO算法易早熟，陷入局部最優(yōu)的缺點，利用貝葉斯網(wǎng)絡推理得到的較優(yōu)解隨機替換掉PSO種群中的一些粒子或粒子的個體最優(yōu)解（pbest）。這些新解的加入將大大增加PSO的多樣性。

簡單分析該模型的機理，即PSO把對當前較優(yōu)解群進行過深度挖掘的一些更優(yōu)解融合到較優(yōu)解群中，并由貝葉斯網(wǎng)絡對這個較優(yōu)解群進行建模，生成符合這個較優(yōu)解群的概率分布，然后貝葉斯網(wǎng)絡通過隨機采樣得到一些較優(yōu)的解，并將這些采樣得到的較優(yōu)解隨機隨機替換掉PSO中的一些粒子或粒子的個體最優(yōu)值（pbest）。在一定程度上增加了PSO的多樣性。

該模型包括貝葉斯網(wǎng)絡推理采樣和粒子群深度搜索兩個步驟。如圖1所示有一個貝葉斯網(wǎng)絡，變量x1條件依賴于變量x2，x3，x4。在本文中，假設貝葉斯網(wǎng)絡為（G，θ），其中G表示當前的貝葉斯網(wǎng)絡結構，θ表示該貝葉斯網(wǎng)絡的變量參數(shù)集，它們構成較優(yōu)解群D={D1，D2，…，DL}。它即包含當前較優(yōu)解群中解，還包括歷史中解群中的一些歷史較優(yōu)的解和PSO生成的較優(yōu)解。貝葉斯網(wǎng)絡概率推理模型將根據(jù)這個的數(shù)據(jù)集D構建，并利用構建好的貝葉斯網(wǎng)絡模型進行預測、推理、采樣。得到符合這個較優(yōu)解群分布的解。然后，粒子群算法被應用到當前得到的較優(yōu)解群中，發(fā)揮粒子群收斂速度快和群體尋優(yōu)的優(yōu)點，快速地收斂到當前較優(yōu)解群中的最優(yōu)解上。再通過兩者之間的交換各自的解，實現(xiàn)一定的信息互通。保證兩者相互之間互相協(xié)作的在解空間進行搜索。

⑴ 在時刻t=0，從所有可行解中根據(jù)均勻分布隨機生成初始的問題解種群P（0）；

⑵ 根據(jù)選擇策略從當前解群中選擇出適應值較優(yōu)的解群，并和一些歷史較優(yōu)解構建P（t），基于當前的較優(yōu)種群P（t）構造貝葉斯網(wǎng)絡B（t）；

⑶ 利用粒子群算法對當前的較優(yōu)解群進行深度搜索，并將PSO算法得到較優(yōu)的解融入P（t）；

⑷ 利用貝葉斯網(wǎng)絡B（t）進行推理和采樣，得到采樣較優(yōu)的解O（t）；

⑸ 隨機選擇O（t）中的一些較優(yōu)解并將其替換PSO中的一些粒子或粒子的個體最優(yōu)值；

⑹ 利用相關的替換策略（替換最差個體或全部替換），由新產(chǎn)生的候選解替換掉當前種群中的某些個體。

4 結束語

本文提出了一種混合粒子群算法的貝葉斯網(wǎng)絡優(yōu)化模型，也就是將粒子群算法的局部尋優(yōu)和貝葉斯網(wǎng)絡的全局尋優(yōu)結合起來，避免了粒子群算法容易造成的早熟狀態(tài)和貝葉斯網(wǎng)絡模型模型推理不夠準確導致的全局盲目搜索問題。同時，還能利用PSO所搜索的較優(yōu)解對某些較優(yōu)的區(qū)域進行深度探索。分析可得，這種優(yōu)化模型能夠表現(xiàn)出很高的有效性和可靠性。后期的工作將在一些實際的問題中對其進行深入的驗證和改進。

參考文獻：

[1] J. Kennedy and R. C. Eberhart， \"Particle swarm optimization，\" in

Proceedings of IEEE international conference on neural networks， Piscataway，1995.

[2] Y. S. G. M. Haibin Duan， Qinan Luo， \"Hybrid particle swarm

optimization and genetic algorithm for multi-uav formation reconfiguration，\" in IEEE Computational Intelligence Magazine，2013.

[3] Amelia W. Azman， Abbas Bigdeli， Yasir Mohd-Mustafah， Morteza

Biglari-Abhari and Brian C. A Bayesian network-based framework with Constraint Satisfaction Problem （CSP） formulations for FPGA system design[J]. Lovell. ASAP 2010.

[4] Shulin Yang and Kuo-Chu Chang， Comparison of Score Metrics

for Bayesian Network Learning[J]. IEEE Transactions On SMC-Part A. 2002.