Implementation of Late Acceptance Hill Climbing (LAHC) algorithm by Burke and Bykov [Burke2017] in python.
Either download the repository to your computer and install, e.g. by pip
pip install .
or install directly from the python package index.
pip install lahc
The package provides a base class for subclassing to a specific
problem. The move and energy methods must be implemented by the
user before the algorithm is applied.
The user controls the algorithm by adjusting a single algorithmic
parameter, the history length, and the termination criteria for
the algorithm. See subsection on each of the topics below.
The search is started by calling the run method.
The example is a good place to start using of the package.
- Note
- The implementation relies heavily on copying the state. The
default copy strategy (
copy_strategy='deepcopy') relies on the STLcopy.deepcopymethod which works for most data structures, but is typically quite slow. Large performance gains can be easily obtained by adapting a different copying strategy, see the documentation of thecopy_statemethod.
The behaviour of the LAHC algorithm is governed by a single parameter,
the history length. To alter the history length of the algorithm,
adjust the history_length parameter of the class.
If the history length is set to one, the LAHC algorithm is equivalent to a greedy Hill Climbing algorithm. Increasing the history length generally improves the solution quality, but also increases the time to convergence.
Selection of the history length should therefore be based on requirements for the quality of the solution and time available for the analysis.
A useful characteristic of the LAHC heuristic is that the runtime to convergence is roughly proportional to the history length. The runtime at any history length can therefore be estimated after applying the algorithm at a few different history lengths.
As a general recommendation, start at a low history length and gradually increase it to determine the runtime and variation in the estimated results. Select a shorter history length that allows multiple runs in the time allocated for simulations rather than a longer history length with a single run.
The algorithm terminates when the terminate_search method evaluates
to True or when a interupt signal (Ctrl-C) is sent to the process.
The default behaviour of the terminate_search method is to
terminate the algorithm when a minimum number of attempts has been
made and the algorithm has not been able to improve the solution for a
certain number of steps. The minimum number of steps and necessary
number of idle iterations can be adjusted with the steps_minimum
and steps_idle_fraction parameters, respectively.
The default value of the steps_idle_fraction (0.02) is generally a
good choice for a variety of problems, but the default
steps_minimum value (100000) may have to be adjusted depending on
the problem. As a general recommendation, the user should reduce the
steps_minimum parameter if the algorithm consistently terminates at
steps_minimum after running for a long period without improving
the solution.
Both the structure and parts of the source code for the
LateAcceptanceHillClimber class is copied from the Annealer
class in the simanneal python project. All contributions from the
simanneal project is hereby gratefully acknowledged. Check out the
simanneal project at
https://github.com/perrygeo/simanneal
which implements the widely used and sucessful Simulated Annealing metaheuristic.
Please open an issue for support.
Please contribute using Github Flow. Create a branch, add commits, and open a pull request.
| [BURKE2017] | E. K. Burke, Y. Bykov, The late acceptance Hill-Climbing heuristic. European Journal of Operational Research. 258, 70–78 (2017). |