Metasezgisel algoritmaların etkinliğini arttırmak için esin kaynağı fraktal geometri olan çözüm oluşturma

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. Keywords: Neighbor generation, local search, simulated annealing, cantor set, traveling salesman problem, quadratic assignment problem.