poster

Using multiple offspring sampling to guide genetic algorithms to solve permutation problems

Authors:

Antonio LaTorre,

José M. Peña,

Victor Robles,

Santiago MuelasAuthors Info & Claims

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

Pages 1119 - 1120

https://doi.org/10.1145/1389095.1389307

Published: 12 July 2008 Publication History

Get Access

Abstract

The correct choice of an evolutionary algorithm, a genetic representation for the problem being solved (as well as their associated variation operators) and the appropriate values for the parameters of the algorithm is a hard task and it is often considered as an optimization problem itself.

In this contribution, we propose a new theoretical formalism, called Multiple Offspring Sampling (MOS). This new technique combines different evolutionary approaches taking advantage of the benefits provided by each of them. MOS dynamically balances the participation of different mechanisms to spawn the new offspring population, according to the benefits provided by each of them in previous generations. This approach evaluates multiple offspring generation methods (for example different coding strategies), and configures appropriate sampling sizes.

This formalism has been applied to a well-known permutation problem, the traveling salesman problem (TSP). The results on several instances of this problem show that most of the combined techniques outperform the results obtained by single ones.

References

[1]

W. Banzhaf. The "molecular" traveling salesman. Biological Cybernetics, 64:7--14, 1990.

Digital Library

Google Scholar

[2]

L. Davis. Applying adaptive algorithms to epistatic domains. In Proceedings of the 9th IJCAI, pages 162--164, 1985.

Google Scholar

[3]

J. Holland. Adaptation in natural and artificial systems. University of Michigan Press, 1975.

Digital Library

Google Scholar

[4]

I. Oliver, D. Smith, and J. Holland. A study of permutation crossover operators on the traveling salesman problem. In Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, pages 224--230, Mahwah, NJ, USA, 1987. Lawrence Erlbaum Associates, Inc.

Digital Library

Google Scholar

Cited By

View all

Liang QPan JChu SKong LLi W(2024)A decomposition framework based on memorized binary search for large-scale optimization problemsInformation Sciences10.1016/j.ins.2024.121063(121063)Online publication date: Jun-2024
https://doi.org/10.1016/j.ins.2024.121063
Romanuke V(2024)Deep clustering of the traveling salesman problem to parallelize its solutionComputers & Operations Research10.1016/j.cor.2024.106548165(106548)Online publication date: May-2024
https://doi.org/10.1016/j.cor.2024.106548
Omidvar MLi XYao X(2022)A Review of Population-Based Metaheuristics for Large-Scale Black-Box Global Optimization—Part IIEEE Transactions on Evolutionary Computation10.1109/TEVC.2021.313083826:5(802-822)Online publication date: Oct-2022
https://doi.org/10.1109/TEVC.2021.3130838
Show More Cited By

Index Terms

Using multiple offspring sampling to guide genetic algorithms to solve permutation problems
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

Hybrid evolutionary algorithms for large scale continuous problems
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Evolutionary Algorithms (EAs) are powerful metaheuristics that can be applied to almost any optimization problem. However, different Evolutionary Algorithms own different search capabilities that make them more suitable for one or another optimization ...
Expanding from Discrete Cartesian to Permutation Gene-pool Optimal Mixing Evolutionary Algorithms
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

The recently introduced Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) family, which includes the Linkage Tree Genetic Algorithm (LTGA), has been shown to scale excellently on a variety of discrete, Cartesian-space, optimization problems. This ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

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: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

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

8
Total Citations
View Citations
225
Total Downloads

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

Reflects downloads up to 20 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liang QPan JChu SKong LLi W(2024)A decomposition framework based on memorized binary search for large-scale optimization problemsInformation Sciences10.1016/j.ins.2024.121063(121063)Online publication date: Jun-2024
https://doi.org/10.1016/j.ins.2024.121063
Romanuke V(2024)Deep clustering of the traveling salesman problem to parallelize its solutionComputers & Operations Research10.1016/j.cor.2024.106548165(106548)Online publication date: May-2024
https://doi.org/10.1016/j.cor.2024.106548
Omidvar MLi XYao X(2022)A Review of Population-Based Metaheuristics for Large-Scale Black-Box Global Optimization—Part IIEEE Transactions on Evolutionary Computation10.1109/TEVC.2021.313083826:5(802-822)Online publication date: Oct-2022
https://doi.org/10.1109/TEVC.2021.3130838
Sato YOku YFukuda MArnold D(2014)Applying GA with local search by taking hamming distances into consideration to credit erasure processing problemsProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2576768.2598229(1183-1190)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2576768.2598229
Latorre APeña JMuelas SFreitas A(2010)Learning hybridization strategies in evolutionary algorithmsIntelligent Data Analysis10.5555/1839514.183951914:3(333-354)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.5555/1839514.1839519
Ortiz-Bayliss JOzcan EParkes ATerashima-Marin H(2010)Mapping the performance of heuristics for Constraint SatisfactionIEEE Congress on Evolutionary Computation10.1109/CEC.2010.5585965(1-8)Online publication date: Jul-2010
https://doi.org/10.1109/CEC.2010.5585965
LaTorre APeña JMuelas SPascual C(2009)Quality measures to adapt the participation in MOSProceedings of the Eleventh conference on Congress on Evolutionary Computation10.5555/1689599.1689716(888-895)Online publication date: 18-May-2009
https://dl.acm.org/doi/10.5555/1689599.1689716
LaTorre APena JMuelas SPascual C(2009)Quality measures to adapt the participation in MOS2009 IEEE Congress on Evolutionary Computation10.1109/CEC.2009.4983039(888-895)Online publication date: May-2009
https://doi.org/10.1109/CEC.2009.4983039

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.

Cited By

Index Terms

Recommendations

Hybrid evolutionary algorithms for large scale continuous problems

Expanding from Discrete Cartesian to Permutation Gene-pool Optimal Mixing Evolutionary Algorithms

An improved class of real-coded Genetic Algorithms for numerical optimization