purpose of this assignment is to implement the Ant Colony Optimization (ACO) algorithm for the travelling salesman problem (TSP).

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Assignment 3 - Ant Colony Optimization for the Travelling Salesman Problem

A travelling salesman needs to travel to “n” cities to do business. Given the location of the cities, find a route that traverses all cities exactly once and returns to the original city the salesman began in. The goal is to minimize the total distance travelled within the route.

 

The TSP can be represented using an undirected, weighted graph. The vertices of the graph represent the cities, the edges represent possible paths, and the edge weights represent the distance of that path. An example of such a graph (taken from the tutorial slides) is given below:

 

The purpose of this assignment is to implement the Ant Colony Optimization (ACO) algorithm for the travelling salesman problem (TSP).

 

Each of the N ants should start in a random city. Ants construct their tours by selecting an unvisited city from the current city probabilistically, as discussed in lecture and tutorial. Each ant maintains a “tabu list”, which is used to store their current incomplete tour. The tabu list is used to determine which cities still need to be visited in order to complete the tour, and guarantee that a feasible solution is created.

The tabu list can also be used once a tour is complete to re-trace the tour of a particular ant. After all N ants have completed their tours, the pheromone matrix is updated. The pheromone trails are reduced using the evaporation rate, and the ants deposit pheromone on the paths they have visited.

 

As a reminder, the ACO pseudocode is as follows:

initialize matrices(pheromone, heuristic, probability) while termination condition not met do:

constructAntSolution() updatePheromones()

end while

Note: Review the lecture and tutorial slides for additional implementation details!

 

Experimental analysis:

Run your ACO on the following dataset from: http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/eil51.tsp. This dataset contains the positions of 51 cities. The cities in this file are given in the format:

city_num x_coordinate y_coordinate

To determine the distance between two cities, calculate the Euclidean distance between the two cities and round the result to the nearest integer value.

 

The parameters being used for experimentation are α and β. Recall that α represents the weight of the pheromone, and β represents the weight of the heuristic. Use the following parameter values for experimentation:

1. α = 0.5, β = 0.5

2. α = 0, β = 1

3. α = 1, β = 0

4. Determine your own parameter settings

 

An evaporation rate of ρ = 0.95 should be kept constant for all of your experiments. You should set your own values for the number of ants (N) and number of generations (g).

 

For each of the above experiments, run your ACO five times. Your program should output the following to either a file or standard output:

1. All ACO parameters, including the random number seed

2. Per generation: average tour length, best tour length

3. Per run: best tour length and the corresponding path

 

Bonus: Implement a graphical display to show the best final path at the end of a run rather than printing it to the console. Note that you should still provide the best path length, whether this is given in the display or printed to the output file/standard output is up to you.

 

For your analysis, compute for the multiple runs: average of best tour length per generation and average tour length per generation. Using a graph drawing tool such as excel, plot well labelled graphs of the best and average tour lengths.

 

Finally, prepare a summarized report of your findings using IEEE format introduced to you at the tutorial. IEEE format details are found at: https://www.ieee.org/conferences/publishing/templates.html.

 

An IEEE report in this format is expected to be 5 pages in length. The report should have the following sections and each section should address the listed points:

1. Introduction

• BRIEFLY introduce the concepts and topics discussed in the report.

• Precisely define the problem (TSP) and explain why its solution is important.

2. Background

• This section should explain the algorithms used in the report (pseudo code is helpful) and provide other information which you feel will be relevant to someone trying to understand your results.

 

3. Experimental Setup

• This section should provide enough information about your experiments to allow someone else to duplicate your results.

• This should include algorithm parameters used and any other relevant implementation details.

 

4. Results

 

 

• This section should summarize your findings.

• For your multiple runs compute the average best tour length per generation and average tour length per generation. Using a graph drawing tool such as excel, plot well labelled

graphs for your experiments.

• Also include summary tables describing the tour lengths of your final solution. Summary statistics such as min and max tour length, mean tour length, median tour length, and standard deviation should be included in your tables. Tests for statistical

significance would also be appropriate, for example T-Tests or Mann-Whitney U tests.

• Explain your graphs/data in detail and emphasize the similarities and differences between different algorithm configurations.

 

5. Discussions and Conclusions.

• This section should provide a BRIEF summary of what experiments you performed and the results you observed.

• Following this BRIEF summary, you should discuss your opinions regarding your results and what conclusions you’ve arrived at.

• This could include issues like which parameter set performed better. How did the choice of ACO parameters affect the final outcome?

6. References

• List your sources here. The text of the report should contain references to your sources.

 

This report is very important, so be sure to include it. Start early, gathering the data and doing the experimental analysis will take much more time than coding the assignment.

 

 

Attachments:

Expert's Answer

274 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of