Diversified Late Acceptance Search
  The well-known Late Acceptance Hill Climbing (LAHC) search aims to overcome
the main downside of traditional Hill Climbing (HC) search, which is often
quickly trapped in a local optimum due to strictly accepting only non-worsening
moves within each iteration. In contrast, LAHC also accepts worsening moves, by
keeping a circular array of fitness values of previously visited solutions and
comparing the fitness values of candidate solutions against the least recent
element in the array. While this straightforward strategy has proven effective,
there are nevertheless situations where LAHC can unfortunately behave in a
similar manner to HC. For example, when a new local optimum is found, often the
same fitness value is stored many times in the array. To address this
shortcoming, we propose new acceptance and replacement strategies to take into
account worsening, improving, and sideways movement scenarios with the aim to
improve the diversity of values in the array. Compared to LAHC, the proposed
Diversified Late Acceptance Search approach is shown to lead to better quality
solutions that are obtained with a lower number of iterations on benchmark
Travelling Salesman Problems and Quadratic Assignment Problems.
