Once computed, your fitness function values will need to be used to update the amount of pheromone left by each anton your graph.

The Ant Colony Optimisation Algorithm

Implement the ACO like this:

1.    Randomly distribute small amounts of pheromone (between 0 and 1) on the construction graph.

2.    Generate a population of ants and compute a path from the start to the end of the graph for each ant.

3.    Update the pheromone in your pheromone table for each ant’s path according to its fitness.

4.    Evaporate the pheromone on all edges in the graph.

5.     If a termination criterion has been reached, then stop. Otherwise return to step 2.

Termination Criterion: When the algorithm has reached 10,000 fitness evaluations. The result is then the fitness of the best antin the population.

Generating Ant Paths:  An ant will traverse your construction graph by making a decision at each new item it comes to (i.e. an ant at S has three possible path choices ahead in the example above).  This selection is made at random, but biased by the amount of pheromone on the choices ahead (e.g. if the antis at position S in the above diagram and the edge to choice 1 has a pheromone value of 0.5, the edge to choice 2 has a pheromone value of 0.8 and the edge to choice 3 has a pheromone value of 0.1, the ant should have a 5/14 chance of selecting choice 1, an 8/14 chance of selecting choice 2, and a 1/14 chance of selecting choice 3). This should be repeated for all variables for the problem represented in your construction graph.

Pheromone Update: Once the fitness has been computed, the pheromone must be updated accordingly. HINT:   You will need to think carefully about  how your fitness is converted into pheromone to ensure it optimizes correctly.

Pheromone Evaporation:  Finally, the pheromone on all paths must be evaporated.  This is achieved simply by multiplying all edges within the construction graph by an evaporation rate, usually between 0.5 and 0.95. 

Literature Review

In this section, you should review a minimum of 3-4 other nature-inspired approaches that could also have been used to solve this problem. This can include variants of the ant-colony approach described here, but   you should take care to properly consider the range of potential approaches and briefly provide a critical analysis of these.

Implementation and Experimentation

Implement the described ACO in such a way that you can address the above problem and then run the following experiments and answer the subsequent questions. Note that, in the experiments below it is recommended that you run the algorithm for at least 10,000 fitness evaluations.  Different trials of the same algorithm should be seeded with different random number seeds.

You should devise your own set of experiments to determine the effect (if any) that the following parameters have on the performance of the optimisation:

1.    Population size (p)

2.   The amount of pheromone that is deposited according to fitness (m)

3.   The evaporation rate (e)

Your experiments should assess the performance of the algorithm over a number of trials for each setting of p, mande,to provide scientifically robust results.

‘Conference Paper’ Report

Your submission should be a PDF in the style of a paper using one of the style files (Latex style file or Word document template) posted on ELE. Please do not include your name in the ‘author’ section – simply

replace the name with your candidate number.

The paper should have a maximum of 5 pages  (5 sides of A4, references do not count towards the limit),  which should include a short  literature  review on nature-inspired approaches and a description of your experiments where tables and/or graphs of results should take up no more than 2 pages. You should also  include a description of your chosen representation in the ‘Method’ section, but there is no need to explain  the basic algorithm (i.e. as described above). In the remaining space, write a ‘ Discussion and Further Work’ section including your answers to the following questions.

Question1: Which combination of parameters produces the best results?

Question 2: What do you think is the reason for your findings in Question 1?

Question 3: How do each of the parameter settings influence the performance of the algorithm?

Question 4: Do you think that one of the algorithms in your literature review might have provided better results? Explain your answer.

In your  answers,  describe your  observations  of the  results,  and  describe  any  tentative  explanations  or conclusions you feel like making, and describe any further experiments you felt it interesting or useful to do.

Your paper should therefore minimally include the following sections: 1) Literature Review, 2) Method (i.e. your algorithm design), 3) Description of Results, 4) Discussion and Further Work, 5) References.

Marking criteria

Submission

In ELE2, you should submit a single compressed (.zip) folder which contains: Paper: a PDF file with your report;

Code: a text file with clearly commented code;

GenAI: a MS word file with the completed GenAI student declaration;

Marking Scheme

Quality of Literature Review                                                                   15%

Algorithm design                                                                                       15%

Correct and efficient implementation of the algorithm                    10%

Quality of code documentation                                                               5%

Correct results from the ACO runs                                                        15%

Quality (e.g. readability & usefulness) of tables and graphs            10%

Answers to Questions 1-4                                                                       15%

Further Experiments                                                                                 10%

Conclusions                                                                                                 5% 

Over length submissions (per page)                                                     -10%