Theory driven design of efficient genetic algorithms for a classical graph problem

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

External organisations

  • University of Sheffield

Abstract

This paper presents a principled way of designing a genetic algorithm which can guarantee a rigorously proven upper bound on its optimization time. The shortest path problem is selected to demonstrate how level-based analysis, a general purpose analytical tool, can be used as a design guide. We show that level-based analysis can also ease the experimental burden of finding appropriate parameter settings. Apart from providing an example of theory-driven algorithmic design, we also provide the first runtime analysis of a non-elitist population-based evolutionary algorithm for both the single-source and all-pairs shortest path problems.

Bibliographic note

In: Amodeo L., Talbi EG., Yalaoui F. (eds) Recent Developments in Metaheuristics.

Details

Original languageEnglish
Pages (from-to)125-140
Number of pages16
JournalOperations Research/ Computer Science Interfaces Series
Volume62
Early online date19 Sep 2017
Publication statusPublished - 1 Jan 2018

Keywords

  • Genetic algorithms, Level-based analysis, Runtime analysis, Shortest path problems