Adaptive Large Neighbourhood Search

Adaptive Large Neighbourhood Search (ALNS; Ropke & Pisinger, 2006) maintains a single incumbent solution and, each iteration, generates one or more candidate solutions by applying a destroy operator followed by a repair operator. Operators are drawn from user-supplied pools by weighted random sampling, and their weights are updated online so that operators that recently produced good moves are picked more often.

The destroy/repair operator pools and the solution representation are defined inside the user’s external model (see the platform ALNSExternalModel interface); only the algorithm-level controls are configured here.

Iteration cycle

Each iteration:

1. Sample candidates_per_iteration destroy operators and the same number of repair operators by weighted random selection.

2. Apply each destroy/repair pair to a copy of the incumbent to produce k candidate solutions.

3. Evaluate the candidates (in parallel when k > 1).

4. Decide whether the best candidate replaces the incumbent via the configured acceptance_criterion.

5. Reward the operator pairs that produced this iteration’s candidates.

6. Every segment_length iterations, decay all operator weights by decay_factor.

Operator reward schedule

Each iteration’s operator pairs are rewarded by tier:

• new_best_reward (\(\sigma_1\)) — produced a new global best.

• improving_reward (\(\sigma_2\)) — improved on the current incumbent but did not become a new global best.

• accepted_reward (\(\sigma_3\)) — did not improve but was accepted by the acceptance criterion.

Weights are then decayed at the end of each segment:

\[w_{t+1} = \rho \cdot w_t\]

where \(\rho\) is decay_factor.

Soft restart on stagnation

stagnation_limit sets the number of consecutive iterations without a new global best before the algorithm triggers a soft restart on the incumbent. The default of 0 disables the soft restart; any non-zero value requires the external model to implement a perturb() method (called to displace the incumbent without losing the recorded global best).

Acceptance criteria

The AcceptanceCriterion controls whether a candidate replaces the incumbent. Two strategies are built in:

• Simulated Annealing — accepts improving moves and probabilistically accepts worsening moves based on a geometric temperature schedule. Configure via AcceptanceCriterion.simulated_annealing with initial_temperature and cooling_rate (applied each iteration).

• Greedy — only accepts improving (or equal) moves. Configure via AcceptanceCriterion.greedy.

Example

from daitum_configuration import (
    AcceptanceCriterion,
    AdaptiveLargeNeighbourhoodSearch,
)

algorithm = AdaptiveLargeNeighbourhoodSearch(
    evaluations=5000,
    candidates_per_iteration=4,
    segment_length=100,
    decay_factor=0.8,
    acceptance_criterion=AcceptanceCriterion.simulated_annealing(
        initial_temperature=100.0,
        cooling_rate=0.9998,
    ),
)

API reference

AdaptiveLargeNeighbourhoodSearch configuration.

class AcceptanceCriterionType(*values)

Strategy used to decide whether a candidate solution replaces the current one.

SIMULATED_ANNEALING = 'Simulated Annealing'

GREEDY = 'Greedy'

class AcceptanceCriterion(name, parameters)

An ALNS acceptance criterion: a AcceptanceCriterionType plus its parameters.

Simulated Annealing accepts improving moves and probabilistically accepts worsening moves based on a temperature schedule. Greedy only accepts improving (or equal) moves.

name: AcceptanceCriterionType

parameters: dict[str, Any]

classmethod simulated_annealing(initial_temperature=None, cooling_rate=None)

Construct a Simulated Annealing acceptance criterion.

Parameters:

• initial_temperature (float | NumericExpression | None) – Starting temperature for the SA schedule. Must be positive. Defaults to 100.0.

• cooling_rate (float | NumericExpression | None) – Geometric cooling factor applied each iteration. Must be in (0, 1). Defaults to 0.9998.

Return type:

AcceptanceCriterion

classmethod greedy()

Construct a Greedy acceptance criterion (only improving moves are accepted).

Return type:

AcceptanceCriterion

class AdaptiveLargeNeighbourhoodSearch(log_info=False, evaluations=100000, max_evaluations_without_improvement=10000, max_time_without_improvement=300, min_improvement=1e-06, max_restart_count=0, prng_seed=None, time_limit=60, candidates_per_iteration=1, segment_length=100, decay_factor=0.8, new_best_reward=33.0, improving_reward=9.0, accepted_reward=3.0, stagnation_limit=0, acceptance_criterion=<factory>)

Adaptive Large Neighbourhood Search (Ropke & Pisinger, 2006).

ALNS maintains a single incumbent solution and, each iteration, generates one or more candidate solutions by applying a destroy operator followed by a repair operator. Operators are drawn from user-supplied pools by weighted random selection; their weights are updated online based on the outcome of each iteration so that operators that recently produced good moves are picked more often.

Each iteration:

1. Select k destroy operators by weighted random sampling.

2. Select k repair operators by weighted random sampling.

3. Generate k candidate solutions by applying each destroy/repair pair to a copy of the incumbent.

4. Evaluate the k candidates (in parallel when k > 1).

5. Decide whether to accept the best candidate via the configured AcceptanceCriterion.

6. Reward the operator pairs that produced this iteration’s candidates.

7. Every segment_length iterations, decay all operator weights by decay_factor.

The operator-reward schedule has three tiers:

• new_best_reward (\(\sigma_1\)) — the candidate became a new global best.

• improving_reward (\(\sigma_2\)) — the candidate improved on the current incumbent but is not a new global best.

• accepted_reward (\(\sigma_3\)) — the candidate did not improve but was accepted by the acceptance criterion (e.g. by SA).

Operator weights are then decayed each segment via:

\[w_{t+1} = \rho \cdot w_t\]

where \(\rho\) is decay_factor.

The destroy and repair operator pools, plus the solution representation, are defined inside the user’s external model implementation (see the platform ALNSExternalModel interface); only the algorithm-level controls are configured here.

candidates_per_iteration: int | NumericExpression | Parameter | Calculation = 1

Number of candidate solutions generated per iteration. k=1 runs sequentially; k>1 evaluates candidates in parallel.

segment_length: int | NumericExpression | Parameter | Calculation = 100

Iterations between operator weight decay steps.

decay_factor: float | NumericExpression | Parameter | Calculation = 0.8

weight multiplier applied per segment. Must be in (0, 1).

Type:

\(\rho\)

new_best_reward: float | NumericExpression | Parameter | Calculation = 33.0

reward applied to operators that produced a new global best.

Type:

\(\sigma_1\)

improving_reward: float | NumericExpression | Parameter | Calculation = 9.0

reward applied to operators that produced a candidate improving on the current incumbent (but not a new global best).

Type:

\(\sigma_2\)

accepted_reward: float | NumericExpression | Parameter | Calculation = 3.0

reward applied to operators that produced an accepted but non-improving candidate.

Type:

\(\sigma_3\)

stagnation_limit: int | NumericExpression | Parameter | Calculation = 0

Number of consecutive iterations without a new global best before triggering a soft restart. Set to 0 to disable. Requires perturb() to be implemented in the external model.

acceptance_criterion: AcceptanceCriterion

Acceptance criterion governing whether candidates replace the incumbent.

property key: str

The algorithm key emitted as algorithmKey in the serialised output.