Skip to content
Permalink
main
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
553 lines (553 sloc) 24.5 KB
Raw Blame
Open in GitHub Desktop
{
"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": 249,
"metadata": {
"ExecuteTime": {
"end_time": "2022-10-25T11:38:31.774523Z",
"start_time": "2022-10-25T11:38:23.464728Z"
}
},
"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": 250,
"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": 251,
"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": 252,
"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": 253,
"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": "code",
"execution_count": 254,
"outputs": [],
"source": [
"from sko.ACA import ACA_TSP\n",
"import numpy as np\n",
"def aco_tsp(G):\n",
" distanceMatrix = np.array(G.adj_matrix)\n",
"\n",
" def cal_total_distance(routine):\n",
" num_points = G.n\n",
" return sum([distanceMatrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])\n",
"\n",
" aca = ACA_TSP(func = cal_total_distance, n_dim=G.n,\n",
" size_pop=50, max_iter=100,\n",
" distance_matrix=distanceMatrix)\n",
"\n",
" best_path, best_cost = aca.run()\n",
"\n",
" return best_path, best_cost"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "code",
"execution_count": 255,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"---\n",
"n=50\n",
"Euclidean - ACO Cost:245.0 - GreedyNN Cost: 467\n"
]
},
{
"ename": "KeyboardInterrupt",
"evalue": "",
"output_type": "error",
"traceback": [
"\u001B[1;31m---------------------------------------------------------------------------\u001B[0m",
"\u001B[1;31mKeyboardInterrupt\u001B[0m Traceback (most recent call last)",
"Cell \u001B[1;32mIn [255], line 11\u001B[0m\n\u001B[0;32m 8\u001B[0m \u001B[38;5;28mprint\u001B[39m(\u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mEuclidean\u001B[39m\u001B[38;5;124m\"\u001B[39m \u001B[38;5;241m+\u001B[39m \u001B[38;5;124m\"\u001B[39m\u001B[38;5;124m - \u001B[39m\u001B[38;5;124m\"\u001B[39m \u001B[38;5;241m+\u001B[39m \u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mACO Cost:\u001B[39m\u001B[38;5;124m\"\u001B[39m \u001B[38;5;241m+\u001B[39m \u001B[38;5;28mstr\u001B[39m(acoResult[\u001B[38;5;241m1\u001B[39m]) \u001B[38;5;241m+\u001B[39m \u001B[38;5;124m\"\u001B[39m\u001B[38;5;124m - \u001B[39m\u001B[38;5;124m\"\u001B[39m \u001B[38;5;241m+\u001B[39m \u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mGreedyNN Cost: \u001B[39m\u001B[38;5;124m\"\u001B[39m \u001B[38;5;241m+\u001B[39m \u001B[38;5;28mstr\u001B[39m(greedyResult[\u001B[38;5;241m1\u001B[39m]))\n\u001B[0;32m 10\u001B[0m graph \u001B[38;5;241m=\u001B[39m Graph(n, \u001B[38;5;28mtype\u001B[39m\u001B[38;5;241m=\u001B[39m \u001B[38;5;124m'\u001B[39m\u001B[38;5;124msymmetric\u001B[39m\u001B[38;5;124m'\u001B[39m)\n\u001B[1;32m---> 11\u001B[0m acoResult \u001B[38;5;241m=\u001B[39m \u001B[43maco_tsp\u001B[49m\u001B[43m(\u001B[49m\u001B[43mgraph\u001B[49m\u001B[43m)\u001B[49m\n\u001B[0;32m 12\u001B[0m greedyResult \u001B[38;5;241m=\u001B[39m greedy_nearest_neighbour(graph)\n\u001B[0;32m 13\u001B[0m \u001B[38;5;28mprint\u001B[39m(\u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mSymmetric\u001B[39m\u001B[38;5;124m\"\u001B[39m \u001B[38;5;241m+\u001B[39m \u001B[38;5;124m\"\u001B[39m\u001B[38;5;124m - \u001B[39m\u001B[38;5;124m\"\u001B[39m \u001B[38;5;241m+\u001B[39m \u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mACO Cost:\u001B[39m\u001B[38;5;124m\"\u001B[39m \u001B[38;5;241m+\u001B[39m \u001B[38;5;28mstr\u001B[39m(acoResult[\u001B[38;5;241m1\u001B[39m]) \u001B[38;5;241m+\u001B[39m \u001B[38;5;124m\"\u001B[39m\u001B[38;5;124m - \u001B[39m\u001B[38;5;124m\"\u001B[39m \u001B[38;5;241m+\u001B[39m \u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mGreedyNN Cost: \u001B[39m\u001B[38;5;124m\"\u001B[39m \u001B[38;5;241m+\u001B[39m \u001B[38;5;28mstr\u001B[39m(greedyResult[\u001B[38;5;241m1\u001B[39m]))\n",
"Cell \u001B[1;32mIn [254], line 14\u001B[0m, in \u001B[0;36maco_tsp\u001B[1;34m(G)\u001B[0m\n\u001B[0;32m 8\u001B[0m \u001B[38;5;28;01mreturn\u001B[39;00m \u001B[38;5;28msum\u001B[39m([distanceMatrix[routine[i \u001B[38;5;241m%\u001B[39m num_points], routine[(i \u001B[38;5;241m+\u001B[39m \u001B[38;5;241m1\u001B[39m) \u001B[38;5;241m%\u001B[39m num_points]] \u001B[38;5;28;01mfor\u001B[39;00m i \u001B[38;5;129;01min\u001B[39;00m \u001B[38;5;28mrange\u001B[39m(num_points)])\n\u001B[0;32m 10\u001B[0m aca \u001B[38;5;241m=\u001B[39m ACA_TSP(func \u001B[38;5;241m=\u001B[39m cal_total_distance, n_dim\u001B[38;5;241m=\u001B[39mG\u001B[38;5;241m.\u001B[39mn,\n\u001B[0;32m 11\u001B[0m size_pop\u001B[38;5;241m=\u001B[39m\u001B[38;5;241m50\u001B[39m, max_iter\u001B[38;5;241m=\u001B[39m\u001B[38;5;241m100\u001B[39m,\n\u001B[0;32m 12\u001B[0m distance_matrix\u001B[38;5;241m=\u001B[39mdistanceMatrix)\n\u001B[1;32m---> 14\u001B[0m best_path, best_cost \u001B[38;5;241m=\u001B[39m \u001B[43maca\u001B[49m\u001B[38;5;241;43m.\u001B[39;49m\u001B[43mrun\u001B[49m\u001B[43m(\u001B[49m\u001B[43m)\u001B[49m\n\u001B[0;32m 16\u001B[0m \u001B[38;5;28;01mreturn\u001B[39;00m best_path, best_cost\n",
"File \u001B[1;32m~\\AppData\\Local\\Programs\\Python\\Python310\\lib\\site-packages\\sko\\ACA.py:42\u001B[0m, in \u001B[0;36mACA_TSP.run\u001B[1;34m(self, max_iter)\u001B[0m\n\u001B[0;32m 40\u001B[0m prob \u001B[38;5;241m=\u001B[39m prob_matrix[\u001B[38;5;28mself\u001B[39m\u001B[38;5;241m.\u001B[39mTable[j, k], allow_list]\n\u001B[0;32m 41\u001B[0m prob \u001B[38;5;241m=\u001B[39m prob \u001B[38;5;241m/\u001B[39m prob\u001B[38;5;241m.\u001B[39msum() \u001B[38;5;66;03m# 概率归一化\u001B[39;00m\n\u001B[1;32m---> 42\u001B[0m next_point \u001B[38;5;241m=\u001B[39m \u001B[43mnp\u001B[49m\u001B[38;5;241;43m.\u001B[39;49m\u001B[43mrandom\u001B[49m\u001B[38;5;241;43m.\u001B[39;49m\u001B[43mchoice\u001B[49m\u001B[43m(\u001B[49m\u001B[43mallow_list\u001B[49m\u001B[43m,\u001B[49m\u001B[43m \u001B[49m\u001B[43msize\u001B[49m\u001B[38;5;241;43m=\u001B[39;49m\u001B[38;5;241;43m1\u001B[39;49m\u001B[43m,\u001B[49m\u001B[43m \u001B[49m\u001B[43mp\u001B[49m\u001B[38;5;241;43m=\u001B[39;49m\u001B[43mprob\u001B[49m\u001B[43m)\u001B[49m[\u001B[38;5;241m0\u001B[39m]\n\u001B[0;32m 43\u001B[0m \u001B[38;5;28mself\u001B[39m\u001B[38;5;241m.\u001B[39mTable[j, k \u001B[38;5;241m+\u001B[39m \u001B[38;5;241m1\u001B[39m] \u001B[38;5;241m=\u001B[39m next_point\n\u001B[0;32m 45\u001B[0m \u001B[38;5;66;03m# 计算距离\u001B[39;00m\n",
"\u001B[1;31mKeyboardInterrupt\u001B[0m: "
]
}
],
"source": [
"for n in range(50, 301, 50):\n",
" print(\"---\")\n",
" print(\"n=\" + str(n))\n",
"\n",
" graph = Graph(n, type= 'euclidean')\n",
" acoResult = aco_tsp(graph)\n",
" greedyResult = greedy_nearest_neighbour(graph)\n",
" print(\"Euclidean\" + \" - \" + \"ACO Cost:\" + str(acoResult[1]) + \" - \" + \"GreedyNN Cost: \" + str(greedyResult[1]))\n",
"\n",
" graph = Graph(n, type= 'symmetric')\n",
" acoResult = aco_tsp(graph)\n",
" greedyResult = greedy_nearest_neighbour(graph)\n",
" print(\"Symmetric\" + \" - \" + \"ACO Cost:\" + str(acoResult[1]) + \" - \" + \"GreedyNN Cost: \" + str(greedyResult[1]))\n",
"\n",
" graph = Graph(n, type= 'asymmetric')\n",
" acoResult = aco_tsp(graph)\n",
" greedyResult = greedy_nearest_neighbour(graph)\n",
" print(\"Asymmetric\" + \" - \" + \"ACO Cost:\" + str(acoResult[1]) + \" - \" + \"GreedyNN Cost: \" + str(greedyResult[1]))\n",
"\n"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Conclusion"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"```\n",
"Below are the results comnparing the outputs of the Nearest Neighbour algorithm and the Ant Colony Optimization for various graph sizes and topologies:\n",
"\n",
"n=50\n",
"Euclidean - ACO Cost:227.0 - GreedyNN Cost: 463\n",
"Symmetric - ACO Cost:252.0 - GreedyNN Cost: 436\n",
"Asymmetric - ACO Cost:243.0 - GreedyNN Cost: 382\n",
"---\n",
"n=100\n",
"Euclidean - ACO Cost:296.0 - GreedyNN Cost: 646\n",
"Symmetric - ACO Cost:368.0 - GreedyNN Cost: 544\n",
"Asymmetric - ACO Cost:284.0 - GreedyNN Cost: 480\n",
"---\n",
"n=150\n",
"Euclidean - ACO Cost:358.0 - GreedyNN Cost: 574\n",
"Symmetric - ACO Cost:364.0 - GreedyNN Cost: 544\n",
"Asymmetric - ACO Cost:387.0 - GreedyNN Cost: 547\n",
"---\n",
"n=200\n",
"Euclidean - ACO Cost:395.0 - GreedyNN Cost: 655\n",
"Symmetric - ACO Cost:394.0 - GreedyNN Cost: 626\n",
"Asymmetric - ACO Cost:405.0 - GreedyNN Cost: 606\n",
"---\n",
"n=250\n",
"Euclidean - ACO Cost:460.0 - GreedyNN Cost: 613\n",
"Symmetric - ACO Cost:450.0 - GreedyNN Cost: 685\n",
"Asymmetric - ACO Cost:457.0 - GreedyNN Cost: 733\n",
"---\n",
"n=300\n",
"Euclidean - ACO Cost:534.0 - GreedyNN Cost: 809\n",
"Symmetric - ACO Cost:545.0 - GreedyNN Cost: 839\n",
"Asymmetric - ACO Cost:561.0 - GreedyNN Cost: 853\n",
"```"
]
},
{
"cell_type": "markdown",
"source": [
"\n",
"We can see that for all topologies and graph sizes, the cost calculated by the ACO is considerably lower. However, it seems that the difference between the 2 algorithms slightly decreases as the amount of cities in the graph increase.\n",
"\n",
"Below are the hyperparameters of the ACO implementations and their effect on time and quality:\n",
"-size_pop: This is the population size and equates to the amount of ants exploring the graph. Increasing the amount improves the quality of results (more ants = shorter path found) but also greatly increases computation time (more ants = more time needed).\n",
"-max_iter: This is the amount of iterations that the program will do to try and find a better solution to our problem. As with the size population, the greater this value, the longer the computation time (as the program does more runs of the algorithm) and the higher the quality of the results. However, from testing, this value seems to have a lower impact on quality and a higher impact on run time.\n",
"\n",
"From our testing, we can theorize that it is more efficient to have a higher amount of ants and a lower amount of iterations. However, we can't prove this as all results are randomised due to our randomised paths. An implementation of evolutionary computing (genetic algorithms) could be used to find the most efficient values of size_pop and max_inter.\n"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# List of references"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"```\n",
"- Scikit Opt. (2022). ACA (Ant Colony Algorithm) for tsp. https://scikit-opt.github.io/scikit-opt/#/en/README?id=_5-aca-ant-colony-algorithm-for-tsp\n",
"- Hsin-Ching Chih. (2020). Ant colony optimization in the travel salesman problem (TSP). https://www.researchgate.net/publication/339375844_Ant_colony_optimization_in_the_travel_salesman_problem_TSP\n",
"- AntColony.jl. (2022). Best hyperparameters? https://docs.juliahub.com/AntColony/yo67k/0.1.1/\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"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.8.3"
},
"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
}