• Stars
    star
    3,654
  • Rank 12,105 (Top 0.3 %)
  • Language
    Python
  • License
    MIT License
  • Created about 7 years ago
  • Updated 11 months ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Solving the Traveling Salesman Problem using Self-Organizing Maps

Solving the Traveling Salesman Problem using Self-Organizing Maps

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 my blog post explaining this implementation and its evaluation.

diagrams/uruguay.gif

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:

pip install -r requirements.txt

To run the code, simply execute:

cd som-tsp
python src/main.py assets/<instance>.tsp

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:

convert -delay 10 -loop 0 *.png animation.gif

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 this repository. Special thanks to Leonard Kleinans, who worked with me in that previous version.

More Repositories

1

ntnu-som

Using Self-Organizing Maps for Travelling Salesman Problem
Python
42
star
2

dvm-emacs

My Emacs configuration
Emacs Lisp
36
star
3

dandelion

Rhyme detection in Python
Python
20
star
4

dotfiles

A compilation of all my everyday tool configurations, along with some installation scripts
Shell
12
star
5

org-css

An org-mode compatible stylesheet
CSS
12
star
6

gpu-python3-kernel

Python 3 kernel with GPU acceleration in NVIDIA Optimus setups
7
star
7

ann-ntnu

Artificial Neural Networks visualization for IT3708@NTNU
Python
6
star
8

advent-of-code-2017

My solutions for Advent of Code 2017
Python
4
star
9

monadic-gcd

Learning exercise (GCD) with explanation about monads
Haskell
4
star
10

sdsc-2024-spacetime

All the content for the workshop "Where and When: A Space-Time Analysis of Vehicle Collisions in London"
4
star
11

gul-emacs-talk

La primera hora de tus próximos diez años: una introducción a Emacs - GUL Talks XXXI
Emacs Lisp
3
star
12

MIPS-Assembly-Notes

Some basic examples and notes of MIPS Assembly Language
Assembly
3
star
13

machine-learning

The Google's Machine Learning Recipes tutorials in YouTube, using Python with TensorFlow and scikit-learn
Python
2
star
14

fractal-go

Mandelbrot set representation in Go
Go
2
star
15

bachelor-thesis

Agis: Heuristic Search Library & Framework in Haskell
TeX
2
star
16

pydata-madrid-bigframes

All the contents of the Google Bigframes talk in PyData Madrid (July 2024)
Jupyter Notebook
2
star
17

Swift-Examples

Some examples of Swift code
Swift
1
star
18

aoc21

Advent of Code 2021 in Nim
Nim
1
star
19

99-problems

But a switch ain't one.
Python
1
star