COMP SCI 4095, COMP SCI 4195, COMP SCI 7093 Evol. Comp. Semester 2, 2019
Assignment 3: Multi-Objective Evolution of Instances for the Traveling Salesperson Problem
Core Body of Knowledge classification (http://tinyurl.com/acscbok): Abstraction (5), Design (5), Teamwork concepts & issues (3), Data (5), Programming (5), Systems development (3)
1 Overview
Assignments should be done in groups consisting of 5-6 students. 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. Programming has to be done in JAVA.
2 Assignment
In this assignment, you have to design multi-objective evolutionary algorithms that evolve Euclidean instances of the Traveling Salesperson (TSP) problem. An instance is given by n cities in the Euclidean plane. Each city i has coordinates (xi,yi), xi,yi ∈ [0,20],
1 ≤ i ≤ n. The distance between two cities is given by d(i,j) = (xi −xj)2 +(yi −yj)2 which is the Euclidean distance between i and j. Given the n cities in [0,20]2, a TSP
instance is fully specified based on the Euclidean distances between the cities. In the assignment, you have to evolve Euclidean instances that exhibit a significant performance difference for algorithms solving the Traveling Salesperson problem.
Reading:
[[1] O. Mersmann, B. Bischl, H. Trautmann, M. Wagner, J. Bossek, F. Neumann: A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem. Ann. Math. Artif. Intell. 69(2): 151-182 (2013). https: //arxiv.org/abs/1208.2318
[2] J. Bossek, P. Kerschke, A. Neumann, M. Wagner, F. Neumann, H. Trautmann: (2019): Evolving diverse TSP instances by means of novel and creative mutation op- erators. In: Foundations of Genetic Algorithms XV, FOGA 2019, ACM Press. https: //cs.adelaide.edu.au/~frank/papers/FOGA19DivTSP.pdf
We only consider Euclidean TSP instances in this assignment and call this a TSP instance (for short).
1
COMP SCI 4095, COMP SCI 4195, COMP SCI 7093 Evol. Comp. Semester 2, 2019
For all exercises of this assignment, you have to use implementations of 2-Opt Local Search (starting with a random initial solution), the Inver-over Algorithm (populations size 10 and parameter setting as described in the original paper), and your own best performing evolutionary algorithm from Exercise 1 using a population size of 10. 2-opt should run on each instance until it has obtained a local optimum and the evolutionary algorithms should run on each instance for 1000 generations.
For all exercises except Exercise 1, you have to evolve instances for the TSP with n = 50, 100 cities that maximize the performance difference for each algorithm in comparison to the other two algorithms. Let algorithm A1 be the 2-Opt Algorithm, A2 be the Inver- over Algorithm, and A3 be your best evolutionary algorithm from Assignment 1.
JMetal (see http://jmetal.github.io/jMetal/) implements most of the important evolutionary multi-objective algorithms and you are able to use this framework for As- signment 3.
Exercise 1 Your first multi-objective optimisation (15 marks)
Download and install JMetal. Run NSGA-II for 10.000 generations on the benchmark functions ZDT 2 and ZDT 3 with population sizes 10, 100, and 1.000. Visualise the six final populations in your report.
Exercise 2 Discrete evolutionary multi-objective algorithms for TSP instances (30 points)
Place a grid on the given area [0, 20]2 such that each cell has width and heights 1. In total, you obtain a grid having 20 · 20 = 400 cells, Use an evolutionary algorithm that places each of the n cities in a different cell. The location for the city in a particular cell is the middle of this cell.
1. Design appropriate mutation and crossover operators that can be used in NSGA-II, SPEA2 and IBEA. Include a description in your report.
2. Apply the algorithms NSGA-II, SPEA2 and IBEA to maximize for each i ∈ {1, 2, 3} the two objectives pi,j(I) = fAj(I)−fAi(I) and pi,k(I) = fAk(I)−fAi(I) where j ̸∈ {k,i} and k ̸∈ {i,j}, 1 ≤ j,k ≤ 3, and fA(I) as defined in Exercise 3 of Assignment 2. Include the results and your findings in your report.
Exercise 3 Continuous evolutionary multi-objective algorithms for TSP instances (20 points)
Cities can now have general coordinates and you are no longer bound by the grid structure. Use continuous evolutionary multi-objective algorithms to optimize the placement of the n coordinates of the cities. You have to make sure that your instances are feasible, i.e. each city is in [0, 20]2.
1. Design appropriate mutation and crossover operators that can be used in NSGA-II, SPEA2 and IBEA. Include a description in your report.
2
COMP SCI 4095, COMP SCI 4195, COMP SCI 7093 Evol. Comp. Semester 2, 2019
2. Apply the algorithms NSGA-II, SPEA2 and IBEA to maximize for each i ∈ {1, 2, 3} the two objectives pi,j(I) = fAj(I)−fAi(I) and pi,k(I) = fAk(I)−fAi(I) where j ̸∈ {k,i} and k ̸∈ {i,j}, 1 ≤ j,k ≤ 3. Include the results and your findings in your report.
Exercise 4 Mixed evolutionary multi-objective algorithms for TSP instances (35 points)
Combine the two previous approaches. A solution should consist of a placement according to Exercise 2, but each cell may contain more than 1 city. Each city may be moved from the middle of the cell by a continuous algorithm. Cities that are placed in the same cell should have different offsets. A solution should be represented as a vector of length 3n where the first n entries are used to address the cells for the n cities and the remaining 2n entries are used to specify the offset for each city.
3
1. 2.
Design appropriate mutation and crossover operators that can be used in NSGA-II, SPEA2 and IBEA. Include a description in your report.
Apply the algorithms NSGA-II, SPEA2 and IBEA to maximize for each i ∈ {1, 2, 3} the two objectives pi,j(I) = fAj(I)−fAi(I) and pi,k(I) = fAk(I)−fAi(I) where j ̸∈ {k,i} and k ̸∈ {i,j}, 1 ≤ j,k ≤ 3. For one fixed setting according to the grid (first n components), you should run a continuous multi-objective evolutionary algorithm that optimizes the placement of the turbines within this grid structure. This means that you are running a multi-objective algorithm ”inside” a multi- objective algorithm. Use appropriate selection methods to merge this resulting population with the current parent population. Tune the algorithms such that they perform as best as possible. Include the results and your findings in your report.
Marking
Marking of implementations will be done according to the following criteria:
4
• • •
•
correct overall implementation 25%
quality of the code (succinctness, object orientated, class structure) 15%
design of the evolutionary algorithms and justification of the operators and algo- rithms – 20%
quality of the results achieved – 40%
Procedure for handing in the assignment
Work should be handed in using MyUni. The submission should include:
• a README.txt file containing instructions to run the code, the names, student numbers, and email addresses of the group members
3
COMP SCI 4095, COMP SCI 4195, COMP SCI 7093 Evol. Comp. Semester 2, 2019
• list showing for each exercise the student(s) taking major responsibility.
• for each student 4-5 sentences summarizing their contribution to this assignment work. item all source files
• all configuration files
• tables, figures and reports for the different exercises (1-2 pages per exercise).
• the log-files containing the results generated by the code. Generate short log-files that still show the overall optimisation.
In addition, there will be a session where you have to present and explain your solutions. A presentation on the main results of your work for this assignment is a requirement in order to obtain the marks.
4