Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Evaluating pheromone intensities and 2-opt local search for the Ant System applied to the Dynamic Travelling Salesman Problem
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2017 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
Utvärdering av feromonintensiteter och 2-opt lokalsökning i Ant System för det dynamiska handelsresandeproblemet (Swedish)
Abstract [en]

Ant Colony Optimization (ACO) algorithms have been successful in solving a wide variety of NPhard optimization problems. The Traveling Salesman Problem (TSP) has served as a benchmarking problem for many novel ACO algorithms. The slightly harder Dynamic Traveling Salesman Problem (DTSP) is more realistic in the sense that real-time changes happen in the graph belonging to a TSP instance. This thesis studied the original ACO algorithm: the Ant System, and how the amount of pheromone deposited by the ants within the algorithm affected the performance when solving both TSP and DTSP problems. Additionally, 2-opt local search was added to the algorithm, to see how it impacted the performance. We found that when the ants deposited a greater amount of pheromone, the performance for TSP increased, while the performance for DTSP decreased. We concluded that the Ant System in its original form is unsuitable for solving the DTSP. 2-opt local search improved the performance in all instances.

Abstract [sv]

Ant Colony Optimization-algoritmer (ACO) har visat sig vara bra på att lösa många olika NP-svåra optimeringsproblem. För att mäta prestandan för nya ACO-algoritmer har i många fall Handelsresandeproblemet (eng. TSP) använts. Den dynamiska varianten av TSP (eng. DTSP), är ett något svårare problem då förändringar i grafen kan ske i realtid. Denna uppsats utredde hur olika mängder feromon som avges av myrorna inuti algoritmen Ant System, påverkade prestandan för både TSPoch DTSP-instanser. Utöver detta studerades hur den lokala sökningsheuristiken 2-opt påverkade prestandan. Resultaten visade att om myrorna tilläts släppa mer feromoner, ökade prestantan för TSP, men minskade för DTSP. Därav drog vi slutsatsen att algoritmen Ant System i sin ursprungliga form ej är lämplig för att lösa DTSP. Den lokala söknigsheuristiken 2-opt förbättrade prestandan i alla tester.

Place, publisher, year, edition, pages
2017.
Keywords [en]
ACO, Ant System, Traveling Salesman Problem, Dynamic Traveling Salesman Problem, 2-opt local search
Keywords [sv]
Handelsresandeproblemet, Dynamiska Handelsresandeproblemet
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-209404OAI: oai:DiVA.org:kth-209404DiVA, id: diva2:1111660
Supervisors
Examiners
Available from: 2017-06-19 Created: 2017-06-19 Last updated: 2018-01-13Bibliographically approved

Open Access in DiVA

fulltext(1388 kB)81 downloads
File information
File name FULLTEXT01.pdfFile size 1388 kBChecksum SHA-512
5056aed48061161ced365913cdad0dbb0512b2f1db4a5ad09a0bf46b21da35fc821fac015307b4e0bb3e8fac76141c8ab89270bc89939e51337fe205ed55b3e2
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 81 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 87 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf