Neidio i’r brif dudalen lywio Neidio i chwilio Neidio i’r prif gynnwys

Performance Analysis of Evolutionary Algorithms for the Minimum Label Spanning Tree Problem

  • Xinsheng Lai
  • , Yuren Zhou
  • , Jun He
  • , Jun Zhang

Allbwn ymchwil: Cyfraniad at gyfnodolyn › Erthygl › adolygiad gan gymheiriaid

34 Dyfyniadau (Scopus)
168 Wedi eu Llwytho i Lawr (Pure)

Crynodeb

A few experimental investigations have shown that evolutionary algorithms (EAs) are efficient for the minimum label spanning tree (MLST) problem. However, we know little about that in theory. In this paper, we theoretically analyze the performances of the (1+1) EA, a simple version of EA, and a simple multiobjective evolutionary algorithm called GSEMO on the MLST problem. We reveal that for the MLSTb problem, the (1+1) EA and GSEMO achieve a (b + 1)/2-approximation ratio in expected polynomial runtime with respect to n, the number of nodes, and k, the number of labels. We also find that GSEMO achieves a (2 lnn+1)-approximation ratio for the MLST problem in expected polynomial runtime with respect to n and k. At the same time, we show that the (1+1) EA and GSEMO outperform local search algorithms on three instances of the MLST problem. We also construct an instance on which GSEMO outperforms the (1+1) EA.
Iaith wreiddiolSaesneg
Rhif yr erthygl6670713
Tudalennau (o-i)860-872
Nifer y tudalennau13
CyfnodolynIEEE Transactions on Evolutionary Computation
Cyfrol18
Rhif cyhoeddi6
Dyddiad ar-lein cynnar20 Tach 2013
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 01 Rhag 2014

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Performance Analysis of Evolutionary Algorithms for the Minimum Label Spanning Tree Problem'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn