MA4601/MAT061 Stochastic Search and Optimisation

MA4601/MAT061 Stochastic Search and Optimisation

Assignment 2: Evolutionary Algorithms

Due 12:00 mid-day, Friday 5th March

      This assignment investigates the use of an Evolutionary Algorithm to solve a Travelling Salesman Problem.

      You will need to submit two files: a programme file titled YOUR NAME assign1.r or .py and a report as a pdf file titled YOUR NAME assign1.pdf. Submission by email to [email protected].

      The report should be typed in a 12 point font and should be no more than four pages long. You must express yourself in your own words and acknowledge your sources: see the university rules on academic misconduct https://intranet.cardiff.ac.uk/students/study/exams-and-assessment/cheating-and-academic-misconduct

      Your code must be submitted as a single file, and must be properly documented, including clear instructions on how to run the code. Data files may be included separately. See the module website for restrictions on the external libraries you can use, and note that jupyter notebooks are not accepted.

(a) (4 marks) Explain what Tournament Selection is, for an Evolutionary Algorithm. In particular explain how selection pressure is expressed in Tournament Selection.

(b) (10 marks) Write an Evolutionary Algorithm for solving the Travelling Salesman Prob-lem.

● Use permutations of 1, . . . , n (where n is the number of cities) to represent solutions

● For mutation use 2-opt moves

● For crossover between x and y use the following rule to produce a single offspring z:

1. Randomly choose a contiguous subsequence w of x. Let a be the last city in w.

2. In the tour y, let b be the first city after a that is not in w.

3. Remove w from y and cycle the result so that it starts with b. Call this v.

4. Put z = (w, v)

● Use Tournament Selection

(c) (6 marks) Apply your code to the Qatar data set from Assignment 1. How does the algorithm respond (in terms of the quality of solution and the run time) to changes in the following meta-parameters:

● Population size

● Crossover rate

● Mutation rate

● Selection pressure