Convergence stabilization Modeling (formerly known as CMOn) is a tool that uses the current search history to detect automatically the moment that a given fitness decay stabilizes, indicating at execution time (Online) that the convergence might not recover easily afterwards.
When dealing with metaheuristics, one important question is how many evaluations are worth spending in the search for better results. This tool estimates automatically the best moment to stop search iterations based on the analysis of the convergence behavior presented during optimization, aiming to provide an effective balance between saving fitness evaluations and keeping the optimization quality.
Estimating Stop Conditions of Swarm Based Stochastic Metaheuristic Algorithms
The increasing complexity of real world optimization problems requires powerful tools with robust configuration sets. Among these tools, stochastic metaheuristics play a special role, and there is a wide variety of literature concerning configuration methods and usage. However, despite their importance, not much effort has been done toward algorithm-independent procedures to determine a good cost/benefit number of fitness function evaluations, specially for continuous problems. Apart from being quite contextual (the solution relies on the strengths and weaknesses of the optimization algorithms and the problem being optimized), their behavior also obeys the unpredictable random numbers logic.
The article titled Estimating Stop Conditions of Swarm Based Stochastic Metaheuristic Algorithms proposes a method that is not dependent on a particular search algorithm but on the standard behavior presented by general memory-based metaheuristics (like swarm algorithms). It treats the optimization algorithm as a black-box, thus exploring several aspects present in the search algorithm instead of requiring core changes to it. The main goal is to provide an on-line estimation of a good cost/benefit stopping point for every optimization run of a search algorithm, aiming to save function evaluations.
Tests has been conducted using CEC13 benchmark and Max-Set random functions, with results showing that a good trade-off can be obtained between the drawback resulting from the fitness approximation and the advantage of saving fitness function evaluations (the classical cost/benefit problem).
As conclusion, the process presented to model the convergence stabilization behavior is able to effectively adapt to each optimization in progress (online), providing support for the search algorithm to decide for the search finalization or for some additional action, like for example to reactivate the convergence.
Download
This package contains CSMOn’s source code and two examples (one for Python and one for C++) using PSO as the search algorithm:
For Linux
For Windows
See the readme file for instructions of how to compile and run the examples:
For complete documentation of CSMOn tool, see:
Paper
References
Peter Frank Perroni, Daniel Weingaertner, and Myriam Regattieri Delgado. 2017. Estimating Stop Conditions of Swarm Based Stochastic Metaheuristic Algorithms. In Proceedings of GECCO ’17, Berlin, Germany, July 15-19, 2017, pg 43-50. DOI: http://dx.doi.org/10.1145/3071178.3071326. http://dl.acm.org/citation.cfm?id=3071326
Thomas Bartz-Beielstein. 2015. How to Create Generalizable Results. In Springer Handbook of Computational Intelligence. Springer, 1127–1142.
Marcus Gallagher and Bo Yuan. 2006. A general-purpose tunable landscape generator. IEEE transactions on evolutionary computation 10, 5 (2006), 590–603.
X. Li, K. Tang, M. Omidvar, Z. Yang, and K. Qin. 2013. Benchmark Functions for the CEC’2013 Special Session and Competition on Large Scale Global Optimization. Evolutionary Computation and Machine. (2013).