Acceptance criteria

The alns.accept module contains the various acceptance criteria the alns package ships with. These criteria are used by the ALNS algorithm to decide whether to accept or reject a candidate solution.

All acceptance criteria implement AcceptanceCriterion.

class alns.accept.AcceptanceCriterion.AcceptanceCriterion(*args, **kwargs)

Protocol describing an acceptance criterion.

Methods

__call__(rng, best, current, candidate)

Determines whether to accept the proposed, candidate solution based on this acceptance criterion and the other solution states.

class alns.accept.AlwaysAccept.AlwaysAccept

This criterion always accepts the candidate solution.

Methods

__call__(rng, best, current, candidate)

Call self as a function.

class alns.accept.GreatDeluge.GreatDeluge(alpha: float, beta: float)

The Great Deluge (GD) criterion accepts solutions if the candidate solution has a value lower than a threshold (originally called the water level [1]). The initial threshold is computed as

threshold = alpha * initial.objective()

where initial is the initial solution passed-in to ALNS.

The threshold is updated in each iteration as

threshold = threshold - beta * (threshold - candidate.objective())

The implementation is based on the description of GD in [2].

Parameters

alpha: Factor used to compute the initial threshold
beta: Factor used to update the threshold

References

1: Dueck, G. New optimization heuristics: The great deluge algorithm and the record-to-record travel. Journal of Computational Physics (1993) 104 (1): 86-92.
2: Santini, A., Ropke, S. & Hvattum, L.M. A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic. Journal of Heuristics (2018) 24 (5): 783-815.

Attributes

alpha
beta

Methods

__call__(rng, best, current, candidate)

Call self as a function.

class alns.accept.HillClimbing.HillClimbing

Hill climbing only accepts progressively better solutions, discarding those that result in a worse objective value.

Methods

__call__(rng, best, current, candidate)

Call self as a function.

class alns.accept.LateAcceptanceHillClimbing.LateAcceptanceHillClimbing(lookback_period: int, greedy: bool = False, better_history: bool = False)

The Late Acceptance Hill Climbing (LAHC) criterion accepts a candidate solution when it is better than the current solution from a number of iterations ago.

This implementation is based on the description of LAHC in [1].

Parameters

lookback_period: int: Non-negative integer specifying which solution to compare against for late acceptance. In particular, LAHC compares against the then-current solution from lookback_period iterations ago. If set to 0, then LAHC reverts to regular hill climbing.
greedy: bool: If set, LAHC always accepts a candidate that is better than the current solution.
better_history: bool: If set, LAHC uses a history management strategy where current solutions are stored only if they improve the then-current solution from lookback_period iterations ago. Otherwise, the then-current solution is stored again.

References

1: Burke, E. K., & Bykov, Y. 2017. “The late acceptance hill-climbing heuristic.” European Journal of Operational Research 258 (1): 70 - 78.

Attributes

better_history
greedy
lookback_period

Methods

__call__(rng, best, current, candidate)

Call self as a function.

class alns.accept.MovingAverageThreshold.MovingAverageThreshold(eta: float, gamma: int)

The Moving Average Threshold (MAT) criterion of [1]. This criterion accepts a candidate solution if it is better than a threshold value that is based on the moving average of the objective values of recently observed candidate solutions. The threshold is computed as:

\[f(s^*) + \eta \left( \sum_{i = 1}^\gamma \frac{f(s^i)}{\gamma} - f(s^*) \right)\]

where \(s^*\) is the best solution observed in the last \(\gamma\) iterations, \(f(\cdot)\) indicates the objective function, \(\eta \in [0, 1]\) and \(\gamma \in \mathbb{N}\) are parameters, and each \(s^i\) is a recently observed solution. The recently observed solutions are stored in a history attributed of size at most \(\gamma\).

Parameters

eta: float: Used to determine the threshold value. Larger values of \(\eta\) result in more accepted candidate solutions. Must be in [0, 1].
gamma: int: History size. Must be positive.

References

1: Máximo, V.R. and M.C.V. Nascimento. 2021. A hybrid adaptive iterated local search with diversification control to the capacitated vehicle routing problem, European Journal of Operational Research 294 (3): 1108 - 1119.

Attributes

eta
gamma
history

Methods

__call__(rng, best, current, candidate)

Call self as a function.

class alns.accept.NonLinearGreatDeluge.NonLinearGreatDeluge(alpha: float, beta: float, gamma: float, delta: float)

The Non-Linear Great Deluge (NLGD) criterion accepts solutions if the candidate solution has a value lower than a threshold (originally called the water level [1]). The initial threshold is computed as

threshold = alpha * initial.objective()

where initial is the initial solution passed-in to ALNS.

The non-linear GD variant was proposed by [2]. It differs from GD by using a non-linear updating scheme; see the _compute_threshold method for details. Moreover, candidate solutions that improve the current solution are always accepted.

The implementation is based on the description in [2].

Parameters

alpha: Factor used to compute the initial threshold. See [2] for details.
beta: Factor used to update the threshold. See [2] for details.
gamma: Factor used to update the threshold. See [2] for details.
delta: Factor used to update the threshold. See [2] for details.

References

1: Dueck, G. New optimization heuristics: The great deluge algorithm and the record-to-record travel. Journal of Computational Physics (1993) 104 (1): 86-92.
2: Landa-Silva, D., & Obit, J. H. Great deluge with non-linear decay rate for solving course timetabling problems. 4th international IEEE conference intelligent systems (2008) Vol. 1: 8-11.
3: Santini, A., Ropke, S. & Hvattum, L.M. A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic. Journal of Heuristics (2018) 24 (5): 783-815.

Attributes

alpha
beta
delta
gamma

Methods

__call__(rng, best, current, candidate)

Call self as a function.

class alns.accept.RandomAccept.RandomAccept(start_prob: float, end_prob: float, step: float, method: str = 'linear')

The Random Accept criterion accepts a candidate solution if it improves over the current one, or with a given probability \(P\) regardless of the cost. \(P\) is updated in each iteration as:

\[P \gets \max \{ P_\text{end},~P - \gamma \}\]

when method = 'linear', or

\[P \gets \max \{ P_\text{end},~\gamma P \}\]

when method = 'exponential'. Initially, \(P\) is set to \(P_\text{start}\).

Parameters

start_prob: The initial probability \(P_\text{start} \in [0, 1]\).
end_prob: The final probability \(P_\text{end} \in [0, 1]\).
step:: The updating step \(\gamma \ge 0\).
method: The updating method, one of {‘linear’, ‘exponential’}. Default ‘linear’.

Attributes

end_prob
method
start_prob
step

Methods

__call__(rng, best, current, candidate)

Call self as a function.

class alns.accept.RecordToRecordTravel.RecordToRecordTravel(start_threshold: float, end_threshold: float, step: float, method: str = 'linear', cmp_best: bool = True)

The Record-to-Record Travel (RRT) criterion accepts a candidate solution if the absolute gap between the candidate and the best or current solution is smaller than a threshold. The threshold \(T\) is updated in each iteration using a step size \(\gamma\), as:

\[T \gets \max \{ T_\text{end},~T - \gamma \}\]

when method = 'linear', or

\[T \gets \max \{ T_\text{end},~\gamma T \}\]

when method = 'exponential'. Initially, \(T\) is set to \(T_\text{start}\).

Parameters

start_threshold: The initial threshold \(T_\text{start} \ge 0\).
end_threshold: The final threshold \(T_\text{end} \ge 0\).
step: The updating step size \(\gamma \ge 0\).
method: The updating method, one of {‘linear’, ‘exponential’}. Default ‘linear’.
cmp_best: This parameter determines whether we use default RRT (True), or threshold accepting (False). By default, cmp_best is True, in which case RRT checks whether the difference between the candidate and best solution is below the threshold [2]. If cmp_best is False, RRT takes the difference between the candidate and current solution instead. This yields the behaviour of threshold accepting (TA), see [3] for details.

References

1: Santini, A., Ropke, S. & Hvattum, L.M. A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic. Journal of Heuristics (2018) 24 (5): 783-815.
2: Dueck, G. New optimization heuristics: The great deluge algorithm and the record-to-record travel. Journal of Computational Physics (1993) 104 (1): 86-92.
3: Dueck, G., Scheuer, T. Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing. Journal of Computational Physics (1990) 90 (1): 161-175.

Attributes

end_threshold
method
start_threshold
step

Methods

`__call__`(rng, best, current, candidate)	Call self as a function.
`autofit`(init_obj, start_gap, end_gap, num_iters)	Returns an RRT object such that the start threshold is set at `start_gap` percent of the initial objective `init_obj` and the end threshold is set at `end_gap` percent of the initial objective.

classmethod autofit(init_obj: float, start_gap: float, end_gap: float, num_iters: int, method: str = 'linear')

Returns an RRT object such that the start threshold is set at start_gap percent of the initial objective init_obj and the end threshold is set at end_gap percent of the initial objective. The step parameter is then chosen such that the end threshold is reached in num_iters iterations using the passed-in update method.

Parameters

init_obj: The initial solution objective
start_gap: Percentage gap of the initial objective used for deriving the start threshold.
end_gap: Percentage gap of the initial objective used for deriving the end threshold.
num_iters: The number of iterations that the ALNS algorithm will run.
method: The updating method, one of {‘linear’, ‘exponential’}. Default ‘linear’.

Returns

RecordToRecordTravel: An autofitted RecordToRecordTravel acceptance criterion.

Raises

ValueError: When the parameters do not meet requirements.

class alns.accept.SimulatedAnnealing.SimulatedAnnealing(start_temperature: float, end_temperature: float, step: float, method: str = 'exponential')

Simulated annealing, using an updating temperature.

A candidate solution \(s^c\) is compared against the current solution \(s\). The probability of accepting \(s^c\) is given by

\[\exp \left\{ \frac{f(s) - f(s^c)}{T} \right\},\]

where \(T\) is the current temperature, and \(f(\cdot)\) gives the objective value of the passed-in solution. The current temperature \(T\) is updated in each iteration using a step size \(\gamma\), as:

\[T \gets \max \{ T_\text{end},~T - \gamma \}\]

when method = 'linear', or

\[T \gets \max \{ T_\text{end},~\gamma T \}\]

when method = 'exponential'. Initially, \(T\) is set to \(T_\text{start}\).

Parameters

start_temperature: The initial temperature \(T_\text{start} > 0\).
end_temperature: The final temperature \(T_\text{end} > 0\).
step: The updating step size \(\gamma \ge 0\).
method: The updating method, one of {‘linear’, ‘exponential’}. Default ‘exponential’.

References

1: Santini, A., Ropke, S. & Hvattum, L.M. A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic. Journal of Heuristics (2018) 24 (5): 783-815.
2: Kirkpatrick, S., Gerlatt, C. D. Jr., and Vecchi, M. P. Optimization by Simulated Annealing. IBM Research Report RC 9355, 1982.

Attributes

end_temperature
method
start_temperature
step

Methods

`__call__`(rng, best, current, candidate)	Call self as a function.
`autofit`(init_obj, worse, accept_prob, num_iters)	Returns an SA object with initial temperature such that there is a `accept_prob` chance of selecting a solution up to `worse` percent worse than the initial solution.

classmethod autofit(init_obj: float, worse: float, accept_prob: float, num_iters: int, method: str = 'exponential') → SimulatedAnnealing

Returns an SA object with initial temperature such that there is a accept_prob chance of selecting a solution up to worse percent worse than the initial solution. The step parameter is then chosen such that the temperature reaches 1 in num_iters iterations.

This procedure was originally proposed by Ropke and Pisinger (2006), and has seen some use since - i.a. Roozbeh et al. (2018).

Parameters

init_obj: The initial solution objective.
worse: Percentage (in (0, 1), exclusive) the candidate solution may be worse than initial solution for it to be accepted with probability accept_prob.
accept_prob: Initial acceptance probability (in [0, 1]) for a solution at most worse worse than the initial solution.
num_iters: Number of iterations the ALNS algorithm will run.
method: The updating method, one of {‘linear’, ‘exponential’}. Default ‘exponential’.

Returns

SimulatedAnnealing: An autofitted SimulatedAnnealing acceptance criterion.

Raises

ValueError: When the parameters do not meet requirements.

References

1: Ropke, Stefan, and David Pisinger. 2006. “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows.” Transportation Science 40 (4): 455 - 472.
2: Roozbeh et al. 2018. “An Adaptive Large Neighbourhood Search for asset protection during escaped wildfires.” Computers & Operations Research 97: 125 - 134.