Program "pure" genetik algoritma üzerinde çalıştığından, 2-opt, greedy vs. bir heuristic kullanan genetik algoritmaya göre daha yavaş sonuca ulaşır. Bu algoritmanın genel adımları şöyle:

1. Tüm şehirlerden bir kez geçilen bir "rota" oluştur. Bu işlemi genetik algoritma X nüfus üzerinde çalışacaksa X kez tekrarla. Tabii aynı rotanın 2 kez olmaması için gerekli önlemleri de almak gerek. Bu rota bizim kromozomumuz olacak.
2. Rulet tekeri yöntemi veya sıralama seçimi kullanarak 2 rotayı ebeveyn olarak seç. Kısaca daha iyi durumdaki yollara daha yüksek olasılık vererek 2 adet rota seçilecek.
3. Seçilen ebeveyn kromozomlar özel bir yöntemle çaprazlanacak. Normal çaprazlama TSP'de işe yaramıyor çünkü bir kromozomda aynı şehir iki kez bulunmamalı. Keyword: Order-based crossover
4. Oluşan çocukların küçük bir ihtimal mutasyona uğrama şansı var. Mutasyon işlemi random iki şehrin yerinin değiştirilmesi şeklinde olabilir.
5. Çocuklar en kötü iki rota yerine geçiyor. Böylece her jenerasyonda nüfusun iyiye gitmesi sağlanmaya çalışılıyor.

Burada bir rotanın iyi mi kötü mü olduğu değerlendirilirken (fitness function) o rotanın toplam uzunluğu dikkate alınıyor. Uzunsa kötü, kısaysa iyi. 20 şehir içeren bir haritada bu algoritma çalıştırılırken iyi bir sonuç alabilmek için 100000 nüfusun 1000 jenerasyon boyunca yaşaması gerekiyor. 28 saniye sürüyor çalışması. Multi-threaded kodlanırsa düşer tabii bu süre. Bir de benim dandik kodlamış olma ihtimalim var :)

Mutasyonu yüzde 10 yapınca, yüzde 5'e göre sonuç kötüleşiyor. Yani mutasyon olayını abartmamak gerekiyor.

Burada önemli bir faktör, heuristic kullanılsaydı daha az nüfus ve daha kısa bir jenerasyon süresi sonunda aynı veya daha iyi bir sonuca ulaşmak mümkündür.

Sonraki yazı Paralel Tepe Tırmanma (Local Beam Search) ile çözümü anlatacak.