Geri Dön

Genetik algoritma ile maksimum bağımsız küme probleminin çözümü

Solution to the maximum independent set problem with genetic algorithm

  1. Tez No: 491149
  2. Yazar: MEHMET GENCER
  3. Danışmanlar: DOÇ. DR. MURAT ERŞEN BERBERLER
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2017
  8. Dil: Türkçe
  9. Üniversite: Dokuz Eylül Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Bilimleri Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 93

Özet

NP-Zor karmaşıklık sınıfına ait çizge problemlerinden biri olan Maksimum Bağımsız Küme (MIS) ile günlük hayatta sıklıkla görüntü işleme, harita işaretleme, moleküler biyoloji, zaman çizelgesi planlama(scheduling), vs. gibi alanlarda sıklıkla karşılaşılır. Bu çalışmada MIS problemine birden fazla uygun çözümün aynı anda oluşturulup kontrol edilebildiği meta sezgisel yöntemlerden birisi olan genetik algoritmalar yardımıyla kısa sürelerde optimuma yakın kalitede çözümler aranmıştır. Literatürdeki çalışmaların büyük bölümünden farklı olarak genetik algoritmanın başlangıç popülasyonu, rastgele belirlenmeyip çeşitli sezgisel yaklaşımlarla oluşturulmuştur. Farklı sezgisel yaklaşımlar ve bu yaklaşımların optimum değer bulamadığı ters örnekler incelenmiş, sezgisel yaklaşımların çözüme ulaşma olasılığı kaydırma operatörü yardımıyla farklı çözümler üretilerek arttırılmıştır. Burada kaydırma operatörü ile kastedilen yapı tepe derecelerine göre sıralı vektör üzerinde farklı çözümleri elde edebilmek için permütasyon uzayının küçük bir alt kümesinin seçilmesidir. Ayrıca çözüm uzayını etkin bir şekilde tarayabilmek amacıyla problemin boyutuna bağlı olarak büyüklüğü değişen başlangıç popülasyonu kullanılmıştır. Algoritma C dilinde kodlanmış olup farklı ayrıt yoğunluklarına sahip rastgele oluşturulmuş problemler üzerinde hesaplama denemeleri yapılmıştır. Çalışma zamanı ve amaç fonksiyonunun değerleri açısından algoritmanın verimli olduğu gözlenmiştir. Oluşturulan problemler klasik genetik algoritma ile de çözülerek, başarım oranları ve çözüm zamanları incelenmiş, sezgisel yaklaşımın etkisini gözlemlemek amacıyla bir biri ile karşılaştırılmıştır.

Özet (Çeviri)

NP-hard graph problems that belong to complexity class which is one of Maximum independent set (MIS) in daily life, often with image processing, map marking, Molecular Biology, planning timeline(scheduling), etc in areas such as often is encountered. In this study, with the help of genetic algorithms which is a meta-heuristic solution approach in which more than one suitable solution of artificial intelligence techniques can be created and controlled at the same time, the solutions to the Maximum Independent Set were searched in a short period of time. Unlike most of the studies in the literature, the initial population of the genetic algorithm has not been determined at random and has been created with various heuristic approaches. Different heuristic approaches and their inverse examples in which these approaches are unable to find the optimum value have been examined, a heuristic approach designed in this process to increase the possibility of reaching to the best solution by the shifting operator, creating different solutions is ensured. Here on the scroll meant by sequential vector building operator in order to obtain different solutions according to the degree peak, is to select a small subset of the permutation space. In order to scan the solution space effectively depending on size of the problem varying size of the initial population was used. The algorithm is coded in the C language and the computational experiments on randomly produced problems in terms of runtime and objective function values have been performed and it was observed that the algorithm is efficient. Problems were solved with classical genetic algorithm, performance ratios and solution times were examined and compared with heuristic one to observe the effect of the heuristic approach.

Benzer Tezler

  1. Binary mean-variance mapping optimization algorithm

    İkili ortalama-varyans eşleme optimizasyonu algoritması

    ALI HAKEM JABOR ALSAEEDI

    Yüksek Lisans

    İngilizce

    İngilizce

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYıldız Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    Assist. Prof. Dr. OĞUZ ALTUN

  2. Multi-objective subcontractor selection model based on performance measurement framework in international construction projects

    Uluslararası inşaat projelerinde performans ölçüm çerçevesine dayalı çok amaçlı alt yüklenici seçim modeli

    BEFRİN NEVAL BİNGÖL

    Doktora

    İngilizce

    İngilizce

    2017

    İnşaat Mühendisliğiİstanbul Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    DOÇ. DR. GÜL POLAT TATAR

  3. Kapasitör uyarmalı asenkron generatörün optimal kapasitesinin hibrit genetik algoritma ile belirlenmesi

    Determination of the optimal capacitance for the capacitor excited induction generator using the hybrid genetic algorithm

    FEVZİ ARSLAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2010

    Elektrik ve Elektronik MühendisliğiDüzce Üniversitesi

    Elektrik Eğitimi Ana Bilim Dalı

    DOÇ. DR. NEDİM TUTKUN

  4. Uçak itkisinin fadec sistemi için performans modellerinin oluşturulması ve optimizasyonu

    Thrust performance modelling and optimization for aircraft fadec system

    ECE YURDUSEVİMLİ METİN

    Doktora

    Türkçe

    Türkçe

    2021

    Havacılık MühendisliğiEskişehir Teknik Üniversitesi

    Havacılık Elektrik ve Elektroniği Ana Bilim Dalı

    PROF. DR. ÖNDER TURAN

  5. Kriging interpolasyonu kullanan vekil modeller ile gemi kıç formunun viskoz direnç yönünden optimizasyonu

    Aft form optimization of ships for minimum viscous resistance by using kriging metamodeling technique

    HAYRİYE PEHLİVAN SOLAK

    Doktora

    Türkçe

    Türkçe

    2020

    Gemi Mühendisliğiİstanbul Teknik Üniversitesi

    Gemi İnşaatı ve Gemi Makineleri Mühendisliği Ana Bilim Dalı

    PROF. DR. ÖMER GÖREN