Etkileşimli Genetik Algoritma Knapsack Çözücü
Evrimsel hesaplamanın klasik Sırt Çantası optimizasyon problemini nasıl çözdüğünü görselleştirmek için Python ve Dash kullanan web tabanlı bir eğitim aracı.
Genel Bakış
Bu proje, klasik Sırt Çantası Problemini (Knapsack Problem) bir Genetik Algoritma (GA) kullanarak çözmek için tasarlanmış etkileşimli bir web uygulamasıdır. Python ve Dash çatısı ile geliştirilen bu araç, biyo-ilhamlı sezgisel yöntemlerin (heuristics) karmaşık optimizasyon zorluklarını nasıl ele aldığını anlamak için dinamik ve görsel bir yol sunar.
Problem
Sırt Çantası Problemi, ünlü bir kombinatoryal optimizasyon problemidir: Belirli bir ağırlığa ve değere sahip bir ürün kümesi verildiğinde, toplam ağırlığın belirli bir sınırı aşmadığı ve toplam değerin mümkün olduğunca büyük olduğu bir koleksiyonu belirlemeyi amaçlar.
Nasıl Çalışır: Genetik Algoritma
Çözüm, doğal seçilimden esinlenen evrimsel bir yaklaşım uygular:
- Başlatma (Initialization): Rastgele "genomlardan" (öğe seçimini temsil eden ikili diziler) oluşan bir popülasyon oluşturulur.
- Uygunluk Değerlendirmesi (Fitness Evaluation): Seçilen öğelerin toplam değerini hesaplar (kapasite aşımı olan çözümleri cezalandırır).
- Seçim (Selection): En iyi "ebeveynleri" seçmek için turnuva seçimi yöntemini kullanır.
- Çaprazlama ve Mutasyon: Ebeveynleri birleştirerek yavru (offspring) oluşturur ve çeşitliliği korumak için rastgele mutasyonlar ekler.
Temel Özellikler
- Etkileşimli Arayüz: Kullanıcılar, web arayüzü üzerinden özel ürün değerleri, ağırlıkları ve kapasite sınırlarını girebilirler.
- Dinamik Görselleştirme: "Uygunluk" (çözüm kalitesi) değerinin nesiller boyunca nasıl geliştiğini gösteren gerçek zamanlı grafikler oluşturmak için Plotly kullanır.
- Detaylı Analitik: Bulunan en iyi çözümü, toplam değeri, toplam ağırlığı ve seçilen belirli öğeleri görüntüler.
Teknoloji Yığını
- Çekirdek Mantık: Python (NumPy, Pandas)
- Web Çatısı: Dash (Plotly tarafından)
- Görselleştirme: Plotly
- Test: Unittest