Overcoming Fitness Barriers in Multi-Modal Search Spaces

Martin J Oates    BT Labs, Adastral Park, Martlesham, Heath, Suffolk, England, IP5 3RE

David Corne    Dept of Computer Science, University of Reading, Reading, RG6 6AY

1 INTRODUCTION

The demands of real-world optimization problems provide the evolutionary algorithm researcher with several challenges. One of the key challenges is that industry needs to feel confident about the speed, reliability, and robustness of EA-based methods [1, 4, 5, 8]. In particular, these issues must be addressed on a case by case basis in respect of tailored EA-based approaches to specific problems. A standard way to address these issues is, of course, to empirically test the performance of a chosen tailored EA against a suite of realistic problems and over a wide range of parameter and /or strategy settings.

Certainly, there are several applications where such a thorough analysis is not strictly necessary. However, where the EA is designed for use in near-real time applications and/or is expected to perform within a given ‘quality of service’ constraint, substantial testing and validation of the algorithm is certainly required. An example of a problem of this type, called the Adaptive Distributed Database Management Problem (ADDMP), is reported in [13, 14, 16].

In order to provide suitably thorough evaluation of the performance of EAs on the ADDMP, substantial experiments have been run to generate performance profiles. A performance profile is a plot of ‘mean evaluations exploited’ (the z axis) over a grid defining combinations of population size and mutation rate (the x and y axes). See Figure 1 for an example, with several others in [13, 14, 16]. ‘Mean evaluations exploited’ is essentially a measure of convergence time - that is, the time taken (in terms of number of evaluations) for the EA to first find the best solution it happens to find in a single trial run. However we do not call it ‘convergence time’, since it does not correspond, for example, to fixation of the entire population at a particular fitness value. It is recognised that this measure is only of real significance if its variation is low. The choice of mean evaluations exploited as a performance measure is guided by the industrial need for speed. The alternative measure would of course be ‘best-fitness found’, but we also need to carefully consider the speed of finding the solution. With reference also to the standard mean-fitness plot, an evaluations-exploited performance profile indicates not only whether adequate fitness can be delivered within the time limit at certain parameter settings, but whether or not we can often expect good solutions well before the time limit – this is of course important and exploitable in near real-time applications.

A single (x, y, z) point in a performance profile corresponds to the mean evaluations exploited (z) over 50 (unless otherwise stated) trial runs with mutation rate set to x and population size set to y. An entire performance profile typically contains several hundred such points, An important feature associated with a performance profile is the time-limit (again, in terms of number of evaluations) given to individual trial runs. A performance profile with a time limit of 20,000 evaluations, for example, consumes in total around half a billion evaluations.

Although a very time consuming enterprise, plotting performance profiles for the ADDMP has yielded some interesting features which has prompted further investigation. As discussed in [13], the original aim has been served in that performance profiles of the ADDMP reveal suitably wide regions of parameter space in which the EA delivers solutions with reliable speed and quality. This initial finding has been sufficiently convincing, for example, to enable maintained funding for further study towards adoption of this EA for live applications (this work is currently at the demonstrator stage). Beyond these basic issues, however, performance profiles on the ADDMP have yielded robust and unexpected features, which have consistently appeared in other problems which have now been explored. The original naive expectation was that the profile would essentially reveal a ‘well’ with its lowest points (corresponding to fast convergence to good solutions) corresponding to ideal parameter choices. What was unexpected was that beyond this well (towards the right – higher mutation rates) there seemed to be an additional well, corresponding to locally good but higher mutation rates yielding fast convergence. Essentially, we expected profiles to be similar in structure to the area between mutation rate = 0 and the second peak to the right in Figure 1; however, instead we tended to find further local structure beyond this second peak.

Hence, the performance profile of the ADDMP seemed to reveal two locally optimal mutation rates in terms of fast and reliable convergence to good solutions. Concerned that this may simply have been an artefact of the chosen EA and the chosen test problems, several further performance profiles were generated which used different time limits, quite different EA designs, and different test problems. These studies revealed that the multimodality of the performance profile seemed to be a general feature of evolutionary search [16–19].

Recently, we have looked further into the multimodal features in the performance profiles of a range of standard test problems, and looked into the positions of the features with respect to the variation in the evaluations exploited measure, and also mean fitness. This has yielded the suggestion that there are identifiable phases of search behaviour which change and repeat as we increase the mutation rate, and that an understanding of these phases could underlay an understanding of the multimodality in performance profiles. Note that these phases are not associated with intervals of time in a single trial run, but with intervals of parameter space. Hence a single run of a particular (non-adaptive) EA operates in a particular phase.

In this article, we describe these observations of phase-based behaviour in association with multimodal performance profiles, considering a range of test problems. In particular, we explore a possible explanation of the phase behaviour in terms of the frequencies of particular mutation events available as we change the mutation rate. In section 2 we describe some background and preliminary studies in more detail, setting the stage for the explorations in this article. Section 3 then describes the main test problem we focus on, Watson et al’s H-IFF problem [21], and describes the phase-based behaviour exhibited by H-IFF performance profiles. In section 4 we set out a simple model to explain phase onsets in terms of the frequencies with which certain specific types of mutation event become available as we increase the mutation rate. The model is investigated with respect to the H-IFF performance profile and found to have some explanatory power, whilst actual fitness distributions are explored in section 5. Section 6 then investigates whether similar effects occur on other problems, namely Kauffman NK landscapes [6] and the tuneable Royal Staircase problem [11, 12], and explores the explanatory power of the ‘mutation-event’ based explanation on these problems. A discussion and conclusions appear in sections 7 and 8 respectively.

2 PRELIMINARY OBSERVATION OF CYCLIC PHASE BEHAVIOUR IN PERFORMANCE PROFILES

In recent studies of the performance profile of the ADDMP [13, 14], Watson et al’s H-IFF problem [21], Kauffman NK landscapes [6] and the tuneable Royal Staircase problem [11], as well as simple MAX-ONES, a cyclic tri-phase behaviour has been observed [18, 19], where phases correspond to intervals on the mutation rate axis. The phases were characterised in...