利用双变量相关加速贝叶斯优化算法中的结构学习过程

doi:10.1007/s11390-012-1285-1

摘要/Abstract

贝叶斯优化算法(BOA)是成功的并被广泛用于解决不同优化问题的分布估计算法(EDAs)的一种。EDAs从所选出的以问题变量间的相互关系作为编码的种群学习一个模型, 并对模型进行采样产生新的个体, 然后这些个体组成群体。不同的概率模型曾在EDAs中用来学习变量间的相关性。贝叶斯网络(BN)是一种众所周知的用在BOA中的图模型。在EDAs中特别是在BOA中, 学习一个合适的模型被认为是一件计算代价昂贵的工作。在已有的文献中, 不同方法曾被提出以改善在EDAs中构建模型的复杂性。本文使用双变量相关以在BOA中高效地学习到准确的BNs。该方法使用一种合适的针对成对变量间相互关系检测的标准来提取双变量相关。使用这种方法, 模型构建的计算代价会剧烈地下降。该算法在大量选出的优化问题进行测试。实验结果表明本文提出的方法可以成功并高效地找到具有不同相互关系类型的问题的最优, 同时可以观察到模型构建过程被显著地加速。

Abstract: Bayesian optimization algorithm (BOA) is one of the successful and widely used estimation of distribution algorithms (EDAs) which have been employed to solve different optimization problems. In EDAs, a model is learned from the selected population that encodes interactions among problem variables. New individuals are generated by sampling the model and incorporated into the population. Different probabilistic models have been used in EDAs to learn interactions. Bayesian network (BN) is a well-known graphical model which is used in BOA. Learning a proper model in EDAs and particularly in BOA is distinguished as a computationally expensive task. Different methods have been proposed in the literature to improve the complexity of model building in EDAs. This paper employs bivariate dependencies to learn accurate BNs in BOA efficiently. The proposed approach extracts the bivariate dependencies using an appropriate pairwise interaction-detection metric. Due to the static structure of the underlying problems, these dependencies are used in each generation of BOA to learn an accurate network. By using this approach, the computational cost of model building is reduced dramatically. Various optimization problems are selected to be solved by the algorithm. The experimental results show that the proposed approach successfully finds the optimum in problems with different types of interactions efficiently. Significant speedups are observed in the model building procedure as well.

Amin Nikanjam and Adel Rahmani. 利用双变量相关加速贝叶斯优化算法中的结构学习过程[J]. , 2012, 27(5): 1077-1090.

Amin Nikanjam and Adel Rahmani. Exploiting Bivariate Dependencies to Speedup Structure Learning in Bayesian Optimization Algorithm[J]. , 2012, 27(5): 1077-1090.

参考文献

[1] Larrañaga P, Lozano J A. Estimation of Distribution Algorithms:A New Tool for Evolutionary Computation. KluwerAcademic, 2002.
[2] Pelikan M, Goldberg D E, Cantu-Paz E. BOA: The Bayesianoptimization algorithm. In Proc. Genetic and Evolutionary Computation Conference, Orlando, Florida, USA, July 13-17,1999, pp.525-532.
[3] Mühlenbein H, Mahnig T. FDA-A scalable evolutionary algorithmfor the optimization of additively decomposed functions.Evolutionary Computation, 1999, 7(4): 353-376.
[4] Etxeberria R, Larrañaga P. Global optimization usingBayesian networks. In Proc. the 2nd Symposium on ArtificialIntelligence, La Habana, Cuba, July 15-17, 1999, pp.332-339.
[5] Pelikan M. Hierarchical Bayesian Optimization Algorithm:Toward a New Generation of Evolutionary Algorithm.Springer-Verlag, 2005.
[6] Mühlenbein H, Mahnig T. Evolutionary synthesis of Bayesiannetworks for optimization. In Advances in Evolutionary Syn-thesis of Intelligent Agents, Honavar V, Patel M, BalakrishnanK (eds.), MIT Press, 2001, pp.429-455.
[7] Soto M, Ochoa A, Acid S, Campos L M. Bayesian evolutionaryalgorithms based on simplified models. In Proc. the 2ndSymposium on Artificial Intelligence, La Habana, Cuba, July15-17, 1999, pp.360-367.
[8] Chen T, Tang K, Chen G, Yao X. Analysis of computationaltime of simple estimation of distribution algorithms. IEEETransactions on Evolutionary Computation, 2010, 14(1): 1-22.
[9] Sastry K, Pelikan M, Goldberg D E. Efficiency enhancementof estimation of distribution algorithms. In Scalable Opti-mization via Probabilistic Modeling: From Algorithms to Ap-plications, Pelikan M, Sastry K, Cantu-Paz E (eds.), Springer,2006, pp.161-185.
[10] Pelikan M, Sastry K, Goldberg D E. Sporadic model buildingfor efficiency enhancement of the hierarchical BOA. GeneticProgramming and Evolvable Machines, 2008, 9(1): 53-84.
[11] Dong W, Yao X. NichingEDA: Utilizing the diversity insidea population of EDAs for continuous optimization. In Proc.IEEE Congress on Evolutionary Computation, Hong Kong,China, June 1-6, 2008, pp.1260-1267.
[12] Dong W, Chen T, Tino P, Yao X. Scaling up estimation ofdistribution algorithms for continuous optimization. ArxivPreprint ArXiv: 1111.2221 v1, 2011.
[13] Dong W, Yao X. Unified eigen analysis on multivariate Gaussianbased estimation of distribution algorithms. InformationSciences, 2008, 178(15): 3000-3023.
[14] Luong H N, Nguyen H T T, Ahn C W. Entropy-based efficiencyenhancement techniques for evolutionary algorithms.Information Sciences, 2012, 188(1): 100-120.
[15] Howard R A, Matheson J E. Influence diagrams. In Readingson the Principles and Applications of Decision Analysis, SdgDecision Systems, 1981, pp.721-762.
[16] Pearl J. Probabilistic Reasoning in Intelligent Systems: Networksof Plausible Inference. Morgan Kaufmann, 1988.
[17] Chickering D M. Learning equivalence classes of Bayesiannetworkstructures. J. Machine Learning Research, 2002,2(3/1): 445-498.
[18] Chickering D M, Heckerman D, Meek C. Large-sample learningof Bayesian networks is NP-hard. J. Machine LearningResearch, 2004, 5(12/1): 1287-1330.
[19] Henrion M. Propagation of uncertainty in Bayesian networksby probabilistic logic sampling. In Proc. Uncertainty in Arti-ficial Intelligence, Seattle, USA, July 10-12, 1988, pp.149-163.
[20] Cano R, Sordo C, Gutiérrez J M. Applications of Bayesiannetworks in meteorology. In Advances in Bayesian Networks,Gámez M S, Salmerón J A (eds.), Springer, 2004, pp.309-327.
[21] Friedman N, Nachman I, Peér D. Learning Bayesian networkstructure from massive datasets: The “sparse candidate” algorithm.In Proc. Uncertainty in Artificial Intelligence,Stockholm, Sweden, July 30-August 1, 1999, pp.206-215.
[22] Tsamardinos I, Brown L E, Aliferis C F. The max-min hillclimbingBayesian network structure learning algorithm. Ma-chine Learning, 2006, 65(1): 31-78.
[23] Gámez J A, Mateo J L, Puerta J M. Learning Bayesian networksby hill climbing: Efficient methods based on progressiverestriction of the neighborhood. Data Mining and KnowledgeDiscovery, 2011, 22(1): 106-148.
[24] Yu T L, Goldberg D E, Yassine A, Chen Y P. Genetic algorithmdesign inspired by organizational theory: Pilot study ofa dependency structure matrix driven genetic algorithm. InProc. Artificial Neural Networks in Engineering, St. Louis,Missouri, USA, November 2-5, 2003, pp.327-332.
[25] Yu T L, Goldberg D E, Sastry K, Lima C F, Pelikan M. Dependencystructure matrix, genetic algorithms, and effectiverecombination. Evolutionary Computation, 2009, 17(4): 595-626.
[26] Yassine A, Joglekar N, Braha D, Eppinger S, Whitney D. Informationhiding in product development: The design churneffect. Research in Engineering Design, 2003, 14(3): 145-161.
[27] Nikanjam A, Sharifi H, Helmi B H, Rahmani A. Enhancingthe efficiency of genetic algorithm by identifying linkagegroups using DSM clustering. In Proc. IEEE Congresson Evolutionary Computation, Barcelona, Spain, July 18-23,2010, pp.1-8.
[28] Nikanjam A, Sharifi H, Rahmani A T. Efficient model buildingin competent genetic algorithms using DSM clustering.AI Communications, 2010, 24(3): 213-231.
[29] Duque T S P C, Goldberg D E. ClusterMI: Building probabilisticmodels using hierarchical clustering and mutual information.In Exploitation of Linkage Learning in EvolutionaryAlgorithms, Chen Y P (ed.), Springer, 2010, pp.123-137.
[30] Lu Q, Yao X. Clustering and learning Gaussian distributionfor continuous optimization. IEEE Transactions on Systems,Man, and Cybernetics, Part C: Applications and Reviews,2005, 35(2): 195-204.
[31] Aporntewan C, Chongstitvatana P. Building-block identificationby simultaneity matrix. Soft Computing, 2007, 11(6):541-548.
[32] Hauschild M, Pelikan M, Lima C F, Sastry K. Analyzingprobabilistic models in hierarchical BOA on traps and spinglasses. In Proc. Genetic and Evolutionary ComputationConference, London, England, July 7-11, 2007, pp.523-530.
[33] Goldberg D E, Sastry K. Genetic Algorithms: The Design ofInnovation (2nd edition), Springer, 2010.
[34] Munetomo M, Goldberg D E. Identifying linkage groups bynonlinearity/non-monotonicity detection. In Proc. Geneticand Evolutionary Computation Conference, Orlando, Florida,USA, July 13-17, 1999, pp.433-440.
[35] Yu T L. A matrix approach for finding extreme: Problemswith modularity, hierarchy and overlap [PhD Thesis]. Universityof Illinois at Urbana-Champaign, USA, 2006.
[36] Tsuji M, Munetomo M. Linkage analysis in genetic algorithms.In Computational Intelligence Paradigms: Innova-tive Applications, Springer, 2008, pp.251-279.
[37] Fischer K H, Hertz J A. Spin Glasses. Cambridge UniversityPress, 1991.
[38] Mühlenbein H, Mahnig T, Rodriguez A O. Schemata, distributionsand graphical models in evolutionary optimization.J. Heuristics, 1999, 5(2): 215-247.
[39] Santana R. Estimation of distribution algorithms withKikuchi approximations. Evolutionary Computation, 2005,13(1): 67-97.
[40] Monien B, Sudborough I H. Min cut is NP-complete for edgeweighted trees. Theoretical Computer Science, 1988, 58(1-3):209-229.
[41] Karshenas H, Nikanjam A, Helmi B H, Rahmani A T. Combinatorialeffects of local structures and scoring metrics inBayesian optimization algorithm. In Proc. World Summiton Genetic and Evolutionary Computation, Shanghai, China,June 12-14, 2008, pp.263-270.
[42] Ocenasek J, Schwarz J. The parallel Bayesian optimizationalgorithm. In Proc. European Symposium on ComputationalIntelligence, Kosice, Slovak Republic, August 30-September1, 2000, pp.61-67.
[43] Lima C F, Lobo F G, Pelikan M. From mating pool distributionsto model overfitting. In Proc. Genetic and Evolution-ary Computation Conference, Atlanta, GA, USA, July 12-16,2008, pp.431-438.
[44] Ackley D H. An empirical study of bit vector function optimization.In Genetic Algorithms and Simulated Annealing,Davies L (ed.), Morgan Kaufmann, 1987, pp.170-204.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed