Rješavanje problema bojanja grafa evolucijskim algoritmom

završni rad

• Naslov (engleski): Solving graph coloring problem using evolutionary algorithm
• Autor: Filip Penzar
• Mentor: Marin Golub (mentor)
• Član povjerenstva: Marin Golub (predsjednik povjerenstva)
• Član povjerenstva: Vjeko Kužina (član povjerenstva)
• Član povjerenstva: Bojan Novković (č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-05, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U ovom je radu prikazan i opisan način rada evolucijskog algoritma i njegova primjena na rješavanje problema bojanja grafa. Navedene su prednosti i mane pojedinih strategija odabira roditelja i strategija mutacije kod genetskog algoritma. Analiziran je utjecaj različitih strategija na točnost određivanja kromatskog broja grafa te su rezultati međusobno uspoređeni i objašnjeni.

Sažetak (engleski)

This paper presents and describes how the evolutionary algorithm works and its application to solving the graph coloring problem. The advantages and disadvantages of individual parent selection strategies and mutation strategies in the genetic algorithm are listed. The influence of different strategies on the accuracy of determining the chromatic number of the graph was analyzed, and the results were compared and explained.

• Ključne riječi: evolucijski algoritam; genetski algoritam; kromatski broj; bojanje grafa; strategija mutacije; strategija odabira roditelja
• Ključne riječi (engleski): evolutionary algorithm; genetic algorithm; chromatic number; graph coloring; mutation strategy; parent selection strategy
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:289084
• 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:06:01