Primjena genetskog algoritma na problem trgovačkog putnika

završni rad

• Naslov (engleski): Application of Genetic Algorithm on Traveling Salesperson Problem
• Autor: Franjo Tukara
• Mentor: Marko Čupić (mentor)
• Član povjerenstva: Marko Čupić (predsjednik povjerenstva)
• Član povjerenstva: Fran Jelenić (član povjerenstva)
• Član povjerenstva: Filip Karlo Došilović (č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: 2023-07-06, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U ovom radu proučavana je primjena genetskog algoritma s lokalnom pretragom za rješavanje problema trgovačkog putnika (TSP). Kroz eksperimente na pet primjera TSP problema različitih veličina, koristeći GUI implementiran u programskom jeziku Java, analiziramo uspješnost genetskog algoritma s i bez lokalne pretrage.

Rezultati pokazuju da uvođenje lokalne pretrage značajno poboljšava performanse genetskog algoritma, omogućavajući brže i preciznije pronalaženje približno optimalnih rješenja za veće TSP probleme.

Ovi rezultati pružaju uvid u primjenu genetskog algoritma i lokalne pretrage za TSP probleme te mogu biti korisni u praktičnim primjenama optimizacijskih problema.

Sažetak (engleski)

In this research, we have investigated the application of a genetic algorithm with local search for solving the traveling salesman problem (TSP).

Through experiments on five instances of TSP problems of varying sizes, using a Java-based GUI implementation, we analyzed the effectiveness of the genetic algorithm.

The results demonstrate that the introduction of local search significantly improves the performance of the genetic algorithm, enabling faster and more precise identification of approximately optimal solutions for larger TSP problems. These findings provide insights into the application of the genetic algorithm and local search for TSP problems and can be valuable in practical implementations of optimization problems.

• Ključne riječi: Genetski algoritam; lokalna pretraga; problem trgovačkog putnika; križanje; mutacija; selekcija; funkcija dobrote; TSP; algoritam
• Ključne riječi (engleski): Genetic algorithm; local search; travelling salesman problem; crossover; mutation; selection; fitness function; TSP; algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:663141
• 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-10-11 10:49:25