Genetik Algoritmalar ile Knapsack Probleminin Çözümü

genetik-algoritma genetik-algoritma   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.

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.