| Exploring the runtime of an evolutionary algorithm for the multi-objective shortest path problem. | |
| | |
MedLine Citation:
|
PMID: 20560760 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
We present a natural vector-valued fitness function f for the multi-objective shortest path problem, which is a fundamental multi-objective 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. Furthermore, we present lower bounds for the worst-case optimization time. |
| | |
Authors:
|
Christian Horoba |
Publication Detail:
|
Type: Journal Article |
Journal Detail:
|
Title: Evolutionary computation Volume: 18 ISSN: 1530-9304 ISO Abbreviation: Evol Comput Publication Date: 2010 |
Date Detail:
|
Created Date: 2010-08-03 Completed Date: 2010-11-05 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9513581 Medline TA: Evol Comput Country: United States |
Other Details:
|
Languages: eng Pagination: 357-81 Citation Subset: IM |
Affiliation:
|
Fakultät für Informatik, TU Dortmund, 44221 Dortmund, Germany. horoba@ls2.cs.tu-dortmund.de |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms* Evolution* Models, Statistical |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: An efficient algorithm for computing hypervolume contributions.
Next Document: Editorial for the Special Issue on Theoretical Aspects of Evolutionary Multi-Objective Optimization.