Homework 1: Traveling salesperson problem

During last weeks, we implemented local search algorithm and an evolutionary algorithm for problems with binary and real representation. The goal of this homework is to apply these algorithms on a traveling salesperson problem.

The traveling salesperson problem is an optimization task with the goal to find the shortest Hamiltonian circle in a graph. In other words, we need to find the shortest path that visits each city exactly once and returns to the city where you started.

TSP is not a single problem, it is a whole class of problems, with many subclasses. Individual instances differ in the number of cities to visit, in the distances between cities, whether the traveling times are symetric or not, etc. A TSP instance is thus usually given either by the matrix of distances between all pairs of cities, or by coordinates of the cities in certain metric space.

We shall concentrate on symmetric instances (the travel time from A to B is the same as the travel time from B to A) from the TSP problem collection called TSPLIB.

There are many potential representations of TSP solutions:

• The most natural one is probably the permutation of numbers which denotes the order in which the cities should be visited.
• Another possible representation is binary string/half-matrix with 1 bit for each pair of cities, meaning whether city i comes before city j. Remember bubble-sort?
• Inversion representation, described in article ucoluk2013tspnew.pdf.

Choose a representation you will use.

Implement a function which will generate a random candidate solution. This generated solution should be feasible, i.e., it should represent a valid sequence of cities to visit. No city should be left out, no city should be visited more than once.

Implement a fitness function for TSP that will allow you to evaluate a candidate solution. It should use the data from the distance matrix.

Implement a function that mutates a solution. It should produce a different valid solution (based on the original solution). There are more reasonable mutation operators, implement at least one. Depending on the chosen representation, you can try:

• Move one city in the sequence to a different position.
• Swap 2 cities in the sequence.
• Reverse a subsequence of cities.
• …

If you have a suitable implementation of local search, you should be able to take your implementation, provide a TSP fitness function, initialization procedure and perturbation operator, and you should have a working TSP solver. Try to apply it on chosen TSP instances, store the results (or better, store info from the whole optimization process).

Again, there are many reasonable crossover operators for TSP. Effective crossover operator requires careful design. Its result should be a valid candidate TSP solution. Implement at least one operator. Depending on the chosen representation, you can try:

• Cycle crossover.
• Order crossover.
• Partially matched crossover.
• Edge recombination crossover.
• Edge assembly crossover (see EvoCOP article.)

Now you should have all the parts of EA for TSP ready. It should be sufficient to correctly configure an EA and run it. Try to apply it on various TSP instances and compare it with the results of local search.

Implement a function that will graphically display the candidate solution of TSP. Ideally, you should be able to watch the sequential improvements, i.e., to see how the best so far solution get better.

We have not talked about memetic algorithms yet. Simply said, each EA combined with a form of local search can be called a memetic algorithm.

The possibilities to combine EA with LS are numerous:

• Instead of random initialization of the EA population, you can first improve them all by LS before you start the evolution.
• Some or all the candidates generated during the run of EA can be improved by LS.
• Etc.

Try to implement a memetic algorithm and compare it with LS and EA.

TSP is actually not a black-box problem; the information hidden in the distance matrix tells us a lot. It allows us to use constructive heuristics to quickly find relatively good solutions. Those solutions can be again used to initialize the EA population.

Try to implement a constructive heuristic and use it

1. as a standalone TSP solver and/or
2. as an initialization method for EA.

Compare the results of both methods, i.e., determine how much the EA can improve the solutions found by the constructive heuristics.

An interesting experiment could be a comparison with a complete systematic search of the space of possible TSP solutions. The space size grows very quickly with the number of cities in TSP instance, and you will find the limit of complete enumeration very soon. If you will not be able to solve the smallest problems from TSP by a complete enumeration, try to generate your own, smaller instance.

Complete enumerative search requires a way how to systematically generate all feasible solutions. But even for complete enumeration, you can create a graph how the best-so-far solution depends on the number of generated and evaluated candidate solutions, and can be thus compared with LS or EA.

With the proposed homework evaluation, we want to give you some freedom in how deep you want to dive into this homework. The homework has some minimal requirements: if you fulfill only them, you will still get the points required for this homework. Anything beyond these minimal requirements will bring you some additional points up to the maximum number of 10 points (and maybe beyond).

We shall deem this homework fulfilled, if you carry out a comparison of

• at least 1 type of LS and
• at least 1 type of EA
• on at least 3 TSP instances from TSPLIB and
• you describe these algorithms concisely (in a report, in an Jupyter notebook, …).

You should submit your solution to task DU1 via a ZIP archive using BRUTE. The ZIP archive shall contain

• source codes of your implementation,
• README file, where you describe how to compile and run the code to get the results of algorithm A on a TSP instance B,
• a short report with the description of your solution (see below).

During the evaluation, we may require you to demonstrate the functionality of your implementation of certail lab exercise (or via an online meeting). If you chose a programming languge other than Pythou, Julia, Java, or C/C++, the demonstration will be probably required.

Expected form of the report:

• It can be a PDF document with text and graphs, but
• a Jupyter notebook (or Pluto.jl notebook) is also acceptable, and
• it can be also a well-commented script that generates the outputs you want to show and describe.

Expected contents of the report:

• Adequate description (not a source code listing) of used algorithms and operators.
• Description of the experimental setup (what parameter values were used for individual algorithms, how many evaluations/generations/minutes they were allowed to run, how many repetitions did you run, etc.)
• Reasonable comparison of the algorithms in tabular or graphical form and a short discussion of the results.
• Warning regarding possible imperfections of the experimental procedure.
• Explicit list of things done beyond the minimal requirements with the links to the places in your source code where their implementations can be found, and a proposal of their point evaluations.

For this homework, you can get up to 10 points.