代码代写｜COS126 Assignment 1: The Traveling Salesperson Problem

这是一篇来自澳洲的关于旅行商销售人员问题的代码代写

Assignments should be done in groups consisting of fifive to six (5–6) students. Please use the Groups feature in myUni. If you have problems fifinding a group use the Discussions forum to search for group partners.

Each student has to take major responsibility for one of the exercises and collaborate with the team members on the remaining exercises. Each exercise needs one student taking major responsibility. The group has to make sure that the workload is evenly distributed.

The goal is to design a library and implement evolutionary algorithms for the traveling 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.

When designing your library for the TSP, it is desirable to follow object-orientated design practices and build a modular system. It should be possible to extend the system by using difffferent methods for each part of the design, e.g., difffferent individual representations,operators, and selection methods. In the following, we list the difffferent modules that need to be implemented for the TSP problem. These are basic requirements and you may feel free to add additional features and operators to your library. If the parameter setting is not specifified in detail then you are free regarding your choice. You should,however, take into account the recommendations given in the lecture.

You can use any of the following programming languages: Python or Java.

Exercise 1 Team work: who has done what? (zero points)

We would like each team member to write one paragraph about what each member has contributed to this assignment. We will not mark this, and it will not have any effffect on the marking of the other exercises. We would like to encourage self-regulation within the group and cooperative learning.

Exercise 2 Problem Representation and TSPlib (5 marks)

Write a class TSPProblem which represents the TSP problem. Your class should enable the construction of TSP problems from the fifiles of the symmetric traveling salesperson problem of the TSPlib, which is available online:

For the problem files:

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

–> Download the file ALL_tsp.tar.gz (this contains some of the instances that are not directly listed on that page)

The TSP main page has more information for you, if you want to read a bit:

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

Exercise 3 Individual and Population Representation (10 marks)

Represent a possible solution to the TSP as a permutation of the given cities and implement it in a class Individual.

Evolutionary algorithms often start with solutions that are constructed uniformly at random. Write a method that constructs such a solution in linear time – not in O(n log n) or even O(n2 ), but in O(n), where n is the number of cities.

A population in an evolutionary algorithms represents a set of solutions. Implement a class Population for representing a population which is a set of individuals. Make sure that you can evaluate the quality of a solution with respect to a given problem.

Exercise 4 Variation operators (8+16 marks)

Exercise 5 Selection (15 marks)

Implement the difffferent selection methods (fifitness-proportional, tournament selection,elitism) given in the lecture.

Exercise 6 Evolutionary Algorithms and Benchmarking (9+10+5 marks)

10 repetitions is a good start, 30 or 100 repetitions will result in more reliable means/medians, however, you might not have the time to run the experiments that often.

It is absolutely critical that you provide detailed instructions on how to reproduce the results. With this, we mean that the TAs have to be able to run your code and get results that are somewhat similar to what you are reporting. This means that you might want to create a fifile with all the commands needed to run each experiment.