Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem
Date
2007
Authors
Neumann, F.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
European Journal of Operational Research, 2007; 181(3):1620-1629
Statement of Responsibility
Frank Neumann
Conference Name
Abstract
Evolutionary algorithms are applied to problems that are not well understood as well as to problems in combinatorial optimization. The analysis of these search heuristics has been started for some well-known polynomial solvable problems. Such analyses are starting points for the analysis of evolutionary algorithms on difficult problems. We present the first runtime analysis of a multi-objective evolutionary algorithm on a NP-hard problem. The subject of our analysis is the multi-objective minimum spanning tree problem for which we give upper bounds on the expected time until a simple evolutionary algorithm has produced a population including for each extremal point of the Pareto front a corresponding spanning tree. These points are of particular interest as they give a 2-approximation of the Pareto front. We show that in expected pseudopolynomial time a population is produced that includes for each extremal point a corresponding spanning tree. © 2006 Elsevier B.V. All rights reserved.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
Copyright © 2006 Elsevier B.V. All rights reserved.