Orientador: Pedro Sergio de Souza

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação

Resumo: Times Assíncronos (do inglês Asynchronous Teams ou A-Teams) constituem uma abordagem multi-algorítmica para a resolução aproximada de problemas, cujo princípio básico é a cooperação sinérgica entre um conjunto de algoritmos, que se comunicam assincronamente através de memórias...

Resumo: Times Assíncronos (do inglês Asynchronous Teams ou A-Teams) constituem uma abordagem multi-algorítmica para a resolução aproximada de problemas, cujo princípio básico é a cooperação sinérgica entre um conjunto de algoritmos, que se comunicam assincronamente através de memórias compartilhadas, propiciando soluções de melhor qualidade do que as geradas pelos mesmos algoritmos quando executados isoladamente. Este método tem sido aplicado com sucesso em problemas combinatórios com uma única função objetivo. O presente trabalho apresenta Times Assíncronos como sendo adequado à resolução de problemas de otimização combinatória com múltiplas funções objetivo. Diferentes estratégias para a manipulação de soluções multidimensionais foram desenvolvidas, tornando possível a rápida obtenção de soluções próximas ou mesmo pertencentes ao Pareto Ótimo do problema. Em especial, foi desenvolvida uma estrutura de manipulação de soluções multidimensionais que possibilita a consideração simultânea de todos os objetivos envolvidos para a geração de soluções. É proposto um novo problema NP-dificil como uma generalização do clássico Problema do Caixeiro Viajante (do inglês Traveling Salesman Problema ou TSP), onde ao invés de apenas uma matriz de distância existem múltiplas matrizes, sendo intitulado Problema do Caixeiro Viajante com Múltiplas Distâncias (do inglês Multi-Distance Traveling Salesman Problem ou MDTSP) e ao qual foi aplicado o método de Times Assíncronos. Os testes computacionais foram realizados de forma concorrente e paralela, obtendo-se conjuntos de soluções não-dominadas bem distribuídas dentro de uma ampla faixa de valores fornecidos pelas funções objetivo envolvidas, para todas as instâncias, mesmo envolvendo várias dimensões. Isto demonstra que os melhores conjuntos de soluções não-dominadas gerados pelos AT eams foram numerosos e contiveram soluções significativamente distintas entre s~ abrangendo todo o espectro desejado. Para as menores instâncias foi possível constatar que o melhor conjunto de soluções não-dominadas obtido fora o próprio Pareto Otimo. Ainda, foram desenvolvidos algoritmos para o novo problema que incorporam conceitos adequados a problemas multiobjetivos

Abstract: Asynchronous Teams or A-Teams constitute a mu1ti-algorithm approach for approximated problem solving, whose basic principle is the sinergic cooperation among a set of algorithms that communicate asynchronously through shared memories, providing solutions of better quality than those...

Abstract: Asynchronous Teams or A-Teams constitute a mu1ti-algorithm approach for approximated problem solving, whose basic principle is the sinergic cooperation among a set of algorithms that communicate asynchronously through shared memories, providing solutions of better quality than those generated by the same algorithms when executed separately. This method has been successfully applied to Combinatorial Optimization Problems with a single objective function. This work presents Asynchronous Teams as an adequated method to solving Combinatorial Optimization Problems with multiple objective junctions. Different strategies to the manipulation of multi-dimensional solutions were developed, allowing it possible to obtain near-optimal or Pareto Optimal solutions quickly. In special, was developed a structure for multidimensional solution manipulation that allowing it possible the simultanea consideration of all objectives involved to the solution generation. It is proposed a new NP-hard problem as a generalization of classic Traveling Salesman Problem or TSP, which, instead of only one distance matrix, has various matrices. It has been entitled of Multi-Distance Traveling Salesman Problem or MDTSP and to which was applied the Asynchronous Teams method. The implementation tests were accomplished in a concurrent and parallel way, obtaining set of non-dominated solutions well-distributed on a wide range of values provided by the objective functions involved, over the tested instances. This demonstrates that the best sets of non-dominated solutions obtained are numerous and contain solutions significantly distinct among them. To the small instances was possible to show that the best set of non-dominated solutions generated was the Pareto Optimal. Algorithms have been developed for the new problem with the incorporation of compromisse decision and dominance concepts. Still, were developed algorithms to the new problem that incorpore adequated concepts to multiobjective problems