6533b82bfe1ef96bd128e024

RESEARCH PRODUCT

Measuring the Spatial Dispersion of Evolutionary Search Processes: Application to Walksat

Jean-jacques ChabrierOlivier BailleuxAlain Sidaner

subject

Metric spaceMathematical optimizationbusiness.industryWalkSATBeam searchLocal search (optimization)Best-first searchGuided Local SearchInterval (mathematics)businessMeasure (mathematics)Mathematics

description

In this paper, we propose a simple and efficient method for measuring the spatial dispersion of a set of points in a metric space. This method allows the quantifying of the population diversity in genetic algorithms. It can also be used to measure the spatial dispersion of any local search process during a specified time interval. We then use this method to study the way Walksat explores its search space, showing that the search for a solution often includes several stages of intensification and diversification.

yearjournalcountryeditionlanguage
2002-01-01
https://doi.org/10.1007/3-540-46033-0_7