Çizge boyama ve çizgeyi kümeli boyama problemi üzerine metasezgisel algoritma

Graph Coloring (GCP) and Graph Set-T Coloring (GSTCP) are NP-hard combinatorial optimization problems.This thesis presents aframework that includes a Ruin and Recreate (RR) procedure, an acceptance criterion and a hill climber in order to solve GCPand GSTCP. Candidate solutions are generated by ruin and recreate methodology and these solutions are enhanced by anintegrated hill climber operation. Then, the acceptance mechanism is utilized for balancing the exploration and exploitationof the search space. Furthermore, two different methodologies are integrated into the framework for solving GCP. First, atabu mechanism is utilized to avoid the search points that are already visited. Then, a population based algorithm thatutilizes a certain amount of crossover operation is integrated into the framework for GCP. The aim is to benefit from thereproduction process that takes place in Genetic Algorithms (GAs). For GSTCP, an extra mutational operator is integrated tothe framework to improve the results obtained. The proposed framework is applied on a collection of data sets from DIMACS challenge suite and GEOM suite. The results are compared with other state of the art algorithms.