If you are looking for an effective optimization heuristic for your project, while not to try the award-winning Late Acceptance Hill-Climbing algorithm? It is the same simple as the greedy Hill-Climbing, but much more powerful. This web page contains helpful information about LAHC: publications, presentations and downloadable examples.
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:
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.
Primary LAHC paper:
E. K. Burke and Y. Bykov, "The Late Acceptance Hill-Climbing Heuristic", European Journal of Operational Research (published online first) pdf
The Technical Report version (CSM-192, Computing Science and Mathematics, University of Stirling, 2012) is here .
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
And many others. See all publications at:
Google Scholar: "Late acceptance" "Hill climbing"
1. A Late Acceptance Strategy - the new general-purpose optimisation metaheuristic .pdf
2. The Wonders of the Late Acceptance Hill-Climbing algorithm .pdf
3. A Late Acceptance Hill-Climbibg algorithm - the winner of the International Optimisation Competition .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
In the last presentation we can find the results of the recent LAHC studies. The performance of the LAHC was compared with the Simulated Annealing on constrained Magic Square problems of different size. It was revealed that the LAHC performs much better than SA on the large-sized problems. These results can be verified by everybody using the original Java code of the International Optimisation Competition entry algorithm. Its modified variant, where besides the LAHC four other heuristics (HC, SA, TA and GDA) can be launched is available here: MSMain.java
Here is an example of the Late Acceptance Hill Climbing for solving TSPlib Traveling Salesman problems. The same algorithm is written in Delphi and Java. The Delphi code: TSPN005L.DPR. The LAHC Java code for TSP is available for download here: LAHC_TSPlib.java
7 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. My very recent results have revealed that the LAHC performs much better than SA on large-sized problems. However, this observation reguire further verification.
5. 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.
6. 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.
7. Google Scholar shows 466000 publications with keyword "Simulated Annealing" and only 226 publications on 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.
LAHC: News and Facts
In June 2014 the research team n.1 from CODeS group , KU Leuven, Belgium, has won the VeRoLog Solver Challenge 2014 using the Late Acceptance method.
Geoffrey De Smet, The project leader of OptaPlanner Software says: In the past, when someone asked me "What metaheuristic should I start with in OptaPlanner ?", I always said Tabu Search (usually entityTabuSize 7). No longer. Now, the answer is Late Acceptance. See Google+
LAHC was widely discussed at MISTA 2013 Conference. By the keyword density in the conference Proceedings LAHC has got the 5th highest density (over 23 most popular optimization methods). See keyword density table.
On MISTA 2013 Conference I have presented a new algorithm called as Step Counting Hill Climbing (SCHC). Its demonstration software can be downloaded from the algorithm's web page
The LAHC has been employed as a kernel optimization heuristic in Rasta Converter project hosted by GitHub Company.
Two research teams participated in ROADEF/EURO Challenge 2012 have submitted LAHC-based entry algorithms. Over 72 participants both teams have got very good results: J17 ( CODeS research group from KAHO, Belgium - they were the first ranked team in the qualification phase) has got the 4th place in category "J". S5 (research team from the University of Patras, Greece) has got the 7th place in category "S".
Our major paper about LAHC is now available in the form of Technical Report. Please see the publications section.
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.
Number of visitors:
Last modified: 15 September 2014