Evolutionary algorithms for the bi-objective adjacent only quadratic spanning tree. (23rd December 2014)

• Record Type: Journal Article
• Authors: Maia, Sílvia Maria Diniz Monteiro; Goldbarg, Elizabeth Ferreira Gouvêa; Goldbarg, Marco César
• Is Part Of: International journal of innovative computing and applications. Volume 6:Number 2(2014)
• Page Start: 63
• Page End: 72
• Publication Date: 2014-12-23
• Subjects: bi-objective adjacent only quadratic spanning tree -- evolutionary algorithm -- multi-objective optimisation; Evolutionary computation -- Periodicals; Neural networks (Computer science) -- Periodicals; Genetic programming (Computer science) -- Periodicals; Biologically-inspired computing -- Periodicals; Swarm intelligence -- Periodicals; Quantum computers -- Periodicals; 006.3
• Languages: English
• ISSNs: 1751-648X

Abstract

The adjacent only quadratic minimum spanning tree (AQMST) is a version of the minimum spanning tree problem in which, besides the traditional linear costs, is necessary to consider quadratic costs resulting from interactions between adjacent edges. AQMST is NP-hard and models real world problems on transportation and distribution networks. Although, in literature, the linear and the quadratic costs are added, in real applications, they may be conflicting. In this case, it may be interesting to consider costs separately and, thus, multi-objective optimisation provides a more realistic model. Evolutionary algorithms have shown to be effective techniques to deal with multi-objective problems and, in this paper, evolutionary algorithms are proposed to the bi-objective version of the AQMST. A computational experiment on 132 instances is reported and conclusions on the proposed techniques are drawn.