Meta-heuristički algoritmi za određivanje kromatskog broja grafa

master's thesis

• Title (english): Meta-heuristic algorithms for determining the chromatic number of graphs
• Author: Lea Bundalo
• Mentor: Goranka Nogo (mentor)
• Committee member: Goranka Nogo (predsjednik povjerenstva)
• Committee member: Marko Vrdoljak (član povjerenstva)
• Committee member: Andrej Dujella (član povjerenstva)
• Committee member: Nenad Antonić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2021-03-04, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Problem bojenja grafa sastoji se od pridruživanja boje svakom vrhu grafa tako da su susjedni vrhovi obojeni različitim bojama, pri čemu je broj boja minimalan. Takav minimalan mogući broj boja naziva se kromatski broj grafa. Kako je problem bojenja grafa NP-potpun, ne postoji algoritam koji bi za bilo koji graf u realnom vremenu odredio pripadni kromatski broj. Zato se za rješavanje tog problema koriste meta-heuristički algoritmi. U ovom radu opisana su i implementirana dva meta-heuristička algoritma za određivanje kromatskog broja grafa - genetski algoritam i algoritam roja čestica u kombinaciji s tabu traženjem. Oba algoritma su populacijska i kao prostor rješenja koriste prostor potpunih, ali ne nužno pravilnih rješenja. Genetski algoritam iterativno, primjenom operatora križanja, mutacije i selekcije iz postojećih rješenja kreira nova, bolja rješenja. Algoritam roja čestica bazira se na kretanju čestice prema svom do sada pronađenom najboljem rješenju, najboljem pronađenom rješenju svojih susjeda ili nasumično generiranom rješenju kako bi istražila prostor rješenja i pronašla ono najbolje. Nakon pomaka pojedine čestice, pokreće se algoritam tabu traženja koji nastoji dodatno poboljšati trenutno rješenje. Algoritmi su testirani na grafovima baze DIMACS. Rezultati pokazuju da oba algoritma za većinu grafova pronalaze optimalna rješenja. Za kompleksnije grafove za koje algoritmi ne pronalaze optimalna rješenja, algoritam roja čestica pronalazi pravilna bojenja s manjim brojem boja nego genetski algoritam, ali mu je za to potrebno dulje vrijeme. Zbog toga odabir algoritma za daljnje korištenje ovisi o konkretnom problemu koji je potrebno riješiti, tj. je li važno da algoritam pronađe rješenje sa što manjim brojem boja ili da u što kraćem vremenu pronađe dovoljno dobro rješenje.

Abstract (english)

The graph coloring problem consists of associating the color to each vertex of the graph so that the adjacent vertices are painted with different colors and the number of colors is minimal. Such a minimum number of colors is called the chromatic number of graph. Since the graph coloring problem is NP-complete, there is no algorithm that would determine the chromatic number of any graph in real time. That is why meta-heuristic algorithms are used to solve this problem. Two meta-heuristic algorithms for determining the chromatic graph number are described and implemented in this thesis - genetic algorithm and hybrid particle swarm algorithm in combination with the taboo search. Both algorithms are population-based and use the solution space of complete improper colorings. The genetic algorithm iteratively, by applying the crossover, mutation and selection operators creates new, better solutions from existing solutions. The particle swarm algorithm is based on the movement of a particle towards its best solution so far, the best solution found by its neighbours or a randomly generated solution in order to explore the solution space and find the best coloring. After the movement of a particle, the tabu search algorithm attempts to further improve the current solution. Algorithms were tested on the DIMACS graphs. The results show that both algorithms find optimal solutions for most graphs. For complex graphs the particle swarm algorithm finds proper coloring with fewer colors than the genetic algorithm, but it takes longer to find it. Therefore, the choice of the algorithm for further use depends on the specific problem that needs to be solved, i.e. whether it is important for the algorithm to find a solution with as few colors as possible or to find a good enough solution as soon as possible.

• Keywords: kromatski broj grafa; genetski algoritam; algoritam roja čestica; algoritam tabu traženja; baza DIMACS
• Keywords (english): chromatic number of graph; genetic algorithm; hybrid particle swarm algorithm; taboo search algorithm; DIMACS graphs
• Language: croatian
• URN:NBN: urn:nbn:hr:217:215985
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2021-03-23 13:24:32