Iterative Optimizers

7Exploitation and Exploration vs Difficulty

Essentially, the sampling strategies of an optimizer are responsible for the latter assuming whether a problem is easy or difficult. For example, for a purely greedy algorithm (see section A.11), a unimodal problem is very easy and a multimodal problem is very difficult as soon as the basin of attraction of the global minimum is significantly smaller than that of a local minimum.

The classic mantra that can be found in many articles and books is that there must be a “balance” between exploitation and exploration (sometimes referred to as intensification and diversification). As such, definitions sufficiently accurate to calculate these two quantities and observe the evolution of their ratio during the iterations are rarely given (see however Naudts et al. (1999) and Chen et al. (2009))

To clearly bring forward the influence of the exploitation/exploration ratio, we shall see:

• – rigorous definitions of these two concepts, making it possible to measure them;
• – then, in the next chapter, a very simple optimizer, which will explicitly use an exploitation method, an exploration method and an evolution strategy of their ratio.

7.1. Exploitation, an incomplete definition

In Clerc (2014), I proposed a formalization of exploitation in the case of particle swarm optimization (PSO), which maintains in permanence a list of “good” positions (swarm-memory). It is revisited here word for word in the box below and it is called Method 0.

Box ...