Neighbourhoods

In simulated annealing, a neighbourhood function defines the set of candidate solutions that can be reached from the current state in a single step. The quality and structure of the neighbourhood are crucial for the algorithm’s performance, as they determine how the search space is explored. The Neighbourhood protocol defines the interface for these functions. A neighbourhood is a callable that takes an AnnealingState and returns a new candidate solution of the same type.

Vector Neighbourhood

The VectorNeighbourhood is designed for continuous optimization problems where the solution is represented as a sequence of floating-point numbers. It generates a new candidate solution by applying a uniform random perturbation to each element of the current vector.

Mathematics

For each component \(x_i\) in the current solution vector, the new component \(x'_i\) is calculated as:

\[x'_i = x_i + (2 \cdot \text{random}() - 1) \cdot \epsilon \cdot \text{scaling}(T)\]

where:

\(\text{random}()\) is a random float in the range \([0, 1)\).
\(\epsilon\) (epsilon) is the maximum magnitude of the perturbation, which can be constant or dynamic via the Epsilon protocol.
\(\text{scaling}(T)\) is the temperature scaling factor at the current annealing temperature \(T\).

Example Usage

from altbacken.external.neighbourhood.numeric import VectorNeighbourhood
from altbacken.core.state import AnnealingState

# Initialize with a perturbation radius of 0.5
neighbourhood = VectorNeighbourhood(epsilon=0.5)

# Current state at temperature 1.0
state = AnnealingState(current_solution=(1.0, 2.0, 3.0), temperature=1.0)

# Generate a neighbor
new_solution = neighbourhood(state)

Parameters

epsilon (float | Epsilon): The maximum distance any single component can move from its original value (before temperature scaling). If a float is provided, it is treated as a constant. Defaults to 0.1.
random (RandomNumberGenerator): A function providing random floats between 0 and 1. Defaults to random.random.
vector_type (Callable): A constructor used to wrap the resulting sequence (e.g., tuple or list). Defaults to tuple.
temperature_scaling (TemperatureScaling): A callable that adjusts the perturbation range based on the current temperature. Defaults to no_temperature_scaling.

```

Integer Vector Neighbourhood

The IntegerVectorNeighbourhood is designed for discrete optimization problems where the solution is represented as a sequence of integers. It generates a new candidate solution by applying a random perturbation and rounding the result to the nearest integer.

Mathematics

For each component \(x_i\) in the current integer vector, the new component \(x'_i\) is calculated as:

\[x'_i = x_i + \text{round}\left( (2 \cdot \text{random}() - 1) \cdot \epsilon \cdot \text{scaling}(T) \right)\]

where:

\(\text{random}()\) is a random float in the range \([0, 1)\).
\(\epsilon\) (epsilon) is the maximum magnitude of the perturbation, which can be constant or dynamic via the Epsilon protocol.
\(\text{scaling}(T)\) is the temperature scaling factor at the current annealing temperature \(T\).

Example Usage

from altbacken.external.neighbourhood.numeric import IntegerVectorNeighbourhood
from altbacken.core.state import AnnealingState

# Initialize with a perturbation radius of 2
neighbourhood = IntegerVectorNeighbourhood(epsilon=2)

# Current state at temperature 1.0
state = AnnealingState(current_solution=(10, 20, 30), temperature=1.0)

# Generate a neighbor (integer results only)
new_solution = neighbourhood(state)

Parameters

epsilon (int | Epsilon): The magnitude of the perturbations. If an integer is provided, it is treated as a constant. Defaults to 1.
random (RandomNumberGenerator): A function providing random floats between 0 and 1. Defaults to random.random.
vector_type (Callable): A constructor used to wrap the resulting sequence (e.g., tuple or list). Defaults to tuple.
temperature_scaling (TemperatureScaling): A callable that adjusts the perturbation range based on the current temperature. Defaults to no_temperature_scaling.

```

Array Neighbourhood

The ArrayNeighbourhood is designed for high-performance optimization tasks using array-based solutions (e.g., NumPy arrays). It utilizes vectorized operations to generate neighbors by adding a uniform random perturbation across the entire array structure.

Mathematics

The neighbor array \(A'\) is calculated from the current array \(A\) as:

\[A' = A + \text{uniform}(-\beta, \beta)\]

where the bound \(\beta\) is defined as:

\[\beta = \text{scaling}(T) \cdot \epsilon\]

and:

\(\text{uniform}(-\beta, \beta)\) generates an array of the same shape as \(A\) with values drawn from a uniform distribution.
\(\epsilon\) (epsilon) is the scaling factor, which can be constant or dynamic via the Epsilon protocol.
\(\text{scaling}(T)\) is the temperature scaling factor at the current annealing temperature \(T\).

Example Usage

import numpy as np
from altbacken.external.neighbourhood.numeric import ArrayNeighbourhood
from altbacken.core.state import AnnealingState

# Initialize for NumPy arrays with a perturbation bound of 0.1
neighbourhood = ArrayNeighbourhood(epsilon=0.1)

# Current state with a 2x2 matrix
vector = np.ones((2, 2))
state = AnnealingState(current_solution=vector, temperature=1.0)

# Generate a neighbor array
new_solution = neighbourhood(state)

Parameters

epsilon (float | Epsilon): Scaling factor for determining the range of the neighborhood bounds. If a float is provided, it is treated as a constant. Defaults to 0.1.
seed (int): Seed for the internal random number generator to ensure reproducibility. Defaults to 0.
temperature_scaling (TemperatureScaling): A callable that adjusts the perturbation range based on the current temperature. Defaults to no_temperature_scaling.

```

Adaptive Epsilon

The Epsilon protocol allows for dynamic adjustment of the perturbation range (step size) based on the current AnnealingState. While passing a constant value to numeric neighbourhoods is common, using a custom epsilon strategy can improve convergence by adapting to the search progress.

Interface

Any callable that accepts an AnnealingState and returns a numeric value (float or int) satisfies the protocol:

from altbacken.core.state import AnnealingState

def my_adaptive_epsilon(state: AnnealingState) -> float:
    # Example: reduce epsilon as iterations increase
    return 1.0 / (state.iteration + 1)

Example Usage

This can be passed directly to any numeric neighbourhood:

from altbacken.external.neighbourhood.numeric import VectorNeighbourhood

neighbourhood = VectorNeighbourhood(epsilon=my_adaptive_epsilon)

Provided Implementations

ConstantEpsilon: A wrapper used internally when a fixed numeric value is provided to a neighbourhood. It always returns the same value regardless of the state.

```

Permutation Neighbourhood

The PermutationNeighbourhood is designed for combinatorial optimization problems where the solution is a specific ordering of elements (e.g., the Travelling Salesman Problem). It generates neighbors by applying one of three stochastic operations: swapping, reversing, or inserting elements.

Operations

The neighborhood combines three common permutation moves. You can control the relative frequency of these moves using weights during initialization.

Swap: Selects two random indices and swaps the elements at those positions.
Reverse: Selects a random subsequence and reverses the order of elements within it.
Insert: Removes an element from a random position and inserts it into another random position.

Example Usage

from altbacken.external.neighbourhood.permutation import PermutationNeighbourhood
from altbacken.core.state import AnnealingState

# Initialize with custom weights (mostly swaps and reversals)
neighbourhood = PermutationNeighbourhood(
    swap_weight=0.5,
    reverse_weight=0.4,
    insert_weight=0.1
)

# Current permutation
state = AnnealingState(current_solution=[1, 2, 3, 4, 5], temperature=1.0)

# Generate a neighbor
new_permutation = neighbourhood(state)

Parameters

swap_weight (float): Relative weight for the swap operation. Defaults to 0.7.
reverse_weight (float): Relative weight for the reverse operation. Defaults to 0.2.
insert_weight (float): Relative weight for the insert operation. Defaults to 0.1.
seq (Callable): A constructor used to wrap the resulting sequence (e.g., tuple or list). Defaults to tuple.
random (RandomNumberRange): A function providing random integers within a range. Defaults to random.randint.

Custom Neighbourhoods

You can implement your own neighbourhood by creating a class or function that follows the Neighbourhood protocol.

from altbacken.core.state import AnnealingState

def my_custom_neighbourhood(state: AnnealingState[float]) -> float:
    # Generate a new solution based on the current one
    return state.current_solution + 0.1