Authors: Horoba, Christian
Title: Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem
Language (ISO): en
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.
URI: http://hdl.handle.net/2003/26165
http://dx.doi.org/10.17877/DE290R-9020
Issue Date: 2008-12
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
25808.pdfDNB223.47 kBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.