COMP7212 Artificial Intelligence Techniques Sample Assignment
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
- Research and analyse the general nature of artificial intelligence and the problems it solves.
- Apply and evaluate artificial intelligence techniques for solving a variety of real world problems.
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:
- Randomly generate an initial population.
- Calculate the fitness of each individual.
- Define selection probabilities for each individual.
- Select probabilistically individuals from the population.
- Produce an offspring via mutation and crossover methods.
- Repeat steps 2-6 until a solution is obtained or the maximum number of iterations is reached.
You are expected to implement a Genetic Algorithm to solve travelling salesman problem.
Implementation Specifications
- Number of cities – 50
- Population size – 16
- Number of iterations – 1000 (or any other termination condition) Selection Strategy:
- Rank Selection (with Elitism strategy) Crossover strategies:
- Partially mapped crossover o Order crossover
- Cycle crossover Mutation strategies:
- Swap mutation o Insertion mutation o Displacement mutation
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:
- Rank Selection + Swap mutation + Cycle crossover
- Rank Selection + Insertion mutation + Cycle crossover
Deliverables
PART A: Source Code in a single zip file, with following methods:
- Initial population
- Mutation
- Crossover
- Evaluate population
- Selecting next generation population
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:
- 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)
- Report back with graph and description of the number of iterations vs best solution values found in each run
- Critically evaluate the performance of two selected strategies of the Genetic Algorithms (by comparing the results)
- Critically evaluate the performance of both the GA and the Local Search Algorithm (by comparing the results)
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)