Made available in DSpace on 2015-03-03T15:47:46Z (GMT). No. of bitstreams: 1 LeonardoCTB_DISSERT.pdf: 2119704 bytes, checksum: 5bdd21de8bfa668bba821593cdd5289f (MD5) Previous issue date: 2011-02-07 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico / Multi-objective combinatorial optimization problems have peculiar characteristics that require optimization methods to adapt for this context. Since many of these problems are NP-Hard, the use of metaheuristics has grown over the last years. Particularly, many different approaches using Ant Colony Optimization (ACO) have been proposed. In this work, an ACO is proposed for the Multi-objective Shortest Path Problem, and is compared to two other optimizers found in the literature. A set of 18 instances from two distinct types of graphs are used, as well as a specific multiobjective performance assessment methodology. Initial experiments showed that the proposed algorithm is able to generate better approximation sets than the other optimizers for all instances. In the second part of this work, an experimental analysis is conducted, using several different multiobjective ACO proposals recently published and the same instances used in the first part. Results show each type of instance benefits a particular type of instance benefits a particular algorithmic approach. A new metaphor for the development of multiobjective ACOs is, then, proposed. Usually, ants share the same characteristics and only few works address multi-species approaches. This works proposes an approach where multi-species ants compete for food resources. Each specie has its own search strategy and different species do not access pheromone information of each other. As in nature, the successful ant populations are allowed to grow, whereas unsuccessful ones shrink. The approach introduced here shows to be able to inherit the behavior of strategies that are successful for different types of problems. Results of computational experiments are reported and show that the proposed approach is able to produce significantly better approximation sets than other methods / Problemas de otimiza??o combinat?ria multiobjetivo apresentam caracter?sticas peculiares que exigem que t?cnicas de otimiza??o se adaptem a esse contexto. Como muitos desses problemas s?o NP-?rduos, o uso de metaheur?sticas tem crescido nos ?ltimos anos. Particularmente, muitas abordagens que utilizam a Otimiza??o por Col?nias de Formigas t?m sido propostas. Neste trabalho, prop?e-se um algoritmo baseado em col?nias de formigas para o Problema do Caminho mais Curto Multiobjetivo, e compara-se o algoritmo proposto com dois otimizadores encontrados na literatura. Um conjunto de 18 inst?ncias oriundas de dois tipos de grafos ? utilizado, al?m de uma metodologia espec?fica para a avalia??o de otimizadores multiobjetivo. Os experimentos iniciais mostram que o algoritmo proposto consegue gerar conjuntos de aproxima??o melhores que os demais otimizadores para todas as inst?ncias. Na segunda parte do trabalho, uma an?lise experimental de diferentes abordagens publicadas para col?nias de formigas multiobjetivo ? realizada, usando as mesmas inst?ncias. Os experimentos mostram que cada tipo de inst?ncia privilegia uma abordagem algor?tmica diferente. Uma nova met?fora para o desenvolvimento deste tipo de metaheur?stica ? ent?o proposta. Geralmente, formigas possuem caracter?sticas comuns e poucos artigos abordam o uso de m?ltiplas esp?cies. Neste trabalho, uma abordagem com m?ltiplas esp?cies competindo por fontes de comida ? proposta. Cada esp?cie possui sua pr?pria estrat?gia de busca e diferentes esp?cies n?o tem acesso ? informa??o dada pelo ferom?nio das outras. Como na natureza, as popula??es de formigas bem sucedidas tem a chance de crescer, enquanto as demais se reduzem. A abordagem apresentada aqui mostra-se capaz de herdar o comportamento de estrat?gias bem-sucedidas em diferentes tipos de inst?ncias. Resultados de experimentos computacionais s?o relatados e mostram que a abordagem proposta produz conjuntos de aproxima??o significativamente melhores que os outros m?todos