Late Acceptance Hill-Climbing algorithm (LAHC)

---

News
In December 2011 the LAHC has won the 1st place prize in the International Optimisation Competition
The description of the winning method (together with the descriptions of other participaiting methods) are available at the unofficial competition website . This site is devoted to those people, who intend to participate and win the future optimization competitions.

A research team from the University of Patras, Greece has employed the LAHC in their entry algorithm in ROADEF/EURO Challenge 2012 . Good luck to guys.

---

What is LAHC?
The Late Acceptance Hill-Climbing is a new optimisation metaheuristic.
Invented: February 2008.
First publicly presented: August 2008 (PATAT 2008 conference).

The basic idea of the LAHC is very simple:

Greedy Hill-Climbing (HC)	Late Acceptance Hill-Climbing (LAHC)
Accepts a candidate solution if it is not worse than the current one.	Accepts a candidate solution if it is not worse than that solution, which was "current" several steps before.

The advantages of the LAHC:
It has just one parameter;
It is not sensitive to initialisation;
It has a strong performance and wide application area;
It is more reliable than some known methods;
It supposes a large number of variants and modifications.

---

Presentations:

A Late Acceptance Strategy - the new general-purpose optimisation metaheuristic
The Wonders of the Late Acceptance Hill-Climbing algorithm

---

Publications:

E. K. Burke and Y. Bykov, "A Late Acceptance Strategy in Hill-Climbing for Exam Timetabling Problems", (extended abstract), in proccedings of PATAT 2008 conference. Montreal, Canada, August 2008. pdf

E. Ozcan, Y. Bykov, M. Birben, E. K. Burke, "Examination timetabling using late acceptance hyper-heuristics", in proccedings of the 11th conference on Congress of Evolutionary Computation. Trondheim, Norway, May 2009. pdf

J. Verstichel and G. Vanden Berghe. “A late acceptance algorithm for the lock scheduling problem” Logistic Management 2009 (5) 457-478. pdf

A. Abuhamdah. “Experimental result of late acceptance randomized descent algorithm for solving course timetabling problems” IJCSNS International Journal of Computer Science and Network Security pdf

---

Here is a sample C++ source code of LAHC for exam timetabling problem (Carter's datasets). A complete starting set (including datafiles) can be downloaded here

---

6 reasons to move from the Simulated Annealing to the LAHC:

If you are working with Simulated Annealing (SA), while not to try LAHC?

1. It is very easy. If you already have the SA code, you just need to change few lines to get the LAHC.

2. The performance of SA and LAHC depends on particular problem instance. Generally, with classical combinatorial optimization problems LAHC performs slightly better.

3. The principal difference between SA and LAHC is that the LAHC is free from a "cooling schedule". The SA is based on the comparison of values of different cost functions, while the LAHC employs just their ranking. This makes LAHC less sensitive do scales, unlinearities, etc. Thus, the LAHC is definetely more reliable with different tricky problems: unlinear, highly constrained ones, etc.

4. The initial temperature in SA is just a "power-eating" parameter. I.e. if it is set up incorrectly, SA just loses its performance without shortening the search time. As this parameter is problem dependent, then SA always requires preliminary experiments to get the highest performance.
In contrast, the LAHC if free from such "power-eaters". Its single parameter defines the search time only, while the performance is always the highest. I.e. with the higher length of the fitness array the search converges later, but result is usulally better, and vice versa. It never happen that the prformance is just lost.

5. The basic idea of the LAHC can be expanded into an enormous number of variants and modifications. This, together with its unuque properties (linear behviour, magnification) opens a wide and completely unexplored area of future inventions.

6. Google Scholar shows 466000 publications with keyword "Simulated Annealing" and only 25 publications on the LAHC. Your publication on the award winning LAHC will be pioneering in the field and interesting for everybody. Just a case study of the LAHC in a new application area is already an acceptable conference paper. Furtermore, if we look into the publications on SA - we find different adaptations, hybridisations, etc. Just take one of that and try to do the same with LAHC - this could be quite interesting study.

---

I am working on this project very intensively.
Currently I am preparing a major journal paper about the LAHC for the second review round.
This page will be updated frequently. Please keep visiting.

---

My E-mail: yxb@cs.nott.ac.uk Worktime Phone:     0115 846 8376 Address:          Yuri Bykov School of Computer Science and IT the University of Nottingham Jubilee Campus, Wollaton Road Nottingham NG8 1BB United Kingdom Number of visitors: Last modified: 7 February 2012