Solving graph coloring problem by using an evolutionary algorithm
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Marmara Üniversitesi, Fen Bilimleri Enstitüsü, Bilgisayar Mühendisliği (İngilizce) Anabilim Dalı, Türkiye
Tezin Onay Tarihi: 2020
Tezin Dili: İngilizce
Öğrenci: SERAP KORKMAZ
Danışman: Betül Boz
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Özet:Grafik renklendirme problemi düğümler ve kenarlardan oluşan yapılar olan grafiklerin renklendirilmesi problemidir. Renklendirme işlemi düğümlerin renklendirilmesi veya kenarların renklendirilmesi gibi farklı şekillerde yapılabilmektedir. Grafik renklendirme problemi problemin türüne göre düğüm sayıları, düğümler arasındaki kenar sayıları ve kenarların düğümlerle bağlanma şekillleri, düğümlerin ağırlığının olup olmaması vs. gibi birçok etkene sahiptir ve bu etkenlerin çeşitliliğine göre problemin karmaşıklığı da değişmektedir. Grafik renklendirme probleminin düğüm renklendirilmesi, kenar renklendirilmesi gibi alt grupları vardır. Düğüm renklendirmesinin bir türü olan "ağırlıklı düğüm renklendirme problemi" bu çalışmada ele alınmaktadır. Bu problemde düğümlerin her birinin ağırlık değeri vardır ve aralarında kenar bulunan düğümler farklı renklerle renklendirilir. Her renk grubundaki en ağır düğüm ilgili renk grubunun temsilci düğümü olarak belirlenir ve temsilci düğümlerin ağırlıkları toplamı grafik renklendirilirken minimize edilmeye çalışılır. Ağırlıklı düğüm renklendirme probleminin çözülmesi gerçek hayat uygulamalarının bir kısmının çözümünde kullanılabilmesi açısından önem taşır. Buna ek olarak problemin polinom zamanda bilinen bir çözümünün olmaması problemle ilgili üretilen çözüm yöntemlerini değerli kılar. Bu çalışmada ağırlıklı düğüm renklendirme probleminin çözümünde kullanmak amacıyla geliştirdiğimiz algoritmayı sunmaktayız. Geliştirdiğimiz algoritma birçok problemde yaygın olarak kullanılan ve doğadan esinlenen genetik algoritma tabanlı bir algoritmadır. Doğada olduğu gibi, genetik algoritmada da bireylerden yeni nesiller oluşur. Bireylerden yeni nesiller oluşurken crossover (çaprazlama) ve mutasyon ile genetik aktarım ve çeşitlilik sağlanır. Çalışmamızda farklı özelliklere öncelik veren ancak birlikte çalışan 2 crossover tekniğini ve bu tekniklerin uygulanması neticesinde elde edilen çözümlere uygulanan bir mutasyon tekniğini önermekteyiz. Önermiş olduğumuz teknikleri literatürde yer alan 3 çalışma ile karşılaştırmış bulunmaktayız. Karşılaştırmada kullanılan materyallerle ilgili bilgileri, karşılaştırma tekniğimizi, elde edilen sonuçları ve bu sonuçların karşılaştırmalarına çalışmamızın ilgili bölümlerinde yer vermekteyiz.