Title :
Predicting Stochastic Search Algorithm Performance using Landscape State Machines
Author :
Rowe, William ; Corne, David ; Knowles, Joshua
Author_Institution :
Univ. of Manchester, Manchester
Abstract :
A landscape state machine (LSM) is a Markov model describing the transition probabilities between the fitness ´levels´ of an optimization problem, when a given neighbourhood (or mutation) operator is applied. Although most optimization problems cannot be modeled precisely by an LSM, an approximate LSM can always be constructed by sampling, and can be used, subsequently, in place of real fitness evaluations in order to model the performance of any search algorithm using the given neighbourhood operator. In this paper, we provide empirical evidence that (a) LSMs constructed by simulated annealing-based sampling of a problem landscape make accurate models in few evaluations; (b) LSMs can accurately rank the performance of diverse algorithms including EAs with/without niching and SA; (c) the LSM approach works on diverse problems from MAX-SAT to NKp; (d) convergence of the LSM can be used as a guide to stopping the sampling phase; and, (e) a single LSM constructed using a low mutation-rate sample is sufficient to accurately rank the performance of search algorithms run at multiples of this mutation rate.
Keywords :
Markov processes; convergence; evolutionary computation; mathematical operators; probability; sampling methods; search problems; simulated annealing; Markov model; convergence; evolutionary algorithm; fitness evaluation; landscape state machine; mutation operator; optimization; sampling method; simulated annealing; stochastic search algorithm; transition probability; Algorithm design and analysis; Genetic mutations; Mathematical model; Performance analysis; Prediction algorithms; Sampling methods; Simulated annealing; Statistical analysis; Stochastic processes; Testing;
Conference_Titel :
Evolutionary Computation, 2006. CEC 2006. IEEE Congress on
Conference_Location :
Vancouver, BC
Print_ISBN :
0-7803-9487-9
DOI :
10.1109/CEC.2006.1688679