Theory Driven Design of Efficient Genetic Algorithms for a Classical Graph Problem. Corus, D. & Lehre, P. K. In Recent Developments in Metaheuristics, of Operations Research/Computer Science Interfaces Series, pages 125–140. Springer, Cham, 2018.
Theory Driven Design of Efficient Genetic Algorithms for a Classical Graph Problem [link]Paper  doi  abstract   bibtex   
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.
@incollection{corus_theory_2018,
	series = {Operations {Research}/{Computer} {Science} {Interfaces} {Series}},
	title = {Theory {Driven} {Design} of {Efficient} {Genetic} {Algorithms} for a {Classical} {Graph} {Problem}},
	copyright = {All rights reserved},
	isbn = {978-3-319-58252-8 978-3-319-58253-5},
	url = {https://link.springer.com/chapter/10.1007/978-3-319-58253-5_8},
	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.},
	language = {en},
	urldate = {2018-03-11},
	booktitle = {Recent {Developments} in {Metaheuristics}},
	publisher = {Springer, Cham},
	author = {Corus, Dogan and Lehre, Per Kristian},
	year = {2018},
	doi = {10.1007/978-3-319-58253-5_8},
	pages = {125--140}
}

Downloads: 0