Parallell Max- Min Myrkoloni Optimering för Handelsresandeproblemet

Ant Colony Optimization (ACO) is a technique which can be used to find approximate Hamilton cycles for the Traveling Salesperson Problem (TSP). OpenMP is a framework which suites well for building multithreaded applications. Reimplementation of the Max- Min ACO algorithm with OpenMP was made in order to investigate whether there were any speedup and efficiency improvements when solving TSP problem instances of different node sizes for increasing number of threads. The algorithm runs showed a speedup improvement for the smallest TSP problem set with four threads. For all other problem sets the speedup was near 1.0 and the efficiency decreased with increasing number of threads. The average best number of iterations decreased for the two largest TSP problem sets as the number of thread increased. The performance results were unexpected and therefore more research of parallel enhancement and correctness verification of the reimplementation needs to be done. Myrkolonioptimering (ACO) är en teknik som kan användas för att hitta approximativa Hamilton cykler för Handelsresandeproblelemet (TSP). OpenMP är ett ramverk som fungerar väl för att bygga flertrådade applikationer. Om- implementering av MaxMin ACO algoritmen genom att nyttja OpenMP utfördes i syfte att undersöka om det fanns några fart och effektivitetsförbättringar när man löser TSP problem av olika hörn storlekar med ökande antal trådar. Algoritm körningarna visade att en fart förbättring kunde uppnås för TSP problemet med minst antal hörn. För alla andra problem låg farten förbättringen på 1.0 och effektiviteten minskade när antalet trådar ökade. Det bästa genomsnittliga antalet iterationer minskade för de två största TSP problemen när antalet trådar ökade. Prestanda resultaten var oväntade och därför behövs det läggas mer forskning inom parallelliseringsmetodik samt verifiering av den om- implementerade algoritmens korrekhet