A novel meta-heuristic for graph coloring problem: Simulated annealing with backtracking

Abstract

Çizge Boyama Problemi (ÇBP) üzerinde en yaygn çalisilan tümlesik optimizasyonproblemlerinden biridir. ÇBP'yi etkin sekilde çözmek için birçok algoritma tasarlanmstir.Hibrit algoritmalarin elde ettigi umut verici sonuçlar, bu algoritmalarin standard teknik veyaklasimlar kadar iyi oldugunu kantlamaktadr. Bu tezde, ÇBP'yi çözmek için, yeni birüst-sezgisel algoritma olan Geriye Dönüs Yöntemiyle Benzetilmis Tavlama (GDBT) yöntemigelistirilmistir. Tasarlanan algoritmada benzetilmis tavlama teknigi (BT) ile geriye dönüsyöntemi birlestirilmistir. GDBT, gruplama problemlerini çözmek için tasarlanmis hibritve genel amaçli bir algoritmadir ve bu algoritmada tanim kümesine özgü bilgi kullanmaz.DIMACS challenge suit'ten birçok kyaslama noktasi örnegi üzerinde yaplan testlerde umutverici sonuçlar elde edilmistir. Diger yandan, GDBT'nin en son gelismeleri yanstan birçokalgoritmayla karsilastirmasi ve algoritmanin performans analizi de tezde sunulmustur.

Graph coloring problem (GCP) is one of the most extensively studied combinatorialoptimization problems. Many algorithms have been proposed to solve GCP efciently. It hasbeen proved that hybrid algorithms are competitive with their pure counterparts as they yieldpromising results. This thesis presents a new meta-heuristic named as Simulated Annealingwith Backtracking (SABT) for solving GCP. The algorithm proposed combines simulatedannealing approach (SA) with a backtracking mechanism. SABT is a hybrid general purposealgorithm designed to solve any grouping problem. It does not exploit any domain-specicinformation. Several tests have been run on a collection of benchmarks from DIMACSchallenge suite and promising results are obtained. A comparison of SABT with someother state-of-the-art algorithms is also presented along with a performance analysis of thealgorithm.