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

završni rad

• Naslov (engleski): Solving traveling salesman problem using genetic algorithm
• Autor: Ivana Dasović
• Mentor: Marin Golub (mentor)
• Član povjerenstva: Marin Golub (predsjednik povjerenstva)
• Član povjerenstva: Antonio Močinić (član povjerenstva)
• Član povjerenstva: Eda Jovičić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2022-07-01, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: problem trgovačkog putnika; evolucija; genetski algoritam; populacija; jedinka; gen; selekcija; križanje; mutacije; kvaliteta rješenja
• Ključne riječi (engleski): traveling salesman problem; evolution; genetic algorithm; population; individual; gene; selection; crossover; mutations; solution quality
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:825916
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-15 09:58:58