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:
–> 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:
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)
- Implement the difffferent mutation operators (insert, swap, inversion, scramble) for permutations given in the lecture.
- Implement the difffferent crossover operators (Order Crossover, PMX Crossover, Cycle Crossover, Edge Recombination) for permutations given in the lecture.
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)
- Design three difffferent evolutionary algorithms using crossover and mutation, based on the implementation of your difffferent modules. Your algorithms should perform as best as possible. Justify your design choices.
- (Experiment 1) Run your three algorithms once with population sizes 10, 20, 50, 100 on the instances EIL51, EIL76, EIL101, ST70, KROA100, KROC100, LIN105,PCB442, PR2392, and USA13509 from TSPlib. Report the outcomes after 5000,10000, and 20000 generations. To clarify: these are 3 ∗ 4 ∗ 10 = 120 runs, i.e., 3 algorithms × 4 population sizes × 10 instances.
- (Experiment 2) From these three algorithms, select your “best” algorithm, justify your selection, and run your “best” algorithm with a population size of 50 for 20000 generations on the ten TSPlib instances mentioned above. Report for each instance either (1) the average cost and the standard deviation or (2) the median cost and the interquartile range.
- For the large instances, e.g., USA13509: if you cannot fifinish a single run, please report the results that you can achieve within some time limit, e.g., “after 4 hours” or “after 8 hours”.
- How often you repeat the experiment involving your best algorithm is up to you.
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.
- How to report the outcomes: for each of Experiment 1 and Experiment 2, submit the results in a plain text fifile or in an Excel spreadsheet (or similar).
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.
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipnxx