Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/66829
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem |
Author: | Neumann, F. |
Citation: | European Journal of Operational Research, 2007; 181(3):1620-1629 |
Publisher: | Elsevier Science BV |
Issue Date: | 2007 |
ISSN: | 0377-2217 1872-6860 |
Statement of Responsibility: | Frank Neumann |
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. |
Keywords: | Evolutionary computations Multi-objective minimum spanning trees Expected optimization time |
Rights: | Copyright © 2006 Elsevier B.V. All rights reserved. |
DOI: | 10.1016/j.ejor.2006.08.005 |
Published version: | http://dx.doi.org/10.1016/j.ejor.2006.08.005 |
Appears in Collections: | Aurora harvest Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.