ACO and TSP

Jean-Luc Ngassa & Jakob Kierkegaard

Studenteropgave: Semesterprojekt

Abstrakt

We took an existing ant colony system framework with an accompanying TSP algorithm, which we changed by implementing different algorithms and extra functionality, in an attempt to acheive better tour constructions. We then extended it by implementing 2-opt and 2,5-opt optimization algorithms. We tested the program with cases found on TSPLIB, and compared our results with results from the original application and a third party ant colony algorithm. These results were then compared with the official optimal solutions. Even though our results never reached the optimal values, we achieved better results than those from the original framework without using our optimization algorithms, but they were never able to compete with the third party application. When applying optimization, we achieved results much better than the original framework, and slightly better than those gotten from the third party application.

UddannelserDatalogi, (Bachelor/kandidatuddannelse) Bachelor el. kandidat
SprogEngelsk
Udgivelsesdato29 maj 2007
VejledereKeld Helsgaun

Emneord

  • TSP
  • Ant Colony Optimization
  • ACS
  • Traveling Salesman problem
  • Ant
  • Local Search
  • ACO