|Title:||Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem|
|Abstract:||We present a natural fitness function f for the multiobjective shortest path problem, which is a fundamental multiobjective combinatorial optimization problem known to be NP-hard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomial-time randomized approximation scheme (FPRAS) for the problem under consideration, which exemplifies how EAs are able to find good approximate solutions for hard problems.|
|Appears in Collections:||Sonderforschungsbereich (SFB) 531|
This item is protected by original copyright
Items in Eldorado are protected by copyright, with all rights reserved, unless otherwise indicated.