Analyzing Fitness Landscapes for the Optimal Golomb Ruler Problem

C. Cotta, A.J. Fernández

Evolutionary Computation in Combinatorial Optimization, J. Gottlieb, G. Raidl (eds.), Lecture Notes in Computer Science 3448, pp. 68-79, Springer-Verlag Berlin, 2005

© Springer-Verlag Berlin Heidelberg 2005. All rights reserved.


We focus on the Golomb ruler problem, a hard constrained combinatorial optimization problem. Two alternative encodings are considered, one based on the direct representation of solutions, and one based on the use of an auxiliary decoder. The properties of the corresponding fitness landscapes are analyzed. It turns out that the landscape for the direct encoding is highly irregular, causing drift to low-fitness regions. On the contrary, the landscape for the indirect representation is regular, and exhibits comparable fitness-distance correlation to that of the former landscape. These findings are validated in the context of variable neighborhood search.

Download BibTEX entry
Download PDF version (266K)
[Back to publications page].