Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.1/203
Título: Ant colony algorithms for multiple objective combinatorial optimization: applications to the minimum spanning trees problems
Outros títulos: Algoritmos de Colonias de Hormigas para Optimizacion Combinatoria con Multiples Objetivos: Aplicaciones a los Problemas de Minimum Spanning Trees
Autor: Cardoso, Pedro J. S.
Palavras-chave: Swarm Intelligence, Multiobjective optimization, Computational Geometry
Investigação operacional
Data de Defesa: 3-Mai-2010
Resumo: 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 $\epsilon$-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.
URI: http://hdl.handle.net/10400.1/203
Aparece nas colecções:ISE1-Teses

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
PedroCardosoPhDTheses03-2007.pdf8,59 MBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.