Fractal geometry inspired solution generation to enhance effectiveness of metaheuristic algorithms

Gerçek hayatta karşılaşılan eniyileme problemleri, en iyi çözümün bulunabilmesi için fazla karmaşıktır. Bu yüzden, birçok araştırmacı daha etkin çözüm yöntemleri üzerinde çalışır. Bunun sonucunda metasezgisel algoritmalar 90'lı yılların ortalarından beri dünya çapında popülerlik kazanmıştır. Bir sezgisel algoritmanın etkinliğini ve etkililiğini artırmak için algoritmanın arama kabiliyeti geliştirilmelidir. Bu yüzden, metasezgisellerin geliştirilmesinde yaygın olarak kullanılan yaklaşım, yeni bir algoritma tasarlamak ya da var olan bir algoritmayı iyileştirmektir. Bu yaklaşıma kıyasla daha az üzerine düşülen başka bir yaklaşım ise, yeni bir komşuluk üretme mekanizması tasarlamaktır. Bu çalışmada, permutasyon çözüm gösterimini kullanan tekli-çözüm tabanlı sezgiseller için kullanılan yeni bir komşuluk üretme mekanizması sunulmuştur. Önerilen mekanizma cantor kümesi tabanlı (CB) yöntem olarak adlandırılmıştır. Bu mekanizmanın esin kaynağı, fraktal bir yapı olan cantor kümesi oluşturmak için kullanılan yineleme algoritmasıdır. Mekanizma basitçe şöyle çalışır: bir çözüm gösterimi, yineleme algoritmasının kurallarına göre parçalara ayrılır, ortaya çıkan parçaların sırası rastgele değiştirilir ve parçalar yeniden birleştirilir. CB yöntemi, klasik değiş tokuş (swap) ve yer değiştirme (insertion) mekanizmalarıyla karşılaştırılmış; bu karşılaştırmanın yapılabilmesi için mekanizmalar yerel arama (local search) ve tavlama benzetimi (simulated annealing) algoritmaları içinde kullanılmıştır. En etkin ve etkili tasarımın bulunabilmesi için farklı uygulama şekilleri dikkate alınarak CB yönteminin türleri oluşturulmuştur. Bu türlerin üzerinde deney yapabilmek için gezgin satıcı problemine (TSP, traveling salesman problem) ve kareli atama problemine (QAP, quadratic assignment problem) ait test problemleri kullanılmıştır. TSP ve QAP problemleri, amaç fonksiyonu değerleri cinsinden birbirlerinden çok farklı çözüm uzayı yapılarına sahip oldukları için seçilmişlerdir. Özel olarak, TSP'nin çözüm uzayı çok girintili-çıkıntılı bir yüzeye sahiptir ve büyük değişikliklerle elde edilebilecek komşu çözümlerden olumlu etkilenir. QAP'nin çözüm uzayı düz bir yüzeye sahiptir ve küçük değişikliklerle yaratılan komşu çözümlerden olumlu etkilenir. TSP ve QAP test problemlerini kullanarak CB yönteminin duyarlılığını analiz etmek amaçlanmıştır. CB türlerini analiz etmeye ek olarak, CB türleri, değiş tokuş ve yer değiştirme mekanizmaları ile karşılaştırılmıştır. Değiş tokuş ve yer değiştirme mekanizmaları, literatürde bulunan en temel mekanizmalar oldukları için seçilmişlerdir. Testler sonucunda CB'nin farklı türlerinin TSP ve QAP'ye etkin bir şekilde çözüm buldukları görülmüştür. Sonuç olarak, TSP ve QAP için tutarlı bir şekilde tatmin edici sonuçlar verebilecek genel bir mekanizmanın tasarlanabileceği kararına varılmıştır. Anahtar kelimeler: Komşuluk oluşturma, yerel arama, tavlama benzetimi, cantor kümesi, gezgin satıcı problem, kareli atama problemi