Naslov
Rješavanje problema bojanja grafova primjenom hibridnog evolucijskog algoritma
(Graph Colouring with a Hybrid Genetic Algorithm)

Autori
Kindl, Hrvoje

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
18.09

Godina
2008

Stranica
52

Mentor
Jakobović, Domagoj

Ključne riječi
bojanje grafova; GA
(graph colouring; GA)

Sažetak
U ovom diplomskom radu proučen je i opisan problem bojanja vrhova jednostavnih grafova te primjene tog problema na praktične probleme iz stvarnog života. Detaljno je istražena i programski ostvarena primjena hibridnog evolucijskog algoritma na rješavanje ovog problema. Ideja hibridnog evolucijskog algoritma sastoji se od ugradnje metode lokalne pretrage u evolucijski algoritam s populacijom rješenja. Također, predstavljena je nova klasa specijaliziranih operatora križanja za ovaj problem. Eksperimentalno je ispitana učinkovitost ostvarenog programskog rješenja na DIMACS ispitnim primjercima grafova. Naposlijetku, načinjena je usporedba s najboljim poznatim rezultatima iz literature i dane su smjernice za daljnje istraživanje.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA