More Web Proxy on the site http://driver.im/

article

Free access

Scalability problems of simple genetic algorithms

Author:

Dirk ThierensAuthors Info & Claims

Evolutionary Computation, Volume 7, Issue 4

Pages 331 - 352

https://doi.org/10.1162/evco.1999.7.4.331

Published: 01 December 1999 Publication History

Abstract

Scalable evolutionary computation has. become an intensively studied research topic in recent years. The issue of scalability is predominant in any field of algorithmic design, but it became particularly relevant for the design of competent genetic algorithms once the scalability problems of simple genetic algorithms were understood. Here we present some of the work that has aided in getting a clear insight in the scalability problems of simple genetic algorithms. Particularly, we discuss the important issue of building block mixing. We show how the need for mixing places a boundary in the GA parameter space that, together with the boundary from the schema theorem, delimits the region where the GA converges reliably to the optimum in problems of bounded difficulty. This region shrinks rapidly with increasing problem size unless the building blocks are tightly linked in the problem coding structure. In addition, we look at how straightforward extensions of the simple genetic algorithm---namely elitism, niching, and restricted mating are not significantly improving the scalability problems.

References

[1]

Bagly, J. D. (1967). The behaviour of adaptive systems which employ genetic and correlation algorithms. Dissertation Abstracts International, 28(12):510B.

[2]

Baluja, S. and Davies, S. (1997). Using optimal dependency-trees for combinatorial optimization: Learning the structure of the search space. Proceedings of the Eleventh International Conference on Machine Learning, pages 30-38, Morgan Kaufmann, San Mateo, California.

[3]

De Bonet, J. S., Isbell, C. L. and Viola, P. (1997). MIMIC. Finding optima by estimating probability densities. Advances in Neural Information Processing Systems. Volume 9, page 424, MIT Press, Cambridge, Massachusetts.

[4]

Deb, K. and Gotdberg, D. E. (1993). Analyzing deception in trap functions. In Whitley, D., editor, Proceedings of Foundations of Genetic Algorithms FOGA-II, pages 93-108, Morgan Kaufmann, San Mateo, California.

[5]

van Dijk, S., Thierens, D. and de Berg, M. (1999). On the design of genetic algorithms for geographical applications. In Banzhaf, W., Daida, J., Eiben, A., Garzon, M., Honovar, V., Jakiela, M. and Smith, R., editors, Proceedings of the Genetic and Evolutionary Computation Conference, pages 188- 195, Morgan Kaufmann, San Mateo, California.

[6]

Frantz, D. R. (1972). Non-linearities in genetic adaptive search. Dissertation Abstracts International, 3(11):5240B.

[7]

Goldberg, D. E. (1989). Genetic Algorithms in Search. Optimization, and Machine Learning. Addison-Wesley, Reading, Massachusetts.

[8]

Goldberg, D. E. (1998). The race, the hurdle, and the sweet spot: lessons from genetic algorithms for the automation of design innovation and creativity. IlliGAL Technical Report 98007, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, Illinois.

[9]

Goldberg, D. E. and Deb, K. (1991). A comparative analysis of selection schemes used in genetic algorithms. In Rawlings, G., editor, Proceedings of Foundations of Genetic Algorithms FOGA-I, pages 69-93, Morgan Kaufmann, San Mateo, California.

[10]

Goldberg, D. E., Deb, K., Kargupta, H. and Harik, G. (1993). Rapid, accurate optimization of difficult problems using fast messy genetic algorithms. In Forrest, S., editor, Proceedings of the Fifth International Conference on Genetic Algorithms ICGA-93, pages 56-64, Morgan Kaufmann, San Mateo, California.

[11]

Goldberg, D. E., Deb, K. and Thierens, D. (1993). Toward a better understanding of mixing in genetic algorithms. Journal of the Society for Instrumentation and Control Engineers, 32(1):10-16.

[12]

Goldberg D. E., Korb B. and Deb, K. (1989). Messy genetic algorithms revisited: motivation, analysis, and first results. Complex Systems, 3:493-530.

[13]

Harik, G. (1997). Learning linkage to efficiently solve problems of bounded difficulty using genetic algorithms. Doctoral dissertation, Department of Computer Science, University of Michigan, Ann Arbor, Michigan.

[14]

Harik, G., Cantú-Paz, E., Goldberg, D. E. and Miller, B. (1997). The gambler's ruin problem, genetic algorithms, and the sizing of populations. In Bäck, T., editor, Proceedings of tbe Fourth International Conference on Evolutionary Computation, pages 7-12, IEEE Press, Piscataway, New Jersey.

[15]

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

[16]

Kargupta, H. (1996). The gene expression messy genetic algorithm. Proceedings of the Third International Conference on Evolutionary Computation, pages 814-819, IEEE Press, Piscataway, New Jersey.

[17]

Kargupta, H. and Goldberg, D. E. (1996). SEARCH, blackbox optimization, and sample complexity. In Belew, R. and Vose, M., editors, Foundations of Genetk Algorithms, pages 91-324, Morgan Kaufmann, San Francisco, California.

[18]

Mahfoud, S. W. (1992). Crowding and preselection revisited. In Männer, R. and Manderick, B., editors, Proceedings of Parallel Problem Solving from Nature PPSN-II, pages 27-36, North-Holland, Amsterdam, The Netherlands.

[19]

Mitchell, T. (1982). Generalization as search. Artificial Intelligence, 18(2):203-226.

[20]

Mühlenbein, H. and Schlierkamp-Voosen, D. (1994). The science of breeding and its application to the breeder genetic algorithm. Evolutionary Computation, 1(4):335-360.

[21]

Mühlenbein, H. and Paaß, G. (1996). From recombination of genes to the estimation of distributions. I. Binary parameters. In Voigt, H. M., Ebeling, W., Rechenberg, I. and Schwefel, H.-P., editors, Proceedings of Parallel Problem Solving from Nature IV, pages 178-187, Springer-Verlag, Berlin, Germany.

[22]

Mühlenbein, H., Mahnig, T. and Rodriguez, A. O. (1998). Schemata, distributions, and graphical models in evolutionary optimization. Technical Report (submitted for publication). GMD, Germany.

[23]

Paredis, J. (1995). The symbiotic evolution of solutions and their representations. In Eshelman, L., editor, Proceedings of the Sixth International Conference on Genetic Algorithms, pages 359-365, Morgan Kaufmann, San Francisco, California.

[24]

Pelikan, M., Goldberg, D. E. and Cantú-Paz, E. (1999). BOA: the bayesian optimization algorithm. In Banzhaf, W. et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference, Volume 1, pages 525-532, Morgan Kaufmann, San Francisco, California.

[25]

Smith, J. and Fogarty, T. (1996). Recombination strategy adaptation via evolution of gene linkage. Proceedings of the IEEE International Conference on Evolutionary Computation, pages 826-831, IEEE Press, Piscataway, New Jersey.

[26]

Thierens, D. (1995). Analysis and Design of Genetic Algorithms. Doctoral Dissertation, Department of Electrical Engineering, Katholieke Universiteit Leuven, Belgium.

[27]

Thierens, D. and Gotdberg, D. E. (1993). Mixing in Genetic Algorithms. In Forrest, S., editor, Proceedings of the Fifth International Conference on Genetic Algorithms ICGA-93, pages 38-45, Morgan Kaufrnann, San Mateo, California.

[28]

Thierens, D. and Goldberg, D. E. (1994). Elitist Recombination: an integrated selection recombination GA. Proceedings of the IEEE World Congress on Computational Intelligence, Volume 1, pages 508-512, IEEE Service Center, Piscataway, New Jersey.

[29]

Thierens, D., Goldberg, D. E. and Pereira, A. G. (1998). Domino Convergence, Drift, and the Temporal-Salience Structure of Problems. Proceedings of the IEEE International Conference on Evolutionary, Computation, Volume 1, pages 535-540, IEEE Press, Piscataway, New Jersey.

[30]

Watanabe, S. (1969). Knowing and guessing, a quantitative study of inference and information. John Wiley and Sons, New York, New York.

[31]

Wolpert, D. H. and Macready, W. G. (1997). No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary, Computation, 1 (1):67-82.

Cited By

Hong HJiang MYen G(2024)Boosting scalability for large-scale multiobjective optimization via transfer weightsInformation Sciences: an International Journal10.1016/j.ins.2024.120607670:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.ins.2024.120607
Sellami KSaied M(2024)Extracting microservices from monolithic systems using deep reinforcement learningEmpirical Software Engineering10.1007/s10664-024-10547-430:1Online publication date: 12-Oct-2024
https://dl.acm.org/doi/10.1007/s10664-024-10547-4
Romanuke V(2023)Parallelization of the Traveling Salesman Problem by Clustering its Nodes and Finding the Best Route Passing through the CentroidsApplied Computer Systems10.2478/acss-2023-001928:2(189-202)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.2478/acss-2023-0019
Show More Cited By

Scalability problems of simple genetic algorithms
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

An improved class of real-coded Genetic Algorithms for numerical optimization

Over the last few decades, many improved Evolutionary Algorithms (EAs) have been proposed to tackle different types of optimization problems. Genetic Algorithm (GA) among other canonical algorithms have not shown consistent performance over a range of ...
Improved Genetic Algorithms to Solving Constrained Optimization Problems
CINC '09: Proceedings of the 2009 International Conference on Computational Intelligence and Natural Computing - Volume 01

The slow convergence speed and the lack of effective constraint handling strategies are the major concerns when applying genetic algorithms (Gas) to constrained optimization problem. An improved genetic algorithm was proposed by dividing population into ...
Self-adjusting the intensity of assortative mating in genetic algorithms

Mate selection plays a crucial role in both natural and artificial systems. While traditional Evolutionary Algorithms (EA) usually engage in random mating strategies, that is, mating chance is independent of genotypic or phenotypic distance between ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Evolutionary Computation

Evolutionary Computation Volume 7, Issue 4

Winter 1999

125 pages

ISSN:1063-6560

EISSN:1530-9304

Issue’s Table of Contents

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 01 December 1999

Published in EVOL Volume 7, Issue 4

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
177
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)2

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hong HJiang MYen G(2024)Boosting scalability for large-scale multiobjective optimization via transfer weightsInformation Sciences: an International Journal10.1016/j.ins.2024.120607670:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.ins.2024.120607
Sellami KSaied M(2024)Extracting microservices from monolithic systems using deep reinforcement learningEmpirical Software Engineering10.1007/s10664-024-10547-430:1Online publication date: 12-Oct-2024
https://dl.acm.org/doi/10.1007/s10664-024-10547-4
Romanuke V(2023)Parallelization of the Traveling Salesman Problem by Clustering its Nodes and Finding the Best Route Passing through the CentroidsApplied Computer Systems10.2478/acss-2023-001928:2(189-202)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.2478/acss-2023-0019
Guijt AThierens DAlderliesten TBosman PSilva SPaquete L(2023)The Impact of Asynchrony on Parallel Model-Based EAsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590406(910-918)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590406
Guijt AThierens DAlderliesten TBosman PWagner M(2022)Solving multi-structured problems by introducing linkage kernels into GOMEAProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528828(703-711)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528828
Omidvar MLi XYao X(2022)A Review of Population-Based Metaheuristics for Large-Scale Black-Box Global Optimization—Part IIEEE Transactions on Evolutionary Computation10.1109/TEVC.2021.313083826:5(802-822)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1109/TEVC.2021.3130838
Przewozniczek MKomarnicki M(2022)Empirical problem decomposition — the key to the evolutionary effectiveness in solving a large-scale non-binary discrete real-world problemApplied Soft Computing10.1016/j.asoc.2021.107864113:PAOnline publication date: 3-Jan-2022
https://dl.acm.org/doi/10.1016/j.asoc.2021.107864
Wittenberg DRothlauf FSchweim DCoello Coello C(2020)DAE-GPProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390180(1037-1045)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390180
Bosman PLuong NThierens DNeumann FSutton A(2016)Expanding from Discrete Cartesian to Permutation Gene-pool Optimal Mixing Evolutionary AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference 201610.1145/2908812.2908917(637-644)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908812.2908917
Feldt RPoulding SGay GAntoniol G(2015)Broadening the search in search-based software testingProceedings of the Eighth International Workshop on Search-Based Software Testing10.5555/2821339.2821341(1-7)Online publication date: 16-May-2015
https://dl.acm.org/doi/10.5555/2821339.2821341
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents