genetik algoritma
💻 Bilgisayar, 💾 Programlama

Genetik Algoritmalar ile Knapsack Probleminin Çözümü

Geçen sene Yapay Zeka dersinde genetik algoritmalar ile uğraşırken bizden genetik algoritmalar ile Knapsack problemini çözmemiz ve üç farklı çaprazlama (crossover) türü için genetik algoritmanın nasıl sonuçlar ürettiğinin analizinin yapılması istenmişti.

genetik algoritmaGeçen sene Yapay Zeka dersinde genetik algoritmalar ile uğraşırken bizden genetik algoritmalar ile Knapsack problemini çözmemiz ve üç farklı çaprazlama (crossover) türü için genetik algoritmanın nasıl sonuçlar ürettiğinin analizinin yapılması istenmişti.

Knapsack Problemi

Öncelikle bilmeyenler için Knapsack problemini hızlıca açıklayayım:

Belirli bir limiti olan bir çantanız var. (Örneğin 15) Elinizde çeşitli büyüklük ve değerlerde maddeler bulunuyor. (Örneğin altın, genişlik 5, değer 10; tahta, genişlik 6, değer 1…) Çantanın kapasitesini aşmamak koşuluyla çantaya koyabileceğiniz maddelerin toplam değeri en fazla ne kadar olabilir?

Genetik Algoritma ile çözüm

Problemin genetik algoritmalar ile çözümü yazılırken JAVA kullanılmıştır. Problemin çözümü dört farklı crossover algoritması ile gerçekleştirilmiştir. Tüm algoritmalarda crossover edilecek genler rastgele olarak rank selection ile belirlenmiştir. Tüm deneyler her nesil için 32 kromozom üzerinden yapılmıştır.

Uygulama her algoritma ile 1000 defa çalıştırılarak hangi crossover algoritması ile ne derece hızlı ettiğine dair istatistiksel bir hesaplama yapılmıştır. Çalışma süreleri 100 nesil için milisaniye cinsindendir.

Detaylar

Kaynak kodun detayları, kullanımı, girdiler, çıktılar, yeni algoritma eklemek, bulgular konusundaki yorumlar ve daha fazlası çok detaylı bir şekilde hazırlamış sekiz sayfalık proje raporunda bulunabilir.

İndir

İlgili Konular

Daha önceden exhaustive search ve dynamic programming yöntemleri ile de Knapsack probleminin çözümünü gerçekleştirmiştim ve bunlarla ilgili de detaylı zaman ölçümü yapmıştım. İlgilenenler buraya tıklayarak yazıya ulaşabilirler.

👋 🚨 Yeni yazılardan haberdar olmak ister misiniz? 👇

Genetik Algoritmalar ile Knapsack Probleminin Çözümü 3 yorum aldı.

  1. şuralara bir fb comment koysan da böle her seferinde bir şey girmesek.

    yazı için teşekkürler.

    -buraya linki kırık. en sonda-

    1. Ya o FB Comment olayını düşünüm de, yorumlar bende kalsın, Facebook'ta durmasın. 🙂 Bir de eski yorumları birleştirmekle uğraşamayacağım o var. Linki düzeltiyorum, teşekkür ettim.

Bir yanıt yazın

E-posta adresiniz yayınlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir