Algorithm

class MemeticSearch(problem_data: ProblemData, problem_type: str | int, budget: int, seed: int, memetic_search_params: MemeticSearchParams | None = None, variable_population_params: VariablePopulationParams | None = None, hop_distance: int = DEFAULT_HOP_DISTANCE, display_interval: float = DEFAULT_DISPLAY_INTERVAL)

Bases: object

Memetic algorithm implementation for Critical Node Problems.

The MemeticSearch class implements a population-based evolutionary algorithm that combines global search through crossover operations with local search refinement. It supports both CNP and DCNP problem types with configurable search strategies and crossover operators.

The algorithm maintains a population of solutions that evolves over generations: * Initialization: Creates initial solutions using local search * Selection: Selects parent solutions using tournament selection * Crossover: Creates offspring by combining parent solutions * Local Search: Improves offspring using a configured search strategy * Population Update: Updates population based on fitness and diversity * Variable Population: Optionally adapts population size based on progress

Parameters:

• problem_data (ProblemData) – The graph problem data containing nodes and edges.

• problem_type (str) – Either “CNP” for Critical Node Problem or “DCNP” for Distance-based CNP.

• budget (int) – Maximum number of nodes that can be removed.

• seed (int) – Random seed for reproducibility.

run(stopping_criterion: StoppingCriterion, collect_stats: bool = True, display: bool = False) → Result

Execute the memetic search algorithm.

This method runs the main optimization loop, repeatedly generating offspring solutions through crossover and improving them through local search until the stopping criterion is satisfied.

Parameters:

• stopping_criterion (StoppingCriterion) – The criterion that determines when to stop the search. Common options: MaxIterations, MaxRuntime, or NoImprovement.

• collect_stats (bool, default=True) – Whether to collect iteration-by-iteration statistics.

• display (bool, default=False) – Whether to display progress information during the search.

Returns:

A Result object containing: * best_solution - Set of node IDs to remove * best_obj_value - Connectivity after removal (lower is better) * num_iterations - Number of iterations performed * runtime - Total runtime in seconds * best_found_at_time - Time when best solution was found * stats - Statistics object if collect_stats=True

Return type:

Result

Examples

>>> from pycnp import read, MemeticSearchParams
>>> from pycnp.stop import MaxIterations
>>>
>>> problem_data = read("graph.txt")
>>> search = MemeticSearch(
...     problem_data=problem_data,
...     problem_type="CNP",
...     budget=5,
...     seed=42
... )
>>> result = search.run(
...     stopping_criterion=MaxIterations(100),
...     display=True
... )

class MemeticSearchParams(search: int | str = 'CHNS', crossover: str | int | None = None, is_problem_reduction: bool = True, is_pop_variable: bool = True, initial_pop_size: int = 5, reduce_params: Dict[str, Any] | None = None)

Memetic search parameter configuration class.

Used to configure various parameters of the MemeticSearch algorithm. Implemented using dataclass to maintain interface compatibility with the original C++ version.

Examples

>>> from pycnp import MemeticSearchParams
>>> params = MemeticSearchParams(
...     search="CHNS",
...     is_problem_reduction=True,
...     is_pop_variable=True,
...     initial_pop_size=5,
...     reduce_params={"search": "CHNS", "beta": 0.9}
... )

class VariablePopulationParams(max_pop_size: int = 20, increase_pop_size: int = 3, max_idle_gens: int = 20)

Parameter configuration for the variable population size mechanism.

Controls how the population size adapts during the memetic algorithm execution based on convergence behavior.

Examples

>>> from pycnp import VariablePopulationParams
>>> params = VariablePopulationParams(
...     max_pop_size=30,
...     increase_pop_size=5,
...     max_idle_gens=15
... )