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

Research output: Contribution to journalArticlepeer-review


Colleges, School and Institutes

External organisations

  • Sheffield University


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.


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


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