The influence of fitness landscape characteristics on the search behaviour of particle swarm optimisers

Abstract

Fitness landscapes facilitate the analysis of optimisation problems in a detailed, yet intuitive manner. Such an analysis can be used to select an appropriate algorithm to solve the problem, based on the strengths and weaknesses of the algorithm. This requires an understanding of the effect of the various fitness landscape characteristics (FLCs) of the problem on the behaviour of the algorithm being considered. The effects of FLCs on the behaviour of particle swarm optimisers (PSOs) is still not well-understood. This dissertation uses a novel measure of PSO behaviour in terms of exploration and exploitation based on the rate of change of the swarm's diversity. The diversity rate-of change (DRoC) measure is shown to be robust to various parameters, and consequently, to be an appropriate measure for quantifying PSO behaviour. Using this DRoC measure to quantify PSO search behaviour, this dissertation then investigates correlations between individual FLCs and the search behaviour of PSOs. Some FLCs, such as search ability, deception, and funnels are found to correlate with PSO search behaviour in an intuitive fashion: when the FLCs indicate that a landscape is easier to solve for a PSO, the PSO tends to converge at a faster rate. The micro ruggedness FLC correlates with PSO search behaviour counterintuitively: although landscapes with more ruggedness at the micro level could be considered harder to solve, they correspond with faster convergence in PSOs, rather than slower. Other FLCs, such as neutrality, macro-ruggedness and gradients, do not correlate significantly with PSO search behaviours.