کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
481942 | 1446192 | 2007 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem](/preview/png/481942.png)
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.
Journal: European Journal of Operational Research - Volume 181, Issue 3, 16 September 2007, Pages 1620–1629