Uma colônia de formigas para o caminho mais curto multiobjetivo

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

Conselho Nacional de Desenvolvimento Científico e Tecnológico

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