Solving dynamic graph coloring problem by using a heuristic algorithm
Sezgisel bir algoritma kullanarak dinamik grafik renklendirme problemi çözme
- Tez No: 501642
- Danışmanlar: YRD. DOÇ. DR. BETÜL DEMİRÖZ BOZ
- 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: 2018
- Dil: İngilizce
- Üniversite: Marmara Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 64
Özet
Grafik renklendirme problemi literatürdeki en popüler optimization problemlerinden biridir. Problemin grafiklerle modellenebilen bir çok gerçek probleme uygulunabilmesi, grafik renklendirme problemini önemli kılmaktadır. Problemin polinom zamanda henüz bir çözümünün bulunamaması, bu problem için bir çok sezgisel algoritmanın geliştirilmesine sebep olmuştur. Ancak geliştirilen bu sezgisel algoritmalar dinamik grafiklerdeki renklendirme problemlerine uyum sağlayamamıştır. Dinamik grafiklerdeki renklendirme problemi dinamik grafik renklendirme problemi olarak adlandırılmış ve bir kaç senedir üzerinde çalışmalar yapılmaya başlanmıştır. Bu sebeple, literatürde bu yeni keşfedilen problem için az sayıda sezgisel algoritma bulunmaktadır. Bu çalışmada, dinamik grafik renklendirme problemini çözmek amacıyla bir evrimsel algoritma geliştirilmiştir. Algoritma belirlenen bir zaman aralığında değişen dinamik grafikleri dikkate almaktadır ve bu değişimlere kolayca uyum sağlayabilmektedir. Algoritma literatürde yer alan ve dinamik grafik renklendirme problemi için geliştirilen iki sezgisel algoritma ile birlikte çeşitli senaryolara sahip bir çok dinamik grafik üzerinde test edilmiştir ve bu çalışmada sunulan algoritmanın bir çok durumda diğer algoritmalardan daha iyi sonuçlar elde ettiği görülmüştür.
Özet (Çeviri)
Graph coloring problem is one of the most popular optimization problem in the literature. The problem can be applied to solve many real-world problems that are modeled by using graphs. Since graph coloring problem is an NP-hard problem, there are many heuristic algorithms to solve the problem in different domains. However, these heuristic solutions are for solving static graphs and they are hard to be adapted in dynamic graphs. Graph coloring problem in dynamic graphs is called dynamic graph coloring problem and this problem has been explored for the last few years. Therefore, there are only a few and recently proposed heuristic algorithms to solve the dynamic graph coloring problem in the literature. In this study, we propose an evolutionary algorithm for solving dynamic graph coloring problem. The algorithm considers dynamic graphs changing over a given number of time steps. It adapts to the changes in the graph with its novel pool-based crossover operator easily. We tested our algorithm with two heuristic methods for dynamic graph coloring problem in the literature on dynamic graphs which have different characteristics and compared the solutions of the algorithms. The results show that our algorithm outperforms these two algorithms in most of the test cases given.
Benzer Tezler
- Dinamik ortamlar için istatiksel metotlar kullanan çoklu evrimsel algoritmalar
Multiploid evolutionary algorithms with statistical methods for dynamic environments
EMRULLAH GAZİOĞLU
Doktora
Türkçe
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AYŞE ŞİMA UYAR
- Hybridization of probabilistic graphical models and metaheuristics for handling dynamism and uncertainty
Değişimin ve belirsizliğin ele alınması için olasılıksal çizgesel biçelerin ve sezgi-üstlerinin melezleştirilmesi
GÖNÜL ULUDAĞ
Doktora
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AYŞE ŞİMA UYAR
- Novel centrality, topology and hierarchical-aware link prediction in dynamic networks
Dinamik ağlarda merkezilik, topoloji ve hiyerarşik tabanlı bağlanti tahmini
ABUBAKHARI SSERWADDA
Doktora
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. YUSUF YASLAN
YRD. DOÇ. ALPER ÖZCAN
- Performance comparison of membrane bioreactor with dynamic membrane bioreactor
Membran biyoreaktör ve dinamik membran biyoreaktörün performans karşılaştırması
MEHMET AKİF VERAL
Yüksek Lisans
İngilizce
2018
Çevre MühendisliğiYıldız Teknik ÜniversitesiBiyomühendislik Ana Bilim Dalı
PROF. DR. ÖZER ÇINAR
- Optimum dinamikli yüksek mertebeden aktif RC filtre sentezi ve simulasyon için bir paket program cafid
A Package program called cafid for the synthesis and the simulation and high order active RC filtres with the optimum dynamic range
ERSİN BAYRAMOĞLU
Yüksek Lisans
Türkçe
1994
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. ALİ NUR GÖNÜLEREN