Predicting stochastic search algorithm performance using landscape state machines

William Rowe, David Corne, Joshua Knowles

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)

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 mutationrate sample is sufficient to accurately rank the performance of search algorithms run at multiples of this mutation rate. © 2006 IEEE.

Original languageEnglish
Title of host publication2006 IEEE Congress on Evolutionary Computation, CEC 2006
Pages2944-2951
Number of pages8
Publication statusPublished - 2006
Event2006 IEEE Congress on Evolutionary Computation - Vancouver, BC, Canada
Duration: 16 Jul 200621 Jul 2006

Conference

Conference2006 IEEE Congress on Evolutionary Computation
Abbreviated titleCEC 2006
CountryCanada
CityVancouver, BC
Period16/07/0621/07/06

Fingerprint Dive into the research topics of 'Predicting stochastic search algorithm performance using landscape state machines'. Together they form a unique fingerprint.

  • Cite this

    Rowe, W., Corne, D., & Knowles, J. (2006). Predicting stochastic search algorithm performance using landscape state machines. In 2006 IEEE Congress on Evolutionary Computation, CEC 2006 (pp. 2944-2951)