Home > Research
Thresheld Convergence in PSO, DE, and Other Search Methods
AbstractMany search techniques (e.g. PSO and DE) use vectors to generate new solutions (e.g. attraction vectors in PSO and difference vectors in DE). These vectors, which can exploit gradients, provide useful information in unimodal search spaces. For the exploration of multi-modal search spaces, it is instead useful to think of the sampling of attraction basins – each local optimum defines an attraction basin which will lead to it through the use of greedy local search. Since many search techniques (such as PSO and DE) also employ elitism, the solutions which guide the search are the fittest solutions found to date. Implicitly, the most promising attraction basins to exploit (i.e. find the exact local optimum) are identified by the fitness of a known solution within them.
This identification works best when the solutions within each basin have the same relative fitness with respect to their local optima. Since local search interferes with this comparison process, the goal of thresheld convergence is to eliminate concurrent global and local search. Specifically, convergence is "held" back through the use of a threshold function [1][2]. Successful applications of thresheld convergence include PSO [3] and DE [4] and two new heuristic search techniques: Minimum Population Search [5] and Leaders and Followers [6]. Observations from these applications provide useful insights into the mechanisms of PSO and DE and the operation of metaheuristics in multi-modal search spaces.
This is an intermediate tutorial which is best suited for researchers already familar with Particle Swarm Optimization, Differential Evolution, and/or other metaheuristics -- especially with their performance characteristics in unimodal and multi-modal search spaces.
Summary Paper
The content of the tutorial is summarized in the following paper:
S. Chen, J. Montgomery, A. Bolufé-Röhler, Y. Gonzalez-Fernandez. (2015) "A Review of Thresheld Convergence." GECONTEC: Revista Internacional de Gestión del Conocimiento y la Tecnología, 3(1): 1-13.
Presentation Slides
In the Tutorial Notes, the outline on page 2 has quick links to each main topic.
Presenters
Dr. Stephen Chen is an Associate Professor of Information Technology at York University in Toronto, Canada. His research focuses on analyzing the mechanisms for exploration and exploitation in techniques designed for multi-modal optimization problems. He is particularly interested in the development and analysis of non-metaphor-based heuristic search techniques. He has conducted extensive research on genetic algorithms and swarm-based optimization systems, and his 50+ peer-reviewed publications include 20 full papers in IEEE CEC proceedings.
Dr. James Montgomery is a Lecturer in Information & Communication Technologies at the University of Tasmania in Hobart, Australia. His research focuses on search space analysis and the design of solution representations for complex, real-world problems. He has conducted extensive research on ant colony optimization and differential evolution, and his 40+ peer-reviewed publications include 11 full papers in IEEE CEC proceedings.
References
[1] S. Chen and J. Montgomery. (2011) “A Simple Strategy to Maintain Diversity and Reduce Crowding in Particle Swarm Optimization.” LNCS Vol. 7106: Proc. 24th Australasian Joint Conference on Artificial Intelligence, pp 281-290. Springer-Verlag.
[2] J. Montgomery and S. Chen. (2012) "A Simple Strategy for Maintaining Diversity and Reducing Crowding in Differential Evolution." Proc. 2012 IEEE Congress on Evolutionary Computation, pp 2692-2699. IEEE Press.
[3] S. Chen and J. Montgomery. (2013) "Particle Swarm Optimization with Thresheld Convergence." Proc. 2013 IEEE Congress on Evolutionary Computation, pp 510-516. IEEE Press.
[4] A. Bolufé Röhler, S. Estévez-Velarde, A. Piad-Morffis, S. Chen, and J. Montgomery. (2013) "Differential Evolution with Thresheld Convergence." Proc. 2013 IEEE Congress on Evolutionary Computation, pp 40-47. IEEE Press.
[5] A. Bolufé Röhler and S. Chen. (2013) "Minimum Population Search – Lessons from building a heuristic technique with two population members." Proc. 2013 IEEE Congress on Evolutionary Computation, pp 2061-2068. IEEE Press.
[6] Y. Gonzalez-Fernandez and S. Chen. (2015) "Leaders and Followers – A New Metaheuristic to Avoid the Bias of Accumulated Information." Proc. 2015 IEEE Congress on Evolutionary Computation, pp 776-783. IEEE Press.
