基于量子遺傳算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)

摘要：將量子遺傳算法用于貝葉斯網(wǎng)絡(luò)(BN)的結(jié)構(gòu)學(xué)習(xí)，對(duì)BN結(jié)構(gòu)進(jìn)行量子編碼得到染色體，通過量子變異操作使其作為一個(gè)完備的獨(dú)立解空間進(jìn)行演化，可快速搜索到全局最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，量子遺傳算法用于BN結(jié)構(gòu)學(xué)習(xí)，可取得很好的效果。

關(guān)鍵詞：貝葉斯網(wǎng)絡(luò); 結(jié)構(gòu)學(xué)習(xí); 量子遺傳算法; 量子位

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)04－0996－03

0引言

在人工智能領(lǐng)域，不確定性知識(shí)的推理和決策一直是一個(gè)重要的研究問題。貝葉斯網(wǎng)絡(luò)正是對(duì)不確定性問題模擬和推理的一種有效工具[1]。它具有堅(jiān)實(shí)的理論基礎(chǔ)、語義清晰的網(wǎng)絡(luò)結(jié)構(gòu)、靈活的推理能力、方便的決策機(jī)制及有效的學(xué)習(xí)機(jī)制等特點(diǎn)。近年來已成為不確定性研究領(lǐng)域中的主流研究方向之一。為了充分發(fā)揮貝葉斯網(wǎng)絡(luò)的作用，人們對(duì)于其結(jié)構(gòu)學(xué)習(xí)提出了較高要求。已經(jīng)證明：完全的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)是NP難題[2]，網(wǎng)絡(luò)結(jié)構(gòu)模型空間的規(guī)模隨網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)的增加而呈指數(shù)增長(zhǎng)，所以需要尋求更好的結(jié)構(gòu)學(xué)習(xí)算法[3]。

量子世界的奇妙特性(如疊加性、相干性和糾纏性等)使得量子信息系統(tǒng)能突破經(jīng)典信息系統(tǒng)的極限。量子計(jì)算利用量子理論中有關(guān)量子態(tài)的疊加、糾纏和干涉等特性，相對(duì)于常規(guī)計(jì)算具有明顯的優(yōu)勢(shì)。應(yīng)用量子并行計(jì)算有可能解決一些經(jīng)典計(jì)算中的NP問題[4]。量子遺傳算法（quantum genetic algorithm，QGA）是新發(fā)展起來的一種基于量子計(jì)算原理的概率優(yōu)化方法。它以量子計(jì)算理論為基礎(chǔ)，用量子比特編碼表示染色體，通過量子門作用和量子門更新來完成進(jìn)化，具有種群規(guī)模小而不影響算法性能、染色體狀態(tài)豐富、收斂速度快和全局尋優(yōu)能力強(qiáng)等特點(diǎn)[5]。本文利用量子遺傳算法的這些特點(diǎn)，提出一種新的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的有效算法。

1貝葉斯網(wǎng)絡(luò)模型和結(jié)構(gòu)學(xué)習(xí)

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

貝葉斯網(wǎng)絡(luò)是根據(jù)各個(gè)變量之間的概率關(guān)系，使用圖論方法表示變量集合的聯(lián)合分布的圖形模型。該模型的形式化描述如下：

從表2可以看出，無論節(jié)點(diǎn)有序或無序，QGA學(xué)習(xí)的結(jié)構(gòu)得分最高，學(xué)習(xí)時(shí)間少于GS和MWST算法；QGA與K2相比，雖然在學(xué)習(xí)時(shí)間上稍遜，但是學(xué)習(xí)結(jié)果明顯占優(yōu)。

5結(jié)束語

本文提出一種基于量子遺傳算法的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)算法。該算法采用BIC評(píng)分標(biāo)準(zhǔn)，用量子遺傳算法對(duì)數(shù)據(jù)庫(kù)進(jìn)行學(xué)習(xí)，可得到全局最優(yōu)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，學(xué)習(xí)速度較快。實(shí)驗(yàn)表明，在數(shù)據(jù)完整的情況下，該算法明顯優(yōu)于已有算法。如何利用該算法進(jìn)行丟失數(shù)據(jù)的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)，將是筆者下一步的研究方向。

參考文獻(xiàn):

[1]FRIEDMAN N， NACHMAN I， PEER D. Learning Bayesian network structure from massive: the sparse candidate algorithm[C]//DUBIOS H， LASKEY K. Proc of the 15th Conference on Uncertainty in Artificial Intelligence. San Francisco: Morgan Kaufmann， 1999:206－215.

[2]CHICKERING D M. Learning Bayesian networks is NP－complete[C]//Learning from Data: Artificial Intelligence and Statistics V. Berlin: Springer－Verlag， 1996:121－130.

[3]KORB A，NICHOLSON A.Bayesian artificial intelligence[M].[S.l.]:Chapman Hall/CRC Press， 2004.

[4]WANG Ling， ZHENG Da－zhong. An effective hybrid optimization strategy for job－shop scheduling problems[J]. Computers and Operations Research， 2001，28(6):585－596.

[5]HAN K H， KIM J H. Quantum－inspired evolutionary algorithm for a class of combinatorial optimization[J].IEEE Trans on Evolutionary Computation， 2002，6(6):580－593.

[6]RAMOS R V， SOUZA R F. Calculation of the quantum entanglement measure of bipartite states， based on relative entropy， using genetics algorithms[J]. Comput Phys， 2002，175(2):576－583.

[7]NEWMAN D J， HETTICH S， BLAKE C L， et al. UCI repository of machine learning databases[D]. Berkeley: University of California， Department of Information and Computer Science.

[8]熊焰，陳歡歡，苗付友，等.一種解決組合優(yōu)化問題的量子遺傳算法QGA[J].電子學(xué)報(bào)，2004，32(11):1855－1858.

[9]張葛祥，李娜，金煒東，等.一種新量子遺傳算法及其應(yīng)用[J].電子學(xué)報(bào)，2004，32(3):476－479.

[10]袁書卿，張葛祥.一種改進(jìn)的遺傳量子算法及其應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件， 2003，20(10):1－2.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”