GitHub

Heuristics

Heuristics in JuLS control how the optimization process explores the solution space. They are divided into three main categories: initialization, neighbourhood exploration, and move selection.

Types of Heuristics

1. Initialization Heuristics

These determine the starting solution for optimization.

SimpleInitialization

Random initialization within variable domains:

init = SimpleInitialization()

GreedyInitialization

Problem-specific greedy construction:

init = GreedyInitialization()

ChristofidesInitialization

Specialized for TSP problems using the Christofides algorithm:

init = ChristofidesInitialization()

2. Neighbourhood Heuristics

These define how to explore the solution space by generating moves.

RandomNeighbourhood

Randomly selects variables and generates moves:

neigh = RandomNeighbourhood(n_vars, n_to_move)  # n_vars total, n_to_move selected

BinaryRandomNeighbourhood

Specialized for binary problems:

neigh = BinaryRandomNeighbourhood(n_moves, n_vars)  # n_moves generated, n_vars flipped each

SwapNeighbourhood

Generates swap moves between variables:

neigh = SwapNeighbourhood()  # No parameters needed

KOptNeighbourhood

k-opt moves for permutation problems:

neigh = KOptNeighbourhood(n_moves, k)  # n_moves generated, k variables each

3. Move Selection Heuristics

These decide which moves to accept during optimization.

GreedyMoveSelection

Always accepts the best improving move:

pick = GreedyMoveSelection()

SimulatedAnnealing

Temperature-based acceptance with cooling:

pick = SimulatedAnnealing(T0=100.0, α=0.95)

Metropolis

Metropolis criterion with fixed temperature:

pick = Metropolis(T=10.0)

Custom Heuristics

You can create custom heuristics by implementing the appropriate interfaces.

Custom Initialization

struct MyInitialization <: InitializationHeuristic
    # Custom parameters
end

function (init::MyInitialization)(experiment::MyExperiment)
    # Return initial solution vector
    return initial_solution
end

Custom Neighbourhood

struct MyNeighbourhood <: NeighbourhoodHeuristic
    # Custom parameters
end

function get_neighbourhood(neigh::MyNeighbourhood, model::Model)
    # Return vector of possible moves
    return moves
end

Custom Move Selection

struct MyMoveSelection <: MoveSelectionHeuristic
    # Custom parameters
end

function pick_a_move(picker::MyMoveSelection, evaluated_moves::Vector{<:MoveEvaluatorOutput})
    # Return selected move or nothing
    return selected_move
end

Heuristic Combinations

Different heuristic combinations work better for different problem types:

For Binary Problems

model = init_model(
    experiment;
    init = GreedyInitialization(),
    neigh = BinaryRandomNeighbourhood(10, 2),
    pick = GreedyMoveSelection()
)

For Permutation Problems

model = init_model(
    experiment;
    init = ChristofidesInitialization(),  # TSP-specific
    neigh = KOptNeighbourhood(5, 2),  # 5 moves, 2-opt
    pick = SimulatedAnnealing(100.0, 0.95)  # T0=100.0, α=0.95
)

For General Integer Problems

model = init_model(
    experiment;
    init = SimpleInitialization(),
    neigh = RandomNeighbourhood(10, 2),  # 10 variables, 2 to move
    pick = Metropolis(5.0)  # T=5.0
)

Next Steps