Evolucijski algoritmi za bojanje grafova

diplomski rad

• Naslov (engleski): Evolutionary Algorithms for Graph Coloring
• Autor: Marko Bukal
• Mentor: Mario Osvin Pavčević (mentor)
• Član povjerenstva: Mario Osvin Pavčević (predsjednik povjerenstva)
• Član povjerenstva: Anamari Nakić (član povjerenstva)
• Član povjerenstva: Domagoj Kovačević (č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: 2019-02-25, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U ovome diplomskom radu proučavana su i implementirana dva hibridna evolucijska algoritma za rješavanje dobro poznatog problema bojanja grafova. Ovi algoritmi u literaturi su poznati pod nazivima \hca{} i \macol{}. Dana su iscrpna objašnjenja svakog evolucijskog operatora i ukazano je na pojedine implementacijske probleme. Algoritmi su testirani na DIMACS-ovoj bazi grafova te su prikazani ostvareni eksperimentalni rezultati. Analizirao se utjecaj određenih parametara i evolucijskih operatora na performanse algoritama.

Sažetak (engleski)

In this master's thesis two hybrid evolutionary algorithms for the well-known graph coloring problem are studied. These algorithms are known in the literature as \hca{} and \macol{}. An elaborate explanation of each evolutionary operator is given and questions concerning some implementation details are raised. The algorithms are evaluated on the DIMACS challenge benchmarks and achieved computational results are presented. The influence of certain parameters and evolutionary operators on the performance of the algorithms is analyzed.

• Ključne riječi: bojanje grafova; tabu pretraga; hibridni evolucijski algoritam; operator križanja; raznolikost populacije
• Ključne riječi (engleski): graph coloring; tabu search; hybrid evolutionary algorithm; crossover operator; population diversity
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:774733
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2019-03-13 19:25:47