Bojanje grafova prilagodljivim metaheurističkim postupcima

master's thesis

• Title (english): Graph coloring with adaptive metaheuristics
• Author: Dino Šantl
• Mentor: Domagoj Jakobović (mentor)
• Committee member: Domagoj Jakobović (predsjednik povjerenstva)
• Committee member: Marko Čupić (član povjerenstva)
• Committee member: Stjepan Groš (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2014-07-09, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U radu se proučava inačica problema bojanja težinskih grafova, gdje je cilj minimizirati sumu težina konfliktnih bridova. Problem je primjenjiv u domeni telekomunikacija gdje se žele raspodijeliti kodovi po mobilnoj mreži. Problem se obrađuje teorijski i praktično. U teorijskom dijelu detaljno se analizira problem i određuju granice njegove rješivosti na računalu. U radu se primjenjuju različiti metaheuristički postupci. Pomoću metoda regresija pokušavaju se pronaći optimalna svojstva grafova, kako bi konvergencija bila što bolja. Na kraju su prikazani rezultati i zaključci.

Abstract (english)

In this work we study one instance of the weight graph coloring problem. The goal is to minimize the weighted sum of conflict edges. Problem can be applied in telecommunication domain, where the goal is to set codes in a mobile network. Problem can be observed as a theoretical problem and also as a practical problem. We study the problem in detail in the theoretical part and we determine the borders of the problem in computability theory. In this work we apply different metaheuristics algorithms. With regression methods we try to find the optimal graph properties for better convergention of algorithms. On the end of this work we show results and give a conclusions.

• Keywords: bojanje grafova; metaheuristika; strojno učenje; regresija; simulirano kaljenje; evolucijska strategija; genetsko kaljenje; agentski algoritam
• Keywords (english): graph coloring; metaheuristics; machine learning; regression; simulated annealing; evolution strategy; genetic annealing; agent algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:168:470371
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 12:11:28