Golomb Rulers: The Advantage of Evolution



In this paper we present a new evolutionary algorithm designed to effciently search for optimal Golomb rulers. The proposed approach uses a redundant random keys representation to codify the information contained in a chromosome and relies on a simple interpretation algorithm to obtain feasible solutions. Experimental results show that this method is successful in quickly identifying good solutions and that can be considered as a realistic alternative to massive parallel approaches that need several months or years to discover high quality Golomb rulers.


Evolutionary Optimization


Workshop on Artificial Life and Evolutionary Algorithms (ALEAâ??03), December 2003

Cited by

Year 2012 : 1 citations

 M Sorge, H Moser, R Niedermeier, M Weller. Exploiting a hypergraph model for finding golomb rulers. Combinatorial Optimization, 2012 - Springer.

Year 2009 : 1 citations

 C. Cotta, A. J. Fernandéz (2009). Solving Constrained Optimization Problems with Hybrid Evolutionary Algortihms. In Optimization Techniques for Solving Complex Problems, E. Alba et. al (Eds.), Wiley.

Year 2007 : 1 citations

 C. Cotta, I. Dotú, A.J. Fernández, P. Van Hentenryck, Local Search-Based Hybrid Algorithms for Finding Golomb Rulers, Constraints, Volume 12, Number 3, September, Springer Netherlands, 2007.

Year 2006 : 2 citations

 C. Cotta, I. Dotú, A. Fernández, P. Van Hentenryck, A Memetic Approach to Golomb Rulers, Parallel Problem Solving from Nature IX, T. Runarsson et al., Lecture Notes in Computer Science 4193, Springer-Verlag, Berlin Heidelberg, 2006.

 I. Dotú (2006). Towards Hybrid Methods for Solving Hard Combinatorial Optimization Problems. Ph. D. Thesis, Universidad Autónoma de Madrid, Spain, September 2006.

Year 2005 : 2 citations

 Ivan Dotu and Pascal Van Hentenryck, A Simple Hybrid Evolutionary
Algortihm for Finding Golomb Rulers, In Proceedings of the 2005 IEEE Congress on Evolutionary Computation (CEC'05), Edimburgh, UK, September 2005.

 Cotta, C; Fernadez, AJ
Analysing fitness landscapes for the optimal Goulomb ruler problem. Proceedings of the 5th European Conference on Combinatorial Optimization, LNCS 3448, 68-79, 2005.

Year 2004 : 2 citations

 C. Cotta, and A. J. Fernndez, Analyzing Fitness Landscapes for the
Optimal Golomb Ruler Problem, In Proceedings of the 5th European
Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP 2005), Lausanne, Switzerland, 30 March - 1 April, 2005.

 C. Cotta, and A. J. Fernndez, A Hybrid GRASP - Evolutionary
Algorithm Approach to Golomb Ruler Search, In Proceedings of
the The 8th International Conference on Parallel Problem Solving from Nature (PPSN VIII), Birmingham, UK, 18-22 September, 2004.