4.7 Article

The late acceptance Hill-Climbing heuristic

Journal

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 258, Issue 1, Pages 70-78

Publisher

ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2016.07.012

Keywords

Combinatorial optimization; Metaheuristics; Late acceptance hill climbing; Timetabling; Travelling salesman problem

Funding

  1. UK Engineering and Physical Sciences Research Council (EPSRC) [GR/S70197/01]
  2. EPSRC [EP/D061571/1, EP/J017515/1] Funding Source: UKRI
  3. Engineering and Physical Sciences Research Council [EP/D061571/1, EP/J017515/1] Funding Source: researchfish

Ask authors/readers for more resources

This paper introduces a new and very simple search methodology called Late Acceptance Hill-Climbing (LAHC). It is a local search algorithm, which accepts non-improving moves when a candidate cost function is better than it was a number of iterations before. This number appears as a single algorithmic input parameter which determines the total processing time of the search procedure. The properties of this method are experimentally studied in this paper with a range of Travelling Salesman and Exam Timetabling benchmark problems. Also, we present a fair comparison of LAHC with well-known search techniques, which employ a cooling schedule: Simulated Annealing (SA), Threshold Accepting (TA) and the Great Deluge Algorithm (GDA). In addition, we discuss the success of the method in winning an international competition to automatically solve the Magic Square problem. Our experiments have shown that the LAHC approach is simple, easy to implement and yet is an effective search procedure. For most of the studied instances (especially for the large sized ones), its average performance is better than competitor methods. Moreover, the LAHC approach has an additional advantage (in contrast to the above cooling schedule based methods) in its scale independence. We present an example where the rescaling of a cost function in the Travelling Salesman Problem dramatically deteriorates the performance of three cooling schedule based techniques, but has absolutely no influence upon the performance of LAHC. (C) 2016 Published by Elsevier B.V.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available