On worst-case and comparative analysis as a design principles for efficient recombination operators: A graph coloring case study

COLL, PABLO; DURAN, GUILLERMO ALFREDO; MOSCATO, PABLO

New Ideas in Optimization

Año: 1999; p. 279 - 292

Abstract: In this chapter, we present a novel methodology for the analysis and the design strategy of recombination operators. As a case study, which will illustrate the technique, we will discuss the principal recombination of the algorithm for the graph coloring problem introduced by Costa, Hertz and Dubuis in 1995. Part of our motivation is based on the good results obtained by these authors on large random graphs of the class Gn,p (graphs with n vertices and density p) as well as some of the limitations of their method. Our approach to the evaluation of the performance of a recombination is inspired on Competitive Analysis and Comparative Analysis, two techniques developed in connection with on-line algorithms.