TY - JOUR

T1 - Improving Tabu Search Performance by Means of Automatic Parameter Tuning

AU - Lagos, Carolina

AU - Crawford, Broderick

AU - Soto, Ricardo

AU - Cabrera, Enrique

AU - Vega, Jorge

AU - Johnson, Franklin

AU - Paredes, Fernando

N1 - Publisher Copyright:
© 2016 IEEE.

PY - 2016/12/1

Y1 - 2016/12/1

N2 - A common problem when performing (meta)heuristic techniques over complex combinatorial optimization problems is parameter tuning. Finding the right parameter values can lead to significant improvements in terms of the best solution objective value found by the heuristic, heuristic reliability, and heuristic convergence, among others. Unfortunately, this is usually a tedious and complicated task if done manually. Furthermore, parameter values usually depend on the problem that is going to be solved. In this paper, we propose a framework that is based on the genetic programming (GP) technique to fine tune a key parameter of the well-known tabu search (TS) algorithm. Several experiments are performed over a set of small instances of the well-known capacitated facility location problem. The results have shown that adjusting the probability of acceptance of the best neighbor ρ in the TS algorithm using GP leads to an average value of the obtained solution that is closer to the optimal solution than the average value obtained by the simple TS algorithm with an a priori selected value for ρ. More importantly, standard deviation of the algorithm is greatly improved by our approach, which makes it much more reliable if time limitations are present. Finally, we confirm that the value of the parameter ρ largely depends on the problem that is attempted to solve.

AB - A common problem when performing (meta)heuristic techniques over complex combinatorial optimization problems is parameter tuning. Finding the right parameter values can lead to significant improvements in terms of the best solution objective value found by the heuristic, heuristic reliability, and heuristic convergence, among others. Unfortunately, this is usually a tedious and complicated task if done manually. Furthermore, parameter values usually depend on the problem that is going to be solved. In this paper, we propose a framework that is based on the genetic programming (GP) technique to fine tune a key parameter of the well-known tabu search (TS) algorithm. Several experiments are performed over a set of small instances of the well-known capacitated facility location problem. The results have shown that adjusting the probability of acceptance of the best neighbor ρ in the TS algorithm using GP leads to an average value of the obtained solution that is closer to the optimal solution than the average value obtained by the simple TS algorithm with an a priori selected value for ρ. More importantly, standard deviation of the algorithm is greatly improved by our approach, which makes it much more reliable if time limitations are present. Finally, we confirm that the value of the parameter ρ largely depends on the problem that is attempted to solve.

KW - Automatic parameter tuning

KW - combinatorial optimization

KW - genetic programming (GP)

KW - tabu search (TS).

UR - http://www.scopus.com/inward/record.url?scp=84964329351&partnerID=8YFLogxK

U2 - 10.1109/CJECE.2015.2496338

DO - 10.1109/CJECE.2015.2496338

M3 - Article

AN - SCOPUS:84964329351

VL - 39

SP - 51

EP - 58

JO - Canadian Journal of Electrical and Computer Engineering

JF - Canadian Journal of Electrical and Computer Engineering

SN - 0840-8688

IS - 1

M1 - 7429013

ER -