Graflarda düğüm boyama problemi için kurbağa sıçrama algoritması tabanlı bir yaklaşım
An approach based on shuffled frog leaping algorithm for vertex coloring problem in graphs
Yazar: MURAT ASLAN
Danışman: YRD. DOÇ. DR. NURDAN BAYKAN
Selçuk Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2017
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Bilim ve Teknoloji = Science and Technology
Dizin: Optimizasyon = Optimization

Özet:
"Bir haritadaki komşu bölgeler farklı renkte boyandığında, en az kaç farklı renk kullanılarak bu harita boyanabilir" problemi olarak ortaya çıkan Graf Boyama Problemi (GBP), günümüzde harita boyama, zamanlama ve çizelgeleme problemi gibi birçok farklı gerçek hayat probleminin çözümünde kullanılmaktadır. Graflarda düğüm boyama ya da kavis boyama probleminde, bir grafı mümkün olan en az sayıda renk kullanarak boyamak, o graf için minimum rengi ifade etmekte ve kromatik sayı olarak adlandırılmaktadır. Graftaki düğüm ve kavis sayısı arttıkça problemin karmaşıklığı da artmaktadır. Bundan dolayı her algoritmasının çalışma süresi farklılık gösterebilir ve her algoritma kromatik sayıya ulaşamayabilir. Doğrudan GBP'nin çözümü için literatürde birçok açgözlü algoritma geliştirilmiştir. Bununla birlikte birçok metasezgisel algoritma GBP'ye uygulanmıştır. Kurbağa Sıçrama Algoritması (KSA), kurbağaların en az hareketle kaliteli besin kaynağına ulaşmak için yaptıkları hareketlerin modellenmesi ile geliştirilen bir algoritmadır. KSA'da bilgi paylaşımının hem mempleks olarak adlandırılan grup içinde hem de bir iterasyon sonunda tüm kurbağalarla yapılması gerek yerel arama uzayında gerekse de genel arama uzayında daha fazla çözüm arama imkânı vermektedir. Yapılan bu çalışma kapsamında KSA'da bazı değişiklikler yapılarak GBP'ye uygulanmıştır. GBP'nin kendine özgü yapısından dolayı KSA'nın saf halinin GBP'ye uygulanması iyi çözümler üretememiştir. Bundan dolayı yapılan değişikliklerle KSA'nın GBP için uygulanabilir bir yöntem olması sağlanmıştır. Bu kapsamda KSA'nın yerel arama mekanizması yeniden düzenlenmiştir. Alt mempleks içindeki en kötü kurbağanın yeni konumu Genetik Algoritmanın (GA) çaprazlama ve mutasyon operatörlerinden faydalanılarak hesaplanmaktadır. Çaprazlama operatörü alt mempleksteki en kötü kurbağanın, yerel ya da genel en iyi kurbağaya yakınsamasını sağlamaktadır. Mutasyon operatörü ise çaprazlama işleminde konumunu değiştiremeyen alt mempleksteki en kötü kurbağanın genlerinin değerlerini değiştirerek, en kötü kurbağa için yeni bir konum oluşturmaktadır. Ayrıca memetik evrim sonunda mempleksteki en iyi kurbağaya düğüm komşuluğu algoritmalarından (DKA) Chain yöntemi uygulanmaktadır. Chain yöntemi komşuları ile aynı renge sahip düğümlerin renklerini, düğümlerin komşuluklarını dikkate alarak değiştirmektedir. Böylece mempleks içindeki en iyi kurbağanın konumunu daha iyi bir noktaya götürmektedir. Algoritmanın çalışması esnasında, düzgün boyama kuralına uygun olarak sonuca ulaşıldığında, bu sonuç o ana kadarki en iyi çözüm olarak kaydedilmektedir. Ancak daha az renk kullanarak grafın boyanıp boyanamayacağını belirlemek amacıyla, renk sayısı bir azaltılarak, popülasyon yeniden üretilmektedir. Bunun için popülasyondaki bireylerden üst sınır (maksimum renk değeri) renk değerine sahip olan bireylerin renk değerleri bir azaltılmakta ve bireylerde güncelleme yapılmaktadır. Böylelikle daha az renk kullanarak, graf boyama işlemi tekrarlanmaktadır. Popülasyonda yapılan bu değişiklik daha iyi çözümlerin bulunmasını hızlandırmıştır. Bu kapsamda ayrıca kromatik sayısı bilinmeyen graflar için de literatürde bulunan en iyi değerlerden daha iyi sonuçlar bulunması hedeflenmiştir. Önerilen algoritma DIMACS tarafından sunulan Benchmark grafları üzerine uygulanarak sonuçlar değerlendirilmiştir. Deneysel sonuçlara göre önerilen yöntem (Modifiye KSA-MKSA) saf KSA'ya göre daha başarılı sonuçlar vermiştir. Ayrıca MKSA, literatürde bulunan algoritmalarla da karşılaştırılmış ve sonuçların başarılı olduğu gösterilmiştir.

Abstract:
The Graph Coloring Problem (GCP), which emerged as a problem such that "When adjacent regions in a map are colored with different colors, at least how many different colors can be used for this map? ", is nowadays being used to solve many different real-world problems such as map coloring, timetabling and scheduling problems. In the problem of vertex or edge coloring in graphs, coloring the graph using the least possible number of colors expresses minimum color for that graph and is called the chromatic number. As the number of vertices or edges in a graph increases, the complexity of the problem also increases. Because of this, each algorithm can not find the chromatic number of the problems and may also be different in their executing times.  Various greedy algorithms have been developed in the literature for the directly solution of the GCP. In addition, many metaheuristic methods are applied to GCP. The Shuffled Frog Leaping Algorithm (SFLA) is an algorithm that is developed by the modeling of the movements of frogs in order to achieve high quality food source with minimal movement.  It enables to find more solutions in both local and global search space because of that the sharing of information in the SFLA is done with all the frogs at the end of iteration and also the frogs in the group called memeplex. In this study, some changes were made to SFLA and applied to GCP. Due to the peculiar nature of the GCP, the implementation of the original SFLA into the GCP can not produce efficient solutions. Therefore, the implementations have made it possible for the SFLA to be available method for the GCP.  For this reason, the SFLA's local search mechanism has been rearranged.  The new position of the worst frog in the sub memeplex was calculated by using the crossover and mutation operators of the Genetic Algorithm (GA). The crossover operator ensures that the worst frog in the sub memeplex is close to the local or global best frog. The mutation operator creates a new position for the worst frog in the sub memeplex by changing the values of their genes. In addition, at the end of memetic evolution, the Chain method from vertex neighborhood algorithms (VNS) is applied to the best frog in the memeplex. The Chain method changes the colors of the nodes which have the same color with their neighbors, taking into consideration the neighborhoods of the nodes. This leads to a better position of the best frog in the memeplex. When the result of the algorithm is reached in accordance with the proper staining rule; this result is recorded as the best solution. However, the population is regenerated by reducing the number of colors by one in order to determine whether the graph can be colored using less color. For this reason, the color values of the individuals with the upper limit of color value (maximum color value) of the individuals in the population are reduced and updated. Thus, the graph coloring process is repeated using less color. This change in the population accelarates the process of finding better solutions. In this case, it is aimed to find better solutions than the current best solutions in the literature for graphs whose chromatic numbers is unknown. The proposed algorithm was applied on the Benchmark graphs presented by DIMACS and the results were evaluated. According to the experimental results, the proposed method (Modified SFLA-MSFLA) is more successful than the original SFLA. In addition, MSFLA is also compared with the algorithms in the literature and the results are shown to be successful.