Details

Autor(en) / Beteiligte

• Lai, Xinsheng

Titel

On Performance of a Simple Multi-objective Evolutionary Algorithm on the Constrained Minimum Spanning Tree Problem

Ist Teil von

• International journal of computational intelligence systems, 2022-08, Vol.15 (1), p.1-11, Article 57

Ort / Verlag

Dordrecht: Springer Netherlands

Erscheinungsjahr

2022

Quelle

Free E-Journal (出版社公開部分のみ）

Beschreibungen/Notizen

• The constrained optimization problems can be transformed into multi-objective optimization problems, and thus can be optimized by multi-objective evolutionary algorithms. This method has been successfully used to solve the constrained optimization problems. However, little theoretical work has been done on the performance of multi-objective evolutionary algorithms for the constrained optimization problems. In this paper, we theoretically analyze the performance of a multi-objective evolutionary algorithms on the constrained minimum spanning tree problem. First, we theoretically prove that the multi-objective evolutionary algorithm is capable of finding a (2,1)-approximation solution for the constrained minimum spanning tree problem in a pseudopolynomial runtime. Then, this simple multi-objective evolutionary algorithm is shown to be efficient on a constructed instance of the problem.