Measuring the Effects of Increasing Dimensionality on Fitness-Based Selection and Failed Exploration

The rate of Successful Exploration is related to the proportion of search solutions from fitter attraction basins that are fitter than the current reference solution. A reference solution that moves closer to its local optimum (i.e. experiences exploitation) will reduce the proportion of these fitter solutions, and this can lead to decreased rates of Successful Exploration/increased rates of Failed Exploration. This effect of Fitness-Based Selection is studied in Particle Swarm Optimization and Differential Evolution with increasing dimensionality of the search space. It is shown that increasing rates of Failed Exploration represent another aspect of the Curse of Dimensionality that needs to be addressed by metaheuristic design.

I. Introduction

Many metaheuristics generate search solutions through the influence of reference solutions. For example, Genetic Algorithms [1] store a population of parent (reference) solutions, and offspring (search) solutions are created from the parents by applying operators such as crossover and mutation. Another example is Particle Swarm Optimization [2] in which a set of personal best (reference) positions are used to guide the search trajectories of moving particles, and these trajectories affect the sampled (search) solutions. In general, the exploratory search solutions that will be generated by a metaheuristic are strongly influenced by a set of retained reference solutions.