Tez detayları

A novel meta-heuristic for graph coloring problem: Simulated annealing with backtracking = Çizge boyama problemi icin yeni bir sez ötesi algoritma: Geriye dönüş yöntemiyle benzetilmiş tavlama

Yazarlar:

Yilmaz, Buse

Yayıncı:

Yeditepe Üniversitesi

Ana Başlıklar:

Veri işleme & bilgisayar bilimi | Mühendislik ve uygulamalı operasyonlar

Belge Tipi:

Tezler

Program Tipi:

Yüksek Lisans

Yayın Tarihi:

12/2010

Belge Dili:

İngilizce

Document ID (Org No.):

2000091166

Özet

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.

Ç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.

Tez detayları

A novel meta-heuristic for graph coloring problem: Simulated annealing with backtracking = Çizge boyama problemi icin yeni bir sez ötesi algoritma: Geriye dönüş yöntemiyle benzetilmiş tavlama

Yazarlar: Yilmaz, Buse

Yayıncı: Yeditepe Üniversitesi

Ana Başlıklar: Veri işleme & bilgisayar bilimi | Mühendislik ve uygulamalı operasyonlar

Belge Tipi: Tezler

Program Tipi: Yüksek Lisans

Yayın Tarihi: 12/2010

Belge Dili: İngilizce

Document ID (Org No.): 2000091166