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
Comparative Analysis of Ant Colony Optimization and Genetic Algorithm in Solving the Traveling Salesman Problem
Blekinge Institute of Technology.
2021 (English)Independent thesis Basic level (university diploma), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Metaheuristics is a term for optimization procedures/algorithms that can be applied to a wide range of problems. These problems for which metaheuristics are used usually fall in the NP-hard category, meaning that they cannot be solved in polynomial time. This means that as the input dataset gets larger the time to solve increases exponentially. One such problem is the traveling salesman problem (TSP) which is and has been widely used as a benchmark problem to test optimization algorithms. This study focused on two such algorithms called ant colony optimization (ACO) and genetic algorithm (GA) respectively. Development of such optimization algorithms can have huge implications in several areas of business and industry. They can for example be used by delivery companies to optimize routing of delivery vehicles as well as in material science/industry where they can be used to calculate the most optimal mix of ingredients to produce materials with the desired characteristics. The approach taken in this study was to compare the performance of the two algorithms in three different programming languages (python, javascript and C#).  Previous studies comparing the two algorithms have reported conflicting results where some studies found that ACO yielded better results but was slower than GA, while others found that GA yielded better results than ACO. Results of this study suggested that both ACO and GA could find the benchmark solution, but  ACO did so much more consistently. Furthermore javascript was found to be the most efficient language with which to run the algorithms in the setup used in this study.

Place, publisher, year, edition, pages
2021.
Keywords [en]
Ant colony optimization, genetic algorithm, metaheuristics, javascript, python, C#
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:bth-21520OAI: oai:DiVA.org:bth-21520DiVA, id: diva2:1566222
Subject / course
PA1438 Självständigt arbete Webbprogrammering
Educational program
PAGWG Webbprogrammering
Supervisors
Examiners
Available from: 2021-06-15 Created: 2021-06-14 Last updated: 2021-06-15Bibliographically approved

Open Access in DiVA

fulltext(794 kB)1760 downloads
File information
File name FULLTEXT01.pdfFile size 794 kBChecksum SHA-512
7350791a278f4491168fce07655b335c15474598db93f3ce8bfe8998b10a4f1a7fe24d1494fd984bdd1f5a8beeb9f1e4de6fd471c967d8e91ce9d53b7a381578
Type fulltextMimetype application/pdf

By organisation
Blekinge Institute of Technology
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 1761 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: 1088 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