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.
|Number of pages||16|
|Journal||Operations Research/ Computer Science Interfaces Series|
|Early online date||19 Sep 2017|
|Publication status||Published - 1 Jan 2018|
Bibliographical noteIn: 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