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

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.