[EN] Travelling Salesman Problem II - Informed Operators

Today, we try to improve our solutions of the TSP problem from the last seminar. As usual, we will try to come up with some informed operators. It is useful to think about the heuristics, which are traditionally used to solve the TSP.

k-OPT

Probably the most famous heuristics for TSP is called 2-OPT. It selects two edges, removes them and replaces them with two other edges (there is only one option, how to do that). Finally it selects the shorter of the two resulting paths. Actually, the same operation is performed by the mutation that takes part of the path and puts it into the individual in the reverse order. The only difference is that 2-OPT only changes the individual, if the resulting path is shorter.

2-OPT can be naturally generalized to k-OPT - k edges are removed and the resulting fragments are connected by new edges in such a way, that the resulting path is the shortest possible.

Nearest neighbors

We can also select a city on the path and add its nearest neighbor right after it. This can be repeated a few times. The idea behind this approach is that it creates short fragments of the path, which can be useful.

Initialization using an approximation algorithm

A clever initialization is also an option. We can use some of the minimum-spanning-tree-based approximation algorithms to create the initial population. However, be careful - such an initialization can create a local optimum which is hard for the algorithm to improve further.