1    Assignment structure and practical requirements

The  assignment  is  done  in groups  of 5-6 students.   Each  student  has  to  take  major responsibility for parts of the assignment and collaborate with the team members.  The group has to make sure that the workload is evenly distributed.  Report progress and task distribution to your tutor during the workshops. This is worth points!

Use the programming language Python and store your code in the Github classroom repository supplied by the course.  Commit updates frequently and write a concise but in- formative commit message.  This will document that all group members have contributed regularly. Save results in the specified files and directories.  Think before committing big output files, because this can make your repository very large over time.  This is worth points!

Use one file  tsp lib.py  for  all  of  the  modular  library  code  and  one  or  more files like run experiments.py to assemble and execute the experiments and files to produce the analysis outputs.  Document your code with concise but informative comments.  This is worth points!

Make the figures self-explanatory and unambiguous. Always include axis labels, if avail- able with units, unique colours and markers for each curve/type of data, a legend and a title. Give every figure a number (e.g.  at start of title), so that it can be referred to from anywhere unambiguously. This is worth points!

Do not use generative AI for coding or text answers.  Do not copy code or text from anywhere.   We  are  automatically running plagiarism checks and generative AI detec- tors. Instead, make your submission original and unique by writing everything yourself, choosing function and variable names well and documenting your code with your own comments.

2    Objective

The objective is to design a library and implement evolutionary algorithms for the travel- ing salesperson problem (TSP). The input for the TSP is given by n cities and distances dij  for traveling from city i to city j, 1 ≤ i,j ≤ n.  A tour starts at one city, visits each city exactly once, and returns to the origin.  The goal is to compute a tour of minimal cost. The TSP is one of the most famous NP-hard optimization problems and you should build an EA library and design evolutionary algorithms for this problem.

3    Team roles and contributions (5 points)

Write a short paragraph for each group member about the role and contributions to the assignment.  Write a draft at the start and update it as needed.  It is normal that the roles change sometimes. It is important to plan and track the roles in a group throughout the process.

Write team contributions into the file  doc/team contributions.txt .   The  final  versions should have at most 50 words per student.

4    Code architecture (10 points)

When designing your library for the TSP, follow object-oriented design practices and build a modular system.  It should be possible to extend the system by using different methods for each part of the design, e.g., different individual representations, operators, and selection methods.

Write your architecture design and rationales into the file doc/architecture  design.txt . Use this file to document your design incrementally and to coordinate within the group.  The final version should have at most 200 words.

Make one diagram to summarise your object-oriented code architecture, for example using UML  (Unified Modelling Language).   Save the figure  as  doc/architecture diagram.png . The diagram can have sub sections, but has to be easily readable when printed on A4 paper.

5    Genetic algorithm design decisions  (20 points)

In the following, we list the different modules that need to be implemented for the TSP. If a parameter setting is not specified in detail, then choose a setting that you consider appropriate and document the rationale for your choice. You should, however, take into account the recommendations given in the lecture.  Examples could be probabilities for operator use, whether all parents are replaced in the new generation and which initiali- sation method to use.

Write your design decisions and rationales into the file doc/algorithm  design.txt .  Use this file to document your design incrementally and to coordinate within the group.  In the final version of the file, the documentation of each individual design decision should be at most 100 words.

6    Problem representation (5 points)

Write a class  TSP which represents the TSP. Your class should enable the construction of TSPs from the files of the symmetric traveling salesperson problem from the TSP benchmarks library available here:

http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/

7    Individual and population representation (5 points)

Represent a possible solution to the TSP as a permutation of the given cities and imple- ment it using a class Individual.

A population in an evolutionary algorithms represents a set of solutions.  Implement a class Population for representing populations, which are sets of individuals.

Evolutionary algorithms often start with individuals that are constructed uniformly at random. Write a method that constructs such an individual in linear time – not in O(n log n) or even O(n2 ), but in O(n), where n is the number of cities.  For example, sorting the cities somehow to determine a good initial guess will take O(n log n) and is not allowed.

8    Variation operators (10 points)

Implement the mutation operators Insert, Swap, Inversion and Scramble for permutations given in the lecture.

Implement the crossover operators Order Crossover, PMX Crossover, Cycle Crossover and Edge Recombination for permutations given in the lecture.

9    Selection operators  (10 points)

Implement the selection methods fitness-proportional and tournament selection given in the lecture.

10    Algorithm comparison and analysis (25 points)

Design and code three different evolutionary algorithms each involving crossover and mutation using your modular implementation.

Justify your design choices in the file doc/algorithm design.txt .  Use at most  100 words for each of the three algorithms.

Test whether your algorithm and code is free of errors and all components interact cor- rectly.   To  do  this,  use a small problem from the benchmarks,  small population and small number of iterations.  Once you are confident about the implementation, scale up gradually.

We will use the PCB442 benchmark problem from TSPlib. For a fair comparison of the algorithms, randomly initialise populations of 20, 50 and 100 individuals each, 30 times (for the repetitions). Use these same initial populations for all three algorithms, so that none is accidentally closer to the optimum.  You can either fix the random seed of your random number source or generate them once and save them to a file in the directory out/.

Run your three algorithms on all of the initial populations for 20000 generations.  In each run at every 10th iteration, save current best fitness and current median fitness for later analysis. Save these series into one or more files in the directory out/.

Make one diagram for each of the 30 repetitions.  Use python code and a for loop, so that you can rerun this when the data are updated.  The diagram has the iterations on the x-axis, and fitness on the y axis.  Each algorithm produces one curve for the best fitness and one for the median fitness over the iterations, and that 3 times for each of the population sizes. Follow all of the figure labelling requirements from above!  Save the diagrams using python to files results/repetitionXX.png.

Make one diagram to compare the final best fitness values across algorithms.  Make a box plot (or violin plot if you like) with the algorithms on the x axis, the fitness on the y-axis and the box plots showing the median and first and third quartile of the 30 fitness values achieved by its 30 repetitions. Add the best fitness value from each algorithm to the diagram. Save the diagram using python to files results/algorithm stats.png .

Make one diagram to compare the best tour found by each of the algorithms.  Plot the city locations (x andy coordinates) as dots.  Plot the best tour from each algorithm using lines between dots, e.g.  in different colour.  Plot the optimal tour from the website into the diagram as well. Follow all of the figure labelling requirements from above! Save the diagram using python to files results/algorithm solutions.png .

Analyse the diagrams while making specific references to observations in specific dia- grams.   Evaluate  the  convergence  speed,  convergence  smoothness,  final  result  fitness, variability across repetitions, observations that may be related to you design decisions, hard to optimise sections of that TSP instance, the algorithm you would choose and why, etc..  Write your analysis into the file results/algorithm analysis.txt using at most 250 words.

11    Inver-over Evolutionary Algorithm (10 points)

Read the paper “Inver-over Operator for the TSP” by Guo Tao and Zbigniew Michalewicz

available here: https://cs.adelaide.edu.au/ zbyszek/Papers/p44.pdf

Implement the algorithm as described in the paper.

Run the inver-over algorithm with a population size of 50 for 20000 generations on the same TSP problem with the same initial populations 30 times and add the results to all of the diagrams above in the same way.

Compare the results with your earlier experiments using the analysis diagram.  Write your answer in file results/inverover comparison.txt . Use at most 100 words for this text answer.

12    Submission

Submit your Github repository to Gradescope within MyUni once per group.  Before you submit, copy the final versions of the following files into the directory final/.  We will mark these final versions.