Joint search with parameterized initialization operators #16

Summary

Add to the hyper-heuristic the ability to jointly optimize:

parameterized initialization operator + sequence of search operators

The goal is to replicate the architectural pattern already used by heuristic_space: a .txt file in collections/ or a Python list containing the available operators. The conceptual difference is that initialization operators are executed only once before the search, while search operators continue to compose the iterative sequence of the metaheuristic.

API and structure changes

• Extend Population.initialise_positions() to accept parameterized initialization, for example ("beta", {"a": 0.5, "b": 0.5}), while maintaining compatibility with all available strategies.
• Add a new search space, initialization_space, accepting either str or list, mirroring heuristic_space.
• Represent each initializer in the format ("scheme", params_dict), for example ("sobol", {"scramble": True}).
• Extend the HH candidate solution to (init_operator_id, operator_sequence).
• Add the ChangeInitOperator action, which changes only the candidate's initialization operator.

Context

The framework now supports multiple initialization strategies in Population.initialise_positions(), in addition to the historical random and vertex strategies. Current examples include sobol, halton, lhs, beta, normal, lognormal, exponential, and rayleigh.

The hyper-heuristic has also started receiving initial_scheme, which is passed on to Metaheuristic(..., initial_scheme=...). However, in the current model, this choice is still fixed for the entire hyper-heuristic execution.

Today, in the static solver, the search optimizes only the sequence of operators:

candidate_solution = [op_1, op_2, op_3, ...]

while initialization is an external parameter:

initial_scheme = "random"

This prevents the hyper-heuristic from exploring the interaction between the population initialization method and the sequence of operators used to refine it.

Problem

1. Fixed initialization selection: the user chooses initial_scheme before execution, and all candidate sequences are evaluated with the same strategy.
2. Initialization outside the solution genotype: the hyper-heuristic cannot modify the initialization strategy during the search.
3. Initialization parameters are not explorable: methods such as beta, normal, lognormal, exponential, and rayleigh have their own parameters, but the public API still does not allow them to be configured through initial_scheme.
4. Loss of synergy: different operator sequences may perform differently depending on the initial population distribution.
5. Incomplete search: the final solution represents only the operator sequence, not the complete composition of the metaheuristic.

Proposed solution

Add a space of parameterized initialization operators, analogous to the search-operator space.

The model changes from:

solution = operator_sequence

To:

solution = (initialization_operator, operator_sequence)

Conceptual example:

candidate_solution = {
    "initialization_operator": ("sobol", {"scramble": True}),
    "operator_sequence": [12, 4, 27, 8]
}

The metaheuristic execution must continue to follow this order:

initialize population -> apply sequence of search operators

The initialization operator must not be inserted in the middle of the search-operator sequence. It is a component of the generated metaheuristic, but it has its own semantics: it is applied only once, before refinement.

Initialization-space format

Create a dedicated collection, for example:

collections/default_initializers.txt

Each line must follow the format:

("random", {})
("vertex", {})
("lhs", {})
("sobol", {"scramble": True})
("halton", {"scramble": True})
("beta", {"a": 0.5, "b": 0.5})
("normal", {"mean": 0.5, "std": 0.25})
("lognormal", {"mean": 0.0, "sigma": 0.5})
("exponential", {"scale": 0.5})
("rayleigh", {"scale": 0.4})

This format essentially replicates the pattern of search operators:

operator name + parameter dictionary

The difference is that initializers do not have a selector, because there is no acceptance/rejection step for a previous population during initialization.

Expected configuration

The hyper-heuristic must accept a new argument or configuration:

hh = Hyperheuristic(
    heuristic_space="default.txt",
    initialization_space="default_initializers.txt",
    problem=problem,
    parameters=parameters,
)

It must also accept a list directly, following the current heuristic_space pattern:

initialization_space = [
    ("random", {}),
    ("sobol", {"scramble": True}),
    ("beta", {"a": 0.5, "b": 0.5}),
]

If initialization_space is a string, the file must be read from collections/, just as already happens with heuristic_space.

Compatibility

The change must preserve the current behavior.

If initialization_space is not provided, the hyper-heuristic must continue using the fixed initial_scheme:

parameters = {
    "initial_scheme": "random"
}

For compatibility, initial_scheme must accept both the old and the new format:

initial_scheme = "random"

initial_scheme = ("beta", {"a": 0.5, "b": 0.5})

When joint search is enabled, initial_scheme may be used as the initializer for the first solution, as long as it exists in initialization_space.

Expected behavior in the static solver

During the static solver, the hyper-heuristic must be able to generate neighbors by changing:

1. Only the sequence of search operators
2. Only the initialization operator

The current actions continue to operate on the operator sequence:

Add
AddMany
Remove
RemoveMany
Shift
LocalShift
Swap
Restart
Mirror
Roll
RollMany

Add a new structural action:

ChangeInitOperator

This action must change only the initialization operator of the candidate solution.

Example:

# Before
{
    "initialization_operator": ("random", {}),
    "operator_sequence": [12, 4, 27]
}

# After ChangeInitOperator
{
    "initialization_operator": ("beta", {"a": 0.5, "b": 0.5}),
    "operator_sequence": [12, 4, 27]
}

Integration with the current code

The implementation must reuse the existing flow:

Metaheuristic(
    problem,
    search_operators,
    num_agents,
    num_iterations,
    initial_scheme=initial_scheme,
)

The evaluate_candidate_solution() method must evaluate the complete composition:

initialization_operator + decoded_operator_sequence

instead of receiving only an operator sequence with a fixed external initial_scheme.

The performance calculated by the static solver now represents the quality of the pair:

(parameterized initialization operator, operator sequence)

Expected changes in Population and Metaheuristic

Population.initialise_positions() must accept strategy-specific parameters.

Desired API example:

pop.initialise_positions("random")
pop.initialise_positions(("beta", {"a": 0.5, "b": 0.5}))
pop.initialise_positions("beta", a=0.5, b=0.5)

The implementation may choose a single internal representation, but it must preserve compatibility with old calls.

Metaheuristic.initial_scheme must be able to store:

"random"

or:

("normal", {"mean": 0.5, "std": 0.25})

Initializer space

Initializers without their own parameters:

random
vertex
lhs

Initializers with natural parameters already existing or desirable:

sobol: scramble
halton: scramble
beta: a, b
normal: mean, std
lognormal: mean, sigma
exponential: scale
rayleigh: scale

It is also necessary to align the list of valid initializers in the hyper-heuristic with what actually exists in Population.initialise_positions(). Currently, any strategy listed as valid must have a corresponding implementation, or it must be removed from the list until it is implemented.

Out of scope for this increment

• Integrating automatic initialization selection into the dynamic and neural_network solvers.

Expected result

The hyper-heuristic must return a complete metaheuristic:

Generated metaheuristic
Initialization: ("sobol", {"scramble": True})
Operators: [op_1, op_2, op_3, ...]
Performance: ...

Thus, the final solution now represents:

how to initialize + how to refine

Benefits

Acceptance criteria

• initial_scheme="random" must continue to work.
• initial_scheme=("beta", {"a": 0.5, "b": 0.5}) must initialize the population with the provided parameters.
• initialization_space must accept either a file in collections/ or a Python list.
• The format of each initializer must be ("scheme", params_dict).
• The static solver must be able to evaluate solutions with different initialization operators.
• ChangeInitOperator must change only the candidate's initialization operator.
• The saved result must include the parameterized initialization operator used by the best solution.
• The list of valid initializers must reflect only strategies that are actually implemented.
• The behavior of the dynamic and neural_network solvers must remain equivalent to the current behavior.

Expected tests

• Compatibility with string-based initial_scheme.
• Compatibility with initial_scheme in the ("scheme", params_dict) format.
• Reading initialization_space from a file.
• Using initialization_space as a Python list.
• Evaluating the same operator sequence with different initializers.
• Candidate mutation through ChangeInitOperator.
• Guarantee that ChangeInitOperator does not change the operator sequence.
• Persistence of the parameterized initializer in the static solver result.
• Parameter validation for initializers such as beta, normal, sobol, and halton.

Assumptions

• The chosen format for initializers is ("scheme", params_dict).
• initialization_space must copy the behavior of heuristic_space, but for initializers.
• The implementation is restricted to the static solver.
• Initialization continues to happen only once before the operator sequence.