user1
Get Complete Project Material File(s) Now! »
The algorithm selection problem
The general problem of selecting an effective or good or best algorithm to solve a givenproblem was formulated by Rice in the 1970s [132]. One of the models described by Riceis the model where algorithm selection is based on features of the problem. This model has four main characteristics: A set of problem instances (problem space P), a set of algorithms for solving the problems (algorithm space A), measures for comparing the performance of algorithms on a particular problem (performance measure space Y ), and measurable characteristics of the problem instances (feature space G).
Fitness landscapes
For most optimisation problems there is a fitness function1 that reflects the objectives of the problem to be solved. (Problems that do not have a readily available fitness function are excluded from this study.) Potential solutions to a problem are compared based on their fitness values, which are determined using the fitness function. In some problem cases, the function is expressed so that the aim is to find the solution that maximises the fitness value and in other cases, the aim is to find the solution that minimises the fitness value.
1PSO algorithms
Particle swarm optimisation (PSO) [31, 75] is a stochastic population-based optimisation technique. Starting with a random swarm of solutions, called particles, the positions of particles in the search space are adjusted at each iteration of the algorithm. The adjustment has random elements, but is largely determined by the distance to the best solution found in the neighbourhood of the particle (called the neighbourhood best) and the distance from best solution found by the particle itself during the search process (called the personal best or pbest). In this way, the swarm of particles move around, exploring the search space, in time hopefully converging on a good solution. There are many different varieties of PSO algorithms. This section describes seven basic variations that differ in their exploration and exploitation behaviours [35]. These seven variations are used later in Chapter 6 when the link between fitness landscapes characteristics and PSO performance is investigated.
Random walk algorithms
Some fitness landscape analysis techniques are based on a random walk through the search space to capture a sequence of neighbouring solutions, such as autocorrelation techniques [177], correlation length [80] and entropic measures of ruggedness and smoothness with respect to neutrality [172]. Adapting these for real-valued problems requires a method for performing a random walk in a continuous space. This section proposes a random walk algorithm for continuous spaces with the following aims: 1. The points in a walk should be ordered based on some generic notion of neighbourhood, such as Euclidean distance.
Existing techniques for measuring evolvability
There are fitness landscape measures that were originally conceived as a way of quantifying problem difficulty. Two such examples are Jones and Forrest’s fitness distance correlation [68] and Borenstein and Poli’s information landscape hardness measure [15]. Both these techniques require knowledge of the global optima, and so cannot be used as predictive measures of algorithm performance on unknown problems when used in their original form. An alternative is to base the measure on a sample of the search space and to use the fittest point from the sample in the place of the global optimum. This implies a shift in focus away from measuring hardness to measuring searchability, since the aim is no longer to quantify how well or badly the problem guides search towards the optimum, but rather to quantify how well or badly the problem guides search towards a place of better fitness.
Summary of conclusions
The first objective of this research was to conduct a survey of existing techniques for a priori characterisation of optimisation problems. To link the survey to fitness landscapes, each technique was categorised in terms of the fitness landscape feature measured (called the ‘Focus’ of the technique in the survey). For some techniques, the focus was not obvious. For example, fitness distance correlation (Technique 7) is described by the authors as a difficulty measure. Although the description of fitness distance correlation is fairly straight-forward, it is not obvious what this translates to in fitness landscape terms (with ‘difficulty’ not sufficient for capturing the focus). By tying each technique to a fitness landscape feature, it became possible to identify gaps in terms of features that do not have associated techniques for measuring them. In addition to the focus, the ‘Search Independence’, ‘Assumptions’ and ‘Result’ descriptors all proved valuable in terms of highlighting ways in which the existing techniques could be adapted for practical use in different contexts.
1.1 The algorithm selection problem
1.2 What makes an optimisation problem hard?
1.3 Existing approaches to fitness landscape analysis
1.4 Research objectives
1.4.1 Objective 1: Survey of existing techniques
1.4.2 Objective 2: Develop a problem characteriser
1.4.3 Objective 3: Develop prediction models for PSO performance
1.5 Contributions
1.6 Thesis outline
2 Background: Analysis of Fitness Landscapes
2.2 Fitness landscapes
2.2.1 Wright’s fitness landscape
2.2.2 Fitness landscape formalisations
2.2.3 One function, many landscapes
2.3 Features of fitness functions and landscapes
3 Benchmarks, Algorithms and Performance
3.1 Benchmarks
3.2 PSO algorithms
3.2.1 Traditional global best PSO
3.2.2 Cognitive PSO
3.2.3 Social PSO
3.2.4 Local best PSO
3.2.5 Asynchronous global best PSO
3.2.6 Bare bones PSO
3.2.7 Modified bare bones PSO
4 Ruggedness, Funnels and Gradients
4.2 Random walk algorithms
4.2.1 Simple random walk
4.2.2 Progressive random walk
4.2.3 Testing coverage of walks
4.3 Simple benchmark problems
4.4 Ruggedness measures
5 Searchability
5.1 Existing techniques for measuring evolvability
5.1.1 Fitness distance correlation
5.1.2 Information landscape measures
5.1.3 Fitness cloud
5.1.4 Negative slope coefficient
5.2 Proposed general searchability measures 5.2.1 Fitness distance correlation as a searchability measure
5.2.2 Information landscape negative searchability measure
5.2.3 Summary of proposed general searchability measures
5.3 Proposed PSO searchability measures
5.3.1 Determining neighbours for fitness clouds using PSO
5.3.2 Proposed measures based on fitness clouds
6 Conclusions
