Algoritmi optimizacije kolonijom mrava

master's thesis

• Author: Iva Hršak
• Mentor: Saša Singer (mentor)
• Committee member: Saša Singer (predsjednik povjerenstva)
• Committee member: Matija Kazalicki (član povjerenstva)
• Committee member: Tina Bosner (član povjerenstva)
• Committee member: Ozren Perše (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2018-11-27, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu bavimo se algoritmima optimizacije kolonijom mrava (engl.\ Ant colony optimization, skraćeno ACO). Na početku objašnjavamo od kuda dolazi motivacija za ovakvu vrstu algoritama i dajemo opis ACO metaheuristike i njezine primjene na problem trgovačkog putnika. U nastavku opisujemo tri najpoznatije vrste ACO algoritama, to su: Mravlji sustav, MAX--MIN mravlji sustav i Sustav mravlje kolonije. Također, navodimo sve njihove najvažnije karakteristike. Na kraju, navodimo eksperimentalne rezultate dobivene primjenom algoritama na problem trgovačkog putnika. Na kraju se nalazi i kod ACO algoritama, implementiran u programskom jeziku Python, iz kojeg su dobiveni navedeni rezultati.

Abstract (english)

This paper presents the Ant colony optimization algorithms (ACO). At the beginning, we explain where the motivation for this kind of algorithm comes from and we give a definition of ACO metaheuristics and its application to the travelling salesman problem. Further, we describe the three most successful ACO algorithms: Ant System, MAX-MIN Ant System and Ant Colony System. Also, we describe all their most important characteristics. At the end of this paper we present experimental results obtained by applying algorithms to the travelling salesman problem. Finally, we also give a code, written in Python, which is used to get the experimental results.

• Keywords: optimizacija kolonije mrava; ACO; ant colony optimization; problem trgovačkog putnika; Python
• Keywords (english): ant colony optimization; ACO; travelling salesman problem; Python
• Language: croatian
• URN:NBN: urn:nbn:hr:217:988806
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-04-26 12:54:29