Solving dynamic graph coloring problem by using a heuristic algorithm


Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Marmara Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2018

Tezin Dili: İngilizce

Öğrenci: GİZEM SÜNGÜ

Danışman: BETÜL BOZ

Ö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. ABSTRACT 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.