research-article

Analysis of estimation of distribution algorithms and genetic algorithms on NK landscapes

Author:

Martin PelikanAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 1033 - 1040

https://doi.org/10.1145/1389095.1389287

Published: 12 July 2008 Publication History

Abstract

This study analyzes performance of several genetic and evolutionary algorithms on randomly generated NK fitness landscapes with various values of n and k. A large number of NK problem instances are first generated for each n and k, and the global optimum of each instance is obtained using the branch-and-bound algorithm. Next, the hierarchical Bayesian optimization algorithm (hBOA), the univariate marginal distribution algorithm (UMDA), and the simple genetic algorithm (GA) with uniform and two-point crossover operators are applied to all generated instances. Performance of all algorithms is then analyzed and compared, and the results are discussed.

References

[1]

H. E. Aguirre and K. Tanaka. Genetic algorithms on nk-landscapes: Effects of selection, drift, mutation, and recombination. In G. R. Raidl et al., editors, Applications of Evolutionary Computing: EvoWorkshops 2003, pages 131--142, 2003.

Digital Library

[2]

L. Altenberg. NK landscapes. In T. Bäck, D. B. Fogel, and Z. Michalewicz, editors, Handbook of Evolutionary Computation, pages B2.7:5--10. Institute of Physics Publishing and Oxford University Press, Bristol, New York, 1997.

[3]

S. Baluja. Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning. Tech. Rep. No. CMU-CS-94-163, Carnegie Mellon University, Pittsburgh, PA, 1994.

Digital Library

[4]

P. A. N. Bosman and D. Thierens. Continuous iterated density estimation evolutionary algorithms within the IDEA framework. Workshop Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000), pages 197--200, 2000.

[5]

D. M. Chickering, D. Heckerman, and C. Meek. A Bayesian approach to learning Bayesian networks with local structure. Technical Report MSR-TR-97-07, Microsoft Research, Redmond, WA, 1997.

[6]

S.-S. Choi, K. Jung, and J. H. Kim. Phase transition in a random NK landscape model. pages 1241--1248, 2005.

Digital Library

[7]

N. Friedman and M. Goldszmidt. Learning Bayesian networks with local structure. In M. I. Jordan, editor, Graphical models, pages 421--459. MIT Press, Cambridge, MA, 1999.

Digital Library

[8]

Y. Gao and J. C. Culberson. An analysis of phase transition in NK landscapes. Journal of Artificial Intelligence Research (JAIR), 17:309--332, 2002.

Digital Library

[9]

D. E. Goldberg. Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading, MA, 1989.

Digital Library

[10]

G. R. Harik. Finding multimodal solutions using restricted tournament selection. Proceedings of the International Conference on Genetic Algorithms (ICGA-95), pages 24--31, 1995.

Digital Library

[11]

D. Heckerman, D. Geiger, and D. M. Chickering. Learning Bayesian networks: The combination of knowledge and statistical data. Technical Report MSR-TR-94-09, Microsoft Research, Redmond, WA, 1994.

Digital Library

[12]

J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, MI, 1975.

Digital Library

[13]

S. Kauffman. Adaptation on rugged fitness landscapes. In D. L. Stein, editor, Lecture Notes in the Sciences of Complexity, pages 527--618. Addison Wesley, 1989.

[14]

S. Kauffman. The origins of Order: Self-and selection in evolution. Oxford University Press, 1993.

[15]

P. Larrañaga and J. A. Lozano, editors. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer, Boston, MA, 2002.

[16]

H. Mühlenbein and G. Paaß. From recombination of genes to the estimation of distributions I. Binary parameters. Parallel Problem Solving from Nature, pages 178--187, 1996.

Digital Library

[17]

M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer, 2005.

[18]

M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 511--518, 2001.

[19]

M. Pelikan and D. E. Goldberg. Hierarchical BOA solves Ising spin glasses and maxsat. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003), II:1275--1286, 2003.

Digital Library

[20]

M. Pelikan, D. E. Goldberg, and F. Lobo. A survey of optimization by building and using probabilistic models. Computational Optimization and Applications, 21(1):5--20, 2002.

Digital Library

[21]

M. Pelikan, H. G. Katzgraber, and S. Kobe. Finding ground states of Sherrington-Kirkpatrick spin glasses with hierarchical BOA and genetic algorithms. MEDAL Report No. 2008004, Missouri Estimation of Distribution Algorithms Laboratory, University of Missouri-St. Louis, St. Louis, MO, 2008.

[22]

K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master's thesis, University of Illinois at Urbana-Champaign, Department of General Engineering, Urbana, IL, 2001.

[23]

A. H. Wright, R. K. Thompson, and J. Zhang. The computational complexity of N-K fitness functions. IEEE Transactions Evolutionary Computation, 4(4):373--379, 2000.

Digital Library

Cited By

Riveros MRojas-Morales NMontero EOchoa GLi XHandl J(2024)Understanding Search Trajectories in Parameter TuningProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654146(778-786)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654146
Canonne LDerbel BTsuji MSato M(2024)Large-scale and cooperative graybox parallel optimization on the supercomputer FugakuJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104921191:COnline publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2024.104921
Willemsen FSchoonhoven RFilipovič JTørring Jvan Nieuwpoort Rvan Werkhoven B(2024)A methodology for comparing optimization algorithms for auto-tuningFuture Generation Computer Systems10.1016/j.future.2024.05.021159(489-504)Online publication date: Oct-2024
https://doi.org/10.1016/j.future.2024.05.021
Show More Cited By

Index Terms

Analysis of estimation of distribution algorithms and genetic algorithms on NK landscapes

Recommendations

NK landscapes, problem difficulty, and hybrid evolutionary algorithms
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

This paper presents an experimental study of NK landscapes with the main focus on the relationship between (1) problem parameters, (2) various measures of problem difficulty of fitness landscapes, and (3) performance of hybrid evolutionary algorithms. ...
Performance of evolutionary algorithms on NK landscapes with nearest neighbor interactions and tunable overlap
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

This paper presents a class of NK landscapes with nearest-neighbor interactions and tunable overlap. The considered class of NK landscapes is solvable in polynomial time using dynamic programming; this allows us to generate a large number of random ...
Using holey fitness landscapes to counteract premature convergence in evolutionary algorithms
GECCO '08: Proceedings of the 10th annual conference companion on Genetic and evolutionary computation

Premature convergence is a persisting problem in evolutionary optimisation, in particular - genetic algorithms. While a number of methods exist to approach this issue, they usually require problem specific calibration or only partially resolve the issue,...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
290
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Riveros MRojas-Morales NMontero EOchoa GLi XHandl J(2024)Understanding Search Trajectories in Parameter TuningProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654146(778-786)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654146
Canonne LDerbel BTsuji MSato M(2024)Large-scale and cooperative graybox parallel optimization on the supercomputer FugakuJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104921191:COnline publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2024.104921
Willemsen FSchoonhoven RFilipovič JTørring Jvan Nieuwpoort Rvan Werkhoven B(2024)A methodology for comparing optimization algorithms for auto-tuningFuture Generation Computer Systems10.1016/j.future.2024.05.021159(489-504)Online publication date: Oct-2024
https://doi.org/10.1016/j.future.2024.05.021
Rojas-Morales NRiff M(2023)Opposite scoring: focusing the tuning process of evolutionary calibratorNeural Computing and Applications10.1007/s00521-023-08203-x35:13(9269-9283)Online publication date: 25-Jan-2023
https://doi.org/10.1007/s00521-023-08203-x
Santana RLiefooghe ADerbel BWagner M(2022)Boomerang-shaped neural embeddings for NK landscapesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528856(858-866)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528856
Rojas-Morales NRiff M(2021)Reducing the effort of Evolutionary Calibrator Using Opposite Information2021 IEEE Latin American Conference on Computational Intelligence (LA-CCI)10.1109/LA-CCI48322.2021.9769793(1-6)Online publication date: 2-Nov-2021
https://doi.org/10.1109/LA-CCI48322.2021.9769793
Cañadillas DValizadeh HKleissl JGonzález‐Díaz BGuerrero‐Lemus R(2021)EDA‐based optimized global control for PV inverters in distribution gridsIET Renewable Power Generation10.1049/rpg2.1203115:2(382-396)Online publication date: 12-Jan-2021
https://doi.org/10.1049/rpg2.12031
Scoczynski MDelgado MLüders ROliva DWagner MSung IEl Yafrani M(2021)Saving computational budget in Bayesian network-based evolutionary algorithmsNatural Computing10.1007/s11047-021-09849-zOnline publication date: 9-Mar-2021
https://doi.org/10.1007/s11047-021-09849-z
Probst MRothlauf F(2020)Harmless overfittingThe Journal of Machine Learning Research10.5555/3455716.345579421:1(2992-3022)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.5555/3455716.3455794
Rojas-Morales NRiff M(2020)A Practical Tuner based on Opposite Information2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185746(1-8)Online publication date: Jul-2020
https://doi.org/10.1109/CEC48606.2020.9185746
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten