ABSTRACT
Pedro Jorge Sequeira Cardoso, Ph.D.
University of Seville, 2006

The study of meta-heuristic solutions based on the Ant Colony Optimization (ACO)
paradigm for the Multiple Objective Minimum Spanning Trees and related combinatorial
problems is the main concern of this investigation.

In the commonly accepted complexity scale for problems, the Multiple Objective
Minimum Spanning Trees is rated as an NP-complete problem. Furthermore, as in the
generality of the multiple objective optimization problem, the solution of the Minimum
Spanning Trees case is a set of trade-off solutions in the sense that to improve one of
the objectives it is necessary to worse at least one of the others, which is a major
concern in a practical point of view.

In the first part of the investigation, a theoretical analysis of the problem is made
to complement the known results. This analysis corroborates the fact that in practice
the use of exact methods to solve the Multiple Objective Minimum Spanning Trees
problems is only applied in specific circumstances. This implies that to solve the problem
an approximation method must be considered as an alternative. In particular, two
methods based on the ACO paradigm are proposed: the Multiple Objective Network
optimization based on an ACO (MONACO) and the e-Depth ANT Explorer (e-DANTE).

The MONACO method uses a set of pheromone trails and specific heuristics to approximate
the Pareto set. The e-DANTE method is an improvement of the MONACO method
that uses a depth search procedure, based on the best performing solutions, to deeply
exploit the search space.

The proposed methods are tested with selected multiple objective problems, improving
the results previously obtained by other authors. To test the MONACO and
e-DANTE algorithms over the Multiple Objective Minimum Spanning Trees problem is
proposed a library/repository of multiple objective network problems established over a
systematized set of networks generators. The results obtained with MONACO and e-DANTE
are then compared with the results obtained with a Brute Force and the Weighted
Sum method.