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

Dogan Corus*, Per Kristian Lehre

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


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.

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

Bibliographical note

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


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

ASJC Scopus subject areas

  • Computer Science(all)
  • Management Science and Operations Research


Dive into the research topics of 'Theory driven design of efficient genetic algorithms for a classical graph problem'. Together they form a unique fingerprint.

Cite this