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)

name	timestamp in video	# nodes
data/video-50.csv	1:17	50
data/video-30.csv	3:14	30
data/video-04.csv	8:57	4
data/video-10.csv	11:25	10
data/video-06.csv	14:54	6
data/video-66.csv	17:44	66

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)

6

# 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)

np.float64(411.3587242298381)

# what it says

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

np.float64(1546.8219089013558)

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()

Error: Layout type: "neato" not recognized. Use one of: dot
Error: Layout was not done.  Missing layout plugins?

---------------------------------------------------------------------------
CalledProcessError                        Traceback (most recent call last)
File /__w/exos-python/exos-python/venv/lib/python3.14/site-packages/graphviz/backend/execute.py:88, in run_check(cmd, input_lines, encoding, quiet, **kwargs)
     87 try:
---> 88     proc.check_returncode()
     89 except subprocess.CalledProcessError as e:

File /usr/lib/python3.14/subprocess.py:509, in CompletedProcess.check_returncode(self)
    508 if self.returncode:
--> 509     raise CalledProcessError(self.returncode, self.args, self.stdout,
    510                              self.stderr)

CalledProcessError: Command '[PosixPath('dot'), '-Kdot', '-Tsvg']' returned non-zero exit status 1.

During handling of the above exception, another exception occurred:

CalledProcessError                        Traceback (most recent call last)
File /__w/exos-python/exos-python/venv/lib/python3.14/site-packages/graphviz/jupyter_integration.py:98, in JupyterIntegration._repr_mimebundle_(self, include, exclude, **_)
     96 include = set(include) if include is not None else {self._jupyter_mimetype}
     97 include -= set(exclude or [])
---> 98 return {mimetype: getattr(self, method_name)()
     99         for mimetype, method_name in MIME_TYPES.items()
    100         if mimetype in include}

File /__w/exos-python/exos-python/venv/lib/python3.14/site-packages/graphviz/jupyter_integration.py:112, in JupyterIntegration._repr_image_svg_xml(self)
    110 def _repr_image_svg_xml(self) -> str:
    111     """Return the rendered graph as SVG string."""
--> 112     return self.pipe(format='svg', encoding=SVG_ENCODING)

File /__w/exos-python/exos-python/venv/lib/python3.14/site-packages/graphviz/piping.py:104, in Pipe.pipe(self, format, renderer, formatter, neato_no_op, quiet, engine, encoding)
     55 def pipe(self,
     56          format: typing.Optional[str] = None,
     57          renderer: typing.Optional[str] = None,
   (...)     61          engine: typing.Optional[str] = None,
     62          encoding: typing.Optional[str] = None) -> typing.Union[bytes, str]:
     63     """Return the source piped through the Graphviz layout command.
     64 
     65     Args:
   (...)    102         '<?xml version='
    103     """
--> 104     return self._pipe_legacy(format,
    105                              renderer=renderer,
    106                              formatter=formatter,
    107                              neato_no_op=neato_no_op,
    108                              quiet=quiet,
    109                              engine=engine,
    110                              encoding=encoding)

File /__w/exos-python/exos-python/venv/lib/python3.14/site-packages/graphviz/_tools.py:185, in deprecate_positional_args.<locals>.decorator.<locals>.wrapper(*args, **kwargs)
    177     wanted = ', '.join(f'{name}={value!r}'
    178                        for name, value in deprecated.items())
    179     warnings.warn(f'The signature of {func_name} will be reduced'
    180                   f' to {supported_number} positional arg{s_}{qualification}'
    181                   f' {list(supported)}: pass {wanted} as keyword arg{s_}',
    182                   stacklevel=stacklevel,
    183                   category=category)
--> 185 return func(*args, **kwargs)

File /__w/exos-python/exos-python/venv/lib/python3.14/site-packages/graphviz/piping.py:121, in Pipe._pipe_legacy(self, format, renderer, formatter, neato_no_op, quiet, engine, encoding)
    112 @_tools.deprecate_positional_args(supported_number=1, ignore_arg='self')
    113 def _pipe_legacy(self,
    114                  format: typing.Optional[str] = None,
   (...)    119                  engine: typing.Optional[str] = None,
    120                  encoding: typing.Optional[str] = None) -> typing.Union[bytes, str]:
--> 121     return self._pipe_future(format,
    122                              renderer=renderer,
    123                              formatter=formatter,
    124                              neato_no_op=neato_no_op,
    125                              quiet=quiet,
    126                              engine=engine,
    127                              encoding=encoding)

File /__w/exos-python/exos-python/venv/lib/python3.14/site-packages/graphviz/piping.py:149, in Pipe._pipe_future(self, format, renderer, formatter, neato_no_op, quiet, engine, encoding)
    146 if encoding is not None:
    147     if codecs.lookup(encoding) is codecs.lookup(self.encoding):
    148         # common case: both stdin and stdout need the same encoding
--> 149         return self._pipe_lines_string(*args, encoding=encoding, **kwargs)
    150     try:
    151         raw = self._pipe_lines(*args, input_encoding=self.encoding, **kwargs)

File /__w/exos-python/exos-python/venv/lib/python3.14/site-packages/graphviz/backend/piping.py:212, in pipe_lines_string(engine, format, input_lines, encoding, renderer, formatter, neato_no_op, quiet)
    206 cmd = dot_command.command(engine, format,
    207                           renderer=renderer,
    208                           formatter=formatter,
    209                           neato_no_op=neato_no_op)
    210 kwargs = {'input_lines': input_lines, 'encoding': encoding}
--> 212 proc = execute.run_check(cmd, capture_output=True, quiet=quiet, **kwargs)
    213 return proc.stdout

File /__w/exos-python/exos-python/venv/lib/python3.14/site-packages/graphviz/backend/execute.py:90, in run_check(cmd, input_lines, encoding, quiet, **kwargs)
     88     proc.check_returncode()
     89 except subprocess.CalledProcessError as e:
---> 90     raise CalledProcessError(*e.args)
     92 return proc

CalledProcessError: Command '[PosixPath('dot'), '-Kdot', '-Tsvg']' returned non-zero exit status 1. [stderr: 'Error: Layout type: "neato" not recognized. Use one of: dot\nError: Layout was not done.  Missing layout plugins? \n']

<graphviz.graphs.Graph at 0x7fa51d9bcd70>

# 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

ants: a genetic algorithm

problem statement¶

traveling salesman¶

ants colony problem¶

ACO: a super useful resource¶

useful data¶

data/*.csv¶

data/*.path¶

problem.py¶

displaying the graphs¶

if you prefer plotly¶

ui.py¶

`data/*.csv`¶

`data/*.path`¶

`ui.py`¶