research-article

A multiset genetic algorithm for the optimization of deceptive problems

Authors:

António Manuel Rodrigues Manso,

Luís Miguel Parreira CorreiaAuthors Info & Claims

GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

Pages 813 - 820

https://doi.org/10.1145/2463372.2463471

Published: 06 July 2013 Publication History

Abstract

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 we present an adaptation of the mutation operator, multiset wave mutation (MWM), that explores the multiset representation to apply different mutation ratios to the same chromosome, and an adaptation of the replacement operator, multiset decimation replacement (MDR) that preserves multiset representation in the main population and helps MuGA to solve hard deceptive problems. Results obtained in different deceptive functions show that pairing both operators is a robust approach with a high success ratio in most of the problems.

References

[1]

J. H. Holland, Adaptation in Natural and Artificial Systems. University of Michigan, 1975.

[2]

T. BDack, F. Hoffmeister and H. P. Schwefel, A survey of evolution strategies, Belew, R., editor, Proc. Fourth Int. Conf. on Genetic Algorithms, pp 2--9, 1991.

[3]

D. B. Fogel, An analysis of evolutionary programming, Fogel and Atmar, vol 684, pp 43--51, 1992.

[4]

J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection, 1st ed. A Bradford Book, 1992.

Digital Library

[5]

T. Bäck, H. Schwefel and F. Informatik, Evolutionary Computation: An Overview, in Proceedings of IEEE International Conference on Evolutionary Computation, 1996, pp 20--29.

[6]

H. Mühlenbein and G. Paaß, From recombination of genes to the estimation of distributions I. Binary parameters, in Parallel Problem Solving from Nature -- PPSN IV, vol 1141, H.-M. Voigt, W. Ebeling, I. Rechenberg, e H.-P. Schwefel, Eds Springer Berlin / Heidelberg, 1996, pp 178--187.

Digital Library

[7]

M. Hauschild and M. Pelikan, An introduction and survey of estimation of distribution algorithms, Swarm and Evolutionary Computation, pp 111--128, 2011.

[8]

J. N. Aparício, L. Correia, and F. Moura-Pires, Populations are Multisets - PLATO, W. Banzhaf, J. Daida, A. Eiben, M. Garzon, V. Honavar, M. Jakiela, and R. Smith, eds., Proc. GECCO, vol Morgan Kaufmann, pp 1845--1850, 1999.

[9]

A. Manso and L. Correia, Genetic algorithms using populations based on multisets, L. Seabra Lopes, N. Lau, P. Mariano, L. Rocha, eds, vol EPIA 2009, pp 53--64, 2009.

[10]

A. Manso and L. Correia, Preservação da Diversidade Genética no Multiset Genetic Algorithm, in Congresso de Métodos Numéricos em Engenharia 2011, Coimbra, 2011.

[11]

A. Manso and L. Correia, A multiset genetic algorithm for real coded problems, in Proceedings of the 13th annual conference companion on Genetic and evolutionary computation - GECCO'11, Dublin, Ireland, 2011, p 153.

Digital Library

[12]

A. Manso and L. Correia, MuGA: multiset genetic algorithm, in Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, New York, NY, USA, 2011, pp 791--794.

Digital Library

[13]

R. Sivaraj and T. Ravichandran, A review of selection methods in genetic algorithm, International Journal of Engineering Science and Technology, vol 3, n 5, pp 3792--3797, 2011.

[14]

A. Otman and A. Jaafar, A Comparative Study of Adaptive Crossover Operators for Genetic Algorithms to Resolve the Traveling Salesman Problem. IJCA (0975--8887), 2011.

[15]

F. Herrera, M. Lozano and A. M. Sanchez, A taxonomy for the crossover operator for real-coded genetic algorithms: An experimental study, Int. J. Intell. Syst., vol 18, n 3, pp 309--338, Mar 2003.

[16]

W. Spears and V. Anand, A Study Of Crossover Operators In Genetic Programming. 1991.

[17]

O. Abdoun, J. Abouchabaka, and C. Tajani, Analyzing the Performance of Mutation Operators to Solve the Travelling Salesman Problem, arXiv:1203.3099, Mar 2012.

[18]

S. Droste, T. Jansen, and I. Wegener, On the analysis of the (1+1) evolutionary algorithm, Theoretical Computer Science, vol 276, n 1, pp 51--81, 2002.

Digital Library

[19]

M. Lozano, F. Herrera, and J. Cano, Replacement strategies to preserve useful diversity in steady-state genetic algorithms, Information Sciences, vol 178, n 23, pp 4421--4433, Dez 2008.

Digital Library

[20]

S. F. Galan and O. J. Mengshoel, Generalized crowding for genetic algorithms, in Proceedings of the 12th annual conference on Genetic and evolutionary computation, New York, NY, USA, 2010, pp 775--782.

Digital Library

[21]

E. L. Yu and P. N. Suganthan, Ensemble of niching algorithms, Information Sciences, vol 180, n 15, pp 2815--2833, Ago 2010.

Digital Library

[22]

J. Jayachandran and S. Corns, A comparative study of diversity in evolutionary algorithms, 2010, pp 1--7.

[23]

A. Manso and L. Correia, MITree - Multiset Indexed Tree, Congresso de Métodos Numéricos em Engenharia 2011, Coimbra, Portugal, 2011.

[24]

L. Spector, T. Helmuth, and K. Harrington, Fecundity and selectivity in evolutionary computation, in Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, New York, NY, USA, 2011, pp 129--130.

Digital Library

[25]

D. E. Goldberg, Simple Genetic Algorithms and the Minimal, Deceptive Problem, Genetic Algorithms and Simulated Annealing, vol L. Davis, editor, San Mateo, CA: Morgan Kaufmann, pp 74--88, 1987.

[26]

S. Yang, Adaptive group mutation for tackling deception in genetic search, WSEAS Transactions on Systems, vol 3, n 1, pp 107--112, 2004.

[27]

Y. Chen, J. Hu, K. Hirasawa, and S. Yu, Solving deceptive problems using a genetic algorithm with reserve selection, in IEEE Congress on Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence), 2008, pp 884--889.

[28]

M. W. Hauschild and M. Pelikan, Network crossover performance on NK landscapes and deceptive problems, in Proceedings of the 12th annual conference on Genetic and evolutionary computation, New York, NY, USA, 2010, pp 713--720.

Digital Library

[29]

M. Pelikan, D. E. Goldberg, and E. Cantu-Paz, BOA: The Bayesian Optimization Algorithm, 1999, pp 525--532.

[30]

L. D. Whitley, Fundamental Principles of Deception in Genetic Search, Foundations of genetic algorithms, vol 1, n 1980, pp 221--241, 1991.

[31]

G. Harik, Linkage learning via probabilistic modeling in the ECGA, Urbana, vol 51, n 61, p 801, 1999.

[32]

M. Pelikan and D. E. Goldberg, Escaping hierarchical traps with competent genetic algorithms, in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), 2001, pp 511--518.

[33]

S. Hill e C. O'Riordan, Examining the use of a non-trivial fixed genotype-phenotype mapping in genetic algorithms to induce phenotypic variability over deceptive uncertain landscapes, in 2011 IEEE Congress on Evolutionary Computation (CEC), 2011, pp 1404--1411.

Cited By

Gagnon RGosselin LPark SStratbücker SDecker S(2018)Comparison between two genetic algorithms minimizing carbon footprint of energy and materials in a residential buildingJournal of Building Performance Simulation10.1080/19401493.2018.150109512:2(224-242)Online publication date: 2-Aug-2018
https://doi.org/10.1080/19401493.2018.1501095
Cicirello V(2016)The Permutation in a Haystack Problem and the Calculus of Search LandscapesIEEE Transactions on Evolutionary Computation10.1109/TEVC.2015.247728420:3(434-446)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1109/TEVC.2015.2477284
Manso ACorreia LEsparcia-Alcázar A(2015)Parasite Diversity in Symbiogenetic Multiset Genetic AlgorithmProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739480.2754780(887-894)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739480.2754780
Show More Cited By

Index Terms

A multiset genetic algorithm for the optimization of deceptive problems
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

Parasite Diversity in Symbiogenetic Multiset Genetic Algorithm: Optimization of Large Binary Problems
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Symbiogenetic MuGA (SMuGA) is a co-evolutionary model exploiting the concept of symbiosis over the Multiset Genetic Algorithm (MuGA). It evolves two species: hosts that represent a solution to the problem, and parasites that represent part-solutions. ...
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 ...
A multiset genetic algorithm for real coded problems
GECCO '11: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation

The Multiset Genetic Algorithm (MuGA) was adapted to real coded problems, tested in benchmark functions, and compared to competitive algorithms. Genetic operators were adapted to take into account the multiset representation of the population, which is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

July 2013

1672 pages

ISBN:9781450319638

DOI:10.1145/2463372

Editor:
Christian Blum
IKERBASQUE and University of the Basque Country UPV/EHU, Spain
,
General Chair:
Enrique Alba
University of Malaga, Spain

Copyright © 2013 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

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '13

Sponsor:

SIGEVO

GECCO '13: Genetic and Evolutionary Computation Conference

July 6 - 10, 2013

Amsterdam, The Netherlands

Acceptance Rates

GECCO '13 Paper Acceptance Rate 204 of 570 submissions, 36%;

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
164
Total Downloads

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

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gagnon RGosselin LPark SStratbücker SDecker S(2018)Comparison between two genetic algorithms minimizing carbon footprint of energy and materials in a residential buildingJournal of Building Performance Simulation10.1080/19401493.2018.150109512:2(224-242)Online publication date: 2-Aug-2018
https://doi.org/10.1080/19401493.2018.1501095
Cicirello V(2016)The Permutation in a Haystack Problem and the Calculus of Search LandscapesIEEE Transactions on Evolutionary Computation10.1109/TEVC.2015.247728420:3(434-446)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1109/TEVC.2015.2477284
Manso ACorreia LEsparcia-Alcázar A(2015)Parasite Diversity in Symbiogenetic Multiset Genetic AlgorithmProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739480.2754780(887-894)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739480.2754780
Correia LManso A(2015)A Multiset Model of Multi-Species Evolution to Solve Big Deceptive ProblemsReticulate Evolution10.1007/978-3-319-16345-1_11(297-337)Online publication date: 10-Jul-2015
https://doi.org/10.1007/978-3-319-16345-1_11

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