Implement Hybrid Evolutionary Algorithm (HEA)

[unbreaking-V]

Description

The task involves the implementation of a Hybrid Evolutionary Algorithm (HEA) and comparing its performance with MSLS and ILSx methods implemented in a previous task. The main aspects of the algorithm to be implemented include an elitist population, a steady-state mechanism, and a specific recombination operator. The algorithm aims to explore the solution space efficiently while avoiding premature convergence through diversification techniques.

Task Breakdown

1. Initialization

   • Generate an initial population of 20 solutions using local search methods.
   • Ensure no duplicate solutions exist in the population.

2. Recombination Operator

   • Select two different parent solutions uniformly at random.
   • Create a child solution by:
     • Starting with one parent.
     • Removing edges not present in the second parent.
     • Removing vertices that become isolated.
     • Repairing the solution using a heuristic method similar to ILS2.

3. Optional Local Search

   • Apply local search to the offspring solution (optional step).

4. Population Update

   • If the offspring is better than the worst solution in the population and sufficiently different from all existing solutions, add it to the population.
   • Remove the worst solution to maintain the population size.

5. Stopping Criteria

   • Repeat the process until the stopping criteria is met, which is the running time of the MSLS algorithm

Pseudocode

// Initialization
GenerateInitialPopulation(P)
P := ApplyLocalSearch(P)
EnsureNoDuplicates(P)

// Main Loop
repeat
    // Selection
    parent1, parent2 := SelectTwoParents(P)

    // Recombination
    child := Recombine(parent1, parent2)

    // Optional Local Search
    if ApplyLocalSearchEnabled then
        child := LocalSearch(child)

    // Population Update
    if IsBetter(child, WorstSolution(P)) then
        P := AddToPopulation(P, child)
        P := RemoveWorstSolution(P)

until StoppingCriteriaMet()