2013 | OriginalPaper | Buchkapitel
Predicting Genetic Algorithm Performance on the Vehicle Routing Problem Using Information Theoretic Landscape Measures
verfasst von : Mario Ventresca, Beatrice Ombuki-Berman, Andrew Runka
Erschienen in: Evolutionary Computation in Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we examine the predictability of genetic algorithm (GA) performance using information-theoretic fitness landscape measures. The outcome of a GA is largely based on the choice of search operator, problem representation and tunable parameters (crossover and mutation rates, etc). In particular, given a problem representation the choice of search operator will determine, along with the fitness function, the structure of the landscape that the GA will search upon. Statistical and information theoretic measures have been proposed that aim to quantify properties (ruggedness, smoothness, etc) of this landscape. In this paper we concentrate on the utility of information theoretic measures to predict algorithm output for various instances of the capacitated and time-windowed vehicle routing problem. Using a clustering-based approach we identify similar landscape structures within these problems and propose to compare GA results to these clusters using performance profiles. These results highlight the potential for predicting GA performance, and providing insight self-configurable search operator design.