Effective Structure Learning for Estimation of Distribution Algorithms via L1-Regularized Bayesian Networks

Estimation of distribution algorithms (EDAs), as an extension of genetic algorithms, samples new solutions from the probabilistic model, which characterizes the distribution of promising solutions in the search space at each generation. This paper introduces and evaluates a novel estimation of a dis...

Full description

Saved in:
Bibliographic Details
Published in:International journal of advanced robotic systems 2013-01, Vol.10 (1)
Main Authors: Xu, Hua, Yang, Jiadong, Jia, Peifa, Ding, Yi
Format: Article
Language:English
Subjects:
Accuracy
Automatic control
Bayesian analysis
Complexity
Genetic algorithms
Machine learning
Networks
Optimization
Optimization algorithms
Probabilistic models
Probability
Random variables
Regression analysis
Statistical analysis
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Estimation of distribution algorithms (EDAs), as an extension of genetic algorithms, samples new solutions from the probabilistic model, which characterizes the distribution of promising solutions in the search space at each generation. This paper introduces and evaluates a novel estimation of a distribution algorithm, called L1-regularized Bayesian optimization algorithm, L1BOA. In L1BOA, Bayesian networks as probabilistic models are learned in two steps. First, candidate parents of each variable in Bayesian networks are detected by means of L1-regularized logistic regression, with the aim of leading a sparse but nearly optimized network structure. Second, the greedy search, which is restricted to the candidate parent-child pairs, is deployed to identify the final structure. Compared with the Bayesian optimization algorithm (BOA), L1BOA improves the efficiency of structure learning due to the reduction and automated control of network complexity introduced with L1-regularized learning. Experimental studies on different types of benchmark problems show that L1BOA not only outperforms BOA when no prior knowledge about problem structure is available, but also achieves and even exceeds the best performance of BOA that applies explicit controls on network complexity. Furthermore, Bayesian networks built by L1BOA and BOA during evolution are analysed and compared, which demonstrates that L1BOA is able to build simpler, yet more accurate probabilistic models.
ISSN:1729-8806
1729-8814
DOI:10.5772/54672