A brief introduction to MA

PyCNP employs a Memetic Algorithm (MA) framework to solve both CNP and DCNP. Originally proposed by Moscato (1989), MAs integrate Local Search (LS) techniques into a population-based Genetic Algorithm (GA). This hybrid approach combines the exploration capabilities of evolutionary algorithms with the exploitation strengths of local optimization.

The canonical memetic algorithm implemented in PyCNP follows this general procedure:

  1. Initialization: A population \(P\) of solutions is generated.

  2. Evolutionary Loop:

    • Crossover: Two parent solutions are selected to produce an offspring solution \(S'\).

    • Local Search: The offspring \(S'\) is improved using a problem-specific local search heuristic.

    • Population Update: The improved solution is incorporated back into the population, potentially replacing a less fit individual.

  3. Termination: The process repeats until a stopping criterion (e.g., time limit, maximum generations) is met.

Pseudocode:

Canonical Memetic Algorithm
Input: Problem instance I, population size θ
Output: The best found solution S*

1:  P ← PopInitialize(θ)                 // Build an initial population
2:  S* ← argmin_{S_i ∈ P} f(S_i)         // Record the best solution found so far
3:  while stopping criteria is not met do
4:      Randomly select two individuals S^a, S^b ∈ P
5:      S' ← Crossover(S^a, S^b)         // Perform solution recombination
6:      S' ← LocalSearch(S')             // Perform local optimization
7:      if f(S') < f(S*) then
8:          S* ← S'                      // Update the best solution
9:      end if
10:     P ← PopUpdate(P, S')             // Update the population
11: end while
12: return S*

PyCNP implements four state-of-the-art memetic algorithms based on this framework:

  • Standard Memetic Search (MS): Uses component-based neighborhood search (CBNS) and double backbone-based crossover (DBX).

  • Variable Population Memetic Search (VPMS): Dynamically adjusts population size to balance exploration and exploitation.

  • Instance Reduction Memetic Search (IRMS): Uses a problem reduction strategy to simplify large instances before solving.

  • Fast Tri-individual Memetic Search (FTMS): A specialized algorithm for DCNP that maintains a small elite population.