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

Abstract

Abstract 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.

Keywords

• Approximation algorithm
• Multi-objective evolutionary algorithm
• Constrained optimization
• Spanning tree problem
• Combinatorial problem