A novel metaheuristic for graph and graphset-T coloring problem
Çizge boyama ve çizgeyi kümeli boyama problemi üzerine metasezgisel algoritma
- Tez No: 438679
- Danışmanlar: DOÇ. DR. EMİN ERKAN KORKMAZ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- 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ı: 70
Özet
Ç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.
Özet (Çeviri)
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.
Benzer Tezler
- 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
- Yüksek düzeyde sentezlemede hızlı tasarım alanı keşfi için makine öğrenmesi tabanlı yeni bir optimizasyon yöntemi
A novel machine learning-based optimization methodology for fast design space exploration in high-level synthesis
ESRA ÇELİK
Doktora
Türkçe
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAtatürk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. DENİZ DAL
- Integrating path planning and image processing with UAVs for disease detection and yield estimation in indoor agriculture
Kapalı alan tarımda hastalık tespiti ve verim tahmini için rota planlama ve görüntü işlemenin İHA'larla entegre edilmesi
ONAT ERDOĞMUŞ
Yüksek Lisans
İngilizce
2024
Mekatronik Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
PROF. DR. ERDİNÇ ALTUĞ
- 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
BUSE YILMAZ
Yüksek Lisans
İngilizce
2011
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