Rješavanje problema trgovačkog putnika uz pomoć genetskog algoritma

undergraduate thesis

• Title (english): Solving traveling salesman problem using genetic algorithm
• Author: Ivana Dasović
• Mentor: Marin Golub (mentor)
• Committee member: Marin Golub (predsjednik povjerenstva)
• Committee member: Antonio Močinić (član povjerenstva)
• Committee member: Eda Jovičić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2022-07-01, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U ovom radu obrađeni su problem trgovačkog putnika i genetski algoritmi. Prva dva poglavlja daju uvid u problem trgovačkog putnika i detaljan opis ideje i vrsta genetskih algoritama te njihovih opetatora. Često korištena metoda rješavanja problema trgovačkog putnika su genetski algoritmi. U svrhu ovog rada napravljeno je programsko rješenje u programskom jeziku Python implementacijom eliminacijskog genetskog algoritma koje je prikazano u 4. poglavlju. Programsko rješenje rješava simetrični i asimetrični problem trgovačkog putnika dajući ne optimalne, ali zadovoljavajuće rezultate. Navedeni su prednosti i nedostaci korištenja genetskih algoritama pri rješavanju problema trgovačkog putnika. Rezultati provedenog eksperimenta dani su grafički i u tablicama.

Abstract (english)

This paper deals with the traveling salesman problem and genetic algorithms. The first two chapters provide an insight into the traveling salesman problem and a detailed description of the idea and types of genetic algorithms and their operators. A commonly used method for solving the traveling salesman problem is genetic algorithms. For the purpose of this paper, a software solution in the Python programming language was developed by implementing the elimination genetic algorithm, which is presented in Chapter 4. The software solution solves the symmetrical and asymmetric traveling salesman problem by giving not optimal, but good enough results. The advantages and disadvantages of using genetic algorithms in solving the traveling salesman problem are listed. The results of the experiment are given graphically and in tables.

• Keywords: problem trgovačkog putnika; evolucija; genetski algoritam; populacija; jedinka; gen; selekcija; križanje; mutacije; kvaliteta rješenja
• Keywords (english): traveling salesman problem; evolution; genetic algorithm; population; individual; gene; selection; crossover; mutations; solution quality
• Language: croatian
• URN:NBN: urn:nbn:hr:168:825916
• 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: 2023-01-15 09:58:58