Geri Dön

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

PDF İndir

  1. Tez No: 453499
  2. Yazar: MURAT ASLAN
  3. Danışmanlar: YRD. DOÇ. DR. NURDAN BAYKAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Bilim ve Teknoloji, Computer Engineering and Computer Science and Control, Science and Technology
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2017
  8. Dil: Türkçe
  9. Üniversite: Selçuk Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 121

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

Özet (Çeviri)

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.

Benzer Tezler

  1. Tez No

    700252

    Anti-KIR ile aktive edilmiş NK-92 hücrelerinin meme kanseri hücreleri üzerindeki öldürücü etkisinin araştırılması

    Investigation of the killer effect of anti-KIR activated NK-92 cells on breast cancer cells

    NİL KILIÇ

    Doktora

    Türkçe

    Türkçe

    2021

    BiyolojiAnkara Üniversitesi

    Biyoloji Ana Bilim Dalı

    PROF. DR. İRFAN KANDEMİR

    ÖĞR. GÖR. MOHAMMADREZA DASTOURI

  2. Tez No

    352440

    Investigation of device for measuring sewability

    Dikilebilirliğin ölçümü için cihaz geliştirilmesi

    GÜLSÜM ÇAKICI

    Yüksek Lisans

    İngilizce

    İngilizce

    2013

    Tekstil ve Tekstil Mühendisliğiİstanbul Teknik Üniversitesi

    Tekstil Mühendisliği Ana Bilim Dalı

    PROF. DR. FATMA KALAOĞLU

  3. Tez No

    69541

    Yoğun muskuler egzersizde L-karnitinin sıçan karaciğeri, iskelet kası ve testis dokularına etkileri

    The Effects of L-carnitine on liver, skeletal muscle and testis tissues during intestive muscular exercise

    ÖMER COŞKUN

    Tıpta Uzmanlık

    Türkçe

    Türkçe

    1998

    MorfolojiErciyes Üniversitesi

    Histoloji ve Embriyoloji Ana Bilim Dalı

    YRD. DOÇ. DR. RECEP KUTLUAY

  4. Tez No

    833334

    Pregestasyonel ve gestasyonel diyabet mellitus tanısı konulan gebelerin doğum sonrası alınan plasenta örneklerinde CD15 ekspresyonunun araştırılması

    Investigation of CD15 expression in placenta samples taken after birth of pregnant pregnants diagnosed with pregestational diabetes mellitus and gestational diabetes mellitus

    KÜBRA KARAKAŞ SOYLU

    Tıpta Uzmanlık

    Türkçe

    Türkçe

    2023

    Kadın Hastalıkları ve DoğumSağlık Bilimleri Üniversitesi

    Kadın Hastalıkları ve Doğum Ana Bilim Dalı

    DOÇ. DR. HAKAN ERENEL

  5. Tez No

    885146

    Sumak, kimyon ve kekik ekstrelerinin hepatoselüler karsinoma hücre hattında apoptoz ve paraptoza etkisi

    Effect of sumac, cumin and thyme extracts on apoptosis and paraptosis on hepatocelular carcinoma cell line

    YAĞMUR YAŞAR FIRAT

    Doktora

    Türkçe

    Türkçe

    2023

    Beslenme ve DiyetetikErciyes Üniversitesi

    Beslenme ve Diyetetik Ana Bilim Dalı

    PROF. DR. BETÜL ÇİÇEK

    DR. AYÇA LEKESİZCAN

Geri Dön