Primjena genetskog algoritma na problem trgovačkog putnika

undergraduate thesis

• Title (english): Application of Genetic Algorithm on Traveling Salesperson Problem
• Author: Franjo Tukara
• Mentor: Marko Čupić (mentor)
• Committee member: Marko Čupić (predsjednik povjerenstva)
• Committee member: Fran Jelenić (član povjerenstva)
• Committee member: Filip Karlo Došilović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-07-06, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

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