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
TODO: experiment with ratio coefficient: coef, that adjust what portion of cycle is deleted in destroy perturbation -> implement random sampling from proposed distribution to get it, e.g.: [0.2, 0.4]
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: