Digitala Vetenskapliga Arkivet

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
Ant Colony Optimization - Optimal Number of Ants
KTH, School of Electrical Engineering and Computer Science (EECS).
KTH, School of Electrical Engineering and Computer Science (EECS).
2018 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
Myrkoloni-optimering - Optimalt antal myror (Swedish)
Abstract [en]

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.

Abstract [sv]

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.

Place, publisher, year, edition, pages
2018.
Series
TRITA-EECS-EX ; 2018:229
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-229764OAI: oai:DiVA.org:kth-229764DiVA, id: diva2:1214402
Subject / course
Computer Science
Supervisors
Examiners
Available from: 2018-08-03 Created: 2018-06-06 Last updated: 2022-06-26Bibliographically approved

Open Access in DiVA

fulltext(466 kB)6313 downloads
File information
File name FULLTEXT01.pdfFile size 466 kBChecksum SHA-512
dc2209375711559401fdad3e0219768d86aa06675083eb30083ea71a5957887b89b261bada8a289d5bf31e4e7a52e08de3cf37f85bdcaedcdd90254d14e548e6
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 6314 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: 647 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