Solving graph coloring problem by using an evolutionary algorithm

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.--------------------Graph coloring problem is the problem of coloring graphs which are structures consisting of vertices and edges. Coloring can be done in different ways such as, edge coloring or vertex coloring. Graph coloring problem includes many factors such as number of vertices, number of edges between vertices, how these edges are connected with the vertices and whether vertices have weight values or not depending on type of the problem. Consequently, degree of complexity of the problem changes according to variety of the factors. Graph coloring problem contains subcategories such as edge coloring and vertex coloring. In this study, Weighted Vertex Coloring Problem which is a type of vertex coloring is studied. In weighted vertex coloring problem, each vertex has a weight value and vertices connected with an edge are colored with different colors. Heaviest vertex in each color class becomes the representative vertex of that color class and sum of weights of the representative vertices is tried to be minimized while coloring the graph.Solving the weighted vertex coloring problem is important because of being used in solving some real life applications. In addition, being an NP-hard problem makes solution methods offered for this problem important. In this study, we offer an algorithm to solve the weighted vertex coloring problem. Our proposed algorithm is based on Genetic Algorithm which is a nature-inspired algorithm and widely used in the literature to solve problems. In Genetic Algorithm, individuals form offspring as in nature. While forming offspring, crossover and mutation operators provide transfer of genes to offspring and variety. In our study, we propose 2 crossover operators working together but giving priority to different features and a mutation operator which is applied on solutions obtained by application of the proposed crossover operators. The proposed techniques are compared with 3 other techniques in the literature. Information about materials used in the comparison, comparison techniques, obtained results and comparison of the results are provided related sections in our study.