摘要
最优树分解是Bayesian网理论和应用研究中的基本问题之一,不仅与Bayesian网的理论分析以及诸多实际算法关系密切,而且在计算理论中也占有重要地位。针对最小团树宽度、最小团树加权宽度和最小团树费用等不同的优化目标,分为treewidth、weighted treewidth、treecost三类不同的最优树分解问题。其中treewidth问题也是图论中的一个经典问题。
虽然图论中对treewidth问题的研究由来已久,但对全部三类最优树分解问题,尤其是消去排序、三角化与最优树分解的关系,尚没有比较完整、严格的系统论述。在求解算法方面,启发式和智能优化是解决此类组合优化问题的两种主要方法,启发式适合在线实时快速求得可行解,智能优化则适合离线获取近似最优解。目前所提出的启发式求解结果大多比较差,而且面对不同具体问题表现并不稳定；针对treecost问题的智能优化方法虽然求解质量好于快速启发式,但与真正最优值相差仍比较大,同时鲁棒性并非足够好；而针对treewidth问题的智能优化方法,大多也存在着求解时间过长的缺点,距离实际应用要求还有很大差距。
本文一方面从集合论和图论的角度,定义子集族评价函数及其稳定性,并在此基础上,对Bayesian网中的消去排序、三角化和treewidth、weighted treewidth、treecost三类树分解问题的若干性质以及相互间关系,在理论上进行系统阐述和严格证明；另一方面,针对现有求解方法缺点,从启发式、迭代局部搜索以及智能优化等角度进行研究,并首次将协同进化机制引入树分解问题,给出Bayesian网树分解问题的一些有效求解算法以及算法框架。研究工作主要内容如下：
1.基于子集族评价函数及其稳定性的定义,对最优树分解与最优三角化、最优消去排序的关系进行严格、系统的论述,厘清三者问关系,用fmax_size、fmax_weight、ftotal_weight三种子集族评价函数定义treewidth、weighted treewidth、treecost树分解,为这三种树分解问题提供统一刻画方式。同时,基于评价函数,对Bayesian网树分解中的预处理等问题进行阐释。
2.针对treecost问题,提出若干新的求解方法：
(1)首先,对求解treecost问题的启发式和迭代搜索方法进行研究。针对现有启发式稳定性不强的缺点,提出可直接求解消去排序的启发式MinFillWeightProduct和MinLinearWeight Sum,同时提出可用于求解三角化的启发式MinLBWeightSum、MinLBFillWeightSum、MinLBFillWeightProduct;针对简单贪心方法虽然执行速度快、但求解质量不高的缺陷,提出迭代搜索方法IRT和多启发式搜索方法kHR,根据Bayesian网树分解的性质,给出时间复杂度比IRT低一个数量级的加速版本FAST-IRT,同时也对FAST-IRT与IRT的等价性进行证明。最后,通过实验对这些方法进行测试分析,在典型Bayesian网上的实验表明,与现有启发式方法相比,这些方法在整体性能上具有明显优势,非常适合在线求解。同时,这些方法也可以与如群智能等其他求解方法相结合,以获得更好的优化效果。
(2)其次,针对现有求解treecost问题的智能优化方法存在的缺点,提出可用于求解treecost问题的两种蚁群方法。混合极大极小蚁群算法MMMAS-SA用伪随机比例规则来构造单个解,以加强全局搜索能力,并采取动态调节信息素下限阈值的方式,使蚁群能够在可行域内进行更多探索；同时,采用复合式模拟退火机制,以提高蚁群的局部搜索能力：MHC-ACS则能充分利用现有启发式优点,通过自适应筛选合适启发式、动态定量控制启发式作用、利用启发式增强局部搜索能力等手段,将启发式有效融入蚁群系统。在一些具有代表性的Bayesian网上进行测试表明, MMMAS-SA和MHC-ACS是解决treecost司题的有效方法,不仅求解质量高、速度快,而且稳定性强于其他方法。
(3)本文还首次将协同进化机制应用于treecost问题求解。提出两个协同进化算法框架FGCC和VNGCC,给出了可用于这两种框架的多种变量分组方案。同时,为FGCC和’VNGCC框架构造了三种基本优化求解器DGHGA、MDPSO和DDE。DGHGA针对一般遗传算法中变异操作并未充分利用具体问题特点的缺点,将启发式引入遗传算法求解过程,使用复合启发式变异操作提高求解稳定性,同时,采用一种易于计算的准则判定群体多样性,度量算法停滞和收敛状态,避免群体进化中的早熟收敛现象；MDPSO以离散方式定义粒子位置和速度的运算,为提高粒子探索能力,采取改进变异操作,并且随机重置全局最好位置上的粒子,防止其停滞于局部极优；DDE是一种离散版本微分进化算法,用交换序列方法执行个体间差分运算,具有控制参数少、自组织性强的特点。实验表明,FGCC和VNGCC协同进化框架下的18种求解算法,均能有效求解treecost问题,从而为进一步利用协同进化机制的分布式、并行性特征求解树分解问题奠定了研究基础。
3.针对现有方法在求解treewidth问题上的不足,本文提出一种离散版本的改进人工蜂群求解方法IDABC,将一般人工蜂群算法从连续论域移植到离散论域,修改蜂群组织结构,增加后备食物源和专职雇佣蜂、迭代搜索蜂、启发式搜索蜂、智能守望蜂等新的蜂种,进一步提高系统全局搜索和开发能力。在与最近提出的迭代搜索和智能优化方法对比测试中,IDABC在求解时间上远快于其他对比算法,而且求解结果也十分具有竞争力。
Bayesian网最优树分解是Bayesian网相关研究中的重要方向,其中treewidth问题还是图论和计算理论中的一个关键问题。对于Bayesian网树分解,无论是理论刻画还是算法求解方面的研究由来已久,但目前解决方法尚不足够成熟和完善,距离实际应用要求尚有很大距离。本文从集合分解和评价函数的角度讨论树分解与消去排序、三角化的关系,抽象程度较高,具有很好的适用性,体现出一定理论意义。同时,本文在启发式、迭代搜索和群智能方法等方面展开算法研究工作,并首次利用协同进化构造有效求解treecost问题的算法框架,为Bayesian网最优树分解问题的在线和离线求解提供多种新的有效方法,具有较强实际应用价值。
Optimal tree decomposition is one of basic problems in the research about Bayesian networks beacause it is closely related to both theoretical and practical aspects about Bayesian networks, and it occupies an important position in theory of computation. According to three different optimization goals:minimum width, minimum weighted width and minimum state space size of join tree, there are three kinds of tree decomposition problems:treewidth, weighted treewidth and treecost, where treewidth is a classical problem in the research area of graph theory.
Although there is a long history about the research on treewidth, no work has been appeared to discuss completely, strictly and generally over all the three problems, especially over the relationship among elimination ordering, triangulation and tree decomposition, In existing solutions to these problems, heuristics and stochasitic optimization are two main methods. Heuristics are very suit to get feasilbe solutions online. On the other hand, stochastic methods are able to achieve near-to-optimal solutions offline. However, resluts given by existing heuristics are usually very worse and not stable in face of various cases. Stochastic approaches to the treecost problem often give better results but still neither good nor stable enough yet. And most stochastic approaches to the treewidth problem are very time-consuming. Existing algorithms are not practical in real application.
On one hand, in view of set theory and graph theory, this paper gives definintion of subset family evaluation function and its stability, and elaborates theoretically the relationship among elimination ordering, triangulation and tree decomposition on this basis. On the other hand, in aims to make improve on existing algorithms, this paper perfoms research from the aspects of heuristics, iterative local search and stochastic methods and presents some effective algorithms and algorithmic framework. The main work of this paper is as follows.
1. Based on the presentation of subset family evaluation function, this paper gives a strict and general elaboration about the relationship among optimal triangulation, optimal elimination ordering and optimal tree decomposition. Treewidth, weighted treewidth and treecost problems are defined formaly via three subset family evaluation functions of fmax_size,fmax_weight andftotal_weight.In a further step, this paper also explains some basic things about tree decomposition of Bayesian network, such as the the preprocessing method of reducing simplicial nodes.
2. To solve the treecost problem, this paper provides some novel algorithms and algorithmic frameworks.
(1) Firstly, the heuristics and iterative search methods are investigated. To overcome the shortcoming of instability of existing heuristics, five new heuristics, MinFillWeightProduct, MinLinearWeightSum, MinLBWeightSum, MinLBFillWeightSum and MinLBFillWeightProduct, are presented. In addition, an iterative local search method named IRT and a multi-heuristic-based greedy method named kHR are proposed. In a further step, based on properties of tree decomposition of Bayesian network, an efficient approach named FAST-IRT, which is equivalent to but more fast than IRT, is provided. The equivalence between IRT and FAST-IRT is also proved formally. Experiments on typical Bayesian network benchmarks show that all these heuristics and iterative methods are more superior to existing heuristics on the whole and very suitable to online problem-solving. More better results can be obtained by combining these heuristics and iterative methods with other methods, such as the stochastic methods proposed in this paper.
(2) Secondly, to improve existing stochastic methods, two ant colony approaches are developed for the treecost problem. MMMAS-SA is a hybrid max-min ant system. To increasing global searching ability, MMMAS uses pseudo-random-proportional rule to construct a feasible solution, adjusts the lower pheromone limit in the runng process to make ants explore more regions in the searching space, and adopts a kind of combined simulated annealing scheme to improve ant colony's exploitation ability. MHC-ACS is an adaptive multi-heuristic ant colony system. It makes full use of the advantages of heuristics, selects appropriate heuristics adaptively, and applies a quantitative control over the heuristics dynamicly. All these mechanisms assure heuristics to be incorporated into MHC-ACS to a great extent. Experimental results on some representative Bayesian networks indicate that MMMAS-SA and MHC-ACS are effective methods for the treecost problem. They can achieve good results in a shor time and presents better robustness than other stochastic optimization methods for the treecost problem.
(3)Thirdly, this paper applies cooperative coevolutionary framework to the treecost problem for the first time and proposes two cooperative coevolutionary frameworks named FGCC and VNGCC respectively. Three optimizers-DGHGA, MDPSO and DDE, are constructed for FGCC and VNGCC frameworks. DGHGA introduces heuristics into its genetic evolution procedure. It uses a multiple-heuristic mutation operation to improve its robustness. In order to avoid premature convergence, DGHGA detects the states of stagnation and convergence by measuring population diversity via an efficient method. MDPSO operates particles'positions and velocities in a discrete manner. It also applies an improved mutation operation to to endow each particle with the ability of global search. To prevent the particles to be trapped in the local optimum, MDPSO resets the particles on the global best-so-far position. DDE is a discrete version of traditional DE algorithm performing the operations between individuals via the method of swap sequence. It runs with few parameters and possesses the feature of strong self-organization. Tests manifest that all the 18 algorithms utilizing FGCC or VNGCC framework can solve the treecost problems effectively. This work lays a solid foundation for the possible solution of treecost problem by utilizing the distribution and parallel characteristics of cooperative coevolution mechanism.
3. To make up the shortfall of long running time of existing stochastic methods for the treewidth problem, this paper proposes an improved discrete ABC algorithm named IDABC. IDABC finds treewidth in the discrete search space composed by elimination orderings. It improves traditional ABC algorithm by adding backup food sources, special employees, iterative searching onlookers, heuristic searching onlookers and intelligent onlookers to the bee colony to enhance the global search ability. By comparison with some recent iterative local search method and stochastic optimization methods on DIMACS becnchmarks, IDABC presented its high efficiency, robustness and comparability to other existing approaches.
Optimal tree decomposition is an important area for research about Bayesian network. Especially, the treewidth problem is also a key topic in graph theory and computation theory. The research work about tree decomposition of Bayesian network, both in theoretical aspect and in algorithmic aspect, has a long history. However, the solution to this problem is neither mature nor perfect enough. The subset-family-evaluation-function-based framework presented in this paper characterize tree decomposition problem in a high level and and has a strong generality so it is of proper theoretical significance. On the other hand, this paper presents some research work about heuristics, iterative search and swarm intelligence methods for the tree decomposition problem. These methods provide useful novel ways for online and offfline solving of the tree decomposition of Bayesian network and possess good application values.
引文
[1]S. L. Lauritzen, D. J. Speigelhalter. Local computation with probabilities on graphical structures and their application to expert systems [J]. Journal of the Royal Statistical Society (Series B),1988,50(2):157-224.
[2]K. Kask, R. Dechter, J. Larrosa, A. Dechter. Unifying tree decompositions for reasoning in graphical models [J]. Artificial Intelligence,166(2005):165-193.
[3]A. Darwiche. Recursive conditioning [J]. Artificial intelligence,2001,126(1-2):5-41.
[4]Dechter R, Mateescu R. AND/OR search spaces for graphical models [J]. Artificial intelligence,2007,171(2-3):73-106.
[5]B. Bidyuk, R. Dechter. Cutset Sampling for Bayesian Networks [J]. Journal of Artificial Intelligence Research 28 (2007) 1-48.
[6]M. Chavira, A. Darwiche. Compiling Bayesian networks using variable elimination [C]. In:Proceedings of the 20th international joint conference on Artifical intelligence (IJCAI 2007), 2007, pp.2443-2449.
[7]Mark Chavira & Adnan Darwiche. Compiling Bayesian networks with local structure [C]. In:IJCAI, pages 1306-1312,2005.
[8]A. M. C. A. Koster, H. L. Bodlaender, S. P. M. Hoesel. Treewidth:computational experiments [C]. In:Electronic Notes in Discrete Mathematics, vol.8, Elsevier Science Publishers, 2001.
[9]H. L. Bodlaender, B. van A. Fluiter. Reduction algorithms for graphs of small treewidth [J]. Information and Computation,167,86-119 (2001).
[10]Carlos Ansotegui, Ramon Bejar, Cesar Fernandez, Carles Mateu, On balanced CSPs with high treewidth [C]. Proceedings of the 22nd national conference on Artificial intelligence, p.161-166, July 22-26,2007, Vancouver, British Columbia, Canada.
[11]H. L. Bodlaender, A. M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth [J]. The Computer Jounal,51(3)(2008) 255-269.
[12]J. M. M. van Rooij, H. L. Bodlaender, and P. Rossmanith. Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution [C]. In ESA, volume 5757 of Lecture Notes in Computer Science, pages 566-577. Springer,2009.
[13]S. Szeider. Monadic Second Order Logic on Graphs with Local Cardinality Constraints [C]. Mathematical Foundations of Computer Science 2008. Lecture Notes in Computer Science, 2008, Volume 5162,2008,601-612.
[14]J. Gustedt, O. Maehle, J. A. Telle. The treewidth of Java programs [C]. Proceedings ALENEX'02-Fourth Workshop on Algorithm Engineering and Experiments, San Francisco, January 4-5,2002, Lecture Notes in Computer Science, Springer, Berlin, vol.2409.
[15]O. Shcherbina. Nonserial Dynamic Programming and Tree Decomposition in Discrete Optimization [C]. Operations Research Proceedings 2006. Operations Research Proceedings,2007, Volume 2006, Part VI,155-160.
[16]G., R. Pichler,F. Wei. Tractable database design and datalog abduction through bounded treewidth [J].Inf. Syst.,35(3):278-298,2010.
[17]Clive G. Bowsher. Information processing by biochemical networks:a dynamic approach [J]. Journal of The Royal Society Interface,8(55)(2011), pp.186-200.
[18]Maurice Jansen, Jayalal Sarma M.N. Balancing Bounded Treewidth Circuits [C]. In:F. Ablayev and E.W. Mayr (Eds.), CSR 2010, LNCS 6072, Springer-Verlag Berlin,2010, pp. 228-239.
[19]B. Kaba, N. Pinet, G. Lelandais, A. Sigayret, A. Berry. Clustering gene expression data using graph separators [J]. Silico Biol.2007;7(4-5):433-52.
[20]R. Gysel, D. Gusfield. Extensions and Improvements to the Chordal Graph Approach to the Multi-state Perfect Phylogeny Problem [C]. In Proceedings of the ISBRA Conference,2010, Springer LNBI Vol.6054, p.52-60.
[21]P. Heggernes. Minimal triangulations of graphs:A survey [J]. Discrete Mathematics, 306(3)(2006):297-317.
[22]S. Arnborg, A. Proskurowski. Characterization and recognition of partial 3-trees [J]. SIAM J. Alg. Disc. Meth.,7:305-314,1986.
[23]Y. Kajitani, A. Ishizuka, S. Ueno. (1986) Characterization of partial 3 trees in terms of 3 structures [J]. Graphs Combin.2,233-246.
[24]J. Matousek, R. Thomas. (1991) Algorithms finding tree-decompositions of graphs [J]. J. Algorithms 12,12-22.
[25]H.L. Bodlaender, A.M.C.A. Koster, F.v.d. Eijkhof. Preprocessing rules for triangulation of probabilistic networks [J]. Comput. Intelligence 21 (3) (2005) 286-305.
[26]H.L. Bodlaender, A.M.C.A. Koster. Safe separators for treewidth [J]. Discrete Math.306 (2006) 337-350.
[27]S. Arnborg, D. G. Corneil, A. Proskurowski. Complexity of finding embeddings in a k-tree [J]. SIAM J. Alg. Disc. Math.,8(1987), pp.277-284.
[28]H. L. Bodlaender, F. V. Fomin, A. M. C. A. Koster, D. Kratsch, D. M. Thilikos. On exact algorithms for treewidth [C]. In:ESA 2006, vol.4168 of Lecture Notes in Comput. Sci., Springer, 2006, pp.672-683.
[29]F. V. Fomin, D. Kratsch, I. Todinca, Y. Villanger. Exact algorithms for treewidth and minimum fill-in [J]. SIAM Journal on Computing 2008 38(3):1058-1079.
[30]V. Gogate, R. Dechter. A complete anytime algorithm for treewidth [C]. In proceedings UAI'04, Uncertainty in Artificial Intelligence,2004.
[31]P. A. Dow, R. E. Korf. Best-First Search for Treewidth [C]. In:Proceedings of the 22nd national conference on Artificial intelligence (AAAI'07), pages 1146-1151,2007.
[32]R. Zhou, E. A. Hansen. Combining Breadth-First and Depth-First Strategies in Searching for Treewidth [C]. Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09),640-645.
[33]P. A. Dow, R. E. Korf. Duplicate Avoidance in Depth-First Search with Applications to Treewidth [C]. Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09),480-485.
[34]D. Rose, R. E. Tarjan, G. S. Lueker. Algorithmic aspects of vertex elimination in graphs [J]. SIAM. J. Comput.5(1976)266-283.
[35]M. Yannakakis, R. E. Tarjan. Simple linear time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs [J]. SIAM J. Comput. 13(1984)566-579.
[36]A. Berry, J. R. S. Blair, P. Heggernes, B. W. Peyton. Maximum cardinality search for computing minimal triangulations of graphs [J]. Algorithmica (2004) 39:287-298.
[37]Y. Villanger. Lex M versus MCS-M [J]. Discrete Mathematics,306(3)(2006):393-400.
[38]A. Berry, R. Krueger, G. Simonet. Ultimate generalizations of LexBFS and LEX M [C]. Proceedings 31st International Workshop on Graph-Theoretic Concepts in Computer ScienceWG'05, Lecture Notes in Computer Science, vol.3787, Springer, Berlin,2005, pp. 199-213.
[39]A. Berry. A wide-range efficient algorithm for minimal triangulation [C]. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithm,1999.
[40]P. Heggernes, Y. Villanger. Efficient Implementation of a minimal triangulation algorithm [C]. In R. Mohring and R. Raman (Eds), ESA2002, LNCS 2461, pp.550-562,2002.
[41]Y. Villanger. Efficient Minimal Triangulation of Graphs by Using Tree Decompositions [R]. Department of Informatics University of Bergen Norway,2002.
[42]A. Berry, J. P. Bordat, P. Heggernes, G. Simonet, Y. Villanger. A wide-range algorithm for minimal triangulation from an arbitrary ordering [J]. Journal of Algorithms,58(1)(2006):33-66.
[43]D. Rose. Triangulated graphs and the elimination process [J]. Journal of Mathematical Analysis and Applications,32(3)(1970), pp.597-609.
[44]A. Berry, R. Krueger, G. Simonet. Ultimate generalizations of LexBFS and LEX M [C]. Proceedings 31st International Workshop on Graph-Theoretic Concepts in Computer ScienceWG'05, Lecture Notes in Computer Science, vol.3787, Springer, Berlin,2005, pp. 199-213.
[45]E. H. Bachoore, H. L. Bodlaender (2005) New upper bound heuristics for treewidth [C]. In S. E. Nikoletseas (ed), Proc.4th Int. Workshop Experimental and Efficient Algorithms WEA 2005, pp.217-227. Lecture Notes in Comuter Science, vol.3503. Springer-Verlag.
[46]H. L. Bodlaender. Discovering treewidth [C]. In Proc.31st Current Trends in Theory and Practice of Comupter Science, vol.3381 of LNCS,1-16. Springer.
[47]F. Clautiaux, J. Carlier, A. Moukrim, S. Negre. (2003) New lower and upper bounds for graph treewidth [C]. In J. D. P. Rolim (ed), Proc. Int. Workshop on Experimental and Efficient Algorithms, WEA 2003, pp.70-80. Lecture Notes in Computer Science, vol.2647. Springer-Verlag.
[48]F. Clautiaux, A. Moukrim, S. Negre, J. Carlier. (2004) Heuristic and meta-heuristic methods for computing graph treewidth [J]. RAIRO Oper. Res.,38, pp.13-26.
[49]E. H. Bachoore, H. L. Bodlaender (2005) New upper bound heuristics for treewidth [C]. In S. E. Nikoletseas (ed), Proc.4th Int. Workshop Experimental and Efficient Algorithms WEA 2005, pp.217-227. Lecture Notes in Comuter Science, vol.3503. Springer-Verlag.
[50]H. L. Bodlaender, A. M. C. A. Koster. Treewidth computations I. upper bounds [J]. Information and Computation 208(3) (2010) 259-275.
[51]B. Reed. Finding approximate separators and computing treewidth quickly [C]. In:Proc. 24th Annual Symposium on Theory of Computing, ACM Press, NY,1992,pp.221-228.
[52]N. Robertson, P. D. Seymour. Graph minors XIII. The disjoint paths problem [J]. J. Combinatorial Theory B 63(1995) 65-110.
[53]A. Becker, D. Geiger. A sufficiently fast algorithm for finding close to optimal clique trees [J]. Artificial Intelligence,125(2001)3-17.
[54]N. Musliu. Generation of Tree Decompositions by Iterated Local Search[C]. In: Proceedings of the 7th European conference on Evolutionary computation in combinatorial optimization (EvoCOP 2007), LNCS, Volume 4446, pages 130-141,2007, Springer.
[55]N. Musliu. An iterative heuristic algorithm for tree decomposition [C]. In:Recent Advances in Evolutionary Computation for Combinatorial Optimization, Volume 153, pages 133-150,2008. Carlos Cotta, Jano van Hemert (Eds.).
[56]S.van Hoesel, B. Marchal. Finding good tree decompositions by local search [J]. Electron. Notes Dis. Math.32 (2009) 43-50.
[57]N. Musliu, W. Schafhauser. Genetic algorithms for generalised hypertree decompositions [J]. European Journal of Industrial Engineering,1(3):317-340, January 2007.
[58]T. Hammerl, N. Musliu. Ant colony optimization for tree decompositions [C]. In Peter I. Cowling and Peter Merz, editors, Proceedings of the Evolutionary 10th European Conference on Computation in Combinatorial Optimization, (EvoCOP'10), Istanbul, Turkey, April 7-9,2010, volume 6022 of Lecture Notes in Computer Science, pages 95-106. Springer,2010.
[59]W. X. Wen. Optimal decomposition of belief networks [C]. In Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, Elsevier Science, pp.245-256,1990.
[60]F.v.d. Eijkhof, H.L. Bodlaender, A.M.C.A. Koster. Safe reduction rules for weighted treewidth [J]. Algorithmica 47 (2007):139-158.
[61]U. Kjaerulff. Triangulation of graphs-algorithms giving small total state space [R]. Technical Report R90-09, Department of Mathematics and Computer Science, Institute for Electronic Systems, Aalborg University.
[62]C. Huang, A. Darwiche. Inference in belief networks:A procedural guide [J]. International Journal of Approximate Reasoning,15(3) (1996):225-263.
[63]A. Cano, S. Moral. Heuristic Algorithms for the Triangulation of Graphs[C]. Proceedings of the 5th International Conference on Information Processing and Management of Uncertainty in Knowledge Based Systems. Paris, France:LNCS 945 Springer,1994.98-107.
[64]C. Harbron. Heuristic algorithm for finding inexpensive eliminatioin schemes [J]. Statistics and Computing,5(4)(1995):275-287.
[65]G. A. Dirac. On rigid circuit graphs [C]. Anh. Math. Sem. Univ. Hamburg, 25(1-2)(1961):71-76.
[66]C. G. Lekkerkerker, J. C. Boland. Representation of a finite graph by a set of intervals on the real line [J]. Fund. Math.,51(1962):45-64.
[67]A. Berry, P. Heggernes, G. Simonet. The minimum degree heuristic and the minmal triangulation process [C]. In:Proceedings WG 2003-29th Workshop on Graph Theoretic Concepts in Computer Science, June 2003, Elspeet, the Netherlands. Springer Verlag, Lecture Notes in Computer Science 2880, pages 58-70.
[68]张聪,沈一栋,程克非.一种用于信度网推理的高效三角化算法[J].计算机科学,32(6)(2005)：114-117.
C. Zhang, Y. D. Shen, K. F. Cheng. An effective triangulation algorithm for Bayesian network inference[J]. COMPUTER SCIENCE,32(6)(2005):114-117.
[69]P. Savicky, J. Vomlel. Triangualtion heuristics for BN20 networks [C]. In:Proceedings of the 10th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2009), July 01-03,2009, Verona, Italy, LNAI 5590, pp.566-577.
[70]H. L. Bodlaender, F. V. Fomin. Tree decompositions with small cost [J]. Discrete Applied Mathematics,145(2005)143-154.
[71]U. Kjaerulff. Optimal networks decomposition of probabilistic by simulated annealing [J]. Statistics and Computing,2(1)(1992):7-17.
[72]P. Larranaga, C. M. H. Kuijpers, M. Poza, R. H. Murga. Decomposing Bayesian networks: triangulation of the moral graph with genetic algorithms [J]. Statistics and Computing, Kluwer Academic,7(1)(1997):19-34.
[73]M. Meila, M. I. Jordan. Triangulation by continuous embedding [R]. ftp://publication.ai.mit.edu.1997.
[74]J. A. Gamez, J. M. Puerta. Searching for the best elimination sequence in Bayesian networks by using ant colony optimization [J]. Pattern Recognition letters,23(1-3)(2002):261-277.
[75]M. Fishelson, D. Geiger. Optimizing exact genetic linkage computations [J]. Journal of Computational Biology 11(2/3)(2004):263-275. (see also RECOMB 2003).
[76]H. Wang, K. Yu, X. H. Wu, H. L. Yao. Triangulation of Bayesian Networks Using an Adaptive Genetic Algorithm [C]. In:The 16th International Symposium on Methodologies for Intelligent Systems. Bari, Italy:LNAI 4203 Springer,2006.127-136.
[77]T. Romero, P. Larranaga. Triangulation of Bayesian networks with recursive estimation of distribution algorithms [J]. International Journal of Approximate Reasoning,50(3)(2009):472-484.
[78]K.G. Olesen, A.L. Madsen. Maximal prime subgraph decomposition of Bayesian networks [R]. Technical report, Department of Computer Science, Aalborg University, Aalborg, Denmark,1999.
[79]K.G. Olesen, A.L. Madsen. Maximal prime subgraph decomposition of Bayesian networks [J]. IEEE Transactions on Systems, Man and Cybernetics, Part B,32 (2002):21-31.
[80]M. J. Flores, J. A. Gamez. Triangulation of Bayesian networks by retriangulation [J]. International Journal of Intelligent Systems,18(2003):153-164.
[81]M. J. Flores, J. A. Gamez. A review on distinct methods and approaches to perform triangulation for Bayesian networks [C]. StudFuzz 213,127-152 (2007).
[82]D. B. West. Introduction to graph theory (2nd Edition) [M]. Prentice Hall, New Jersey, 2001.
[83]C. Bartels, J. Bilmes. Non-Minimal Triangulations for Mixed Stochastic/Deterministic Graphical Models [C]. In:Proceedings of the Twenty Second Conference on Uncertainty in Artificial Intelligence (UAI06), AUAI Press, Cambridge, MA, July 2006, pp.15-22.
[84]X. F. Wang, J. H. Guo. Junction trees for general graphs [J]. Front. Math. China, 3(3)(2008):399-413.
[85]J.R.S. Blair, B.W. Peyton. An introduction to chordal graphs and clique trees [C]. In: Graph Theory and Sparse matrix Computations, J.A. George, J.R. Gilbert, and J.W.H. Liu, eds., Springer-Verlag, New York,1993, pp.1-30. IMA Volumes in Mathematics and its Applications, Vol.56.
[86]F. V. Jensen, F. Jensen. Optimal junction trees [C]. In:Proceedings of the Tenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-94),360-366, Morgan-Kaufmann,1994.
[87]A. Berry, J. R. S. Blair, P. Heggernes, B. W. Peyton. Maximum cardinality search for computing minimal triangulations of graphs [J]. Algorithmica (2004) 39:287-298.
[88]M. Yannakakis, R. E. Tarjan. Simple linear time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs [J]. SIAM J. Comput. 13(1984)566-579.
[89]M. C. Golumbic. Algorithmic graph theory and perfect graph (Second Edition) [M]. Annals of Discrete Mathematics 57, Elsevier,2004.
[90]S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi. Optimization by simulated annealing [J]. Science,220(4598)(1983):671-680.
[91]V. Cerny. A thennodynamical approach to the traveling salesman problem:an efficient simulation algorithm [J]. J. Optim. Theory Appl.45(1985):41-51.
[92]B. Suman. Study of simulated annealing based algorithms for multiobjective optimization of a constrained problem [J]. Computers & Chemical Engineering,28(9)(2004):1849-1871.
[93]N. Safaei, M. Saidi-Mehrabad, M.S. Jabal-Ameli. A hybrid simulated annealing for solving an extended model of dynamic cellular manufacturing system [J]. European Journal of Operational Research,185(2)(2008):563-592.
[94]R.S. Tavares, T.C. Martins, M.S.G. Tsuzuki. Simulated annealing with adaptive neighborhood:A case study in off-line robot path planning [J]. Expert Systems with Applications, 38(4)(2011):2951-2965.
[95]邢文训,谢金星。现代优化计算方法(第2版)[M].北京：清华大学出版社,2005.
[96]B. Hajek. Cooling schedules for optimal annealing [J]. Mathematics of Operations Research,13(2)(1988):311-329.
[97]P. J. M. van Laarhoven, E. H. L. Aarts. Simulated Annealing:Theory and Applications [M]. Kluwer Academic Publishers,1987.
[98]M. Lundy, A. Mees. Convergence of an annealing algorithm [J]. Mathematical Programming,34(1986):111-124.
[99]M. D. Huang, F. Romeo, A. L. Sangiovanni-Vincentelli. An efficient general cooling schedule for simulated annealing [C]. In:Proceeding of IEEE International Conference on Computer-Aided Design. Santa Clara,1986, pp.381-384.
[ioo]A. S. Fraser. Simulation of genetic systems by automatic digital computers [J]. Australian Journal of Biological Science,10(1957):484-499.
[101]J. H. Holland. Adaptation in Natural and Artificial Systems [M]. The University of Michigan Press, Ann Harbor, MI,1975.
[102]J. D. Bagley. The behavior of adaptive systems which employ genetic and correlation algorithms [D]. Ph. D. dissertation, University of Michigan, Ann Arbor,1967.
[103]K. A. De Jong. An analysis of the behavior of a class of genetic adaptive systems [D]. Ph. D. dissertation, University of Michigan, Ann Arbor,1975.
[104]J. J. Grefenstette. GENESIS:a system for using genetic search procedures [C]. Proceedings of the 1984 Conference on Intelligent Systems and Machines,161-165,1984.
[105]D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning [M]. Reading, MA:Addison-Wesley,1989.
[106]L. Davis (Ed.).Handbook of Genetic Algorithms [M]. New York:Van Nostrand Reinhold, 1991.
[107]汪定伟,王俊伟,王洪峰,张瑞友,郭哲.智能优化方法[M].北京：高等教育出版社,2007.4.
[108]R. Storn, K. Price. Differential evolution-a simple and efficient heuristic for global optimization over vcontinuous spaces [J]. Journal of Global Optimization,11(1997):341-359.
[109]D. G. Mayer, B. P. Kinghorn, A. A. Archer. Differential evolution-an easy and efficient evolutionary algorithm for model optimisation [J]. Agricultural Systems,83(2005):315-328.
[110]K. V. Price. An introduction to differential evolution [C]. In:D. Corne, M. Dorigo, F. Glover (Eds), New Ideas in Optimization. McGraw-Hill, London,1999, pp.79-108.
[111]R. Storn. Disigning digital filters with differential evolution [C]. In:D. Corne, M. Dorigo, F. Glover (Eds), New Ideas in Optimization. McGraw-Hill, London,1999, pp.109-125.
[112]刘波,王凌,金以慧.差分进化算法研究进展[J].控制与决策,22(7)(2007)：721-729.
[113]周艳平,顾幸生.差分进化算法研究进展[J].综述与评论,34(3)(2007)：1-5.
[114]杨启文,蔡亮,薛云灿.差分进化算法综述[J].模式识别与人工智能,21(4)(2008)：506-513.
[115]R. C. Eberhart, J. Kennedy. A new optimizer using particle swarm theory [C]. In: Proceedings of the Sixth International Symposium on Micromachine and Human Science, Nagoya, Japan,1995, pp.39-43.
[116]J. Kennedy, R. C. Eberhart. Particle swarm optimization [C]. In:Proceedings of the IEEE International Joint Conference on Neural Networks, IEEE Press, Honolulu, Hawaii,2002.
[117]F. van den Bergh, A. P. Engelbrecht. A study of particle swarm optimizatioin particle trajectories [J]. Information Sciences,176(2006):937-971.
[118]R. C. Eberhart, Y. Shi. Comparing inertia weights and constriction factors in particle swarm optimization [C]. In:Proceedings of the IEEE Congress on Evolutionary Computation, San Diego, USA,2000, pp.84-88.
[119]M. Jiang, Y. P. Luo, S. Y. Yang. Stochastic convergence analysis and parameter selection of the standard particle swarm optimization algorithm [J]. Information Processing Letters, 102(2007):8-16.
[120]A. Carlisle, G. Dozier. An off-the-shelf PSO [C]. In:Proceedings of the Workshop on Particle Swarm Optimization, Indianapolis, USA,2001.
[121]M. Clerc, J. Kennedy. The particle swarm-explosion, stability and convergence in a multidimensional complex space [J]. IEEE Transactions on Evolutionary Computation,6(1)(2002): 58-73.
[122]I. C. Trelea. The particle swarm optimization algorithm:convergence analysis and parameter selection [J]. Information Processing Letters,85(2003):317-325.
[123]M. Dorigo, V. Maniezzo, A. Colomi. The ant system:optimization by a colony of cooperating ants [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B,26(1),1996, 29-41.
[124]M. Dorigo, L. M. Gambardella. Ant colony system:a cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation,1(1)(1997): 53-66.
[125]B. Bullnheimer, R. Hartl, C. Strauss. A new rank-based version of the ant system:a computational study [J]. Central European Journal for Operations Research and Economics, 7(1)(1999):25-38.
[126]T. Sttzle, H. Hoos. MAX-MIN ant system [J]. Future Generat. Comput. Syst,16(8)(2000): 889-914.
[127]C. Blum, M. Dorigo. The hyper-cube framework for ant colony optimization [J]. IEEE Transactions on Systems, Man, and Cybernetics Part B,34(2)(2004):61-72.
[128]M. Dorigo, C. Blum. Ant colony optimization theory:a survey [J]. Theoretical Computer Science,344(2005):243-278.
[129]C. Blum. Ant colony optimization:introduction and recent trends [J]. Physics of Life Reviews,2(2005):353-373.
[130]L. M. Gambardella, M. Dorigo. Ant-Q:a reinforcement learning approach to the traveling salesman problem [C]. In:Proceedings of the twelfth International Conference on Machine Learning, Morgan Kaufmann,1995, pages 252-260.
[131]T. Sttzle, H. Hoos Improving the ant system:a detailed report on the MAX-MIN ant system [R]. Technical report AIDA-96-12, FG Intellektik, FB Informatik, TU Darmstadt,1996. (See also:The Max-Min Ant System and Local Search for the Travelling Salesman Problem [C]. In: ICEC 1997, pp.309-314)
[132]D. Karaboga. An idea based on honey bee swarm for numerical optimization [R]. Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department,2005.
[133]B. Basturk, D. Karaboga. An artificial bee colony (ABC) algorithm for numeric function optimization [C]. In:IEEE Swarm Intelligence Symposium 2006, May 12-14, Indianapolis, IN, USA,2006.
[134]D. Karaboga, B. Basturk. A powerful and efficient algorithm for numerical function optimization:artificial bee colony (ABC) algorithm [J]. Journal of Global Optimization, 39(3)(2007):459-471
[135]D. karaboga, B. Basturk. On ther performance of artificial bee colony (ABC) algorithm [J]. Applied Soft Computing,8(2008):687-697.
[136]D. Daraboga, B. Akay. A comparative study of aartificial bee colony algorithm [J]. Appplied Mathematics and Computation,214(2009):108-132.
[137]M. A. Potter, K. A. De Jong. A cooperative coevolutionary approach to function optimization [C]. In:Proceedings of the Third Conference on Parallel Problem Solving from Nature, vol.2, pp.249-257,1994.
[138]M. A. Potter, K. A. De Jong. Cooperative coevolution:an architecture for evolving coadapted subcomponents [J]. Evolutionary Computation,8(1):1-29,2000.
[139]R. P. wiegand, W. C. Liles, K. A. De Jong. An empirical analysis of collaboration methods in cooperative coevolutionary algorithms [C]. In L. Spector, E. D. Goodman, A. Wu, W. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. H. Garzon, and E. Burke, editors, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2001, pages 1235-1242. Morgan Kaufmann,2001.
[140]Y. Liu, X. Yao, Q. Zhao, T. Higuchi. Scaling up fast evolutionary programming with cooperative coevolution [C]. In:Proceedings of the 2001 Congress on Evolutionary Computation, pp.1101-1108,2001.
[141]Z. Yang, K. Tang, X. Yao. Large scale evolutionary optimization using cooperative coevolution [J]. Information Sciences,178(2008):2986-2999.
[142]F. van den Bergh, A. P. Engelbrecht. A cooperative approach to particle swarm optimization [J]. IEEE Transactions on Evolutionary Comutation 8(3)(2004):225-239.
[143]A. Parra, P. Scheffler. How to use the minimal separators of a graph for its chordal triangulation [C]. Proceedings of the 22nd International Colloquium on Automata, Languages and Programming (ICALP'95), Lecture Notes in Computer Science,944:123-134,1995.
[144]V. Bouchitte, I. Todinca. Listing all potential maximal cliques of a graph [J]. Theoret. Comput. Sci.,276(2002), pp.17-32.
[145]V. Bouchitte, I. Todinca. Treewidth and minimum fill-in:Grouping the minimal separators [J]. SIAM J. Comput.,31:212-232,2001.
[146]Y. Shi, H. Teng, Z. Li. Cooperative coevolutionary differential evolution for function optimization [C]. In:Proc. Of the First International Conference on Natural Computation, pp. 1080-1088,2005.
[147]R. Diestel. Graph theory (Fourth Edition) [M]. Graduate Texts in Mathematics, Volume 173, Springer-Verlag, Heidelberg,2010.
[148]T. Stiitzle, H. Hoos. MAX-MIN ant system [J]. Future Generation Computer Systems, 2000,6(8):889-914.
[149]R. Pitakaso, C. Almeder, K. F. Doerner, R. F. Hartl, et. al. A MAX-MIN ant system for unconstrained multi-level lot-sizing problems [J]. Computers & Operations Research,2007,34(9): 2533-2552.
[150]K. Y. Wong, P. C. See. A new minimum pheromone threshold strategy (MPTS) for max-min ant system [J]. Applied Soft Computing,2009,9(3):882-888.
[151]N. Azizi, S. Zolfaghari. Adaptive temperature control for simulated annealing:a comparative study [J]. Computers & Operations Research,2004,31(14):2439-2451.
[152]Y. Xu, J. Hu, K. Hirasawa, X. Pang. A new cooperative approach to discrete particle swarm optimization [C]. In:SICE Annual Conference 2007, Takamatsu, Japan:IEEE,2007. 1311-1318.
[153]K. P. Wang, L. Huang, C. G. Zhou, W. Pang. Particle swarm optimization for traveling salesman problem [C]. ICMLC 2003:1583-1585.