COMP7212 Artificial Intelligence Techniques

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

1. Research and analyse the general nature of artificial intelligence and the problems it solves.
2. Apply and evaluate artificial intelligence techniques for solving a variety of real world problems.

Marks allocation

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:

1. Randomly generate an initial population.
2. Calculate the fitness of each individual.
3. Define selection probabilities for each individual.
4. Select probabilistically individuals from the population.
5. Produce an offspring via mutation and crossover methods.
6. 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

Analysis

Appendix

Table: Distance matrix of 15 cities (exemplar)