Home > Research
From Thresheld Convergence to Leaders and Followers
AbstractExploration and Exploitation are critical concepts that are poorly defined, and thus often misunderstood. We begin by defining an attraction basin as all of the search points that will lead to the same local optimum when greedy local search is applied. We then define exploration to be a search movement that involves multiple attraction basins and exploitation to be a search movement that involves (i.e. stays within) only one attraction basin. Assuming every point in the search space belongs to exactly one attraction basin, we can then accurately classify every search movement as one of either exploration or exploitation.
Based on the above definitions, many search techniques (e.g. PSO, DE, ES, EDA, Simulated Annealing, etc) allow concurrent exploration and exploitation. We will present experiments which show how concurrent exploration and exploitation weakens exploration and is a primary cause of (premature) convergence. We will then introduce “Thresheld Convergence” in which convergence is “held” back through the use of a threshold function [1]. This focus on attraction basins has also led to the development of “Leaders and Followers” [2] – a new metaheuristic which focuses on how solutions are compared as opposed to how solutions are created.
Target Audience
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.
Presentation Slides
In the Tutorial Notes, the outline on page 2 has quick links to each main topic.
Presenters
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+ that have been presented at previous CEC events.
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 10+ that have been presented at previous CEC events.
References
[1] 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.
[2] 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.
