Characterization of neighborhood behaviours in a multi-neighborhood
  local search algorithm
  We consider a multi-neighborhood local search algorithm with a large number
of possible neighborhoods. Each neighborhood is accompanied by a weight value
which represents the probability of being chosen at each iteration. These
weights are fixed before the algorithm runs, and are considered as parameters
of the algorithm. Given a set of instances, off-line tuning of the algorithm's
parameters can be done by automated algorithm configuration tools (e.g., SMAC).
However, the large number of neighborhoods can make the tuning expensive and
difficult even when the number of parameters has been reduced by some
intuition. In this work, we propose a systematic method to characterize each
neighborhood's behaviours, representing them as a feature vector, and using
cluster analysis to form similar groups of neighborhoods. The novelty of our
characterization method is the ability of reflecting changes of behaviours
according to hardness of different solution quality regions. We show that using
neighborhood clusters instead of individual neighborhoods helps to reduce the
parameter configuration space without misleading the search of the tuning
procedure. Moreover, this method is problem-independent and potentially can be
applied in similar contexts.
