research-article

Rank based variation operators for genetic algorithms

Authors:

Jorge Cervantes,

Christopher Rhodes StephensAuthors Info & Claims

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

Pages 905 - 912

https://doi.org/10.1145/1389095.1389271

Published: 12 July 2008 Publication History

Abstract

We show how and why using genetic operators that are applied with probabilities that depend on the fitness rank of a genotype or phenotype offers a robust alternative to the Simple GA and avoids some questions of parameter tuning without having to introduce an explicit encoded self-adaptation mechanism. We motivate the algorithm by appealing to previous theoretic analysis that show how different landscapes and population states require different mutation rates to dynamically optimize the balance between exploration and exploitation. We test the algorithm on a range of model landscapes where we can see under what circumstances this Rank GA is likely to outperform the Simple GA and how it outperforms standard heuristics such as 1/N. We try to explain the reasons behind this behaviour.

References

[1]

J.J. Grefenstette, Optimisation of Control Parameters for Genetic Algorithms, IEEE Trans SMC, 16(1), 122--128 (1986).]]

Digital Library

[2]

T. Bäck, Optimal Mutation Rates in Genetic Search. In Proceedings of ICGA 5, ed. S. Forrest, 2--8, Morgan Kaufmann (1993).]]

Digital Library

[3]

J. Cervantes, C. R. Stephens, "Optimal" mutation rates for genetic search. Proceedings of Genetic and Evolutionary Computation Conference (GECCO) 06, pp 1313--1320, Maarten Keijzer et. al. (2006).]]

Digital Library

[4]

J. Cervantes, C. R. Stephens, A Rank Proportional Generic Genetic Algorithm. Lecture Series on Computer and Computational Sciences, Volume 7, 2006, pp 71--74. Brill Academic Publishers.]]

[5]

H. Mühlenbein, How Genetic Algorithms Really Work: Mutation and Hill Climbing, PPSN II, ed.s B. Männer and R. Manderick, 15--25, North Holland (1992).]]

[6]

T. Bäck, Self-adaptation in Genetic Algorithms, In Proceedings of 1st European Conference on Artificial Life, 263--271 MIT Press (1991).]]

[7]

J. Hesser and R. Männer, Towards an Optimal Mutation Probability for Genetic Algorithms, LNCS 496, ed. H.P. Schwefel, Springer Verlag (1991).]]

Digital Library

[8]

T.C. Fogarty, Varying the Probability of Mutation in the Genetic Algorithm, ICGA 3, ed. J.D. Schaffer, 104--109, Morgan-Kaufmann (1989).]]

Digital Library

[9]

C.R. Stephens, I. Garcia Olmedo, J. Mora Vargas and H. Waelbroeck, Self-Adaptation in Evolving Systems, Artificial Life, Vol. 4, Issue 2, 183--201 (1998).]]

Digital Library

[10]

J.E. Smith and T.C. Fogarty, Self Adaptation of Mutation Rates in a Steady State Genetic Algorithm, Proceedings of CEC, 318 -- 323, IEEE Press (1996).]]

[11]

G. Ochoa, I. Harvey and H. Buxton, Error Thresholds and their Relation to Optimal Mutation Rates. In D. Floreano, J-D. Nicoud, and F. Mondada (Eds.) ECAL'99, Lecture Notes in Artificial Intelligence 1674, pp 54--63, Springer-Verlag, Berlin (1999).]]

Digital Library

[12]

G. Ochoa, Setting the Mutation Rate: Scope and Limitations of the 1/L Heuristics, GECCO-2002, pp 315--322, Morgan Kaufmann, San Francisco, CA (2002).]]

[13]

G. Ochoa, Error Thresholds in Genetic Algorithms. Evolutionary Computation, MIT Press (in press).]]

Digital Library

[14]

M. Srinivas, Lait M. Patnaik. Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Transactions on Systems, Man and Cybernetics, 24(4):656--667, April 1994.]]

[15]

M. Sewell, J. Samarabandu, R. Rodrigo, and K. McIsaac. The Rank-scaled Mutation Rate for Genetic Algorithms. International Journal of Information Technology, Volume 3 Number 1, 2006.]]

[16]

H. Hoos, T. Stützle. Evaluating Las Vegas Algorithms: Pitfalls and Remedies. Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, UAI-98 pages 238--245, Morgan Kaufmann Publishers, San Francisco CA, 1998.]]

Digital Library

[17]

H. Ishibuchi and Y. Shibata. A Similarity-Based Mating Scheme for Evolutionary Multiobjective Optimization. E.Cantú-Paz et al.(Eds.):GECCO 2003, LNCS 2723, pp.1065--1076,2003. Copyright Springer Verlag Berlin Heidelberg 2003.]]

Digital Library

[18]

H. Ishibuchi and K. Narukawa. Recombination of similar parents in EMO algorithms. Lecture Notes in Computer Science 3410:Evolutionary Multi-Criterion Optimization, pp.265--279, Springer, Berlin, March 2005.]]

Digital Library

[19]

G. Chakraborty, K. Hoshi. Rank Based Crossover - A new technique to improve the speed and Quality of convergence in GA. Proceedings of the 1999 Congress on Evolutionary Computation, CEC 99.]]

Cited By

Lara-Caballero ACervantes-Ojeda JGómez-Fuentes M(2024)Novel Approaches to the Minimum Identifying Code Problem Using Enhanced Genetic AlgorithmsAdvances in Soft Computing10.1007/978-3-031-75543-9_8(97-110)Online publication date: 17-Oct-2024
https://doi.org/10.1007/978-3-031-75543-9_8
Cervantes-Ojeda JGómez-Fuentes MFresán-Figueroa J(2023)Applying Genetic Algorithms to Validate a Conjecture in Graph Theory: The Minimum Dominating Set ProblemAdvances in Computational Intelligence10.1007/978-3-031-47765-2_20(271-282)Online publication date: 9-Nov-2023
https://doi.org/10.1007/978-3-031-47765-2_20
Doerr BGieβen CWitt CYang J(2019)The ($$1+\lambda $$1+ý) Evolutionary Algorithm with Self-Adjusting Mutation RateAlgorithmica10.1007/s00453-018-0502-x81:2(593-631)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00453-018-0502-x
Show More Cited By

Index Terms

Rank based variation operators for genetic algorithms
1. Applied computing
2. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

Simultaneously Applying Multiple Mutation Operators in Genetic Algorithms

The mutation operation is critical to the success of genetic algorithms since it diversifies the search directions and avoids convergence to local optima. The earliest genetic algorithms use only one mutation operator in producing the next generation. ...
Three interconnected parameters for genetic algorithms
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

When an optimization problem is encoded using genetic algorithms, one must address issues of population size, crossover and mutation operators and probabilities, stopping criteria, selection operator and pressure, and fitness function to be used in ...
Improving genetic algorithms performance via deterministic population shrinkage
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Despite the intuition that the same population size is not needed throughout the run of an Evolutionary Algorithm (EA), most EAs use a fixed population size. This paper presents an empirical study on the possible benefits of a Simple Variable Population ...

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

8
Total Citations
View Citations
294
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lara-Caballero ACervantes-Ojeda JGómez-Fuentes M(2024)Novel Approaches to the Minimum Identifying Code Problem Using Enhanced Genetic AlgorithmsAdvances in Soft Computing10.1007/978-3-031-75543-9_8(97-110)Online publication date: 17-Oct-2024
https://doi.org/10.1007/978-3-031-75543-9_8
Cervantes-Ojeda JGómez-Fuentes MFresán-Figueroa J(2023)Applying Genetic Algorithms to Validate a Conjecture in Graph Theory: The Minimum Dominating Set ProblemAdvances in Computational Intelligence10.1007/978-3-031-47765-2_20(271-282)Online publication date: 9-Nov-2023
https://doi.org/10.1007/978-3-031-47765-2_20
Doerr BGieβen CWitt CYang J(2019)The ($$1+\lambda $$1+ý) Evolutionary Algorithm with Self-Adjusting Mutation RateAlgorithmica10.1007/s00453-018-0502-x81:2(593-631)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00453-018-0502-x
Flores DCervantes J(2011)Rank Based Evolution of Real Parameters on Noisy Fitness FunctionsProceedings of the 2011 10th Mexican International Conference on Artificial Intelligence10.1109/MICAI.2011.40(72-76)Online publication date: 26-Nov-2011
https://dl.acm.org/doi/10.1109/MICAI.2011.40
Tiwari SFadel GDeb K(2011)AMGA2: improving the performance of the archive-based micro-genetic algorithm for multi-objective optimizationEngineering Optimization10.1080/0305215X.2010.49154943:4(377-401)Online publication date: Apr-2011
https://doi.org/10.1080/0305215X.2010.491549
Cervantes JSanchez MGonzalez P(2010)Emerging traits in the application of an evolutionary algorithm to a scalable bioinformatics problemIEEE Congress on Evolutionary Computation10.1109/CEC.2010.5585961(1-8)Online publication date: Jul-2010
https://doi.org/10.1109/CEC.2010.5585961
Oliveto PLehre PNeumann F(2009)Theoretical analysis of rank-based mutationProceedings of the Eleventh conference on Congress on Evolutionary Computation10.5555/1689599.1689791(1455-1462)Online publication date: 18-May-2009
https://dl.acm.org/doi/10.5555/1689599.1689791
Oliveto PLehre PNeumann F(2009)Theoretical analysis of rank-based mutation - combining exploration and exploitation2009 IEEE Congress on Evolutionary Computation10.1109/CEC.2009.4983114(1455-1462)Online publication date: May-2009
https://doi.org/10.1109/CEC.2009.4983114

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