Elena Ikonomovska, Dejan Gjorgjevik, Suzana Loskovska

Abstract: This paper describes the Adaptive Tabu Search algorithm (A-TS), an improved tabu search algorithm for combinatorial optimization. A-TS uses a novel approach for evaluation of the moves, incorporated in a new complex evaluation function. A new decision making mechanism triggers the evaluation function providing means for avoiding possible infinite loops. The new evaluation function implements effective diversification strategy that prevents the search from stagnation. It also incorporates two adaptive coefficients that control the influence of the aspiration criteria and the long-term memory, respectively. The adaptive nature of A-TS is based on these two adaptive coefficients. This article also presents a new data mining approach towards improving the performance of A-TS by tuning these coefficients. A-TS performance is applied to the Quadratic Assignment Problem. Published results from other authors are used for comparison. The experimental results show that A-TS performs favorably against other established techniques.