Article

Anisotropic selection in cellular genetic algorithms

Authors:

David Simoncini,

Sébastien Verel,

Philippe Collard,

Manuel ClergueAuthors Info & Claims

GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

Pages 559 - 566

https://doi.org/10.1145/1143997.1144098

Published: 08 July 2006 Publication History

Get Access

Abstract

In this paper we introduce a new selection scheme in cellular genetic algorithms (cGAs). Anisotropic Selection (AS) promotes diversity and allows accurate control of the selective pressure. First we compare this new scheme with the classical rectangular grid shapes solution according to the selective pressure: we can obtain the same takeover time with the two techniques although the spreading of the best individual is different. We then give experimental results that show to what extent AS promotes the emergence of niches that support low coupling and high cohesion. Finally, using a cGA with anisotropic selection on a Quadratic Assignment Problem we show the existence of an anisotropic optimal value for which the best average performance is observed. Further work will focus on the selective pressure self-adjustment ability provided by this new selection scheme.

References

[1]

E. Alba and B. Dorronsoro. The exploration/exploitation tradeoff in dynamic cellular genetic algorithms. In IEEE transactions on Evolutionnary Computation, volume 9, pages 126--142, 2005.]]

Digital Library

Google Scholar

[2]

E. Alba and J. M. Troya. Cellular evolutionary algorithms: Evaluating the influence of ratio. In PPSN, pages 29--38, 2000.]]

Digital Library

Google Scholar

[3]

J. R. C. E. Nugent, T. E. Vollman. An experimental comparison of techniques for the assignment of techniques to locations. Operations Research, 16:150--173, 1968.]]

Digital Library

Google Scholar

[4]

W. Cedeño and V. R. Vemuri. On the use of niching for dynamic landscapes. IEEE International Conference on Evolutionary Computation, pages 1--6, 1997.]]

Crossref

Google Scholar

[5]

M. Giacobini, E. Alba, A. Tettamanzi, and M. Tomassini. Modeling selection intensity for toroidal cellular evolutionary algorithms. In GECCO, pages 3--11, 2004.]]

Crossref

Google Scholar

[6]

M. Giacobini, A. Tettamanzi, and M. Tomassini. Modelling selection intensity for linear cellular evolutionary algorithms. In P. L. et al., editor, Artificial Evolution, Sixth International Conference, Evolution Artificielle, EA 2003, Lecture Notes in Computer Science, pages 345--356, Marseille, France, October 2003. Springer.]]

Crossref

Google Scholar

[7]

D. E. Golberg and J. Richardson. Genetic algorithms with sharing for multimodal function optimization. International Conference on Genetic Algorithms, pages 41--49, 1987.]]

Digital Library

Google Scholar

[8]

D. E. Goldberg and K. Deb. A comparative analysis of selection schemes used in genetic algorithms. In FOGA, pages 69--93, 1990.]]

Google Scholar

[9]

K. A. D. Jong and J. Sarma. On decentralizing selection algorithms. In ICGA, pages 17--23, 1995.]]

Digital Library

Google Scholar

[10]

T. Koopmans and M. Beckmann. Assignment problems and the location of economic activities. Econometrica, 25(1):53--76, 1957.]]

Crossref

Google Scholar

[11]

V. V. Migkikh, A. P. Topchy, V. M. Kureichik, and A. Y. Tetelbaum. Combined genetic and local search algorithm for the quadratic assignment problem.]]

Google Scholar

[12]

B. Sareni and L. Krähenbühl. Fitness sharing and niching methods revisited. IEEE transactions on evolutionary computation, 2(3):1--9, 1998.]]

Digital Library

Google Scholar

[13]

J. Sarma and K. A. De Jong. An analysis of the effects of neighborhood size and shape on local selection algorithms. In PPSN, pages 236--244, 1996.]]

Digital Library

Google Scholar

[14]

P. Spiessens and B. Manderick. A massively parallel genetic algorithm: Implementation and first analysis. In ICGA, pages 279--287, 1991.]]

Google Scholar

Cited By

View all

Letras MMorales-Reyes ACumplido RMartínez-Peñaloza MFeregrino-Uribe C(2024)A novel partition strategy for efficient implementation of 3D Cellular Genetic AlgorithmsMicroprocessors & Microsystems10.1016/j.micpro.2023.104986104:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.micpro.2023.104986
Simoncini DZhang K(2019)Population-Based Sampling and Fragment-Based De Novo Protein Structure PredictionEncyclopedia of Bioinformatics and Computational Biology10.1016/B978-0-12-809633-8.20507-4(774-784)Online publication date: 2019
https://doi.org/10.1016/B978-0-12-809633-8.20507-4
Burguillo JDorronsoro BBurguillo J(2017)Optimization Models with Coalitional Cellular AutomataSelf-organizing Coalitions for Managing Complexity10.1007/978-3-319-69898-4_8(139-169)Online publication date: 14-Dec-2017
https://doi.org/10.1007/978-3-319-69898-4_8
Show More Cited By

Index Terms

Anisotropic selection in cellular genetic algorithms
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

An improved genetic algorithm with conditional genetic operators and its application to set-covering problem

The genetic algorithm (GA) is a popular, biologically inspired optimization method. However, in the GA there is no rule of thumb to design the GA operators and select GA parameters. Instead, trial-and-error has to be applied. In this paper we present an ...
Clustering using Cellular Genetic Algorithms
IJCCI 2015: Proceedings of the 7th International Joint Conference on Computational Intelligence

The goal of the clustering process is to find groups of similar patterns in multidimensional data. In this work,

the clustering problem is approached using cellular genetic algorithms. The population structure adopted in

the cellular genetic algorithm ...
Introduction to genetic algorithms
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

July 2006

2004 pages

ISBN:1595931864

DOI:10.1145/1143997

General Chair:
Mike Cattolico
Tiger Mountain Scientific, Inc., USA

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO06

Sponsor:

GECCO06: Genetic and Evolutionary Computation Conference

July 8 - 12, 2006

Washington, Seattle, USA

Acceptance Rates

GECCO '06 Paper Acceptance Rate 205 of 446 submissions, 46%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
13
Total Downloads

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

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Letras MMorales-Reyes ACumplido RMartínez-Peñaloza MFeregrino-Uribe C(2024)A novel partition strategy for efficient implementation of 3D Cellular Genetic AlgorithmsMicroprocessors & Microsystems10.1016/j.micpro.2023.104986104:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.micpro.2023.104986
Simoncini DZhang K(2019)Population-Based Sampling and Fragment-Based De Novo Protein Structure PredictionEncyclopedia of Bioinformatics and Computational Biology10.1016/B978-0-12-809633-8.20507-4(774-784)Online publication date: 2019
https://doi.org/10.1016/B978-0-12-809633-8.20507-4
Burguillo JDorronsoro BBurguillo J(2017)Optimization Models with Coalitional Cellular AutomataSelf-organizing Coalitions for Managing Complexity10.1007/978-3-319-69898-4_8(139-169)Online publication date: 14-Dec-2017
https://doi.org/10.1007/978-3-319-69898-4_8
Alba EArnold D(2014)Cellular genetic algorithmsProceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2598394.2605356(733-748)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2598394.2605356
Payne JGiacobini MMoore J(2013)Complex and dynamic population structuresSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-013-0994-x17:7(1109-1120)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1007/s00500-013-0994-x
Al-Naqi AErdogan AArslan T(2013)Adaptive three-dimensional cellular genetic algorithm for balancing exploration and exploitation processesSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-013-0990-117:7(1145-1157)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1007/s00500-013-0990-1
Dorronsoro BBurguillo JPeleteiro ABouvry P(2013)Evolutionary Algorithms Based on Game Theory and Cellular Automata with CoalitionsHandbook of Optimization10.1007/978-3-642-30504-7_19(481-503)Online publication date: 2013
https://doi.org/10.1007/978-3-642-30504-7_19
Foong HLeow SOng T(2012)Probabilistic selection in cellular genetic algorithm2012 8th International Conference on Natural Computation10.1109/ICNC.2012.6234715(688-692)Online publication date: May-2012
https://doi.org/10.1109/ICNC.2012.6234715
Vatanutanon JNoman NIba HLanzi P(2011)Polynomial selection scheme with dynamic parameter estimation in cellular genetic algorithmProceedings of the 13th annual conference on Genetic and evolutionary computation10.1145/2001576.2001734(1171-1178)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001576.2001734
Vatanutanon JNoman NIba H(2010)Polynomial Selection: A new way to tune selective pressure2010 Second World Congress on Nature and Biologically Inspired Computing (NaBIC)10.1109/NABIC.2010.5716313(597-602)Online publication date: Dec-2010
https://doi.org/10.1109/NABIC.2010.5716313
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.

Cited By

Index Terms

Recommendations

An improved genetic algorithm with conditional genetic operators and its application to set-covering problem

Clustering using Cellular Genetic Algorithms

Introduction to genetic algorithms