research-article

Injection, Saturation and Feedback in Meta-Heuristic Interactions

Authors:

Krzysztof Nowak,

Daniel HennesAuthors Info & Claims

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Pages 1167 - 1174

https://doi.org/10.1145/2739480.2754729

Published: 11 July 2015 Publication History

Abstract

Meta-heuristics have proven to be an efficient method of handling difficult global optimization tasks. A recent trend in evolutionary computation is the use of several meta-heuristics at the same time, allowing for occasional information exchange among them in hope to take advantage from the best algorithmic properties of all. Such an approach is inherently parallel and, with some restrictions, has a straight forward implementation in a heterogeneous island model.

We propose a methodology for characterizing the interplay between different algorithms, and we use it to discuss their performance on real-parameter single objective optimization benchmarks. We introduce the new concepts of feedback, saturation and injection, and show how they are powerful tools to describe the interplay between different algorithms and thus to improve our understanding of the internal mechanism at work in large parallel evolutionary set-ups.

References

[1]

David H. Wolpert and William G. Macready. No free lunch theorems for optimization. Evolutionary Computation, IEEE Transactions on, 1(1):67--82, 1997.

Digital Library

[2]

Rainer Storn and Kenneth Price. Differential evolution--a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization, 11(4):341--359, 1997.

Digital Library

[3]

Kennedy James and Eberhart Russell. Particle swarm optimization. In Proceedings of 1995 IEEE International Conference on Neural Networks, pages 1942--1948, 1995.

[4]

Nikolaus Hansen and Andreas Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary computation, 9(2):159--195, 2001.

Digital Library

[5]

Nikolaus Hansen, Sibylle D. Müller, and Petros Koumoutsakos. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolutionary Computation, 11(1):1--18, 2003.

Digital Library

[6]

Tianjun Liao and Thomas Stuetzle. Benchmark results for a simple hybrid algorithm on the CEC 2013 benchmark set for real-parameter optimization. In Luis Gerardo de la Fraga, editor, 2013 IEEE Conference on Evolutionary Computation, volume 1, pages 1938--1944, Cancun, Mexico, June 20--23 2013.

[7]

A. Kai Qin, Vicky Ling Huang, and Ponnuthurai N. Suganthan. Differential evolution algorithm with strategy adaptation for global numerical optimization. Evolutionary Computation, IEEE Transactions on, 13(2):398--417, 2009.

Digital Library

[8]

Anne Auger and Nikolaus Hansen. A restart CMA evolution strategy with increasing population size. In Evolutionary Computation, 2005. The 2005 IEEE Congress on, volume 2, pages 1769--1776. IEEE, 2005.

[9]

T. Vinkó, D. Izzo, and F. Pinna. Learning the best combination of solvers in a distributed global optimization environment. Proceedings of Advances in Global Optimization: Methods and Applications (AGO), Mykonos, Greece, pages 13--17, 2007.

[10]

Edmund Burke, Graham Kendall, Jim Newall, Emma Hart, Peter Ross, and Sonia Schulenburg. Hyper-heuristics: An emerging direction in modern search technology. In Handbook of metaheuristics, pages 457--474. Springer, 2003.

[11]

Erick Cantú-Paz. Topologies, migration rates, and multi-population parallel genetic algorithms. In Proc. Genetic and Evolutionary Computation Conference (GECCO'99), volume 1, pages 91--98, 1999.

[12]

Dario Izzo, Marek Ruciński, and Francesco Biscani. The generalized island model. In Francisco Fernández de Vega, José Ignacio Hidalgo Pérez, and Juan Lanchares, editors, Parallel Architectures and Bioinspired Algorithms, volume 415 of Studies in Computational Intelligence, pages 151--169. Springer Berlin Heidelberg, 2012.

[13]

Mario García-Valdez, Leonardo Trujillo, Juan Julián Merelo-Guérvos, and Francisco Fernández de Vega. Randomized parameter settings for heterogeneous workers in a pool-based evolutionary algorithm. In Thomas Bartz-Beielstein, Jürgen Branke, Bogdan Filipič, and Jim Smith, editors, Parallel Problem Solving from Nature -- PPSN XIII, volume 8672 of Lecture Notes in Computer Science, pages 702--710. Springer International Publishing, 2014.

[14]

Y. Gong and A. Fukunaga. Distributed island-model genetic algorithms using heterogeneous parameter settings. In Evolutionary Computation (CEC), 2011 IEEE Congress on, pages 820--827, June 2011.

[15]

Thiago T. Magalhães, Luis Henrique C. Nascimento, Eduardo Krempser, Douglas A. Augusto, and Helio J. C. Barbosa. Hybrid metaheuristics for optimization using a parallel islands model. In Ibero-Latin American Congress on Computational Methods in Engineering, November 2014.

[16]

Matteo Rosa Sentinella and Lorenzo Casalino. Cooperative evolutionary algorithm for space trajectory optimization. Celestial Mechanics and Dynamical Astronomy, 105(1--3):211--227, 2009.

[17]

M. Ruciński, D. Izzo, and F. Biscani. On the impact of the migration topology on the island model. Parallel Comput., 36(10--11):555--571, October 2010.

Digital Library

[18]

Erick Cantú-Paz. Efficient and Accurate Parallel Genetic Algorithms. Kluwer Academic Publishers, Norwell, MA, USA, 2000.

Digital Library

[19]

Nikolaus Hansen. Injecting external solutions into CMA-ES. CoRR, abs/1110.4181, 2011.

[20]

Nikolaus Hansen and Anne Auger. Performance evaluation of an advanced local search evolutionary algorithm. In In Proceedings of the IEEE Congress on Evolutionary Computation, pages 1777--1784. IEEE Press, 2005.

[21]

Janez Brest, Viljem Zumer, and Mirjam Sepesy Maucec. Self-adaptive differential evolution algorithm in constrained real-parameter optimization. In Evolutionary Computation, 2006. CEC 2006. IEEE Congress on, pages 215--222. IEEE, 2006.

[22]

Riccardo Poli, James Kennedy, and Tim Blackwell. Particle swarm optimization. Swarm intelligence, 1(1):33--57, 2007.

[23]

J.J. Liang, B.Y. Qu, P.N. Suganthan, and Alfredo G. Hernández-Díaz. Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization. Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou, China and Nanyang Technological University, Singapore, Technical Report, 201212, 2013.

Cited By

Karunakaran DMei YZhang M(2019)Multitasking Genetic Programming for Stochastic Team Orienteering Problem with Time Windows2019 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI44817.2019.9002804(1598-1605)Online publication date: Dec-2019
https://doi.org/10.1109/SSCI44817.2019.9002804
Karunakaran DMei YChen GZhang M(2018)Sampling Heuristics for Multi-objective Dynamic Job Shop Scheduling Using Island Based Parallel Genetic ProgrammingParallel Problem Solving from Nature – PPSN XV10.1007/978-3-319-99259-4_28(347-359)Online publication date: 21-Aug-2018
https://doi.org/10.1007/978-3-319-99259-4_28

Index Terms

Injection, Saturation and Feedback in Meta-Heuristic Interactions
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

A hybrid particle swarm optimization approach with prior crossover differential evolution
GEC '09: Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation

Particle swarm optimization (PSO) is population-based heuristic searching algorithm. PSO has excellent ability of global optimization. However, there are some shortcomings of prematurity, low convergence accuracy and speed, similarly to other ...
Differential evolution with individual-dependent and dynamic parameter adjustment

Differential evolution (DE) is a powerful and versatile evolutionary algorithm for global optimization over continuous search space, whose performance is significantly influenced by its mutation operator and control parameters (population size, scaling ...
Non-monotone differential evolution
GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

The Differential Evolution algorithm uses an elitist selection, constantly pushing the population in a strict downhill search, in an attempt to guarantee the conservation of the best individuals. However, when this operator is combined with an ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

July 2015

1496 pages

ISBN:9781450334723

DOI:10.1145/2739480

Editor:
Sara Silva
Universidade de Lisboa, Portugal
,
General Chair:
Anna I. Esparcia-Alcázar
Universitat Politècnica de València, Spain

Copyright © 2015 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 the author(s) 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: 11 July 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '15

Sponsor:

SIGEVO

GECCO '15: Genetic and Evolutionary Computation Conference

July 11 - 15, 2015

Madrid, Spain

Acceptance Rates

GECCO '15 Paper Acceptance Rate 182 of 505 submissions, 36%;

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

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

Reflects downloads up to 22 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Karunakaran DMei YZhang M(2019)Multitasking Genetic Programming for Stochastic Team Orienteering Problem with Time Windows2019 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI44817.2019.9002804(1598-1605)Online publication date: Dec-2019
https://doi.org/10.1109/SSCI44817.2019.9002804
Karunakaran DMei YChen GZhang M(2018)Sampling Heuristics for Multi-objective Dynamic Job Shop Scheduling Using Island Based Parallel Genetic ProgrammingParallel Problem Solving from Nature – PPSN XV10.1007/978-3-319-99259-4_28(347-359)Online publication date: 21-Aug-2018
https://doi.org/10.1007/978-3-319-99259-4_28

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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents