The Importance of Being Structured: a Comparative Study on Multi Stage Memetic Approaches

Abstract

Memetic Computing (MC) is a discipline which studies optimization algorithms and sees them as structures of operators, the memes. Although the choice of memes is crucial for an effective algorithmic design, special attention should be paid also to the coordination amongst the memes. This paper presents a study on a basic sequential structure, namely Three Stage Optimal Memetic Exploration (3SOME). The 3SOME algorithm is composed of three operators (or memes) which progressively perturbs a single solution. The first meme, long distance exploration is characterized by a long search radius and is supposed to detect promising areas of the decision space. The second meme, middle distance exploration, is characterized by a moderate search radius and is supposed to focus the search in the the most promising basins of attraction. The third meme, short distance exploration, is characterized by a short search radius and had the role of performing the local optimal search in the areas detected by the first two memes. To assess the importance of the structure within MC we compare the performance of 3SOME with two modified versions of it over two complete benchmarks. In both cases, while retaining the 3SOME structure, we replace one of the three original components (short distance exploration) with an alternative deterministic local search, respectively Rosenbrock and Powell methods. Numerical results show that, regardless of the choice of the specific memes, as far as the 3SOME structure contains memes which perform long, middle, and short distance explorations a similar performance is achieved. These results remark that besides the intuitive finding that a proper choice of operators is fundamental for the algorithmic success, the structure composing them also plays a crucial role.