You are here

Measuring the Searched Space to Guide Efficiency: The Principle and Evidence on Constraint Satisfaction

TitleMeasuring the Searched Space to Guide Efficiency: The Principle and Evidence on Constraint Satisfaction
Publication TypeConference Paper
Year of Publication2002
Authorsvan Hemert, JI, Bäck, T
Conference NameSpringer Lecture Notes on Computer Science
PublisherSpringer-Verlag, Berlin
EditorMerelo, JJ, Panagiotis, A, Beyer, H-G, Fern{\'a}ndez-Villaca{\~n}as, J{\'e}-L, Schwefel, H-P
ISBN Number3-540-44139-5
Keywordsconstraint satisfaction; resampling ratio
Abstract

In this paper we present a new tool to measure the efficiency of evolutionary algorithms by storing the whole searched space of a run, a process whereby we gain insight into the number of distinct points in the state space an algorithm has visited as opposed to the number of function evaluations done within the run. This investigation demonstrates a certain inefficiency of the classical mutation operator with mutation-rate 1/l, where l is the dimension of the state space. Furthermore we present a model for predicting this inefficiency and verify it empirically using the new tool on binary constraint satisfaction problems.

Full Text