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

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

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

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 年對鳥群覓食行為的研究所提出的，主要是在深入研究其集群活動(dòng)的規(guī)律性啟發(fā)后所建立的一個(gè)群體智能模型。與其他進(jìn)化算法相比，PSO主要是通過粒子間的協(xié)作和競爭，在充分保證群體中的個(gè)體對信息進(jìn)行共享的同時(shí)，可使得整個(gè)群體在問題求解空間中進(jìn)行從無序到有序的運(yùn)動(dòng)演化過程，從而搜索到最優(yōu)解。

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

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

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

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

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

⑴

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(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.