research-article

Adaptation of expansion rate for real-coded crossovers

Authors:

Youhei Akimoto,

Shigenobu KobayashiAuthors Info & Claims

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Pages 739 - 746

https://doi.org/10.1145/1569901.1570004

Published: 08 July 2009 Publication History

Abstract

Premature convergence is one of the most notable obstacles that GAs face with. Once it happens, GAs cannot generate candidate solutions globally and the solutions are finally captured by local minima. To overcome it, we propose a mechanism that indirectly controls the variety of the population. It is realized by adapting the expansion rate parameter of crossovers, which determines the variance of the crossover distribution. The resulting algorithm is called adaptation of expansion rate (AER). The performance of the proposed methods is compared to an existing GA on several benchmark functions including functions whose landscape have ridge or multimodal structure. On these functions, existing GAs are likely to lead to premature convergence. The experimental result shows our approach outperforms the existing one on deceptive functions without disturbing the performance on comparatively easy problems.

References

[1]

D. H. Ackley. An empirical study of bit vector function optimization. Genetic Algorithms and Simulated Annealing, 1:170--204, 1987.

[2]

Y. Akimoto, R. Hasada, J. Sakuma, I. Ono, and S. Kobayashi. Generation alternation model for real-coded ga using multi-parent: Proposal and evaluation of just generation gap (JGG). In Proceedings of the 19th SICE Symposium on Decentralized Autonomous Systems, pages 341--346, 2007. In Japanese.

[3]

Y. Akimoto, J. Sakuma, I. Ono, and S. Kobayashi. Functionally specialized CMA-ES: A modification of CMA-ES based on the specialization of the functions of covariance matrix adaptation and step size adaptation. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2008, pages 479--486. ACM, 2008.

Digital Library

[4]

K. Deb, A. Anand, and D. Joshi. A computationally efficient evolutionary algorithm for real-parameter optimization. Evolutionary Computation, 10:371--395, 2002.

Digital Library

[5]

L. Eshelman. Real-coded genetic algorithms and interval-schemata. Foundations of Genetic Algorithms, 2:187--202, 1993.

[6]

L. J. Eshelman. The chc adaptive search algorithm: How to have safe search when engaging in nontraditional genetic recombination. Foundations of Genetic Algorithms, pages 265--283, 1991.

[7]

L. J. Eshelman, K. E. Mathias, and J. D. Schaffer. Crossover operator biases: Exploiting the population distribution. In Proceedings of the 7th International Conference on Genetic Algorithms, pages 354--361, 1997.

[8]

D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison Wsley Publishing Company Inc., 1989.

Digital Library

[9]

J. Grahl, P. A. N. Bosman, and F. Rothlauf. The correlation-triggered adaptive variance scaling idea. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2006, pages 397--404. ACM, 2006.

Digital Library

[10]

N. Hansen. The CMA evolution strategy: a comparing review. In Towards a new evolutionary computation. Advances on estimation of distribution algorithms, pages 75--102. Springer, 2006.

[11]

D. A. Harville. MATRIX ALGEBRA FROM A STATISTICIAN'S PERSPECTIVE. Springer-Verlag, 2008.

[12]

H. Kita, I. Ono, and S. Kobayashi. Theoretical analysis of the unimodal normal distribution crossover for real-coded genetic algorithms. In Proceedings of the IEEE Congress on Evolutionary Computation, pages 529--534, 1998.

[13]

H. Kita, I. Ono, and S. Kobayashi. Multi-parental extension of the unimodal normal distribution crossover for real-coded genetic algorithms. In Proceedings of the IEEE Congress on Evolutionary Computation, pages 1581--1587, 1999.

[14]

H. Kita and M. Yamamura. A function specialization hypothesis for designing genetic algorithms. In Proceedings of the IEEE Congress on Systems, Man and Cybernetics, pages 579--584, 1999.

[15]

S. Kobayashi. The frontiers of real-coded genetic algorithms. Transactions of the Japanese Society for Artificial intelligence, 24(1):147--162, 2009. In Japanese.

[16]

N. Mori, J. Yoshida, H. Tamaki, H. Kita, and Y. Nishikawa. A thermodynamical selection rule for the genetic algorithm. In Proceedings of the IEEE Congress on Evolutionary Computation, pages 188--192, 1995.

[17]

I. Ono, H. Kita, and S. Kobayashi. A robust real-coded genetic algorithm using unimodal normal distribution crossover augmented by uniform crossover: Effects of self-adaptation of crossover probabilities. In Proceedings of the Genetic and Evolutionary Computation Conference(GECCO 1999), 13-17 July 1999, Orlando, Florida, USA, pages 496--503. Morgan Kaufmann, 1999.

[18]

I. Ono and S. Kobayashi. A real-coded genetic algorithm for function optimization using unimodal normal distribution crossover. In Proceedings of the 7th International Conference on Genetic Algorithms, pages 246--253, 1997.

[19]

A. Ostermeier, A. Gawelczyk, and N. Hansen. Step-size adaptation based on non-local use of selection information. In Parallel Problem Solving from Nature -- PPSN III, pages 189--198. Springer, 1994.

Digital Library

[20]

A. I. Oyman, H.-G. Beyer, and H.-P. Schwefel. Analysis of the (1, λ)-es on the parabolic ridge. Evolutionary Computation, 8(3):249--265, 2000.

Digital Library

[21]

A. I. Oyman, H.-G. Beyer, and H.-P. Schwefel. Analysis of the (μ/μ, λ)-es on the parabolic ridge. Evolutionary Computation, 8(3):267--289, 2000.

Digital Library

[22]

J. Sakuma and S. Kobayashi. Extrapolation-directed crossover for real-coded ga: Overcoming deceptive phenomena by extrapolative search. In Proceedings of the IEEE Congress on Evolutionary Computation, pages 655--662, 2001.

[23]

J. Sakuma and S. Kobayashi. Latent variable crossover for k-tablet structures and its application to lens design problems. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2005, pages 1347--1353. ACM, 2005.

Digital Library

[24]

H. Satoh, M. Yamamura, and S. Kobayashi. Minimal generation gap model for GAs considering both exploration and exploitation. In Proceedings of IIZUKA'96, pages 494--497, 1996.

[25]

H. Someya. Theoretical parameter value for appropriate population variance of the distribution of children in real-coded ga. In Proceedings of the IEEE Congress on Evolutionary Computation: CEC 2008 (IEEE World Congress on Computational Intelligence: WCCI 2008), pages 2722-- 2729, 2008.

[26]

H. Someya and M. Yamamura. A robust real-coded evolutionary algorithm with toroidal search space conversion. Soft Computing--A Fusion of Foundations, Methodologies and Applications, 9(4):254--269, 2005.

Digital Library

[27]

G. Syswerda. A study of reproduction in generational and steady-state genetic algorithms. Foundations of Genetic Algorithms, pages 94--101, 1991.

[28]

O. Takahashi, H. Kita, and S. Kobayashi. A real-coded genetic algorithm using distance dependent alternation model for complex function optimization. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2000, pages 219--226. Morgan Kaufmann, 2000.

[29]

D. Thirens and D. E. Goldberg. Elitist recombination: An integrated selection recombination ga. In Proceedings of the IEEE Congress on Evolutionary Computation, pages 508--512, 1994.

[30]

S. Tsutsui. Sampling bias and search space boundary extension in real coded genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2000, pages 211--218. Morgan Kaufmann, 2000.

[31]

S. Tsutsui, M. Yamamura, and T. Higuchi. Multi-parent recombination with simplex crossover in real coded genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 1999, pages 657--664. Morgan Kaufmann, 1999.

[32]

A. Tuson and P. Ross. Cost based operator rate adaptation. In Parallel Problem Solving from Nature -- PPSN IV, pages 461--469. Springer, 1996.

Digital Library

Cited By

Tanabe RIshibuchi HAuger AStützle T(2019)Non-elitist evolutionary multi-objective optimizers revisitedProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321754(612-619)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321754
Obata TKurahashi S(2019)A Research of Variable Selection Method within A Framework of Real-coded Genetic Algorithm2019 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2019.8790346(3388-3395)Online publication date: Jun-2019
https://doi.org/10.1109/CEC.2019.8790346
Obata TKurahashi S(2019)A Study of New Variable Selection Method Within a Framework of Real-Coded Genetic AlgorithmNew Frontiers in Artificial Intelligence10.1007/978-3-030-31605-1_4(50-64)Online publication date: 11-Oct-2019
https://doi.org/10.1007/978-3-030-31605-1_4
Show More Cited By

Index Terms

Adaptation of expansion rate for real-coded crossovers
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
  2. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Recommendations

Two-Loop Real-Coded Genetic Algorithms with Adaptive Control of Mutation Step Sizes

Genetic algorithms are adaptive methods based on natural evolution that may be used for search and optimization problems. They process a population of search space solutions with three operations: selection, crossover, and mutation. Under their initial ...
Hybridizing adaptive and non-adaptive mutation for cooperative exploration of complex multimodal search space
ACST'07: Proceedings of the third conference on IASTED International Conference: Advances in Computer Science and Technology

One of the most efficient Real-Coded Genetic Algorithms (RCGAs) for function optimization currently is the G3-PCX (Parent-Centric Crossover) algorithm. However, its performance for solving complex multimodal problems with highly deceptive fitness ...
Multithreaded Parallel Dual Population Genetic Algorithm (MPDPGA) for unconstrained function optimizations on multi-core system

Various problems viz. population diversity problem, premature convergence problem and curse of dimensionality problem, are associated with Genetic Algorithm (GA). Dual Population GA (DPGA) helps to provide additional population diversity to the main ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

July 2009

2036 pages

ISBN:9781605583259

DOI:10.1145/1569901

General Chair:
Franz Rothlauf
University of Mainz, Germany

Copyright © 2009 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: 08 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO09

Sponsor:

GECCO09: Genetic and Evolutionary Computation Conference

July 8 - 12, 2009

Québec, Montreal, Canada

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
237
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tanabe RIshibuchi HAuger AStützle T(2019)Non-elitist evolutionary multi-objective optimizers revisitedProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321754(612-619)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321754
Obata TKurahashi S(2019)A Research of Variable Selection Method within A Framework of Real-coded Genetic Algorithm2019 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2019.8790346(3388-3395)Online publication date: Jun-2019
https://doi.org/10.1109/CEC.2019.8790346
Obata TKurahashi S(2019)A Study of New Variable Selection Method Within a Framework of Real-Coded Genetic AlgorithmNew Frontiers in Artificial Intelligence10.1007/978-3-030-31605-1_4(50-64)Online publication date: 11-Oct-2019
https://doi.org/10.1007/978-3-030-31605-1_4
Uemura KOno I(2016)AEGA: A New Real-Coded Genetic AlgorithmTaking Account of ExtrapolationJournal of Advanced Computational Intelligence and Intelligent Informatics10.20965/jaciii.2016.p042920:3(429-437)Online publication date: 19-May-2016
https://doi.org/10.20965/jaciii.2016.p0429
Someya H(2013)Striking a Mean- and Parent-Centric Balance in Real-Valued Crossover OperatorsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2012.220025517:6(737-754)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1109/TEVC.2012.2200255
Uemura KNakashima NNagata YOno I(2013)A new real-coded genetic algorithm for implicit constrained black-box function optimization2013 IEEE Congress on Evolutionary Computation10.1109/CEC.2013.6557920(2887-2894)Online publication date: Jun-2013
https://doi.org/10.1109/CEC.2013.6557920
Komori AMaki YNakatsui MOno IOkamoto M(2012)Efficient Numerical Optimization Algorithm Based on New Real-Coded Genetic Algorithm, AREX + JGG, and Application to the Inverse Problem in Systems BiologyApplied Mathematics10.4236/am.2012.33020503:10(1463-1470)Online publication date: 2012
https://doi.org/10.4236/am.2012.330205
Takahashi K(2012)Remarks on Servo Controller Using Quantum Neural Network with Qubit Neurons2012 Spring Congress on Engineering and Technology10.1109/SCET.2012.6341959(1-4)Online publication date: May-2012
https://doi.org/10.1109/SCET.2012.6341959
Someya H(2012)Theoretical basis of parameter tuning for finding optima near the boundaries of search spaces in real-coded genetic algorithmsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-011-0732-116:1(23-45)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1007/s00500-011-0732-1
Someya H(2011)Theoretical Analysis of Phenotypic Diversity in Real-Valued Evolutionary Algorithms With More-Than-One-Element ReplacementIEEE Transactions on Evolutionary Computation10.1109/TEVC.2010.208366815:2(248-266)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1109/TEVC.2010.2083668
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