Multi-structure problems: Difficult model learning in discrete EDAs
Pages 3448 - 3454
Abstract
Decomposition to smaller sub-problems is a general approach in problem solving. Many of the real-world problems can be decomposed into a number of sub-problems which may be solved easier. Appropriate decomposition is a significant issue specially for optimization problems where the optimal solution is usually obtained by combining the solutions of sub-problems. Estimation of distribution algorithms (EDAs) are a type of evolutionary algorithms that learn a model of problem from the population of candidate solutions. This model is intended to capture the interactions between problem variables, thus facilitating problem decomposition and is used to generate new solutions. In this paper, a novel type of problems is presented that is designed to challenge the model building process in discrete EDAs. The main idea is to propose a set of problems that their candidate solutions can be simultaneously decomposed into different sub-problems. This means that the candidate solution of a problem may be interpreted by two or more different structure where only one is true, resulting in the optimal solution to that problem. Some of these decompositions or structures may be more likely according to the low-order statistics collected from the population of candidate solutions, but may not necessarily lead to the optimal solution. Learning the correct structure/decomposition is a challenge for the model building process in EDA. The experimental results show that the proposed problems are indeed difficult for EDAs even when expressive models such as Bayesian networks are used to capture the interactions in the problem.
References
[1]
S. Baluja. Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning. Technical Report CMU-CS-94–163, Carnegie-Mellon University, Pittsburgh PA, 1994.
[2]
S.-C. Chen and T.-L. Yu Difficulty of linkage learning in estimation of distribution algorithms. In Genetic and Evolutionary Computation Conference (GECCO‘09), pages 397–404. ACM, 2009.
[3]
C.- Y. Chuang and W.-L. Hsu. Multivariate multi-model approach for globally multimodal problems. In Genetic and Evolutionary Computation Conference (GECCO‘10), pages 311–318. ACM, 2010.
[4]
D. Coffin and R. Smith. The limitations of distribution sampling for linkage learning. In IEEE Congress on Evolutionary Computation (CEC‘07), pages 364–369. IEEE, 2007.
[5]
E. Correa and J. Shapiro. Model complexity vs. performance in the Bayesian optimization algorithm. Parallel Problem Solving from Nature-PPSN IX, 4193:998–1007, 2006. Lecture Notes In Computer Science
[6]
Y. Davidor. Epistasis variance: A viewpoint on GA-hardness. In Foundations of Genetic Algorithms (FOGA), volume 90, pages 23–25, 1990.
[7]
K. Deb and D. E. Goldberg. Analyzing deception in trap functions. In Foundations of Genetic Algorithms (FOGA), volume 2, pages 98–108, 1992.
[8]
C. Echegoyen, R. Santana, J. A. Lozano, and P. Larrañaga. The impact of exact probabilistic learning algorithms in EDAs based on Bayesian networks. In Linkage in Evolutionary Computation, pages 109–139.Springer 2008.
[9]
C. Echegoyen, Q. Zhang, A. Mendiburu, R. Santana, and J. A. Lozano. On the limits of effectiveness in estimation of distribution algorithms. In Proceedings of 2011 IEEE Congress on Evolutionary Computation (CEC), pages 1573–1580. IEEE, 2011.
[10]
R. Etxeberria and P. Larrañaga. Global optimization using Bayesian networks. In Second Symposium on Artificial Intelligence (CIMAF-99), pages 332–339, 1999.
[11]
G. Harik, F. Lobo, and D. Goldberg. The compact genetic algorithm. IEEE Transactions on Evolutionary Computation, 3(4):287–297, 1999.
[12]
G. R. Harik, F. G. Lobo, and K. Sastry Linkage learning via probabilistic modeling in the extended compact genetic algorithm (ECGA). In E. C.-P. Martin Pelikan, Kumara Sastry, editor, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, volume 33 of Studies in Computational Inteligence, chapter 3, pages 39–61.Springer 2006.
[13]
M. Hauschild and M. Pelikan. Advanced neighborhoods and problem difficulty measures. In Genetic and Evolutionary Computation Conference (GECCO), pages 625–632. ACM, 2011.
[14]
D. Iclanzan. Hierarchical allelic pairwise independent functions. In Genetic and Evolutionary Computation Conference (GECCO‘11), pages 633–640. ACM, 2011.
[15]
T. Jones and S. Forrest. Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In ICGA, volume 95, pages 184–192. Citeseer, 1995.
[16]
P. Larrañaga and J. A. Lozano, editors. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers Norwell, MA, USA, 2001.
[17]
F. G. Lobo, D. E. Goldberg, and M. Pelikan. Time complexity of genetic algorithms on exponentially scaled problems. Technical Report 61801, Illinois Genetic Algorithms Laboratory (IlliGAL), 2000.
[18]
G. Lu, J. Li, and X. Yao. Fitness landscapes and problem difficulty in evolutionary algorithms: From theory to applications. In Recent Advances in the Theory and Application of Fitness Landscapes, pages 133–152.Springer 2014.
[19]
H. Mühlenbein, T. Mahnig, and A. Ochoa Rodríguez. Schemata, distributions and graphical models in evolutionary optimization. Journal of Heuristics, 5(2):215–247, July 1999.
[20]
H. Mühlenbein and G. Paaß. From recombination of genes to the estimation of distributions I. Binary parameters. In H.-M. Voigt, W. Ebeling, I. Rechenberger, and H.-P. Schwefel, editors, Fourth International Conference on Parallel Problem Solving from Nature (PPSN IV), volume 1141 of Lecture Notes in Computer Science pages 178–187. Springer, September 1996.
[21]
M. Pelikan. Hierarchical Bayesian Optimization Algorithm: Toward a New Generation of Evolutionary Algorithms. Springer 2005.
[22]
M. Pelikan and D. E. Goldberg. Hierarchical problem solving and the Bayesian optimization algorithm. In Conference on Genetic and Evolutionary Computation (GECCO ‘00), pages 267–274.Morgan Kaufmann 2000.
[23]
M. Pelikan and D. E. Goldberg Hierarchical BOA solves Ising spin glasses and MAXSA T. In Genetic and Evolutionary Computation Conference (GECCO‘03), pages 1271–1282.Springer 2003.
[24]
M. Pelikan, D. E. Goldberg, and E. Cantú-Paz. BOA: The Bayesian optimization algorithm. In Conference on Genetic and Evolutionary Computation (GECCO ‘99), pages 525–532, Orlando, Florida, USA, July 1999.Morgan Kaufmann Publishers
[25]
M. Pelikan, M. Pelikan, D. Goldberg, and D. Goldberg. Escaping hierarchical traps with competent genetic algorithms. In Conference on Genetic and Evolutionary Computation (GECCO ‘01), pages 511–518.Morgan Kaufmann 2001.
[26]
K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master's thesis, University of Illinois at Urbana-Champaign, 2001.
[27]
H. Sharifi, A. Nikanjam, H. Karshenas, and N. Najimi. Complexity of model learning in EDAs: Multi-structure problems. In Conference Companion on Genetic and Evolutionary Computation, pages 55–56, New York, NY, USA, 2014. ACM.
Index Terms
- Multi-structure problems: Difficult model learning in discrete EDAs
Index terms have been assigned to the content through auto-classification.
Recommendations
Complexity of model learning in EDAs: multi-structure problems
GECCO Comp '14: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary ComputationMany of the real-world problems can be decomposed into a number of sub-problems for which the solutions can be found easier. However, proper decomposition of large problems remains a challenging issue, especially in optimization, where we need to find ...
Maintaining Diversity in EDAs for Real-Valued Optimisation Problems
FBIT '07: Proceedings of the 2007 Frontiers in the Convergence of Bioscience and Information TechnologiesA recent extension applicable to a wide range of discrete EDA algorithms, called Sampling-Mutation, has shown promise on a non-stationary problem, as well as on a hierarchical deceptive problem. In this paper we further the empirical exploration on ...
A framework for multi-model EDAs with model recombination
EvoApplications'11: Proceedings of the 2011 international conference on Applications of evolutionary computation - Volume Part IEstimation of Distribution Algorithms (EDAs) are evolutionary optimization methods that build models which estimate the distribution of promising regions in the search space. Conventional EDAs use only one single model at a time. One way to efficiently ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
5624 pages
Copyright © 2016.
Publisher
IEEE Press
Publication History
Published: 01 July 2016
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 01 Jan 2025