Cantor set based neighbor generation method for permutation solution representation

Abstract

Metaheuristics gained world-wide popularity and researchers have been studying them vigorously in the last two decades. A relatively less explored approach in the improvement of metaheuristics is to design new neighbor generation mechanisms. Neighbor generation mechanisms are very important in the success of any single solution-based heuristic since they directly guide the search. In this study, a neighbor generation mechanism called cantor-set based (CB) method for single solution-based heuristics which use permutation solution representation is described. The inspiration for CB method stems from the recursive algorithm that constructs a cantor set which is a fractal set. Three variations of CB method are discussed (CB-1, CB-2, CB-3) considering the presented design possibilities. The computational experiments are conducted by embedding the mechanisms into the classical local search and simulated annealing algorithms, separately, to test their efficiency and effectiveness by comparing them to classical swap and insertion mechanisms. The traveling salesman problem (TSP) and quadratic assignment problem (QAP) which are very different problems that have incompatible characteristics have been chosen to test the mechanisms and sets of benchmark instances with varying sizes are chosen for the comparisons. The computational tests show that CB-2 gives very favorable results for TSP and CB-1 gives favorable results for QAP which means that CB-2 is suitable for problems that have steep landscapes and CB-1 is suitable for the problems that have flat landscapes. It is observed that CB-3 is a more generalized mechanism because it gives consistently good results for both TSP and QAP instances. The best mechanism for a given instance of the both problem types outperforms the classical neighbor generation of swap and insertion in terms of effectiveness.