TY - CONF
T1 - Measuring the Searched Space to Guide Efficiency: The Principle and Evidence on Constraint Satisfaction
T2 - Springer Lecture Notes on Computer Science
Y1 - 2002
A1 - van Hemert, J. I.
A1 - Bäck, T.
ED - J. J. Merelo
ED - A. Panagiotis
ED - H.-G. Beyer
ED - Jos{\'e}-Luis Fern{\'a}ndez-Villaca{\~n}as
ED - Hans-Paul Schwefel
KW - constraint satisfaction
KW - resampling ratio
AB - 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.
JF - Springer Lecture Notes on Computer Science
PB - Springer-Verlag, Berlin
SN - 3-540-44139-5
ER -