Ayrık orka yırtıcı algoritmasının geliştirilmesi

Gezgin Satıcı Problemi (Traveling Salesman Problem - TSP), günümüzde en sık çalışılan kombinatoryal optimizasyon problemlerinden birisidir. Çizelgeleme, devre tasarlama, fabrikalarda tesislerin yerleşim tasarımı, rota planlama ve baskı devre tasarlama gibi birçok gerçek dünya problemlerini çözmek için kullanılır. Bu nedenle, ayrık optimizasyon yöntemleri alanında çalışan araştırmacılar, onu gerçekçi bir test ortamı olarak kabul ederler ve geliştirdikleri yeni algoritmaların performansını onun üzerinde değerlendirirler. Bu çalışmada, orka yırtıcı algoritmasının (Orca Predation Algorithm - OPA) ayrık bir versiyonu geliştirilmiş, ayrık orka yırtıcı algoritması (Discrete Orca Predation Algorithm - DOPA) olarak adlandırılmıştır ve TSP'yi çözmek için kullanılmıştır. OPA gibi DOPA da kovalama ve saldırı olmak üzere iki fazdan oluşmaktadır. Kovalama fazında orkalar arasındaki mesafeler Hamming mesafesi ile hesaplanmış, hesaplanan bu değerler kullanılarak hız değerleri elde edilmiştir. Hız değerleri ve 2-opt algoritması kullanılarak orkaların konumları güncellenmiştir. Saldırı fazında orkaların konumları sıralı çaprazlama (Order Crossover - OX1) operatörü ile hesaplanmıştır. Pozisyon ayarlama prosedüründe ise takas (swap) lokal arama operatörü kullanılmıştır. DOPA'nın parametreleri Taguchi istatistiksel yöntemi ile ayarlanmıştır. DOPA 67 iyi bilinen TSP örneği üzerinde test edilmiştir. Ayrıca, DOPA ile diğer güncel dokuz yöntem arasında önemli farklılıklar olup olmadığını kontrol etmek için Friedman ve Wilcoxon işaretli sıra testleri uygulanmıştır. Deneysel sonuçlar DOPA'nın diğer yöntemlere alternatif ve oldukça rekabetçi bir yöntem olduğunu göstermiştir.