Instructions
This assignment is an individual assignment.
NOTE: It is your responsibility to clarify any aspect of the assignment that you are unsure of, with your lecturer.
You are required to upload a single zip file on moodle before due date. The assignment will not be accepted using any other method.
Your lecturer may use an oral examination or any other mode to test your understanding of the material submitted.
PART A of this assignment is due one week prior to the submission of PART B.
Learning Outcomes Covered
Marks allocation
Questions |
Marks |
PART A |
30 |
PART B |
50 |
Total |
80 |
Assessment 1 – Combinatorial Optimization
Travelling Salesman Problem
The “Travelling Salesman Problem” (TSP) is about a salesman that must visit every city in his assigned territory exactly once and then return back to the starting point. The goal is to find the best tour with the lowest possible cost. A possible search space for the TSP problem is a permutation of the n cities. Any single permutation of n cities yields a solution, which is interpreted as a complete tour, with a return home implied as soon as the last city in the sequence is visited.
Genetic Algorithm
Genetic Algorithms (GAs) are adaptive heuristic search algorithms based on the evolutionary ideas of natural selection and genetics. The basic concept of GAs is to simulate processes in the natural system necessary for evolution, especially those that follow the principles first laid down by Charles Darwin of survival of the fittest. As such, they represent an intelligent exploitation of a random search within a defined search space to solve a problem. The algorithm can be summarized as:
You are expected to implement a Genetic Algorithm to solve travelling salesman problem.
Implementation Specifications
Select any two crossover and/or mutation strategies stated above and implement the genetic algorithm solution on the travelling salesman problem. For example, you can use following two set of parameters for your assignment:
Deliverables
PART A: Source Code in a single zip file, with following methods:
PART B: Analysis.docs file
This file should have comparative analysis of the two selected parameter settings of the GA and an extensive comparison of results obtained by the GA with the Local Search Algorithm. The Analysis includes:
Marking Criteria
Source Code
Functions |
Marks |
Initializing Travelling Salesman problem |
5 |
Initial population |
5 |
Mutation |
5 |
Crossover |
5 |
Evaluate population |
5 |
Selecting next generation population |
5 |
TOTAL |
30 |
Analysis
CATEGORY |
Unacceptable (Below Standards) |
Acceptable (Meets Standards) |
Good (Occasionally Exceeds) |
Excellent (Exceeds Standards) |
Run the algorithm a minimum 10 times and report back the best solution values found in each run (also report the average of the best solution values in 10 runs) |
Poor graph and analysis 0-3 mark |
average graph and analysis 4-6 marks |
good graph and analysis 7-9 marks |
excellent graph and analysis 10 marks |
Report back with graph and description of the number of iterations vs best solution values found in each run |
Poor graph and analysis 0-3 mark |
average graph and analysis 4-6 marks |
good graph and analysis 7-9 marks |
excellent graph and analysis 10 marks |
Critically evaluate the performance of two selected strategies of the Genetic Algorithms (by comparing the results) |
Poor graph and analysis 0-4 mark |
Average graph and analysis 5-8 marks |
Good graph and analysis 9-14 marks |
Excellent Literature Review 15 marks |
Critically evaluate the performance of both the GA and the Local Search Algorithm (by comparing the results) |
Poor comparison 0-4 marks |
Average comparison 5-8 marks |
Good comparison 9-14 marks |
Excellent comparison 15 marks |
TOTAL |
50 |
Appendix
Table: Distance matrix of 15 cities (exemplar)
Urgenthomework helped me with finance homework problems and taught math portion of my course as well. Initially, I used a tutor that taught me math course I felt that as if I was not getting the help I needed. With the help of Urgenthomework, I got precisely where I was weak: Sheryl. Read More
Follow Us