#+TITLE: Solving the Traveling Salesman Problem using Self-Organizing Maps
#+AUTHOR: Diego Vicente Martín
#+EMAIL: mail@diego.codes
This repository contains an implementation of a Self Organizing Map that can be
used to find sub-optimal solutions for the Traveling Salesman Problem. The
instances of the problems that the program supports are =.tsp= files, which is
a widespread format in this problem. All the source code can be found in the
=src= directory, while a report and brief presentation slides (in Spanish) can
be found in the =report= folder. However, for a complete read on the topic, you
can read [[https://diego.codes/post/som-tsp/][my blog post explaining this implementation and its evaluation]].
To run the code, only Python 3 and the dependencies (=matplotlib=, =numpy= and =pandas=,
which are included in the Anaconda distribution by default) are needed. In case
you are not using Anaconda, you can install all the dependencies with:
#+BEGIN_SRC sh
pip install -r requirements.txt
#+END_SRC
To run the code, simply execute:
#+BEGIN_SRC sh
cd som-tsp
python src/main.py assets/.tsp
#+END_SRC
The images generated will be stored in the =diagrams= folder. Using a tool like
=convert=, you can easily generate an animation like the one in this file by
running:
#+BEGIN_SRC sh
convert -delay 10 -loop 0 *.png animation.gif
#+END_SRC
This code is licensed under MIT License, so feel free to modify and/or use it
in your projects. If you have any doubts, feel free to contact me or contribute
to this repository by creating an issue.
This code was presented for the Bio-Inspired Artificial Intelligence course in
the Computer Science & Technology master's degree @ UC3M. A previous version of
this code can be found in [[https://github.com/DiegoVicen/ntnu-som][this repository]]. Special thanks to [[https://github.com/leo-labs][Leonard Kleinans]],
who worked with me in that previous version.