Geri Dön

Küme örtüsü probleminin genetik algoritma ile çözümü

Solution of the set covering problem with genetic algorithm

  1. Tez No: 842319
  2. Yazar: MÜGE OLUÇOĞLU
  3. Danışmanlar: PROF. 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: 2023
  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ı: Bilgisayar Bilimleri Bilim Dalı
  13. Sayfa Sayısı: 69

Özet

Küme Örtüsü Problemi (KÖP), çeşitli alanlarda uygulamaları olan bir kombinatoryal optimizasyon problemidir. Seçilen kümelerin toplam sayısını en aza indirirken tüm öğeleri kapsayacak şekilde belirli bir uzaydan alt küme seçmeyi amaçlar. Doğal evrim süreçlerinden esinlenen Genetik Algoritmalar (GA), karmaşık optimizasyon problemlerinin çözümünde umut vaat eden sonuçlar vermektedir. Bu çalışmada, KÖP'ün üstesinden gelmek için başlangıç popülasyonunda kümelerin frekanslarına göre sıralama yapan bir sezgisel algoritma kullanılarak genetik algoritma ile çözüm sunulmaktadır. Ayrıca çözüm kümesine iyi katkı yapacak alt kümelerin seçimlerine öncelik verilmesi için bir seçim formülü geliştirilmiştir. Önerilen algoritma, seçim, çaprazlama ve mutasyon gibi genetik operatörleri kullanarak bir çözüm popülasyonunu geliştirmeyi amaçlamaktadır. Bireylerin uygunluğu, minimum sayıda küme ile tüm elemanların örtülme yeteneklerine göre belirlenmektedir. Genetik algoritma, nesiller boyunca çözümleri yinelemeli olarak iyileştirir ve kademeli olarak optimum veya optimuma yakın çözümlere yaklaşmaktadır. KÖP'ün çeşitli örnek problemleri üzerinde deneyler yaparak önerilen algoritmanın sonuçları gösterilmiştir.

Özet (Çeviri)

The Set Covering Problem (SCP) is a combinatorial optimization problem with applications in various fields. It aims to select subsets from a given space to cover all elements while minimizing the total number of selected sets. Genetic Algorithms (GA), inspired by natural evolutionary processes, show promising results in solving complex optimization problems. In this study, a genetic algorithm to overcome SCP using a heuristic that sorts sets by their frequency in the initial population is proposed. Additionally, a formula for selecting subsets that will make a positive contribution to the solution set has been established. The proposed algorithm aims to evolve a population of solutions using genetic operators such as selection, crossover and mutation. The fitness of individuals is determined by their ability to cover all elements with a minimum number of sets. The genetic algorithm iteratively improves solutions over generations and gradually approaches optimum or near-optimal solutions. The results of the proposed algorithm are demonstrated by conducting experiments on various example problems of the SCP.

Benzer Tezler

  1. Diskrit programlama problemlerinde tümleme prensipleri üzerine

    On complement princibals of discrete programming problems

    DUYGU VARGÖR

    Yüksek Lisans

    Türkçe

    Türkçe

    2005

    MatematikEge Üniversitesi

    Matematik Ana Bilim Dalı

    DOÇ.DR. URFAT NURİYEV

  2. Minimal ağırlıklı dominant alt küme problemi(MADAK) üzerine

    On dominating subset with the minimal weight problem (DSMW)

    BURAK ORDİN

    Doktora

    Türkçe

    Türkçe

    2004

    MatematikEge Üniversitesi

    Matematik Ana Bilim Dalı

    DOÇ.DR. URFAT NURİYEV

  3. Statistical learning with proximity catch digraphs

    Yakınlık yakalama yönlü çizgeleri ile istatistiksel öğrenme

    ARTÜR MANUKYAN

    Doktora

    İngilizce

    İngilizce

    2017

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MİNE ÇAĞLAR

  4. Telsiz duyarga ağları için çizge teorik topoloji kontrol algoritmaları

    Graph-theoretic topology control algorithms for wireless sensor networks

    YASİN YİĞİT

    Yüksek Lisans

    Türkçe

    Türkçe

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge Üniversitesi

    Uluslararası Bilgisayar Ana Bilim Dalı

    DOÇ. DR. ORHAN DAĞDEVİREN

  5. Traffic and mobility aware delay modeling for software-defined networks (SDN)

    Yazılım tanımlı ağlar için trafik ve hareket duyarlı gecikme modeli

    MÜGE ÖZÇEVİK

    Doktora

    İngilizce

    İngilizce

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. BERK CANBERK