This is the assignment for the sub-module Artificial Intelligence Search of the module Software Methodologies. The hand-out date is Monday 14th October 2019 and it is to be completed and handed in via DUO by 2 p.m. on Friday 17th January 2020.

***** It is really important that you read this document *****
***** thoroughly before you start. I’m sorry to appear *****
***** so dramatic with my bold-italic-red script but it *****
***** really is important that you follow the guidelines. *****

Overview

You are to implement two different algorithms (call them Algorithm A and Algorithm B) in Python using techniques studied during the lectures, but possibly also other algorithms you have devised or discovered for yourself, to solve the Travelling Salesman Problem (TSP). Your implementations should seek to obtain the best TSP tours that you can, given 10 collections of cities and their distances that I will supply to you. You will need to hand in the following items:

• between 2 and 4 correct Python programs comprising of: at least a basic implementation of each of your chosen algorithms (these are the files necessarily named AlgAbasic.py and AlgBbasic.py); and possibly an enhanced implementation of each of your chosen algorithms (these are the files necessarily named AlgAenhanced.py and AlgBenhanced.py)

• for each of the two algorithms that you implement, 10 tours, one for each city-set that I give you, detailing the best tours you have found with any implementation of that algorithm (moreover, each tour needs to be in a specifically named and formatted text file as dictated in Section 4; so this amounts to 20 tour files)

• a one-page proforma (a pdf document) briefly describing the algorithms you implemented and any enhancements you have made.

The content is as follows: the mark scheme is in Section 1; the FAQs in Section 2; the algorithm tariffs in Section 3; how your tour files should be formatted in Section 4; and finally some hints and tips as regards the core algorithms in Section 5.

1 Mark scheme

The mark scheme is complicated so please read it carefully as it will determine which algorithms you ultimately choose to implement and help you plan your time. A list of FAQs follows in Section 2.
Marks will be awarded for:

(a) the sophistication of the algorithms that you implement

(b) the correctness of your basic implementations (AlgAbasic.py and AlgBbasic.py)

(c) any enhancements you have made so as to obtain enhanced implementations of your basic implementations (AlgAenhanced.py and AlgBenhanced.py)

(d) the quality of the tours that you obtain.

I will measure ‘sophistication’ and ‘correctness’ as follows.

• ‘Sophistication’: Each algorithm has a tariff associated with it (see Section 3) where this tariff gives the maximum number of marks that you can secure with your basic implementation of the ‘vanilla’ version of that particular algorithm (by ‘basic’ I mean the standard version covered in lectures). The tariff is such that the more technically complex the algorithm, the more marks you can secure.

• ‘Correctness’: I will run your basic implementations (AlgAbasic.py and AlgBbasic.py) on 2 secret sets of cities that I will not divulge to you beforehand. One city-set will have 48 cities and the other city-set will have 90 cities.

Your basic implementations (AlgAbasic.py and AlgBbasic.py) need to be correct.

• By ‘correct’ I mean that when I run your basic implementations on my secret city-sets, a legal tour is produced for both city-sets.

However, : : : your ‘sophistication’ mark will be the maximum tariff from your ‘correct’ basic implementations (I’ll say why in Section 2). Your ‘correctness’ mark will only be earned if both of your basic implementations are correct (I’ll say why in Section 2).

• So, if you have only one ‘correct’ basic implementation then your ‘sophistication’ mark will be the tariff corresponding to the ‘correct’ basic implementation but you will not be awarded a ‘correctness’ mark. (Of course, if neither of your basic implementations is ‘correct’ then you will not be awarded either a ‘sophistication’ mark or a ‘correctness’ mark).

In addition, you can pick up extra ‘enhancement’ marks by enhancing and experimenting with your basic implementations to obtain two enhanced implementations (AlgAenhanced.py and AlgBenhanced.py).

• For example, you might try different versions of crossover for a genetic algorithm and this experimentation might secure extra bonus marks (at my discretion).

It is up to you as to whether you wish to try and enhance your basic implementations (though once you have your basic implementations, it is not particularly time-consuming to do a little bit of experimentation). Ideally, you should hand in 2 basic implementations (AlgAbasic.py and AlgBbasic.py) of two distinct TSP algorithms as well as 2 enhanced implementations (AlgAenhanced.py and AlgBenhanced.py) of the same algorithms. 

• Note that you are not allowed to implement 4 different TSP algorithms!

You will be awarded an ‘enhancement’ mark for each ‘correct’ enhanced implementation (with ‘correct’ defined as above) but these marks will depend upon how innovative I feel your enhancements are.
You will also receive a ‘basic quality’ mark corresponding to how good the tours are that you have found. For each of the 10 given city-sets, you should return: the best tour you have produced by any implementation of your first algorithm (Algorithm A), enhanced or otherwise; and the best tour you have produced by any implementation of your second algorithm (Algorithm B), enhanced or otherwise. However, : : : the ‘basic quality’ mark will be determined only by the best tour you have found for each of the 10 city-sets (regardless whether this is via an implementation of Algorithm A or of Algorithm B; I’ll say why in Section 2).
You could also receive an ‘enhanced quality’ mark. For each algorithm, I will run your basic implementation and your enhanced implementation on my secret city-sets and depending upon how well your enhanced implementation does in comparison with your basic implementation, I will award extra marks (at my discretion); so, the ‘enhanced quality’ mark is derived from both of your enhanced implementations.

• When I compare a basic implementation with an enhanced implementation, please ensure that the parameters are identically set, e.g., if your Algorithm A is a genetic algorithm then you should ensure that the number of iterations, mutation probability, size of pupulation, and so on, are identically set in AlgAbasic.py and AlgAenhanced.py (failure to do so could mean you lose ‘enhancement quality’ marks).
The possible marks for each category follow:

The possible marks for each category follow:

• ‘sophistication’: the maximum obtainable is 10 but this will depend upon the tariff of the algorithms implemented

• ‘correctness’: if both basic implementations are ‘correct’ then a mark of 4 is awarded, otherwise a mark of 0

• ‘enhancement’: there is a maximum of 3 marks available for each enhanced implementation; so, the overall ‘enhancement’ mark is at most 6

• ‘quality’: the maximum ‘basic quality’ mark available is 8 and the maximum ‘enhanced quality’ mark available is 2; so, the overall ‘quality’ mark is at most 10.

Consequently, the maximum mark achievable is 30.

2 FAQs

• Student: Why do you insist on Python?

• Iain: Every student has completed Computational Thinking and so can program in Python; this yields a ‘level playing field’ when it comes to implementation. Also, restricting to Python-only leads to fairer marking.

• Student: Why do you take the maximum tariff from two ‘correct’ implementations as the ‘sophistication’ mark?

• Iain: On occasion, a more sophisticated algorithm may give worse results than a more elementary algorithm. I want to reward both the quality of the tours that you find and also your accomplishments in coding up a more difficult algorithm. With things set up as above, I encourage you to code up a more sophisticated algorithm without harming your chances of getting good tours.

• So I guess that’s why you take the best overall tour found when you give the ‘basic quality’ mark? So that we don’t harm the quality of the tours we find if we choose to implement a more sophisticated algorithm?

• Iain: Correct!

• Student: And I suppose you ask us to implement two algorithms and to experiment so that you can assess both our understanding of the algorithms in the sub-module, through our capacity to code them up, along with our ingenuity and deeper understanding in obtaining good tours?

• Iain: Correct again! If all I asked you to do was to produce basic implementations of two algorithms and produce some half-decent tours  then there wouldn’t be much of a challenge (nor fun) in that. So, I would like you to experiment. I understand that some of you will have more time and inclination for this than others so I ensure that if all you do is produce basic implementations and some half-decent tours then this will suffice to pass the coursework, which I think is fair. But I’m also giving you the opportunity to show me what you can do and be rewarded for it. In the past, many students have enjoyed the challenge of producing good tours.

• Student: Why do you only give us a ‘correctness’ mark if both basic implementations give tours on your secret city-sets?

• Iain: I think it is reasonable that your two basic implementations should both be correct. Don’t you agree? My definition of ‘correctness’ is not exactly challenging!

• Student: Why do you not just ask us to return the best tour we have found by whatever algorithm for each of the 10 city-sets rather than one tour for each algorithm?

• Iain: I get to see the profile of tours you have produced for each algorithm. This allows me to have confidence that the tours you have supplied to me are indeed produced by the implementations stated, as I know (roughly) how different algorithms should perform. Also, I will run your basic and enhanced implementations on the 10 city-sets to provide me with a sanity check that your codes are what you say they are.

• Student: What if we have worked hard to fine-tune our implementations to perform really well on the 10 city-sets but when you run them on your secret city-sets, they don’t do so well?

• Iain: There is a small chance that this might happen but if your enhanced implementation improves things across many of the 10 citysets, it is likely that it will improve things on my secret city-sets too. Also, the ‘enhanced quality’ mark is relatively small.

• Student: Can you give me some illustrations of the different mark awards depending upon what sort of a student I am?

• Iain: OK; here are some illustrations.

- Student A: Maybe you are hard-pushed and will not have the time nor inclination for experimenting but correctly implement a reasonably sophisticated algorithm at tariff 8 and a less complicated algorithm at tariff 6; so, your ‘sophistication’ mark will be  8 and your ‘correctness’ mark will be 4. The lack of experimentation means: that you get an ‘enhancement’ mark of 0; and that you only obtained moderately good tours overall. Perhaps you get a ‘basic quality’ mark of 5 and so an overall ‘quality’ mark of 5. You would score 17=30 = 57% (a very solid lower-second mark).

- Student B: Maybe you are struggling and cannot correctly implement two algorithms but get a basic tariff-6 TSP algorithm working, though the tours produced are not very good, resulting in a ‘quality’ mark of 4. You would receive a ‘sophistication’ mark of 6, a ‘correctness’ mark of 0 and an ‘enhancement’ mark of 0. Your total mark would be 10=30 = 34% (a fail mark).

- Student C: maybe you are like Student A but you are inclined to experiment. Your enhanced impementations are correct and moderately innovative; so you obtain an ‘enhancement’ mark of 3. The tours of the secret city-sets produced by your enhanced implementations produce a modest improvement over those produced by your basic implementations and you obtain an ‘enhanced quality’ mark of 1. So, you would score 21=30 = 70% (a first-class mark).

The moral of the story? Show ambition with your implementations and experiment.

• Student: Is the assignment the same as last year?

• Iain: No, it has changed. First, the city-sets are different to last year; but more importantly you are being asked to do less work. Last year, students felt that the amount of work required did not match the credit available. This year, students no longer need to supply a 4-page report and I have also supplied to you all of the Python code (skeleton code.py) required for reading and writing data files (you should use this code as directed; it is well commented). I implemented a basic greedy algorithm and a genetic algorithm in an afternoon : : : and I can assure you that your programming skills are way better than mine!

3 Algorithm tariff

Brute-force search: As you are doubtless aware, a brute-force search for the TSP will only work for very, very small sets of cities; of course, when it works, the tour obtained is optimal. (Note that it is not combinatorially straightforward to generate all possible tours for checking.) Tariff: 6/10 

Basic greedy algorithm: The most obvious greedy algorithm is that obtained by starting at some city and iteratively moving to the nearest city to the last city visited. This is trivial to implement. Tariff: 5/10

Best-first search without heuristic data: Depending on how you choose your evaluation function, you can implement a breadth-first search, a depth-first search and various other algorithms. However, you should bear in mind that a breadth-first search is demanding on memory and a depth-first search runs the risk of not terminating (though this will depend upon how you define your search problem). Of course, you can choose to refine a best-first search by forcing termination under given circumstances. Tariff: 7/10

Iterative deepening: One way of getting round the memory requirements of a breadth-first search is to undertake repeated depth-first searches with bounds on the depth. Tariff: 8/10 

Best-first search with heuristic data: You’ll have to build your own heuristic functions as none are supplied. Tariff: 9/10

A* search: You’ll have to build your own heuristic functions as none are supplied. Also, note that an A* search with a ‘good’ heuristic is optimal and also that the TSP is NP-hard; so, if you don’t have a heuristic that gives a good estimation then it is unlikely that you’ll get good tours. Of course, you can choose to terminate an A* search under given user-defined circumstances. Tariff: 10/10

Hill-climbing search: This is very easy to implement once you decide upon the representation of the TSP as a search problem. Tariff: 6/10

Simulated annealing: This is moderately easy to implement once you decide upon the representation of TSP as a search problem. Tariff: 7/10

Genetic algorithm: There are many ways in which you can represent the TSP using a genetic algorithm. Tariff: 8/10

Some of the above algorithms lend themselves to experimentation more than others so you might bear this is mind when making your choices.

In the past, many students have implemented algorithms they have found themselves from books and the general literature, such as Ant Colony Optimisation, Recursive Best-First Search and Beam Search. There are lots of nature-inspired algorithms to choose from with new ones regularly being devised. If you wish to implement an algorithm not covered in the course (and I welcome this) then please e-mail me beforehand and I will supply you with the tariff.
One final thing: I will be executing your implementations automatically and it is possible that you choose parameters so that your implementations (on my secret city-sets) take a long time to execute. When you hand your implementations in, you should ensure that your implementations will take no more than two minutes on my secret city-sets (of sizes 48 and 90). Typical parameters that you will need to adjust are, for example, the  number of iterations in a genetic algorithm, the temperature function in simulated annealing, and so on. If an implementation of yours takes too long then it will be killed and you will run the risk of losing a significant number of marks.

4 The format of your submission

All submissions should be named using your username as follows. I illustrate using the dummy username abcd12 but you should substitute your own. If you don’t follow the rules below then you run the risk of getting no marks!
All files should be in a folder called abcd12. Within this folder there
should be:

• 4 Python programs (.py) entitled AlgAbasic.py, AlgBbasic.py, AlgAenhanced.py and AlgBenhanced.py which are the basic versions of your two chosen algorithms, Algorithm A and Algorithm B, along with the enhanced versions

• 10 tour-files (.txt) entitled AlgA012.txt, AlgA017.txt, AlgA021.txt, AlgA026.txt, AlgA042.txt, AlgA048.txt, AlgA058.txt, AlgA175.txt, AlgA180.txt and AlgA535.txt, with each tour-file containing the best tour you have found using your first chosen algorithm, Algorithm A, on the corresponding city-set

• 10 tour-files (.txt) entitled AlgB012.txt, AlgB017.txt, AlgB021.txt, AlgB026.txt, AlgB042.txt, AlgB048.txt, AlgB058.txt, AlgB175.txt, AlgB180.txt and AlgB535.txt, with each tour-file containing the best tour you have found using your second chosen algorithm, Algorithm B, on the corresponding city-set

• one proforma (.pdf) entitled AISearchProforma.pdf (I give you the template in Word but please save it and return it in the form of a pdf).

You need to ensure that all of your Python implementations can be executed in command-line mode by supplying the city-file, e.g., via the command python AlgAbasic.py AISearchfile012.txt

If I cannot execute your implementations as above then I will not be able to run your codes and you will lose marks. Using skeleton code.py will enable such a command-line execution (and if the input file is omitted then there is a default input file embedded in the code; take a look).
Also, when I run one of your implementations, in your folder abcd12, via a command-line instruction such as • python AlgAbasic.py AISearchfile012.txt the actual input file AISearchfile012.txt is assumed to reside in a folder named city-files that is in the same folder as abcd12. So, the folders cityfiles, abcd12, xyzp32, gdhn74, : : : will all reside in the same folder.

5 The data-files

The actual instances of the Travelling Salesman problem (more precisely, the symmetric Travelling Salesman problem, where the distance from city x to city y, denoted (x; y), is always the same as the distance from city y to city x, that is, (y; x)) will be given in the following form (the cities are always named 0; 1; : : : ; n - 1).
NAME = <string = name-of-the-data-file>,
SIZE = <integer n = the number of cities in the instance>,
<list-of-integers d1; d2; d3; : : : ; dm> where the list consists of
the distances between cities (0; 1); (0; 2); : : : ; (0; n - 1),
then the distances between cities (1; 2); (1; 3); : : : ; (1; n - 1),
: : :
and finally the distance between the cities (n - 2; n - 1)
Commas ‘,’ are used as delimitters in data-files; carriage returns, end-of-line markers, spaces, etc., should be ignored.
So, for example, the instance with 5 cities where: the city 0 is at the origin; the city 1 is 3 miles north; the city 2 is 4 miles east; the city 3 is 3 miles south; and the city 4 is 4 miles west, and all distances are the Euclidean distances between cities, is encoded as the city-file AISearchsample.txt:
NAME = AISearchsample,
SIZE = 5,
3, 4, 3, 4,
5, 6, 5,
5, 8,
5
With reference to the remark above, re: delimitters, the above city-file could well be presented with no carriage returns or spaces, etc., as simply
NAME=AISearchsample,SIZE=5,3,4,3,4,5,6,5,5,8,5
Note that in general a given instance need not be based on the Euclidean distances of a collection of cities on the plane. You should assume that a given distance between two cities is a non-negative integer (and so it could well be the case that the distance between two distinct cities is 0).
As stated earlier, I supply you with the (well commented) skeleton of a Python program called skeleton code.py. The code reads a given input file (in the format above) and supplies the number of cities (num cities in skeleton code.py) and a two-dimensional symetric array (distance matrix in skeleton code.py) containing the distances between cities. You should use skeleton code.py. 

The data-files that you will have to execute your code on will be called AISearchfile012.txt, AISearchfile017.txt, AISearchfile021.txt, AISearchfile026.txt, AISearchfile042.txt, AISearchfile048.txt, AISearchfile058.txt, AISearchfile175.txt, AISearchfile180.txt and AISearchfile535.txt. The numeric digits denote the number of cities in the particular instance.

When you have computed a legitimate tour of some set of cities, there is code in skeleton code.py that checks that this tour is legitimate and writes the tour to an output-file in the correct format. You should supply your tours to me in the file obtained by using this code (after renaming it).

Some remarks and hints

As mentioned earlier, the following methods are available to you (as studied in the course):
• brute-force search
• basic greedy algorithm (‘nearest-neighbour’)
• best-first search without heuristic data
• greedy best-first search
• A∗ search
• hill-climbing search
• simulated annealing
• genetic algorithm.
There is a little bit of work to do as regards the implementation of each method and here is a little bit of help.

Brute-force search

Here is a hint as to how all tours in an n-city Travelling Salesman instance can be generated. Each tour is stored in a 1-dimensional list T of size n, where the elements are all distinct and come from f0; 1; : : : ; n - 1g. The tour stored in T is T[0]; T[1]; : : : ; T[n - 1]; T[0]. In fact, we can similarly store a tour of the m ≤ n cities f0; 1; : : : ; m -1g in T[0]; T[1]; : : : ; T[m -1], with T[m] = T[m + 1] = : : : = T[n - 1] = 0.

Our procedure gen(T ,m) takes as input a tour of m cities, x0; x1; : : : ; xm-1; x0, say, held in the list T (as above), and proceeds as follows.
• If m = n then we compare the length of the tour T (of n cities) with the length of the shortest tour found so far and if T is shorter then we remember T and its length.
• If m < n then gen(T ,m) generates all tours of the cities f0; 1; : : : ; m- 1; mg by inserting the value m after location 0, then after location 1, : : :, then after location m - 1 of T (so that the cities coming after m are ‘shifted’ along the array). Interleaved with generating each tour, which we refer to as T 0, we recursively call the procedure gen(T 0,m + 1).
In more detail, gen(T ,m) is as follows.
if m == n then
calculate the length of the tour T and if it is shorter
than the best tour found so far, remember T and its
length as the best tour found so far
else
for i = 0 to m - 1 do
T 0 = T with the city m inserted after location i
call gen(T 0,m + 1)
T 0 = T with the city m removed from after location i
fi
Thus, the following pseudo-code generates and tests all possible tours, given the distance-file of n cities.

T = [1; 0; 0; : : : ; 0] m = 1 call gen(T ,m)

%initialize tour T as [1] %initialize number of cities of tour T as 1

output the shortest tour found
Although I don’t recommend that you implement a brute-force search, brute-force searches are good for checking optimal values in small cases;  also generating all combinatorial possibilities comes up regularly and it is useful to know how to do this. If you do implement a brute-force search then you can always choose to kill an execution and take the best tour you have found up until that point as a guide.

Best-first, greedy best-first and A∗ search

The Travelling Salesman Problem needs to be realised as a search problem.One way of doing this is to have the set of all lists of distinct cities as the states together with the lists of n distinct cities augmented with the start city (and so a state is a list of between 0 and n cities, or a list of n + 1 cities where the first n are distinct and the last city equals the first). There is one action with a state t0 being a successor of a state t if the list t0 is the partial tour t extended with one new city (not appearing in t), or if t has length n and t0 is t augmented with the first city of t. The step-cost associated with any transition from state t to state t0 is the cost of moving from the final city in the list t to the final city of the list t0. The initial state is the list t0 consisting of just the start city and a goal state is a list of n + 1 cities. An optimal solution is thus a path from the initial state to a goal state of minimal cost.

There are a number of heuristic functions available for the Travelling Salesman Problem. One of these is the heuristic h where, given a state t = x1; x2; : : : ; xr, h(t) is defined to be the minimal step-cost of moving to
a state of the form t0 = x1; x2; : : : ; xr; xr+1 (that is, always move to the nearest legal city from where you are; if there is no city to move to then h(t) = 0).

Another heuristic is as follows. Given some state t, your heuristic function h(t) is the sum of the distance of the closest city c that has not been visited to the last city of the partial tour t plus the distance of any other unvisited city (different from c) to the start city (if there aren’t enough unvisited cities to apply this rule then the heuristic value is 0). This heuristic reflects that you want your next city to be visited to be close to the current city but that you don’t want to be left with a city that is a long way from the start city.

Yet another heuristic h is as follows. Given a state