A Particle Swarm Approach for Combinatorial Optimization Problems

Os problemas de otimização combinatória têm como objetivo maximizar ou minimizar uma função definida sobre um certo domínio finito. Já as metaheurísticas são procedimentos destinados a encontrar uma boa solução, eventualmente a ótima, consistindo na aplicação de uma heurística subordinada, a qual tem que ser modelada para cada problema específico. Este trabalho apresenta algoritmos baseados na técnica de otimização por nuvem de partículas (metaheurística) para dois problemas de otimização combinatória: o Problema do Caixeiro Viajante e o Problema da Árvore Geradora Mínima Restrita em Grau Multicritério. O primeiro é um problema em que apenas um objetivo é otimizado, enquanto o segundo é um problema que deve lidar com múltiplos objetivos. Os algoritmos propostos são comparados a outras abordagens para o mesmo problema em questão, em termos de qualidade de solução, a fim de verificar a eficiência desses algoritmosCombinatorial optimization problems have the goal of maximize or minimize functions defined over a finite domain. Metaheuristics are methods designed to find good solutions in this finite domain, sometimes the optimum solution, using a subordinated heuristic, which is modeled for each particular problem. This work presents algorithms based on particle swarm optimization (metaheuristic) applied to combinatorial optimization problems: the Traveling Salesman Problem and the Multicriteria Degree Constrained Minimum Spanning Tree Problem. The first problem optimizes only one objective, while the other problem deals with many objectives. In order to evaluate the performance of the algorithms proposed, they are compared, in terms of the quality of the solutions found, to other approache