A New Evolutionary Algorithm for the Bi-objective Minimum Spanning Tree

Author

Rocha, Daniel A M ; Goldbarg, Elizabeth F G ; Goldbarg, Marco C.

Author_Institution

UFRN, Natal

fYear

2007

fDate

20-24 Oct. 2007

Firstpage

735

Lastpage

740

Abstract

Combinatorial optimization problems with multiple objectives are, in general, more realistic representations of practical situations than their counterparts with a single-objective. The bi-objective minimum spanning tree problem is an NP-hard problem with applications in network design. In this paper a transgenetic algorithm is applied to this problem. A computational experiment compares the proposed approach with a memetic algorithm. The comparison of the algorithms is done with basis on three indicators and statistical tests.

Keywords

computational complexity; genetic algorithms; network theory (graphs); statistical testing; trees (mathematics); NP-hard problem; biobjective minimum spanning tree; combinatorial optimization problems; evolutionary algorithm; memetic algorithm; network design; statistical testing; transgenetic algorithm; Approximation algorithms; Biology computing; Clustering algorithms; Design optimization; Evolutionary computation; Intelligent systems; NP-hard problem; Polynomials; Testing; Tree graphs;

fLanguage

English

Publisher

ieee

Conference_Titel

Intelligent Systems Design and Applications, 2007. ISDA 2007. Seventh International Conference on

Conference_Location

Rio de Janeiro

Print_ISBN

978-0-7695-2976-9

Type

conf

DOI

10.1109/ISDA.2007.24

Filename

4389695