Article

PSO and multi-funnel landscapes: how cooperation might limit exploration

Authors:

Andrew M. Sutton,

Darrell Whitley,

Adele HoweAuthors Info & Claims

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

Pages 75 - 82

https://doi.org/10.1145/1143997.1144008

Published: 08 July 2006 Publication History

Abstract

Particle Swarm Optimization (PSO) is a population-based optimization method in which search points employ a cooperative strategy to move toward one another. In this paper we show that PSO appears to work well on "single-funnel" optimization functions. On more complex optimization problems, PSO tends to converge too quickly and then fail to make further progress. We contend that most benchmarks for PSO have classically been demonstrated on single-funnel functions. However, in practice, optimization tasks are more complex and possess higher problem dimensionality. We present empirical results that support our conjecture that PSO performs well on single-funnel functions but tends to stagnate on more complicated landscapes.

References

[1]

P. Angeline. Using selection to improve particle swarm optimization. In Proceedings of the IEEE Congress on Evolutionary Computation, 1998.

[2]

A. Carlisle and G. Dozier. An off-the-shelf PSO. In Proc. Workshop on Particle Swarm Optimization, Indianapolis, IN, 2001.

[3]

M. Clerc and J. Kennedy. The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Trans. Evolutionary Computation, 6(1):58--73, 2002.

Digital Library

[4]

J. Doye, R. Leary, M. Locatelli, and F. Schoen. Global optimization of Morse clusters by potential energy transforms. INFORMS Journal on Computing, 16(4):371--379, 2004.

Digital Library

[5]

J. P. Doye. Physical perspectives on the global optimization of atomic clusters. In Global optimization - select case studies, Kluwer, 2006.

[6]

J. P. Doye, M. A. Miller, and D. J. Wales. The double-funnel energy landscape of the 38-atom Lennard-Jones cluster. Journal of Chemical Physics, 110(14), April 1999.

[7]

R. C. Eberhart and Y. Shi. Comparison between genetic algorithms and particle swarm optimization. In Evolutionary Programming VII, pages 611--616.

Digital Library

[8]

R. C. Eberhart and Y. Shi. Comparing inertia weights and constriction factors in particle swarm optimization. In Proc. of the 2000 Congress on Evolutionary Computation, pages 84--88, Piscataway, NJ, 2000.

[9]

N. Hansen and S. Kern. Evaluating the CMA evolution strategy on multimodal test functions. In PPSN. Springer, 2004.

[10]

N. Hansen and A. Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation, 9(2):159--195, 2001.

Digital Library

[11]

J. Hooker. Testing heuristics: We have it all wrong, 1996.

[12]

J. Kennedy. Bare bones particle swarms. In Proc. IEEE Swarm Intelligence Symposium, 2003.

[13]

J. Kennedy and R. Eberhart. Particle swarm optimization. In International Conference on Neural Networks, pages 1942--1948, Perth, Australia, 1995.

[14]

M. Locatelli. On the multilevel structure of global optimization problems. Computational Optimization and Applications, 30, 2005.

Digital Library

[15]

R. Mendes, J. Kennedy, and J. Neves. The fully informed particle swarm: Simpler, maybe better. IEEE Trans. Evolutionary Computation, 8(3):204--210, 2004.

Digital Library

[16]

C. K. Monson and K. D. Seppi. Exposing origin-seeking bias in pso. In Proceedings of the Genetic and Evolutionary Computation

Digital Library

[17]

P. M. Pardalos and F. Schoen. Recent advances and trends in global optimization: Deterministic and stochastic methods. In Proceedings of the Sixth International Conference on Foundations of Computer-Aided Process Design, 2004.

[18]

J. Riget and J. Vesterstroem. A diversity-guided particle swarm optimizer - the ARPSO, 2002.

[19]

Y. Shi and R. C. Eberhart. Parameter selection in particle swarm optimization. In Evolutionary Programming VII, pages 591--600.

Digital Library

[20]

Y. Shi and R. C. Eberhart. Empirical study of particle swarm optimization. In Proceedings of the Congress of Evolutionary Computation, volume 3, pages 1945--1950, 1999.

[21]

D. J. Wales. Energy landscapes and properties of biomolecules. Physical Biology, 2:S86--S93, 2005.

[22]

D. Whitley. The GENITOR algorithm and selection pressure. In Third International Conference on Genetic Algorithms, 1989. Morgan Kaufman.

Digital Library

[23]

Z.-L. Y. Xiao-Feng Xie, Wen-Jun Zhang. Adaptive particle swarm optimization on individual level. In International Conference on Signal Processing, 2002.

Cited By

Fang JLiu HGu F(2024)A constrained multi-objective evolutionary algorithm based on fitness landscape indicatorApplied Soft Computing10.1016/j.asoc.2024.112128(112128)Online publication date: Aug-2024
https://doi.org/10.1016/j.asoc.2024.112128
Blackwell TSilva SPaquete L(2023)The Barrier Tree Benchmark: Many Basins and Double FunnelsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590478(13-20)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590478
Tkach IBlackwell TWagner M(2022)Measuring optimiser performance on a conical barrier tree benchmarkProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528842(22-30)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528842
Show More Cited By

Index Terms

PSO and multi-funnel landscapes: how cooperation might limit exploration

Recommendations

PSO+: A new particle swarm optimization algorithm for constrained problems
Abstract
The Particle Swarm Optimization algorithm is a metaheuristic based on populations of individuals in which solution candidates evolve through simulation of a simplified model of social adaptation. By aggregating robustness, efficiency ...
Highlights
- The algorithm ensures there will always be particles fully respecting constraints.
Opposition based initialization in particle swarm optimization (O-PSO)
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers

Particle Swarm Optimization, a population based optimization technique has been used in wide number of application areas to solve optimization problems. This paper presents a new algorithm for initialization of population in standard PSO called ...
CAPSO: Centripetal accelerated particle swarm optimization

Meta-heuristic search algorithms are developed to solve optimization problems. Such algorithms are appropriate for global searches because of their global exploration and local exploitation abilities. Swarm intelligence (SI) algorithms comprise a branch ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

Copyright © 2006 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: 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,532 of 4,029 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
46
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fang JLiu HGu F(2024)A constrained multi-objective evolutionary algorithm based on fitness landscape indicatorApplied Soft Computing10.1016/j.asoc.2024.112128(112128)Online publication date: Aug-2024
https://doi.org/10.1016/j.asoc.2024.112128
Blackwell TSilva SPaquete L(2023)The Barrier Tree Benchmark: Many Basins and Double FunnelsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590478(13-20)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590478
Tkach IBlackwell TWagner M(2022)Measuring optimiser performance on a conical barrier tree benchmarkProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528842(22-30)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528842
Yi HKim I(2022)Differential evolutionary cuckoo-search-integrated tabu-adaptive pattern search (DECS-TAPS): a novel multihybrid variant of swarm intelligence and evolutionary algorithm in architectural design optimization and automationJournal of Computational Design and Engineering10.1093/jcde/qwac1009:5(2103-2133)Online publication date: 20-Sep-2022
https://doi.org/10.1093/jcde/qwac100
Zhou XSong JWu SNi WWang M(2022)Fitness Landscape Analysis: From Problem Understanding to Design of Evolutionary AlgorithmsBio-Inspired Computing: Theories and Applications10.1007/978-981-19-1256-6_21(281-293)Online publication date: 24-Mar-2022
https://doi.org/10.1007/978-981-19-1256-6_21
Nourmohammadzadeh ASarhani MVoß S(2022)Fitness Landscape Ruggedness Impact on PSO in Dealing with Three Variants of the Travelling Salesman ProblemLearning and Intelligent Optimization10.1007/978-3-031-24866-5_31(429-444)Online publication date: 5-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-24866-5_31
Parsopoulos K(2018)Particle Swarm MethodsHandbook of Heuristics10.1007/978-3-319-07124-4_22(639-685)Online publication date: 14-Aug-2018
https://doi.org/10.1007/978-3-319-07124-4_22
Caamao PVarela GDuro R(2017)An evolutionary approach to constrained sampling optimization problemsApplied Soft Computing10.1016/j.asoc.2016.12.00251:C(266-279)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1016/j.asoc.2016.12.002
Serna LMañanas MMarín JHernández ABenito S(2016)Optimization techniques in respiratory control system modelsApplied Soft Computing10.1016/j.asoc.2016.07.03348:C(431-443)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1016/j.asoc.2016.07.033
Parsopoulos K(2016)Particle Swarm MethodsHandbook of Heuristics10.1007/978-3-319-07153-4_22-1(1-47)Online publication date: 8-Nov-2016
https://doi.org/10.1007/978-3-319-07153-4_22-1
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.

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