A novel metaheuristic for graph and graphset-T coloring problem

Abstract

Çizgeyi boyama ve çizgeyi kümeli boyamaNP_zorkombinasyoneloptimizasyon problemleridir. Bu tezde, bu iki probleme çözüm getirmek için yapım ve yeniden yıkım prosedürü, kabul etme kriteri ve tepe tırmanma yönteminin bütünleştirildiği bir yöntem tasarlanmıştır. Yeni aday çözümler yapım ve yeniden yıkım prosedürü tarafından oluşturulurken, bu çözümler daha sonra tepe tırmanma yöntemi tarafından geliştirilmiştir. Geliştirilen çözüm belirli bir kabul etme kriterine göre kabul edilir ya da reddedilir. Buna ek olarak, iki farklı yöntem, kümeyi boyama problemi için tasarlanan yönteme ayrı ayrı eklenmiştir. İlk olarak, aynıçözümlerin yinelenmesini engellemek için tabu mekanizması algoritmaya entegre edilmiştir. Daha sonra ise belirli bir miktar çaprazlama işlemi gerçekleştirmek üzere algoritma popülasyon tabanlı yapıya dönüştürülmüştür. Amaç evrimsel algoritmada kullanılan çaprazlama işleminin sağladığıavantajlardan faydalanmaktır. Ayrıca çizgeyi kümeli boyama işlemi için de, mutasyon benzeri bir operatör sonuçları iyileştirmek için tasarlanan yapıya eklenmiştir.Tasarlanan yapı DIMACS ve GEOM test kümeleri üzerinde denenmiştir. Elde edilen sonuçlar bu iki alanda yapılan benzer ve en iyi sonuçları elde etmişçalışmalarla kıyaslanmıştır.

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.