Distributed evolutionary algorithm search for multiobjective spanning tree problem

Kumar, Rajeev ; Singh, P. K. ; Chakrabarti, P. P. (2005) Distributed evolutionary algorithm search for multiobjective spanning tree problem Lecture Notes in Computer Science, 3326 . pp. 103-120. ISSN 0302-9743

Full text not available from this repository.

Official URL: http://www.springerlink.com/content/05vgnxka2322bd...

Related URL: http://dx.doi.org/10.1007/978-3-540-30536-1_65


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.

Item Type:Article
Source:Copyright of this article belongs to Springer-Verlag.
ID Code:5995
Deposited On:19 Oct 2010 09:58
Last Modified:16 Jul 2012 05:05

Repository Staff Only: item control page