Artificial Bee Colony Algorithm är en algoritm som tidigare tillämpats på många numeriska optimeringsproblem. Algoritmen är dock inte vanligt förekommande vad gäller vägplanering i dataspel. Detta arbete undersöker ifall algoritmen presterar bättre än A* på fyra olika testmiljöer eftersom A* är en av de mest använda algoritmerna för vägplanering i dataspel och således en bra referens. De aspekter som jämförs vid mätningarna är algoritmernas tidsåtgång samt längden på de resulterande vägarna. En riktad slumpgenerering av vägar har implementerats till algoritmen som gör att den inte fungerar på djupa återvändsgränder. Algoritmen har också en roulettehjulsselektion samt egenskapen att kunna generera slumpade grannvägar till de som skapats hittills. Resultaten visar att Artificial Bee Colony Algorithm presterar betydligt sämre än A* och att algoritmen därför inte är en bättre algoritm för vägplanering i dataspel. Algoritmen har dock potential till att prestera bättre och fungera på återvändsgränder om man förbättrar dess slumpgenerering av vägar.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-03-06T11:57:32Z No. of bitstreams: 1 grasielereginaduarte.pdf: 2553018 bytes, checksum: e0b9afbcc0b18965321f8db8ea7d38b8 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-03-06T20:19:40Z (GMT) No. of bitstreams: 1 grasielereginaduarte.pdf: 2553018 bytes, checksum: e0b9afbcc0b18965321f8db8ea7d38b8 (MD5) / Made available in DSpace on 2017-03-06T20:19:40Z (GMT). No. of bitstreams: 1 grasielereginaduarte.pdf: 2553018 bytes, checksum: e0b9afbcc0b18965321f8db8ea7d38b8 (MD5) Previous issue date: 2015-03-06 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Os problemas de otimização estão presentes em diversas áreas de atuação da sociedade e o uso de algoritmos bio-inspirados para a resolução de problemas complexos deste tipo vem crescendo constantemente. O Algoritmo Colônia de Abelhas Artificiais (ABC – do inglês Artificial Bee Colony) é um algoritmo bio-inspirado proposto em 2005 para a resolução de problemas de otimização multimodais e multidimensionais. O fenômeno natural que inspirou o desenvolvimento do ABC foi o comportamento inteligente observado em colônias de abelhas, mais especificamente no forrageamento. O ABC foi proposto inicialmente para ser aplicado na resolução de problemas sem restrições. Este trabalho avalia o desempenho do ABC quando aplicado na resolução de problemas de otimização com restrições. Para o tratamento das restrições, métodos de penalização serão incorporados ao ABC. São analisados diversos métodos de penalização, de diferentes tipos, com o objetivo de identificar com qual deles o algoritmo apresenta melhor desempenho. Além disto, são avaliadas possíveis limitações e cuidados que devem ser tomados ao combinar métodos de penalização ao ABC. O algoritmo proposto é avaliado através da resolução de problemas de otimização encontrados na literatura. Vários experimentos computacionais são realizados e gráficos e tabelas são gerados para demonstração dos resultados obtidos que também são discutidos. / Optimization problems are present in several areas of society and the use of bio-inspired algorithms to solve complex problems of this type has been growing constantly. The Artificial Bee Colony Algorithm (ABC) is a bio-inspired algorithm proposed in 2005 for solving multimodal and multidimensional optimization problems. The natural phenomenon that inspired the development of the ABC was intelligent behavior observed in bee colonies, more specifically in foraging. The ABC was initially proposed to be applied to solve unconstrained problems. This study evaluates the performance of ABC when applied in solving constrained optimization problems. For the treatment of constraints, penalty methods will be incorporated into the ABC. Several penalty methods, of different types, are analyzed with the goal of identifying which of these penalty methods offers better performance. Furthermore, possible limitations and care that should be taken when combining penalty methods to ABC are evaluated. The proposed algorithm is evaluated by solving optimization problems found in the literature. Several computational experiments are performed and graphs and tables are generated for demonstration of the obtained results which are also discussed.