Description:
This algorithm leverages movement ratings from previous iterations with an ordered list of movements. The list should include both inter- and intra-route movements. In the case of intra-route movements, such as exchanging two edges, it is essential to thoroughly understand the description from lectures concerning the Traveling Salesman Problem.

Steps:

1. Initialize LM - a list of movements that lead to improvement, ordered from best to worst.

2. Generate initial solution ( x ).

3. Repeat:

   • Scan all new movements and add movements that lead to improvement to LM.
   • Examine movements ( m ) from LM, starting from the best until an applicable movement is found.
   • Check if ( m ) is applicable, and if not, remove it from LM.
   • If an applicable movement ( m ) is found:
     • Update ( x ) with ( m(x) ) (accept ( m(x) )).

4. Continue until an applicable movement ( m ) is found after scanning the entire LM list.

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()

Recombination Algorithm:

1. Take two random parents
2. Find edges that do not occur in the second parent
3. Remove them from the cycle, also remove the vertices that have no more edges from the cycle
4. Connect the remaining vertices, which occur in both parents, to each other
5. Apply the regret or nearest neighbor algorithm to restore the cycle

Refactor already implemented heuristics

Implement random walk, as a reference - in each iteration performs a randomly selected move (regardless of its evaluation) and returns the best solution thus found solution thus found.

Important: This algorithm should run in the same amount of time as the slowest of the average
version of the local search.

Iterative local search with Large-scale neighborhood search, i.e., a larger Destroy-Repair perturbation.

Perturbation2 (ILS2) should involve removing more edges and vertices (e.g., 30%) (destroy) and fixing the solution using a heuristic method, one of those implemented in the first lesson. The vertices/edges to be removed can be chosen randomly or heuristically, such as those that are close to the second cycle. We also test this version without a local search (only subject the initial solution to a local search, as long as the starting solution was random) The stop condition for ILSx is to reach a time equal to the average MSLS time for the same instance.

Attention , one run of MSLS includes 100 iterations of LS, and the the final result is the best solution obtained in those 100 runs. The starting solution can be a random solution or one obtained using a randomized heuristic.

Pseudo code:

Generate the initial solution x
x := Local search (x) (option)
Repeat
    y := x
    Destroy (y)
    Repair (y)
    y := Local search (y) (option)
    If f(y) > f(x) then
         x := y
To meet the stop conditions

• Write pseudocode for each algorithm
• Write report
• Update readme

Local search from various random or randomized starting points. You can create random solutions, or use the randomized heuristics from previous classes.

Pseudo code:

Repeat
    Generate a randomized starting solution x
    Local search (x)
Until stop conditions are met
Return the best solution found

Separate approaches to distinct files (greedy, local_search etc) - or propose smarter solution

• Leverage random distribution for choosing start nodes
• Create and adjust script to run each heuristic 100 times
• Adjust the script to store and analyze cycles for report purposes - #8

Iterative local search with little perturbation. Perturbation1 (ILS1) can involve, for example, replacing several edges and/or vertices with others selected at random. The stop condition for ILSx is to reach a time equal to the average MSLS time for the same instance.

Attention , one run of MSLS includes 100 iterations of LS, and the the final result is the best solution obtained in those 100 runs. The starting solution can be a random solution or one obtained using a randomized heuristic.

Pseudo code:

Generate the initial solution x
x := Local search (x)
Repeat
    y := x
    Perturbation (y)
    y := Local search (y)
    If f(y) > f(x) then
         x := y
To meet the stop conditions

For report purposes

Create instance loader and transform raw data into rounded euclidian distance matrix.

Handle execution times of given algorithms similarly as was done for cycle lengths.

• Random cycle
• Best greedy solution

Define neighbourhoods including 2 types of moves:

• Two vertices exchange
• Two edges exchange

Remember to include both intra-class and interclass movements.

Add objective function that uses delta.

• Store cycles in files
• Modify visualization script to plot only the best solutions (or arbitrary chosen one) - use cycles stored in files

Merge all local search functionalities, generate entire pipeline for results aggregation and visualization

• Adjust report.sh to be compatible with all types of algo

Description:
In this algorithm, candidate movements are those that introduce at least one candidate edge into the solution. Candidate edges are defined by selecting 10 other nearest vertices for each vertex. This parameter can also be adjusted experimentally to achieve optimal results. For example, the process of examining movements (between routes or within a route) can be as follows:

For each vertex ( n1 ):

• For each vertex ( n2 ) from the list of the nearest vertices to ( n1 ):
  • Evaluate the movement(s) introducing the edge ( n1-n2 ) into the solution. (Note: This is not equivalent to exchanging vertex ( n1 ) with ( n2 )).

Note: It's crucial to understand that the process involves assessing movements introducing specific edges into the solution, not merely exchanging vertices.

Come up with and idea of how to present number of iterations of ILSx and HEA for report purposes.

• Add titles
• Bigger legend

In this issue, I propose a specific solution to the reconstruction challenge that arises during the implementation of evolutionary algorithms.

The idea is outlined as follows:

Following certain perturbation operations (or their equivalent in genetic programming), the vector typically containing all vertices within a circle would be divided into what we'll refer to as "paths." Each path would consist of a vector with a minimum size of 2 (or possibly 1, depending on further considerations) - representing the initial cycle. Subsequently, we would iteratively apply the nearest neighbor heuristic to each path, attaching the closest vertex to the given path. If a vertex is already assigned to a different path (associated with the appropriate cycle), the paths would be combined to form a new, longer path. This iterative process would continue until both cycles are fully reconstructed.

Change movement definitions for further task compatibility

To advance the implementation of evolutionary algorithms, we need to prepare a comprehensive report that includes details such as visualizations of the greedy method and the number of iterations in ILSx algorithms. To achieve this, it would be beneficial to implement and test various reconstruction approaches from incomplete solutions, other than the weighted regret algorithm. We can explore simple regret, greedy cycles, and nearest neighbors methods.

Furthermore, to support the initial concept outlined in [#39], it is essential to implement the nearest neighbor reconstruction.

Develop an easily extendable TSP class for future convenience.