Fractal geometry inspired solution generation to enhance effectiveness of metaheuristic algorithms

Abstract

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.

Real-life optimization problems are too complex to solve optimally. Therefore, numerous researchers work on more efficient solution methods which led metaheuristic algorithms to gain world-wide popularity since mid-90s. To improve the efficiency and effectiveness of a heuristic algorithm, the searching capability of the algorithm needs to be improved. Hence, the usual approach in improving the science of metaheuristics is to design a novel algorithm or improve an existing algorithm. However, a relatively less explored approach is to design a new neighbor generation mechanism. In this study, a novel neighbor generation mechanism for single solution-based heuristics which use permutation solution representation is presented. The proposed mechanism is called cantor-set based (CB) method. The inspiration for the mechanism is the recursive algorithm that constructs a cantor set which is a fractal shape. Simply, a solution representation is divided based on the recursive algorithm and the resulting pieces are permutated and then combined again to generate neighbors. CB method is embedded into the classical local search (LS) and simulated annealing (SA) algorithms to test its advantages and to compare it with classical swap and insertion neighbor generation mechanisms. Different types of applications are considered to design CB method to find the most effective and efficient design of the method. A set of benchmark problems of the traveling salesman problem (TSP) and quadratic assignment problem (QAP) are used in the experiments to test these applications. TSP and QAP have very different solution spaces considering their objective functions which is why they are chosen as test problems. More specifically TSP has a steep landscape and benefits from drastic changes in neighbor generation while QAP has a flat landscape and requires delicate changes in neighbor generation. Therefore, the aim in using TSP and QAP as test problems is to analyze sensitivity of CB method. In addition to analyzing CB applications, CB method is compared to swap and insertion mechanisms. Swap and insertion are chosen because they are the most used and basic mechanisms that are encountered in the literature. The computational tests show that different applications of CB solve TSP and QAP very efficiently. In the end, it is concluded that it is possible to design a general mechanism that gives consistently good results for both TSP and QAP.