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.
Original language | English |
---|---|
Pages (from-to) | 125-140 |
Number of pages | 16 |
Journal | Operations Research/ Computer Science Interfaces Series |
Volume | 62 |
Early online date | 19 Sept 2017 |
DOIs | |
Publication status | Published - 1 Jan 2018 |
Bibliographical note
In: Amodeo L., Talbi EG., Yalaoui F. (eds) Recent Developments in Metaheuristics.Keywords
- Genetic algorithms
- Level-based analysis
- Runtime analysis
- Shortest path problems
ASJC Scopus subject areas
- Computer Science(all)
- Management Science and Operations Research