Myrkoloni-optimering - Optimalt antal myror

The focus of this thesis paper is to study the impact the number of ants has on the found solution of the Ant Colony Optimization (ACO) metaheuristic when solving the Traveling Salesman Problem. The goal was to find out how the length of the computed tours change for different amounts of ants within a limited number of iterations. To study this, three well known versions of the ACO algorithm were implemented and tested: Min-Max Ant System (MMAS), Elitist Ant System (EliteAS) and Ranked Ant System (RankedAS). The results showed trends that were consistent over several test cases. EliteAS and RankedAS which both utilize specialist ants showed clear signs that the number of specialists had a large influence on the length of solutions. Meanwhile, normal ants did not affect the solutions as much. MMAS and EliteAS only had a small variation on the answer, with lower amount of ants being more favorable. On the other hand, RankedAS performed better by a large margin when working with five specialists and a number of ants equaling the number of cities in the problem.Målet med denna rapport var att studera hur antalet myror som används av Ant Colony Optimization (ACO) påverkar resultatet vid lö- sandet av Traveling Salesman Problem (TSP). Hur ändras lösningens längd med olika antal myror, när antalet iterationer som får användas är begränsat? För att få fram ett svar på frågan implementerades och testades tre välkända ACO algoritmer: Min-Max Ant System (MMAS), Elitist Ant System (EliteAS) och Ranked Ant System (RankedAS). Efter implementering och utförlig testning så uppdagades trender som var konsistenta över flera testfall. För EliteAS och RankedAS, som bå- da förlitar sig på specialiserade myror, hade antalet specialister en stor påverkan på den funna längden. Normala myror hade istället en liten påverkan på slutresultatet. För MMAS och EliteAS så var skillnaden minimal, med en viss favör mot ett lägre antal myror. RankedAS hade en motsatt trend och hade bäst resultat med fem specialister och lika många normala myror som antalet städer i TSP instansen