Küme örtüsü probleminin genetik algoritma ile çözümü
Solution of the set covering problem with genetic algorithm
- Tez No: 842319
- Danışmanlar: PROF. DR. MURAT ERŞEN BERBERLER
- 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: 2023
- Dil: Türkçe
- Üniversite: Dokuz Eylül Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Bilimleri Bilim Dalı
- 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
- Diskrit programlama problemlerinde tümleme prensipleri üzerine
On complement princibals of discrete programming problems
DUYGU VARGÖR
- Minimal ağırlıklı dominant alt küme problemi(MADAK) üzerine
On dominating subset with the minimal weight problem (DSMW)
BURAK ORDİN
- Statistical learning with proximity catch digraphs
Yakınlık yakalama yönlü çizgeleri ile istatistiksel öğrenme
ARTÜR MANUKYAN
Doktora
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DOÇ. DR. MİNE ÇAĞLAR
- 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
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiUluslararası Bilgisayar Ana Bilim Dalı
DOÇ. DR. ORHAN DAĞDEVİREN
- 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
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. BERK CANBERK