Publication
Ant colony algorithms for multiple objective combinatorial optimization: applications to the minimum spanning trees problems
| dc.contributor.author | Cardoso, Pedro J. S. | |
| dc.date.accessioned | 2010-05-03T14:50:23Z | |
| dc.date.available | 2010-05-03T14:50:23Z | |
| dc.date.issued | 2010-05 | |
| dc.description.abstract | 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. | pt |
| dc.identifier.other | AUT: PCA01382; | |
| dc.identifier.uri | http://hdl.handle.net/10400.1/203 | |
| dc.language.iso | eng | pt |
| dc.subject | Swarm Intelligence, Multiobjective optimization, Computational Geometry | pt |
| dc.subject | Investigação operacional | pt |
| dc.title | Ant colony algorithms for multiple objective combinatorial optimization: applications to the minimum spanning trees problems | pt |
| dc.title.alternative | Algoritmos de Colonias de Hormigas para Optimizacion Combinatoria con Multiples Objetivos: Aplicaciones a los Problemas de Minimum Spanning Trees | pt |
| dc.type | doctoral thesis | |
| dspace.entity.type | Publication | |
| person.familyName | Cardoso | |
| person.givenName | Pedro | |
| person.identifier.ciencia-id | 5F10-1C37-FE45 | |
| person.identifier.orcid | 0000-0003-4803-7964 | |
| person.identifier.rid | G-6405-2013 | |
| person.identifier.scopus-author-id | 35602693500 | |
| rcaap.rights | openAccess | pt |
| rcaap.type | doctoralThesis | pt |
| relation.isAuthorOfPublication | 62bebc54-51ee-4e35-bcf5-6dd69efd09e0 | |
| relation.isAuthorOfPublication.latestForDiscovery | 62bebc54-51ee-4e35-bcf5-6dd69efd09e0 |