We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 27 Issue 5
September  2012
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Amin Nikanjam, Adel Rahmani. Exploiting Bivariate Dependencies to Speedup Structure Learning in Bayesian Optimization Algorithm[J]. Journal of Computer Science and Technology, 2012, 27(5): 1077-1090. DOI: 10.1007/s11390-012-1285-1
Citation: Amin Nikanjam, Adel Rahmani. Exploiting Bivariate Dependencies to Speedup Structure Learning in Bayesian Optimization Algorithm[J]. Journal of Computer Science and Technology, 2012, 27(5): 1077-1090. DOI: 10.1007/s11390-012-1285-1
shu

Exploiting Bivariate Dependencies to Speedup Structure Learning in Bayesian Optimization Algorithm

  • School of Computer Engineering, Iran University of Science and Technology, Tehran 1684613114, Iran

More Information
  • Received Date: October 23, 2011
  • Revised Date: March 20, 2012
  • Published Date: September 04, 2012
    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.
    • FullText(HTML)
    • References (44)
  • [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.
    • Relative Articles

  • Related Articles

    [1]Teng-Yue Han, Peng-Fei Wang, Shao-Zhang Niu. Multimodal Interactive Network for Sequential Recommendation[J]. Journal of Computer Science and Technology, 2023, 38(4): 911-926. DOI: 10.1007/s11390-022-1152-7
    [2]Bo-Han Li, An-Man Zhang, Wei Zheng, Shuo Wan, Xiao-Lin Qin, Xue Li, Hai-Lian Yin. GRIP: A Group Recommender Based on Interactive Preference Model[J]. Journal of Computer Science and Technology, 2018, 33(5): 1039-1055. DOI: 10.1007/s11390-018-1846-z
    [3]Jing Wu, Paul L. Rosin, Xianfang Sun, Ralph R. Martin. Improving Shape from Shading with Interactive Tabu Search[J]. Journal of Computer Science and Technology, 2016, 31(3): 450-462. DOI: 10.1007/s11390-016-1639-1
    [4]Jun-Gang Xu, Yue Zhao, Jian Chen, Chao Han. A Structure Learning Algorithm for Bayesian Network Using Prior Knowledge[J]. Journal of Computer Science and Technology, 2015, 30(4): 713-724. DOI: 10.1007/s11390-015-1556-8
    [5]Concha Bielza, Juan A. Fern&aacutendez del Pozo, Pedro Larra&ntildeaga. Parameter Control of Genetic Algorithms by Learning and Simulation of Bayesian Networks —— A Case Study for the Optimal Ordering of Tables[J]. Journal of Computer Science and Technology, 2013, 28(4): 720-731. DOI: 10.1007/s11390-013-1370-0
    [6]Yang Li, Chang-Jun Hu, Xin Yao. Innovative Batik Design with an Interactive Evolutionary Art System[J]. Journal of Computer Science and Technology, 2009, 24(6): 1035-1047.
    [7]LI Yang, GUAN ZhiWei, DAI GuoZhong, REN XiangShi, HAN Yong. A Context-Aware Infrastructure for Supporting Applications with Pen-Based Interaction[J]. Journal of Computer Science and Technology, 2003, 18(3).
    [8]YANG Bo, ZHENG Fengzhou, WANG Dingxing, ZHENG Weimin. Interactive and Symbolic Data Dependence Analysis Based on Renges of Expressions[J]. Journal of Computer Science and Technology, 2002, 17(2).
    [9]LIANG Yongquan, SHI Zhongzhi. A Multimedia Synchronization Model Based on Timed Petri Net[J]. Journal of Computer Science and Technology, 1999, 14(3): 276-282.
    [10]Dong Yunmei. An Interactive Learning Algorithm for Acquisition of Concepts Represented as CFL[J]. Journal of Computer Science and Technology, 1998, 13(1): 1-8.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (13) PDF downloads (1595) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return