research-article

Voronoi-initializated island models for solving real-coded deceptive problems

Authors:

Santiago Muelas,

José M. Peña,

Víctor Robles,

Antonio LaTorreAuthors Info & Claims

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

Pages 993 - 1000

https://doi.org/10.1145/1389095.1389282

Published: 12 July 2008 Publication History

Abstract

Deceptive problems have always been considered difficult for Genetic Algorithms. To cope with this characteristic, the literature has proposed the use of Parallel Genetic Algorithms (PGAs), particularly multi-population island-based models. Although the existence of multiple populations encourages population diversity, these problems are still difficult to solve. This paper introduces a new initialization mechanism for each of the populations of the islands based on Voronoi cells. In order to analyze the results, a series of different experiments using several real-value deceptive problems and a set of representative parameters (migration ratio, migration frequency and connectivity) have been chosen. The results obtained suggest that the Voronoi initialization method improves considerably the performance obtained with a traditionally uniform random initialization.

References

[1]

F. Aurenhammer. Voronoi diagrams, a survey of a fundamental geometric data structure. ACM Comput. Surv., 23:345--405, 1991.

Digital Library

[2]

T. C. Belding. The distributed genetic algorithm revisited. In Proceedings of the Sixth ICGA, pages 114--121. Morgan Kaufmann, 1995.

Digital Library

[3]

H. Bersini, M. Dorigo, S. Langerman, G. Seront, and L. Gambardella. Results of the first international contest on evolutionary optimisation (1st iceo). In ICEC, pages 611--615, 1996.

[4]

H. Beyer and K. Deb. On self-adaptive features in real-parameter evolutionary algorithms. IEEE TEC, 5(3):250--270, 2001.

Digital Library

[5]

E. Cantú-Paz. Efficient and accurate parallel genetic algorithms. Kluwer Academic Publishers, 2001.

Digital Library

[6]

D. Dasgupta. Handling deceptive problems using a different genetic search. In ICEC, pages 807--811, 1994.

[7]

H. de Garis. Genetic programming: artificial nervous systems artificial embryos and embryological electronics. In PPSN - Proceedings of 1st Workshop, volume 496, pages 117--123. Springer-Verlag, Berlin, Germany, 1-3 1991.

Digital Library

[8]

D. Goldberg. Genetic Algorithms and Simulated Annealing, chapter Simple Genetic Algorithms and the Minimal Deceptive Problem, pages 74--88. Morgan Kaufmann, 1987.

[9]

D. E. Goldberg. Real-coded genetic algorithms, virtual alphabets, and blocking. Complex Systems, 5:139--167, 1991.

[10]

D. E. Goldberg, M. Pelikan, and S. Tsutsui. Getting the best of both worlds: Discrete and continuous genetic and evolutionary algorithms in concert. Information Sciences, 156(3-4):147--171, 2003.

Digital Library

[11]

J. Grefensette. Genetic Algorithms and Simulated Annealing, chapter Incorporating problem specific knowledge into genetic algorithms, pages 42--46. Morgan Kauffmann Publishers, 1987.

[12]

F. Herrera, M. Lozano, and A. Sánchez. A taxonomy for the crossover operator for real-coded genetic algorithms. an experimental study. International Journal of Intelligent Systems, 18(3):309--338, 2003.

[13]

J. Holland. Cohort GAs and hyperplane-defined functions. Evolutionary Computation, 8(4):372--391, 2000.

Digital Library

[14]

L. Kallel and M. Schoenauer. Alternative random initialization in genetic algorithms. In Proceedings of the 7th ICGA, pages 268--275, 1997.

[15]

J. R. Koza and D. Andre. Parallel genetic programming on a network of transputers. Technical report, 1995.

Digital Library

[16]

J.-P. Li, M. E. Balazs, G. T. Parks, and J. P. Clarkson. A species conserving genetic algorithm for multimodal function optimization. Evol. Comput., 10(3):207--234, 2002.

Digital Library

[17]

K. Ohkura and K. Ueda. An extended framework for overcoming premature convergence. In Proceedings of the 7th ICGA, pages 260--267, 1997.

[18]

H. Pei and E. Goodman. A comparison of cohort genetic algorithms with canonical serial and island-model distributed GA's. In GECCO'01, pages 501--510, 2001.

[19]

C. Petty and M. Leuze. A theoretical investigation of a parallel genetic algorithm. In Proc. 3rd ICGA, pages 398--405, 1989.

Digital Library

[20]

M. Saska, M. Hess, and K. Schilling. Voronoi strains: a spline path planning algorithm for complex environments. In Proceedings of the 25th IASTED International Multi-Conference, pages 498--502, 2007. ACTA Press.

Digital Library

[21]

I. Sekaj. Robust parallel genetic algorithms with re-initialisation. In PPSN, pages 411--419, 2004.

[22]

Z. Skolicki and K. De Jong. The influence of migration sizes and intervals on island models. In GECCO '05, pages 1295--1302. ACM Press, 2005.

Digital Library

[23]

Z. Skolicki and K. A. D. Jong. Improving evolutionary algorithms with multi-representation island models. In PPSN, pages 420--429, 2004.

[24]

P. A. Whigham and G. Dick. A voronoi-based distributed genetic algorithm. In Fifteenth Annual Colloquium of the Spatial Information Research Centre, 2003.

[25]

D. Whitley, S. Rana, and R. Heckendorn. The island model genetic algorithm: On separability, population size and convergence. Journal of Computing and Information Technology, 7:33--47, 1999.

[26]

L. D. Whitley. Fundamental principles of deception in genetic search. In Foundations of genetic algorithms, pages 221--241. Morgan Kaufmann, 1991.

[27]

D. Wyatt and H. Lipson. Finding building blocks through eigenstructure adaptation. In GECCO'03, page 207, 2003.

Digital Library

Cited By

Abdul Halim ADas SIsmail IAbdul Halim ADas SIsmail I(2025)Location, Size, and CapacityInto a Deeper Understanding of Evolutionary Computing: Exploration, Exploitation, and Parameter Control10.1007/978-3-031-75577-4_1(1-152)Online publication date: 18-Jan-2025
https://doi.org/10.1007/978-3-031-75577-4_1
Alba ELuque GNesmachnow S(2012)Parallel metaheuristics: recent advances and new trendsInternational Transactions in Operational Research10.1111/j.1475-3995.2012.00862.x20:1(1-48)Online publication date: 13-Aug-2012
https://doi.org/10.1111/j.1475-3995.2012.00862.x

Index Terms

Voronoi-initializated island models for solving real-coded deceptive problems
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

An analysis of multi-chromosome GAs in deceptive problems
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

This paper discusses a new approach to using GAs to solve deceptive fitness landscapes by incorporating mechanisms to control the convergence direction instead of simply increasing the population diversity. In order to overcome some of the difficulties ...
Using behavioral exploration objectives to solve deceptive problems in neuro-evolution
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Encouraging exploration, typically by preserving the diversity within the population, is one of the most common method to improve the behavior of evolutionary algorithms with deceptive fitness functions. Most of the published approaches to stimulate ...
A multiset genetic algorithm for the optimization of deceptive problems
GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

MuGA is an evolutionary algorithm (EA) that represents populations as multisets, instead of the conventional collection. Such representation can be explored to adapt genetic operators in order to increase performance in difficult problems. In this paper ...

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

2
Total Citations
View Citations
148
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Abdul Halim ADas SIsmail IAbdul Halim ADas SIsmail I(2025)Location, Size, and CapacityInto a Deeper Understanding of Evolutionary Computing: Exploration, Exploitation, and Parameter Control10.1007/978-3-031-75577-4_1(1-152)Online publication date: 18-Jan-2025
https://doi.org/10.1007/978-3-031-75577-4_1
Alba ELuque GNesmachnow S(2012)Parallel metaheuristics: recent advances and new trendsInternational Transactions in Operational Research10.1111/j.1475-3995.2012.00862.x20:1(1-48)Online publication date: 13-Aug-2012
https://doi.org/10.1111/j.1475-3995.2012.00862.x

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