research-article

Among-site rate variation: adaptation of genetic algorithm mutation rates at each single site

Authors:

Fatemeh Vafaee,

Peter C. Nelson,

Tanya Y. Berger-WolfAuthors Info & Claims

GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

Pages 863 - 870

https://doi.org/10.1145/2576768.2598216

Published: 12 July 2014 Publication History

Abstract

This paper is concerned with proposing an elitist genetic algorithm which makes use of a new mutation scheme aimed to tackle both explorative and exploitative responsibilities of genetic operators. The proposed mutation scheme follows an approach similar to motif representation in biology, to derive the underlying pattern of highly-fit solutions discovered so far. This pattern is then used to derive mutation rates specified for every site along the encoded solutions. The site-specific rates are amended for every individual to balance the required explorative and exploitative power. The Markov chain model of the proposed method is also derived and used to analyze its convergence properties.

References

[1]

T. Back and M. Schutz. Intelligent mutation rate control in canonical genetic algorithms. In Foundations of Intelligent Systems, Springer, pages 158--167, 1996.

Digital Library

[2]

H. G. Beyer. On the “explorative power” of ES/EP-like algorithms. Proc. of the 7th Annual Conf. on Evolutionary Programming, Lecture Notes in Computer Science. Springer, Berlin, 1998.

Digital Library

[3]

S. Bottcher et al. Optimal fixed and adaptive mutation rates for the leadingones problem parallel problem solving from nature. In Proc. of the 11th international Conf. on Parallel Problem Solving from Nature (PPSN XI), Springer, 2010.

Digital Library

[4]

J. Cervantes and C. R. Stephens. Limitations of existing mutation rate heuristics and how a rank GA overcomes them. IEEE Trans. on Evolutionary Computation, 13(2):369--397, 2009.

Digital Library

[5]

M. K. Das and H.-K. Dai. A survey of DNA motif finding algorithms. BMC Bioinformatics, page 8(Suppl 7):S21, 2007.

[6]

E. David et al. Finite Markov chain analysis of genetic algorithms. In Grefensttete 1987 (Ed.), ICGA89, pages 1 -- 8, 1987.

Digital Library

[7]

T. E. Davis and J. C. Principe. A simulated annealing like convergence theory for the simple genetic algorithm. In: R.K. Belew, L.B. Booker (Eds.), ICGA91, pages 174--181, 1991.

[8]

K. A. DeJong. Analysis of the behavior of a class of genetic adaptive systems. Ph.D. thesis, University of Michigan, Ann Arbor, MI, 1975.

[9]

K. A. DeJong, W. M. Spears, and D. F. Gordon. Using Markov chains to analyze GAFOs. In Foundations of Genetic Algorithms 3, pages 115--137, 1995.

[10]

A. Eiben et al. Parameter control in evolutionary algorithms. IEEE Trans. on Evolutionary Computation, 3(2):124--141, July 1999.

Digital Library

[11]

A. E. Eiben and C. A. Schipper. On evolutionary exploration and exploitation. Fundamenta Informaticae, 35:35--50, 1998.

Digital Library

[12]

L. J. Fogel. Evolving artificial intelligence. Ph.D. dissertation, Univ. of California, San Diego, 1992.

Digital Library

[13]

W. Hordijk and B. Manderick. The usefulness of recombination. In Proc. of the 3rd Int. Conf. on Artif. Life, 929:908--919, 1995.

Digital Library

[14]

X. B. Hu and S. F. Wu. A self-adaptive genetic algorithm based on fuzzy mechanism. IEEE Congress on Evolutionary Computation, pages 4646--4652, 2007.

[15]

M. Iosifescu. Finite Markov Processes and Their Applications. Wiley, 1980.

[16]

J. Koljonen and J. T. Alander. Effects of population size and relative elitism on optimization speed and reliability of genetic algorithms. In Proc. of the 9th Scand. Conf. on Artif. Intel., pages 25--27, 2006.

[17]

T. Kotzing et al. How crossover helps in pseudo-boolean optimization. In Proc. of the 13th annual Conf. on Genetic and evolutionary computation (GECCO 11), ACM, 2011.

Digital Library

[18]

R. Li et al. On the log-normal self-adaptation of the mutation rate in binary search spaces. In Proc. of the 13th annual Conf. on Genetic and evolutionary computation (GECCO 11), ACM, 2011.

Digital Library

[19]

L. Lin and M. Gen. Auto-tuning strategy for evolutionary algorithms: balancing between exploration and exploitation. Soft Computing, Springer, 13:157--168, 2009.

Digital Library

[20]

F. Nadi and A. T. Khader. A parameter-less genetic algorithm with customized crossover and mutation operators. In Proc. of the Genetic and Evolutionary Computation (GECCO 2011).

Digital Library

[21]

F. Neumann and M. Theile. How crossover speeds up evolutionary algorithms for the multi-criteria all-pairs-shortest-path problem. In Proc. of the 11th international Conf. on Parallel Problem Solving from Nature (PPSN XI), Springer, 2010.

Digital Library

[22]

A. Nix and M. D. Vose. A Markov chain analysis on a genetic algorithm. Annals of Mathematics and Artificial Intelligence, 5:79--88, 1992.

[23]

J. N. Richter et al. Ignoble trails-where crossover is provably harmful. In Proc. of the 10th international Conf. on Parallel Problem Solving from Nature (PPSN X), Springer, 2008.

Digital Library

[24]

G. Rudolph. Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kovac, Hamburg, Germany.

[25]

G. Rudolph. Massively parallel simulated annealing and its relation to evolutionary algorithms. Evolutionary Computation, 4(1):361--383, 1993.

Digital Library

[26]

G. Rudolph. Convergence analysis of canonical genetic algorithms. IEEE Trans. on Neural Networks, 5(1):96--101, 1994.

Digital Library

[27]

J. Smith and T. Fogarty. Self adaptation of mutation rates in a steady state genetic algorithm. In Proc. of congress on evolutionary computation, pages 318--323, 1996.

[28]

W. M. Spears. Evolutionary algorithms, the role of mutation and recombination. Natural Computing, Springer-Verlag, Berlin, 2000.

Digital Library

[29]

D. Sudholt. Crossover is provably essential for the ising model on trees. In Proc. of the 7th annual Conf. on Genetic and evolutionary computation (GECCO 05), ACM, 2005.

Digital Library

[30]

J. Suzuki. A Markov chain analysis on simple genetic algorithms. IEEE Trans. on Sys., Man, and Cyber., 25(4):655--659, 1995.

[31]

D. L. Swofford et al. Phylogenetic inference. Sinauer Associates, Massachusetts.

[32]

S. Tsutsui et al. A real coded genetic algorithm with an explorer and an exploiter populations. In Proc. of the 73th Int. Con. on GAs, pages 238--245, 1997.

[33]

F. Vafaee and P. C. Nelson. An explorative and exploitative mutation scheme. In Proc. of IEEE Conf. on Evolutionary Computation, 2010.

[34]

M. D. Vose and G. E. Liepins. Punctuated equilibria in genetic search. Complex Systems, 5:31--44, 1991.

[35]

S. Y. Yuen and C. K. Chow. A genetic algorithm that adaptively mutates and never revisits. IEEE Trans. on Evolutionary Computation, 13(2):454--472, April 2009.

Digital Library

Cited By

Zhang WFang WSun JChen Q(2020)Learning Bayesian Networks Structures with an Effective Knowledge-driven GA2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185884(1-8)Online publication date: Jul-2020
https://doi.org/10.1109/CEC48606.2020.9185884
Contaldi CVafaee FNelson P(2019)Bayesian network hybrid learning using an elite-guided genetic algorithmArtificial Intelligence Review10.1007/s10462-018-9615-552:1(245-272)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10462-018-9615-5
Contaldi CVafaee FNelson PBosman P(2017)The role of crossover operator in bayesian network structure learning performanceProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071240(769-776)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071240
Show More Cited By

Index Terms

Among-site rate variation: adaptation of genetic algorithm mutation rates at each single site
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
  2. Machine learning
    1. Learning paradigms
    2. Machine learning approaches
      1. Markov decision processes
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Markov decision processes

Recommendations

Optimizing genetic operator rates using a markov chain model of genetic algorithms
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

This work is concerned with proposing a robust framework for optimizing operator rates of simple Genetic Algorithms (GAs) during a GA run. The suggested framework is built upon a formerly proposed GA Markov chain model to estimate the optimal values of ...
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 ...
Limitations of existing mutation rate heuristics and how a rank GA overcomes them

Using a set of different search metrics and a set of model landscapes we theoretically and empirically study how "optimal" mutation rates for the simple genetic algorithm (SGA) depend not only on the fitness landscape, but also on population size and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

July 2014

1478 pages

ISBN:9781450326629

DOI:10.1145/2576768

Editor-in-chief:
Christian Igel
Ruhr University of Bochum, University of Copenhagen
,
General Chair:
Dirk V. Arnold
Dalhousie University

Copyright © 2014 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 the author(s) 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

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '14

Sponsor:

SIGEVO

GECCO '14: Genetic and Evolutionary Computation Conference

July 12 - 16, 2014

BC, Vancouver, Canada

Acceptance Rates

GECCO '14 Paper Acceptance Rate 180 of 544 submissions, 33%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
148
Total Downloads

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

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang WFang WSun JChen Q(2020)Learning Bayesian Networks Structures with an Effective Knowledge-driven GA2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185884(1-8)Online publication date: Jul-2020
https://doi.org/10.1109/CEC48606.2020.9185884
Contaldi CVafaee FNelson P(2019)Bayesian network hybrid learning using an elite-guided genetic algorithmArtificial Intelligence Review10.1007/s10462-018-9615-552:1(245-272)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10462-018-9615-5
Contaldi CVafaee FNelson PBosman P(2017)The role of crossover operator in bayesian network structure learning performanceProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071240(769-776)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071240
Vafaee FTuran GNelson PBerger-Wolf T(2014)Balancing the exploration and exploitation in an adaptive diversity guided genetic algorithm2014 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2014.6900257(2570-2577)Online publication date: Jul-2014
https://doi.org/10.1109/CEC.2014.6900257

View Options

Get Access

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.

Media

Figures

Other

Tables

View Table of Contents