by van Hemert, J and T Bäck
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.
Reference:
Measuring the Searched Space to Guide Efficiency: The Principle and Evidence on Constraint Satisfaction (van Hemert, J and T Bäck), In Parallel Problem Solving from Nature (JJ Merelo, A Panagiotis, H-G Beyer, José-Luis Fernández-Villacañas, Hans-Paul Schwefel, eds.), Springer, volume 2439, 2002.
Bibtex Entry:
@article{HB2002,
_address = {Granada, Spain},
_day = {12},
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.},
author = {van Hemert, J and T B{\"a}ck},
date-added = {2008-08-18 12:44:11 +0100},
date-modified = {2009-07-28 16:33:47 +0100},
editor = {JJ Merelo and A Panagiotis and H-G Beyer and Jos{\'e}-Luis Fern{\'a}ndez-Villaca{\~n}as and Hans-Paul Schwefel},
isbn = {3-540-44139-5},
journal = {Parallel Problem Solving from Nature},
keywords = {constraint satisfaction; evolutionary computation},
pages = {23--32},
publisher = {Springer},
series = {{LNCS}},
title = {Measuring the Searched Space to Guide Efficiency: The Principle and Evidence on Constraint Satisfaction},
volume = {2439},
year = {2002}}