Dissimilarity measures for population-based global optimization algorithms

Very hard optimization problems, i.e., problems with a large number of variables and local minima, have been effectively attacked with algorithms which mix local searches with heuristic procedures in order to widely explore the search space. A Population Based Approach based on a Monotonic Basin Hopping optimization algorithm has turned out to be very effective for this kind of problems. In the resulting algorithm, called Population Basin Hopping, a key role is played by a dissimilarity measure. The basic idea is to maintain a sufficient dissimilarity gap among the individuals in the population in order to explore a wide part of the solution space. The aim of this paper is to study and computationally compare different dissimilarity measures to be used in the field of Molecular Cluster Optimization, exploring different possibilities fitting with the problem characteristics. Several dissimilarities, mainly based on pairwise distances between cluster elements, are introduced and tested. Each dissimilarity measure is defined as a distance between cluster descriptors, which are suitable representations of cluster information which can be extracted during the optimization process. It will be shown that, although there is no single dissimilarity measure which dominates the others, from one side it is extremely beneficial to introduce dissimilarities and from another side it is possible to identify a group of dissimilarity criteria which guarantees the best performance.