Prikaz rada algoritma skupine mrava na problemu trgovačkog putnika

undergraduate thesis

• Title (english): Demonstration of Ant Colony Algorithm Applied on Travelling Salesman Problem
• Author: Mateo Kelrajter
• Mentor: Nikica Hlupić (mentor)
• Committee member: Nikica Hlupić (predsjednik povjerenstva)
• Committee member: Damir Kalpić (član povjerenstva)
• Committee member: Boris Milašinović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2017-09-13, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Problem trgovačkog putnika problem je diskretne kombinatorne optimizacije. Tradicionalne metode rješavanja daju uvijek optimalne rezultate ali su nepogodne kod velikog broja gradova. Zbog velikog broja praktičnih primjena problema trgovačkog putnika postoji veliki interes za pronalaženjem pogodnih metoda rješavanja. Razvojem metoda heuristike javljaju se približni algoritmi. Takvi algoritmi daju približna rješenja problema koja odstupaju od optimalnih ali ih je moguće izvesti u razumnom vremenu.
Jedan od takvih algoritama je i algoritam skupine mrava, kojem je inspiracija ponašanje mrava u prirodi. Mravi u prirodi kao i umjetni mravi u algoritmu rješavaju kompleksne probleme iako su vrlo jednostavna stvorenja. Za njihov uspjeh je zaslužna međusobna komunikacija.
Algoritam skupine mrava daje rješenja koja odstupaju od optimalnih ali su dobivena u razumnom vremenu.

Abstract (english)

The traveling salesman is a descrete combinatorial optimization problem. Traditional solving methods allways return optimal results, however they are unfavorable for a large number of cities. Becouse there is a great number of practical applications, there is great interest to find favorable solving methods. With the developement of heuristic methods aproximate algorithms emerge. That kind of algorithms give apriximate solutions of problems, which diferentiate slightly from optimal solutions but are able to find solutions in reasonable time. One of those algorithms is ant colony optimization algorithm, which gains inspiration from the behavior of ants in nature. Although the are very simple creatures, nature ants like artificial ants in the algorithm solve complex problems.
Ant colony optimization algorithm offers solutions that differ slightly form optimal solutions but are solved in resonable time.

• Keywords: Problem trgovačkog putnika; algoritam skupine mrava; stimergija; umjetni mrav; feromon; parametri; alfa; beta; globalno isparavanje; lokano isparavanje; pseudoslučajni koeficijent
• Keywords (english): Traveling salesman problem; ant colony algorithm; stimergy; artificial ant; pheromone; parameters; alpha; beta; global evaporation; local evaporation; pseudorandom coefficient
• Language: croatian
• URN:NBN: urn:nbn:hr:168:088809
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-13 21:30:05