Análise de Desempenho de Técnicas de Otimização Swarm Intelligence

A otimização nas aplicações modernas assume um carácter fortemente interdisciplinar relacionando-se com a necessidade de integração de diferentes técnicas e paradigmas na resolução de problemas reais complexos. Nas últimas décadas, tem havido um interesse crescente na aplicação de algoritmos que adotam de algum modo os princípios de processos estritamente naturais. São bem conhecidos os casos do Arrefecimento Simulado e da Pesquisa Tabu, permitindo a capacidade de aprendizagem e generalização. Por outro lado, a partir de paradigmas diferentes, ainda que claramente naturais, surgiram a partir de ideias iniciais de John Holland (1979) os primeiros conceitos sobre a Computação Evolucionária, introduzindo a capacidade evolutiva de adaptação e de hereditariedade de uma população. Dentro destes tipos de Computação Evolucionária e seguindo o mesmo princípio comum - a de uma população que se autoperpetua ao longo de uma série de transformações, lutando pela própria sobrevivência - os algoritmos genéticos são de longe os mais conhecidos. Mais recentemente, com inspiração no comportamento social dos insetos e outros animais surgiu o paradigma da Inteligência dos Enxames (Swarm Intelligence) desenvolvido a partir do estudo do comportamento coletivo auto-organizado de sistemas descentralizados, constituídos por um número elevado de agentes, com o objetivo de realizar uma determinada tarefa (Dorigo, 2007). Neste contexto, esta dissertação apresenta e discute a aplicabilidade de duas técnicas de otimização com base em Swarm Intelligence ao problema de Single Machine Total Weighted Tardiness, através do desenvolvimento de uma aplicação capaz de implementar algoritmos com base nas técnicas discutidas e da realização de testes de escalamento de tarefas que permitam obter métricas relevantes para a avaliação dosresultados obtidos. Em função destes, é efetuada uma análise estatística que permite retirar conclusões sobre a análise experimental efetuada. Este estudo permitiu concluir que o algoritmo de Ant Colony Optimization é capaz de bter resultados com tardeza total significativamente inferior ao algoritmo de Artificial Bee Colony, apesar de essa melhora se refletir num tempo de execução também maior, enquanto que o ABC é capaz de providenciar soluções muito rapidamente, a custo da qualidade da solução. A aplicabilidade de cada um dos algoritmos a este problema dependerá sempre do objetivo final da sua implementação, sendo o ACO claramente superior se o objetivo for obter a melhor solução possível. Caso o objetivo seja a obtenção de resultados com maior rapidez, então o ABC será mais adequado.The optimization in modern applications takes a strong interdisciplinary approach, relating to the integration needs of several different techniques and paradigms in solving complex real problems. In recent decades, there has been increasing interest in the application of algorithms that take some of the principles of strictly natural processes. Cases such as Simulated Annealing nd Tabu Search are well known. On the other hand, different paradigms, although clearly natural, have emerged from the initial ideas of John Holland (1979), such as the first concepts on Evolutionary Computation, which introduced the evolutionary adaptability and heredity of population. Within these types of Evolutionary Computation and following the same common principle - that of a population that is self-perpetuating over a series of transformations, fighting or survival - the genetic algorithms are by far the best known. More recently, inspired by the social behavior of insects and other animals came the paradigm of intelligence of Swarms (swarm intelligence) developed from the study of selforganized collective behavior of decentralized systems, consisting of a large number of agents, with the objective to perform a certain task in an optimal form (Dorigo, 2007). In this context, this dissertation presents and discusses the applicability of two optimization techniques based in swarm intelligence to the single machine total weighted tardiness problem, through the development of an application capable of implementing the discussed algorithms and solving appropriate task scheduling test cases, from which relevant metrics will be collected and used to properly derive the experimental analysis conclusions. This study allows us to conclude that the Ant Colony Optimization algorithm is capable of obtaining significantly lower total tardiness values when compared to the Artificial Bee Colony algorithm, despite also requiring higher amounts of execution time, while ABC is capable of providing solutions much faster, at the cost of solution quality. The applicability of each algorithm to the mentioned problem will always depend on the implementation objectives, ACO being clearly more adequate when the objective is to obtain the best solution possible. When the objective is to obtain solutions as fast as possible, then ABC seems to be more adequate