Skip to content
Permalink
ac58e57e1b
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

7159CEM-Portfolio/ACO.ipynb

Go to file
 
 
Cannot retrieve contributors at this time
779 lines (779 sloc) 25.8 KB
Raw Blame
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Ant Colony Optimisation (ACO) for the Travelling Salesman Problem (TSP)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let $G$ be a complete weighted graph with $n$ vertices.\n",
"\n",
"**Optimisation TSP**:\n",
"> Given $G$, find a Hamiltonian cycle of minimal total cost.\n",
"\n",
"This problem is **NP-Hard** (Garey and Johnson, 1979, p. 211)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Use the `scikit-opt` library, or an equivalent one, to benchmark the performance of the Ant Colony Optimisation (ACO) metaheuristic on a variety of graph **sizes** ($n=50,100,150,200,250,300$) and **topologies** (Euclidean, Symmetric, Asymmetric).\n",
"\n",
"Compare its results against the results obtained using the **nearest neighbour** greedy approach. (An implementation is provided below.)\n",
"\n",
"What is the effect of the ACO's hyperparameters on time and quality of solutions?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Marking scheme\n",
"\n",
"|Item|Mark|\n",
"|:----|---:|\n",
"|Euclidean|/4|\n",
"|Symmetric|/4|\n",
"|Asymmetric|/4|\n",
"|Effect of `size_pop`|/4|\n",
"|Effect of `max_iter`|/4|\n",
"|||\n",
"|**Total**: |/20|\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Graph types and generation of random instances"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The code below provides 3 types of TSP instances by creating an **adjacency matrices** $M$ as follows:\n",
"\n",
"1. **Asymmetric**: The edge weights are independent and uniformly distributed in an interval $[1,\\text{MAX\\_WEIGHT}]$, i.e the graph is assumed to be directed.\n",
"2. **Symmetric**: Like the asymmetric case but the graph is undirected, and the adjacency matrix is therefore symmetric: $M_{ij}=M_{ji}$.\n",
"3. **Euclidean**: Generate points using $(x,y)$ coordinates, then generate the adjacency matrix by calculating all the required distances. \n",
" > Recall that the distance between two points $(x_1,y_1)$ and $(x_2,y_2)$ is $\\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$.\n",
" \n",
" The points are generated in the rectangle defined by the points $(0,0)$ and $(\\text{MAX\\_Y},\\text{MAX\\_Y})$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Implementation of the instances generation"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"First start by importing relevant libraries."
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {
"ExecuteTime": {
"end_time": "2022-10-25T11:38:31.774523Z",
"start_time": "2022-10-25T11:38:23.464728Z"
},
"scrolled": true
},
"outputs": [],
"source": [
"from random import randint, shuffle # random integers and random shuffling of a list\n",
"from itertools import permutations # iterate over all possible permutations of a list\n",
"from itertools import chain # concatenate range()'s'\n",
"from math import inf as oo # Infinity (∞) is larger than any number\n",
"from math import sqrt, log, factorial # square root, logarithm, and n!\n",
"from time import perf_counter # for measuring time. NB. 'perf_counter' is better/more accurate than 'time'\n",
"import networkx as nx # to draw sample graphs\n",
"import pandas as pd # to show the adjacency matrix in a nice format\n",
"import matplotlib.pyplot as plt # to plot graphs of time and quality vs n\n",
"import seaborn as sns # nice statistical plots -- see e.g. https://seaborn.pydata.org/tutorial/relational.html#relational-tutorial\n",
"sns.set_style(\"white\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Basics"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let the set of vertices be $\\{0, 1, 2,\\ldots, n-1\\}$.\n",
"\n",
"For simplicity, we will consider $0$ to be the start and end point of cycles."
]
},
{
"cell_type": "code",
"execution_count": 74,
"metadata": {
"ExecuteTime": {
"end_time": "2022-10-25T11:38:31.830857Z",
"start_time": "2022-10-25T11:38:31.778480Z"
}
},
"outputs": [],
"source": [
"class Graph:\n",
" ''' Random graphs '''\n",
" def __init__(self, n=0, type='asymmetric', MAX_WEIGHT=100, MAX_X=200, MAX_Y=200):\n",
" self.n = n\n",
" self.vertices = list(range(n)) # [0,1,...,n-1]\n",
" self.type = type\n",
" self.adj_matrix = [[oo for i in range(n)] for j in range(n)]\n",
" # Generate a random adjacency matrix according to the required type\n",
" if type=='symmetric': self.__random_symmetric_graph(n,MAX_WEIGHT)\n",
" elif type=='Euclidean': self.__random_euclidean_graph(n,MAX_X,MAX_Y)\n",
" elif type=='easy': self.__random_cycle_graph(n)\n",
" else: self.__random_asymmetric_graph(n,MAX_WEIGHT) # assume 'asymmetric' otherwise\n",
" \n",
" def __getitem__(self, i):\n",
" ''' Allow indexing to get the weights '''\n",
" return self.adj_matrix[i]\n",
" \n",
" def __random_asymmetric_graph(self,n, MAX_WEIGHT):\n",
" ''' Asymmetric adjacency matrix of size nxn '''\n",
" for i in range(n):\n",
" for j in range(n):\n",
" if i==j: continue # no self-loops\n",
" self.adj_matrix[i][j] = randint(1,MAX_WEIGHT)\n",
"\n",
" def __random_symmetric_graph(self,n,MAX_WEIGHT):\n",
" ''' Symmetric adjacency matrix of size nxn '''\n",
" for i in range(n):\n",
" for j in range(i+1,n):\n",
" w = randint(1,MAX_WEIGHT)\n",
" self.adj_matrix[i][j] = w\n",
" self.adj_matrix[j][i] = w\n",
"\n",
" def __random_cycle_graph(self,n):\n",
" ''' Symmetric adjacency matrix of size nxn with one reandomly chosen cycle\n",
" All the edge weights are 2 except for the cycle (weight=1) '''\n",
" self.adj_matrix = [[2 for _ in range(n)] for _ in range(n)] # All weights=2\n",
" # Select a random cycle which will have weight=1\n",
" cycle = list(range(1,n)) # don't include 0 as we want to be at the start\n",
" shuffle(cycle) # in-place random permutation\n",
" cycle = [0]+cycle+[0] # cycle starting and ending at 0\n",
" for a,b in zip(cycle, cycle[1:]): # set the cycle's weights to 1\n",
" self.adj_matrix[a][b] = 1\n",
" self.adj_matrix[b][a] = 1\n",
"\n",
" def __random_euclidean_graph(self,n,MAX_X,MAX_Y):\n",
" ''' Symmetric adjacency matrix of a Euclidean graph of size nxn '''\n",
" # (1/2) Generate random (x,y) points\n",
" points = set()\n",
" while len(points)<n: # We may get duplicate (x,y) so we try until we get enough points\n",
" x,y = randint(0,MAX_X), randint(0,MAX_Y)\n",
" points.add((x,y))\n",
" points = list(points) # Sets are not indexed, so convert into a list\n",
" # (2/2) Now compute the adjacency matrix\n",
" for i in range(n):\n",
" p1 = points[i]\n",
" for j in range(i+1,n):\n",
" p2 = points[j]\n",
" distance = sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)\n",
" self.adj_matrix[i][j] = distance\n",
" self.adj_matrix[j][i] = distance\n",
" self.points=points"
]
},
{
"cell_type": "code",
"execution_count": 75,
"metadata": {
"ExecuteTime": {
"end_time": "2022-10-25T11:38:31.846797Z",
"start_time": "2022-10-25T11:38:31.837802Z"
}
},
"outputs": [],
"source": [
"def cost(G, cycle):\n",
" ''' Calculate the cost of the given cycle [0,...,0] in G '''\n",
" return sum(G[a][b] for a,b in zip(cycle, cycle[1:]))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Functions to show the graphs as **adjacency matrices** or as a **drawing**:"
]
},
{
"cell_type": "code",
"execution_count": 76,
"metadata": {
"ExecuteTime": {
"end_time": "2022-10-25T11:38:31.879902Z",
"start_time": "2022-10-25T11:38:31.850793Z"
}
},
"outputs": [],
"source": [
"def show(G):\n",
" ''' Show adjacency matrix. Useful for debugging.\n",
" 'type' is a string from: Euclidean, Cycle, ...\n",
" The distances are round to 1 decimal point for clarity/simplicity\n",
" '''\n",
" print(f\"{G.n}x{G.n} {G.type} graph:\")\n",
" if G.type=='Euclidean': print(\"Points:\",G.points)\n",
" r = pd.DataFrame({str(i): G[i] for i in range(G.n)})\n",
" display(r)\n",
" \n",
"def nx_graph(G):\n",
" ''' Convert G into NetworkX format '''\n",
" nxG = nx.Graph() if G.type!='asymmetric' else nx.DiGraph() # undirected/directed graph\n",
" nxG.add_nodes_from(G.vertices) # Add the vertices\n",
" # Now add the edges\n",
" for a in G.vertices:\n",
" for b in G.vertices:\n",
" if a==b: continue # no self-loops\n",
" nxG.add_edge(a, b, weight=G[a][b]) \n",
" if G.type=='Euclidean': # add (x,y) coordinates if available\n",
" pos=dict(enumerate(G.points)) # vertex:(x,y) pairs\n",
" nx.set_node_attributes(nxG, pos, 'coord')\n",
" return nxG\n",
"\n",
"def draw(G):\n",
" ''' Draw the graph G using NetworkX '''\n",
" nxG = nx_graph(G)\n",
" weights_dictionary = nx.get_edge_attributes(nxG,'weight')\n",
" edges,weights = zip(*weights_dictionary.items())\n",
" pos = nx.circular_layout(nxG) if G.type!='Euclidean' else nx.get_node_attributes(nxG,'coord')\n",
" nx.draw(nxG, pos, \\\n",
" with_labels=True, node_color='red', font_color='white', font_weight='bold', font_size=14,\\\n",
" edge_color=weights, width=1.5, connectionstyle=\"arc3,rad=0.1\", edge_cmap=plt.cm.copper)\n",
" # see https://matplotlib.org/stable/gallery/color/colormap_reference.html\n",
" nx.draw_networkx_edge_labels(nxG, pos, edge_labels=weights_dictionary, label_pos=0.5 if G.type!=\"asymmetric\" else 0.25)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3) Nearest Neigbour Greedy method"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Idea\n",
"\n",
"Start at city 0, move to the nearest city, then from there to the next nearest city, and so on, until all cities are visited. Finally, return back to the start city."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Pseudocode\n",
"\n",
"1. $city \\gets 0$\n",
"2. $visited\\gets []$\n",
"3. **while** not all cities are visited **do**\n",
"4. $\\quad$ $nearest\\_city \\gets \\text{nearest city to $city$ that has not been visited yet}$\n",
"5. $\\quad$ Append $city$ to $visited$ $\\qquad\\qquad\\text{(i.e. mark $city$ as visited)}$\n",
"5. $\\quad$ $city\\gets nearest\\_city$\n",
"6. **end while**\n",
"8. **return** $visited$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Implementation"
]
},
{
"cell_type": "code",
"execution_count": 77,
"metadata": {
"ExecuteTime": {
"end_time": "2022-10-25T11:38:31.900873Z",
"start_time": "2022-10-25T11:38:31.879902Z"
}
},
"outputs": [],
"source": [
"def greedy_nearest_neighbour(G):\n",
" ''' Returns best found cycle and its cost '''\n",
" unvisited = G.vertices.copy()\n",
" visited = [] # solution to be built\n",
" city = 0 # Start city\n",
" while len(unvisited)>0:\n",
" # Find nearest neighbour\n",
" nearest_city = None\n",
" shortest_distance = oo\n",
" for neighbour in unvisited:\n",
" if G[city][neighbour] < shortest_distance:\n",
" shortest_distance = G[city][neighbour]\n",
" nearest_city = neighbour\n",
" # Update 'cycle' and 'cities' and G then 'city'\n",
" visited.append(city)\n",
" unvisited.remove(city)\n",
" city = nearest_city\n",
" return (visited, cost(G, visited+[0]))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Ant Colony Optimisation (ACO)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Idea\n",
"starting at city 0, send ants on all available paths while also leaving pheomeone data. repeat this multiple times to find the route with the more pheomeone as this would be the shortest path for the ant to finish.\n",
"\n",
"Pseudocode:\n",
"1. city <- 0\n",
"2. visited <- $[]$\n",
"3. **while** not_termination **do**\n",
"4. $\\quad$ generateSolutions()\n",
"5. $\\quad$ daemonActions()\n",
"6. $\\quad$ pheromoneUpdate()\n",
"7. **repeat**\n",
"8. visited <- highest pheromone edges\n",
"9. **return** visited\n",
"\n",
"*adapted by Taylor Ring from https://towardsdatascience.com/the-inspiration-of-an-ant-colony-optimization-f377568ea03f*"
]
},
{
"cell_type": "code",
"execution_count": 83,
"metadata": {},
"outputs": [],
"source": [
"from sko.ACA import ACA_TSP\n",
"import numpy as np\n",
"\n",
"curr_distance_matrix = [[]]\n",
"curr_num_of_cities = 0\n",
"\n",
"# code adapted by Taylor Ring from https://github.com/guofei9987/scikit-opt/blob/master/examples/demo_aca_tsp.py#L17\n",
"def cal_total_distance(routine):\n",
" ''' Calculates the total distance of the Ants journey'''\n",
" num_points, = routine.shape\n",
" #print(num_points)\n",
" return sum([curr_distance_matrix[routine[i% curr_num_of_cities]][routine[(i+1) % curr_num_of_cities]] for i in range(curr_num_of_cities)])\n",
"\n",
"def Ant_Colony_Optimisation(G, iter_num = 200, ant_pop = 50):\n",
" ''' Performs ACO in a function'''\n",
" global curr_distance_matrix\n",
" global curr_num_of_cities\n",
" \n",
" curr_distance_matrix = G.adj_matrix\n",
" curr_num_of_cities = G.n\n",
" \n",
" aca = ACA_TSP(func = cal_total_distance, n_dim = curr_num_of_cities, size_pop = ant_pop, max_iter = iter_num, distance_matrix=curr_distance_matrix)\n",
" best_x, best_y = aca.run()\n",
" \n",
" return best_x, best_y, aca \n",
"\n",
"\n",
"graph_list = [Graph(50),Graph(100),Graph(150),Graph(200),Graph(250),Graph(300)] # all asymmetric\n",
" \n",
"type_list = [graph_list[1],Graph(100, type=\"symmetric\"),Graph(100, type=\"euclidean\")]\n",
"\n",
"def city_Test():\n",
" ''' A test to measure the GNN with ACO on number of cities'''\n",
" print(\"CITY TEST\")\n",
" for g in graph_list:\n",
" \n",
" best_x, best_y, aca = Ant_Colony_Optimisation(g)\n",
" \n",
" gnVisited, gnCost = greedy_nearest_neighbour(g)\n",
" \n",
" print(\"for \"+ str(g.n) + \" cities: \")\n",
" print(\"ACO\")\n",
" #print(best_x)\n",
" print(\" cost-> \"+ str(best_y))\n",
" print(\"\")\n",
" \n",
" print(\"GNN\")\n",
" #print(gnVisited)\n",
" print(\" cost-> \" + str(gnCost))\n",
" print(\"\")\n",
" print(\"\")\n",
" \n",
"def type_Test():\n",
" ''' A test between GNN and ACO on the type of graph to transverse'''\n",
" print(\"TYPE TEST\")\n",
" for g in type_list:\n",
" \n",
" best_x, best_y, aca = Ant_Colony_Optimisation(g)\n",
" gnVisited, gnCost = greedy_nearest_neighbour(g)\n",
" \n",
" print(\"for \"+ str(g.n) + \" cities and type-> \"+g.type+\": \")\n",
" print(\"ACO\")\n",
" #print(best_x)\n",
" print(\" cost-> \"+ str(best_y))\n",
" print(\"\")\n",
" \n",
" print(\"GNN\")\n",
" #print(gnVisited)\n",
" print(\" cost-> \" + str(gnCost))\n",
" print(\"\")\n",
" print(\"\")\n",
" \n",
"def iter_Test():\n",
" '''A ACO test on the number of iterations to see if the solution improves'''\n",
" print(\"ITERATION TEST\")\n",
" for i in range(50,500,50):\n",
" \n",
" best_x, best_y, aca = Ant_Colony_Optimisation(graph_list[0],iter_num = i)\n",
" \n",
" print(\"for \"+ str(g.n) + \" cities and iter-> \"+str(i)+\": \")\n",
" print(\"ACO\")\n",
" #print(best_x)\n",
" print(\" cost-> \"+ str(best_y))\n",
" print(\"\")\n",
" \n",
"def pop_Test():\n",
" '''A ACO test to measure how size population will affect the final result'''\n",
" print(\"POPULATION TEST\")\n",
" for i in range(50,300,50):\n",
" \n",
" best_x, best_y, aca = Ant_Colony_Optimisation(graph_list[0],ant_pop = i)\n",
" \n",
" print(\"for \"+ str(g.n) + \" cities and ant population-> \"+str(i)+\": \")\n",
" print(\"ACO\")\n",
" #print(best_x)\n",
" print(\" cost-> \"+ str(best_y))\n",
" print(\"\") "
]
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CITY TEST\n",
"for 50 cities: \n",
"ACO\n",
" cost-> 254\n",
"\n",
"GNN\n",
" cost-> 350\n",
"\n",
"\n",
"for 100 cities: \n",
"ACO\n",
" cost-> 325\n",
"\n",
"GNN\n",
" cost-> 441\n",
"\n",
"\n",
"for 150 cities: \n",
"ACO\n",
" cost-> 337\n",
"\n",
"GNN\n",
" cost-> 516\n",
"\n",
"\n",
"for 200 cities: \n",
"ACO\n",
" cost-> 416\n",
"\n",
"GNN\n",
" cost-> 493\n",
"\n",
"\n",
"for 250 cities: \n",
"ACO\n",
" cost-> 497\n",
"\n",
"GNN\n",
" cost-> 725\n",
"\n",
"\n",
"for 300 cities: \n",
"ACO\n",
" cost-> 511\n",
"\n",
"GNN\n",
" cost-> 732\n",
"\n",
"\n"
]
}
],
"source": [
"city_Test()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## City test conclusion\n",
"from the results above with the cities incremented by 50, it is clear that the ACO algorithm has reduced the cost that the GNN has offered. What's also interesting to note is how there is a sudden increase of cost between 200 and 250 cities for GNN but ACO gradually increases."
]
},
{
"cell_type": "code",
"execution_count": 81,
"metadata": {
"scrolled": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"TYPE TEST\n",
"for 100 cities and type-> asymmetric: \n",
"ACO\n",
" cost-> 302\n",
"\n",
"GNN\n",
" cost-> 441\n",
"\n",
"\n",
"for 100 cities and type-> symmetric: \n",
"ACO\n",
" cost-> 349\n",
"\n",
"GNN\n",
" cost-> 489\n",
"\n",
"\n",
"for 100 cities and type-> euclidean: \n",
"ACO\n",
" cost-> 263\n",
"\n",
"GNN\n",
" cost-> 418\n",
"\n",
"\n"
]
}
],
"source": [
"type_Test()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Type test conclusion\n",
"The type test was to look how both algorithms react when the data is different, whether the data is symmetrical or based on position. From the looks of the results, ACO managed to find a smaller cost for all three. What is interesting is that a symmetric problem costs more in general than a asymmetric problem."
]
},
{
"cell_type": "code",
"execution_count": 82,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"ITERATION TEST\n",
"for 10 cities and iter-> 50: \n",
"ACO\n",
" cost-> 264\n",
"\n",
"for 10 cities and iter-> 100: \n",
"ACO\n",
" cost-> 259\n",
"\n",
"for 10 cities and iter-> 150: \n",
"ACO\n",
" cost-> 247\n",
"\n",
"for 10 cities and iter-> 200: \n",
"ACO\n",
" cost-> 239\n",
"\n",
"for 10 cities and iter-> 250: \n",
"ACO\n",
" cost-> 231\n",
"\n",
"for 10 cities and iter-> 300: \n",
"ACO\n",
" cost-> 235\n",
"\n",
"for 10 cities and iter-> 350: \n",
"ACO\n",
" cost-> 245\n",
"\n",
"for 10 cities and iter-> 400: \n",
"ACO\n",
" cost-> 241\n",
"\n",
"for 10 cities and iter-> 450: \n",
"ACO\n",
" cost-> 257\n",
"\n"
]
}
],
"source": [
"iter_Test()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Iteration test conclusion\n",
"This test was purely on the ACO and how it performs if the amount of iterations increases by 50. From the looks of the data, as the iterations increases, the cost to visit all 10 cities decreases. However, what is evident is that after a certain amount, the iteration amount causes the cost to increase. This means that with a city, there is an number of iterations for it to perform optimally before it damages the cost. "
]
},
{
"cell_type": "code",
"execution_count": 84,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"POPULATION TEST\n",
"for 10 cities and ant population-> 50: \n",
"ACO\n",
" cost-> 271\n",
"\n",
"for 10 cities and ant population-> 100: \n",
"ACO\n",
" cost-> 244\n",
"\n",
"for 10 cities and ant population-> 150: \n",
"ACO\n",
" cost-> 233\n",
"\n",
"for 10 cities and ant population-> 200: \n",
"ACO\n",
" cost-> 256\n",
"\n",
"for 10 cities and ant population-> 250: \n",
"ACO\n",
" cost-> 255\n",
"\n"
]
}
],
"source": [
"pop_Test()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Population test conclusion\n",
"The population test looks into how the number of ants into the algorithm can adjust the cost and effectiveness of the algorithm. From the data above, the more ants in the algorithm would cause the cost to decrease. However, as with the iterations, there is an optimal amount of ants that the algorithm can have before the cost starts to increase. This might be due to overfitting which causes the accuracy and cost to reduce."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Conclusion"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Each of the tests demostrate the differences between Greedy Nearest Neighbour and Ant Colony Optimisation. Additional tests were done for ACO to demostrate how it's hyperparameters can influence it's performances. Overall, ACO has performed GNN at each test and set. ACO can be further improved when the iterations and size population increases. However, there is a limit to both on how much they improve ACO before it increases the cost of the data.\n",
"\n",
"Not included was the time taken to complete each test and specifically each run. While it would be useful to measure the time difference between them, its clear how the time is performed on two observations: Greedy takes the smallest, non-marked value and repeats until all cities have been visited. ACO sends ants out and use the concept of phonemones with iterations to discover the best possible route. GNN will most likely take less time than ACO. Another observation is that with more ants and iterations, more data is evaluated and thus would increase the time taken as well.\n",
"\n",
"If there was additional time on the coursework, then more factors would be explored. This includes time measurements, combining hyperparemeters, and producing graphs and plots to show visually how each algorithm moves."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# List of references"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"https://towardsdatascience.com/the-inspiration-of-an-ant-colony-optimization-f377568ea03f - Providing the initial pseudocode for ACO (with slight adaptations)\n",
"\n",
"https://scikit-opt.github.io/scikit-opt/#/en/README?id=_5-aca-ant-colony-algorithm-for-tsp - Initial setup for ACO"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.12"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": false,
"sideBar": true,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": false
},
"vscode": {
"interpreter": {
"hash": "6d1e45cadc3597bb8b6600530fbdf8c3eefe919a24ef54d9d32b318795b772e0"
}
}
},
"nbformat": 4,
"nbformat_minor": 4
}