基于量子遺傳算法的貝葉斯網絡結構學習

摘要：將量子遺傳算法用于貝葉斯網絡(BN)的結構學習，對BN結構進行量子編碼得到染色體，通過量子變異操作使其作為一個完備的獨立解空間進行演化，可快速搜索到全局最優的網絡結構。實驗結果表明，量子遺傳算法用于BN結構學習，可取得很好的效果。

關鍵詞：貝葉斯網絡; 結構學習; 量子遺傳算法; 量子位

中圖分類號：TP391文獻標志碼：A

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

0引言

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

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

1貝葉斯網絡模型和結構學習

1．1貝葉斯網絡模型

貝葉斯網絡是根據各個變量之間的概率關系，使用圖論方法表示變量集合的聯合分布的圖形模型。該模型的形式化描述如下：

從表2可以看出，無論節點有序或無序，QGA學習的結構得分最高，學習時間少于GS和MWST算法；QGA與K2相比，雖然在學習時間上稍遜，但是學習結果明顯占優。

5結束語

本文提出一種基于量子遺傳算法的貝葉斯網絡學習算法。該算法采用BIC評分標準，用量子遺傳算法對數據庫進行學習，可得到全局最優的貝葉斯網絡結構，學習速度較快。實驗表明，在數據完整的情況下，該算法明顯優于已有算法。如何利用該算法進行丟失數據的貝葉斯網絡學習，將是筆者下一步的研究方向。

參考文獻:

[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]熊焰，陳歡歡，苗付友，等.一種解決組合優化問題的量子遺傳算法QGA[J].電子學報，2004，32(11):1855－1858.

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

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

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”