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
- Tez No: 305830
- Danışmanlar: DOÇ. DR. EMİN ERKAN KORKMAZ
- Tez Türü: Yüksek Lisans
- Konular: Mühendislik Bilimleri, Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Engineering Sciences, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2011
- Dil: İngilizce
- Üniversite: Yeditepe Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Ç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.
Özet (Çeviri)
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.
Benzer Tezler
- A novel metaheuristic for graph and graphset-T coloring problem
Çizge boyama ve çizgeyi kümeli boyama problemi üzerine metasezgisel algoritma
ÇAĞRI YEŞİL
Yüksek Lisans
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. EMİN ERKAN KORKMAZ
- Optimization of SPARQL queries using artificial intelligence techniques
Yapay zeka teknikleri kullanılarak SPARQL sorgularının optimizasyonu
ELEM GÜZEL KALAYCI
Yüksek Lisans
İngilizce
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDokuz Eylül ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. DERYA BİRANT
- Optimization methodology for application mapping in wireless network-on-chip
Kablosuz yonga-üstü-ağlar için uygulama eşleme optimizasyon metodolojisi
ALPEREN ÇAKIN
Yüksek Lisans
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHacettepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. SÜLEYMAN TOSUN
- A condition coverage-based black hole inspired meta-heuristic for test data generation
Koşullu kaplam tabanlı ve kara delik algoritması bazlı test verisi üretimi için meta-sezgisel bir yöntem
DERYA YELİZ ULUTAŞ
Yüksek Lisans
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ AYŞE TOSUN KÜHN
- Yeni bir biyolojik ilhamlı metasezgisel optimizasyon metodu: Yapay alg algoritması
A novel bio-inspired metaheuristic optimization method: Artificial algae algorithm
SAİT ALİ UYMAZ
Doktora
Türkçe
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. GÜLAY TEZEL
DOÇ. DR. ESRA YEL