MM - Memetic Algorithm

The Memetic Algorithm module implements a hybrid metaheuristic that combines genetic algorithms with local search strategies. This implementation supports both standard and distributed execution modes.

class Memetic(domain: Domain, fitness_function: Callable[[Solution], float], population_size: int = 10, max_iterations: int = 20, mutation_rate: float = 0.1, neighbor_population_size: int = 10, alteration_limit: float = 1.0, distributed: bool = False, log_dir: str = 'logs/MM', distribution_level: int = 0)

Bases: Metaheuristic

This class implements the Memetic algorithm. It uses the Solution class as an abstraction of an individual for the meta-heuristic.

It solves an optimization problem defined by a Domain object and an implementation of a fitness function.

The algorithm combines genetic algorithms with local search strategies to enhance solution quality. Each generation involves: 1. Selection of best parents 2. Genetic operations (crossover and mutation) 3. Local search improvement 4. Population update

Parameters:

  • domain (Domain) – The problem domain

  • fitness_function (Callable[[Solution], float]) – The fitness function to optimize

  • population_size (int) – The population size, defaults to 10

  • max_iterations (int) – The maximum number of iterations, defaults to 20

  • mutation_rate (float) – The mutation rate, defaults to 0.1

  • neighbor_population_size (int) – The size of neighborhood in local search, defaults to 10

  • alteration_limit (float) – The maximum alteration allowed in local search, defaults to 1.0

  • distributed (bool) – Whether to use distributed computation, defaults to False

  • log_dir (str) – The logging directory, defaults to “logs/MM”

  • distribution_level (int) – The level of distribution (0=none), defaults to 0

Code example

from metagen.framework import Domain
from metagen.metaheuristics import Memetic

# Create domain and fitness function
domain = Domain()
domain.defineInteger(0, 1)
fitness_function = lambda x: sum(x)

# Create and run memetic algorithm
memetic = Memetic(domain, fitness_function, population_size=50)
best_solution = memetic.run()

Initialize the Memetic Algorithm with the given parameters.

initialize(num_solutions=10) → Tuple[List[Solution], Solution]

Initialize the population with random solutions.

Parameters:

num_solutions (int) – The number of solutions to generate, defaults to 10

Returns:

A tuple containing the initial population and the best solution

Return type:

Tuple[List[Solution], Solution]

iterate(solutions: List[GASolution]) → Tuple[List[Solution], Solution]

Perform one iteration of the memetic algorithm.

This method: 1. Selects the best parents 2. Creates offspring through genetic operations 3. Improves offspring through local search 4. Updates the population

Parameters:

solutions (List[GASolution]) – The current population

Returns:

A tuple containing the updated population and the best solution

Return type:

Tuple[List[Solution], Solution]

stopping_criterion() → bool

Check if the stopping criterion is met.

The stopping criterion is met when the maximum number of generations is reached.

Returns:

True if the stopping criterion is met, False otherwise

Return type:

bool