Distributed evolutionary algorithm search for multiobjective spanning tree problem

Abstract

The problem of computing spanning trees along with specific constraints is mostly NP-hard. Many approximation and stochastic algorithms which yield a single solution, have been proposed. Essentially, the problem is multi-objective in nature, and a major challenge to solve the problem is to capture possibly all the (representative) equivalent and diverse solutions at convergence. In this paper, we formulate the generic multi-objective spanning tree (MOST) problem, and attempt to solve, in a novel way, with evolutionary algorithm (EA). We consider, without loss of generality, edge-cost and diameter as the two objectives. Since the problem is hard, and the Pareto-front is unknown, the main issue in such problem-instances is how to assess the convergence. We use a multiobjective evolutionary algorithm (MOEA) that produces diverse solutions without needing a priori knowledge of the solution space. We employ a distributed version of the algorithm and generate solutions from multiple tribes in order to have some approximation of the movement of the solution front. Since no experimental results are available for MOST, we consider two well known diameter-constrained spanning tree algorithms and modify them, for fair comparison, to yield a near-optimal solution-front. We observe that EA could provide superior solutions in the entire-range of the Pareto-front, which none of the existing algorithms could do.