Solving graph coloring problem by using an evolutionary algorithm
Başlık çevirisi mevcut değil.
- Tez No: 623818
- Danışmanlar: DR. ÖĞR. ÜYESİ 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: 2020
- 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 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.
Özet (Çeviri)
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.
Benzer Tezler
- Solving dynamic graph coloring problem by using a heuristic algorithm
Sezgisel bir algoritma kullanarak dinamik grafik renklendirme problemi çözme
GİZEM SÜNGÜ
Yüksek Lisans
İngilizce
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. BETÜL DEMİRÖZ BOZ
- Introduction to vertex-coloring problem
Köşe renklendirme problemine giriş
MOHAMMED JABBAR ABDULLAH AL-SHAFEAY
Yüksek Lisans
İngilizce
2022
MatematikÇankırı Karatekin ÜniversitesiMatematik Ana Bilim Dalı
DR. ÖĞR. ÜYESİ CELALETTİN KAYA
- A novel metaheuristic for graph and graphset-T coloring problem
Çizge boyama ve çizgeyi kümeli boyama problemi üzerine metasezgisel algoritma
ÇAĞRI YEŞİL
Yüksek Lisans
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. EMİN ERKAN KORKMAZ
- Graf renklendirme problemine uyarlanmış personel atama uygulaması
An implementation of personnel assignment adapted to graph coloring problem
MURAT CAN BURAK YILDIZ
Yüksek Lisans
Türkçe
2017
Endüstri ve Endüstri MühendisliğiBeykent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. ÜMİT TERZİ
- BitVertex evolutionary algorithm for accelerating graph coloring in register allocation
Kayıt tahsisinde çizge renklendirmeyi hızlandırmak için BitVertex evrimsel algoritması
GİZEM SÜNGÜ TERCİ
Doktora
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGebze Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ALP ARSLAN BAYRAKÇİ
DR. ÖĞR. ÜYESİ BETÜL BOZ