A novel direct measure of exploration and exploitation based on attraction basins

Exploration, the process of visiting a new region in a search space, and exploitation, the process of searching in the neighborhood of previously visited regions, are two centerpieces of any metaheuristic algorithm. It is a common belief that good results can be obtained only if there is a good balance between exploration and exploitation. Hence, there is an urgent need to control the balance between exploration and exploitation in a direct manner. But, currently, direct measures of exploration and exploitation are almost non-existent, and researchers rely on indirect measures of exploration and exploitation, such as diversity, entropy, and fitness improvements. To remedy this situation, in this paper, a novel direct measure of exploration and exploitation is proposed that is based on attraction basins - parts of a search space where each part has its own point called an attractor, to which neighboring points tend to evolve. Each search point can be associated with a particular attraction basin. If a newly generated search point belongs to the same attraction basin as its parent then the search process is identified as exploitation, otherwise as exploration. In this paper, a new technique to compute attraction basins is presented, as well as a novel direct measure (ExaBas) of exploration and exploitation based on attraction basins. On the selected set of unimodal and multimodal optimization problems it is shown that the newly proposed direct measure of exploration and exploitation is more accurate than our previously proposed direct measure (ExpDist), as well as the common indirect measure based on diversity (Diversity).

Automated summary

This paper introduces a novel direct measure based on attraction basins to address the lack of direct measures of exploration and exploitation. Through this new technique, it is shown to be more accurate than previously proposed direct measures and common indirect measures.