ants: a genetic algorithm

problem statement¶

our goal in this activity is to implement an optimization algorithm that is an example of a genetic algorithm
it turns out this algorithm can solve two equivalent problems

traveling salesman¶

specifically, we consider a famous problem, which is of great importance for everything logistics, and is known as the “traveling salesman” problem
consider for example a truck that needs to deliver parcels in several locations
the problem is to find the shortest path (or more accurately, a reasonably short path)

• that starts from the warehouse

• goes through all the locations

• and returns to the warehouse

ants colony problem¶

the traveling salesman problem is in fact equivalent to the one known as the the “ants colony” problem, where the colony needs to find the best route from the ant hill and back, that goes through the spots where food has been found

this latter metaphor is a little more helpful though in the context of the genetic algorithm, because the algorithm indeed mimicks the existence of several ants that concurrently walk the graph, and leave pheromons to keep track of the past

ACO: a super useful resource¶

the YouTube video below gives a 20’ introduction on the algorithm known as Ants Colony Optimization (ACO), and explains essentially all the logic and formulas needed to implement it

so it is a highly recommended resource to get started with the details of the algorithm

useful data¶

in the zip file you will find:

data/*.csv¶

we provide a few datafiles in the data/ folder, made from some graphs that appear in the video
these use a simple csv format that should be self explanatory (just forget the radius column)

plus for convenience some polygon-like shapes in poly*.csv

data/*.path¶

here we provide the results found by our own implementation; this in particular is used by the ‘Cheat’ button in ui.py - see below

problem.py¶

also provided in the zip, you can use problem.py like so:

from problem import Problem2D

problem = Problem2D("data/video-06.csv")

# how many nodes
len(problem)

# to iterate over nodes

for node in problem:
    print(node)

Problem2D.Node(name='b', x=627, y=146)
Problem2D.Node(name='a', x=50, y=142)
Problem2D.Node(name=' ', x=227, y=50)
Problem2D.Node(name=' ', x=106, y=255)
Problem2D.Node(name=' ', x=213, y=189)
Problem2D.Node(name=' ', x=125, y=83)

# or rather

for index, node in enumerate(problem):
    print(f"{index}-th node is {node}")

0-th node is Problem2D.Node(name='b', x=627, y=146)
1-th node is Problem2D.Node(name='a', x=50, y=142)
2-th node is Problem2D.Node(name=' ', x=227, y=50)
3-th node is Problem2D.Node(name=' ', x=106, y=255)
4-th node is Problem2D.Node(name=' ', x=213, y=189)
5-th node is Problem2D.Node(name=' ', x=125, y=83)

# get distance between 2 nodes

problem.distance(0, 2)

# what it says

problem.distance_along_path([0, 1, 2, 3, 0])

displaying the graphs¶

we’ve also coded some display featured for your convenience

1st off, provided that you have graphviz installed

# you can do display it with graphviz like this

problem.to_graphviz()

# or this if you prefer

problem.to_graphviz(show_distances=False)

if you prefer plotly¶

and there again, provided that you have plotly installed you could do

import plotly.io as pio

# Try one of these depending on your setup:
pio.renderers.default = "notebook"     # for classic Jupyter Notebook

problem.to_plotly()

ui.py¶

might come in handy too, it is a simple flet UI that lets you visualize your work; you might consider

• reading its code

• make sure your solver.py code fits the expected interface - or tweak ui.py according to your own interface

• run it with

flet run -d ui.py

so that the UI will hot reload upon any change you make in solver.py