Title: Multi-objective evolutionary algorithm on simplified bi-objective minimum weight minimum label spanning tree problems

Authors: Xinsheng Lai; Xiaoyun Xia

Addresses: School of Mathematics and Computer Science, ShangRao Normal University, Shangrao, 334001, China ' College of Mathematics, Physics and Information Engineering, Jiaxing University, Jiaxing, 314001, China

Abstract: As general purpose optimisation methods, evolutionary algorithms have been efficiently used to solve multi-objective combinatorial optimisation problems. However, few theoretical investigations have been conducted to understand the efficiency of evolutionary algorithms on such problems, and even fewer theoretical investigations have been conducted on multi-objective combinatorial optimisation problems coming from real world. In this paper, we analyse the performance of a simple multi-objective evolutionary algorithm on two simplified instances of the bi-objective minimum weight minimum label spanning tree problem, which comes from real world. Though these two instances are similar, the analysis results show that the simple multi-objective evolutionary algorithm is efficient for one instance, but it may be inefficient for the other. According to the analysis on the second instance, we think that the restart strategy may be useful in making the multi-objective evolutionary algorithm more efficient for the bi-objective problem.

Keywords: multi-objective evolutionary algorithm; bi-objective; spanning tree problem; minimum weight; minimum label.

DOI: 10.1504/IJCSE.2019.103940

International Journal of Computational Science and Engineering, 2019 Vol.20 No.3, pp.354 - 361

Received: 08 Sep 2016
Accepted: 22 May 2017
Published online: 03 Dec 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article