Parameterising Simulated Annealing for the Travelling Salesman Problem

Overview

Parameterising Simulated Annealing for the Travelling Salesman Problem

animated

Abstract

The Travelling Salesman Problem is a well known NP-Hard problem. Given a list of cities, find the shortest path that visits all cities once.

Simulated annealing is a well known stochastic method for solving optimisation problems and is a well known non-exact algorithm for solving the TSP. However, it's effectiveness is dependent on initial parameters such as the starting temperature and cooling rate which is often chosen empirically.

The goal of this project is to:

  • Determine if the optimal starting temperature and cooling rate can be parameterised off the input
  • Visualise the solving process of the TSP

Usage

Running the code

Examples of common commands to run the files are shown below. However, both src/main.py and src/benchmark.py have a --help that explains the optional flags.

# To visualise annealing on a problem set from the input file
python3 -m src.main -f <input_file>

# To visualise TSP on a random graph with 
   
     number of cities
   
python3 -m src.main -c <city_count>

# Benchmark the parameters using all problems in the data folder
python3 -m src.benchmark

Keyboard Controls

There are also ways to control the visualisation through key presses while it plays.

Key Action
Space Bar Pauses or unpauses the solver
Left / Right arrow Control how frequently the frame is redrawn
c Toggles showing the cities as nodes (this is off by default as it causes lag)

Creating your own model

If you would like to create your own instance of the TSP problem and visualise it:

  1. Create a new file
  2. Within this file ensure you have the line NODE_COORD_SECTION, and below that EOF.
  3. Between those two lines, you can place the coordinates of the cities, i.e. for the nth city, have a line like , where x and y are the x and y coordinates of the city.
  4. Run python3 -m src.main -f , where is the path to the file you have just made.

Files

File / Folder Purpose
data This contains TSP problems in .tsp files and their optimal solution in .opt.tour files, taken from TSPLIB
report The report detailing the Simulated Annealing and the experimentation
results The output directory containing results of the tests
src/benchmark.py Code for benchmarking different temperatures and cooling rates using the problems in the data folder
src/main.py Driver code to start the visualisation
src/setup.py Code for loading in city coordinates from a file, or generating random ones
src/solvers.py Module containing the python implementations of TSP solving algorithms

FAQ

What do you use to generate the graphics?

This project uses the p5py library for visualisation. Unfortunately, (to of my knowledge) this may not work with WSL.

What are the results of your research?

Idk. Still working on it.

What can I do to contribute?

Pog.

This is more of a "what I would I do if I have more time" but whatever, let's say you actually are interested. Disclaimer - the code isn't particularly polished (from me pivoting project ideas multiple times).

  • If you're up for a challenge, it would be interesting to implement LKH (Lin-Kernighan heuristic) efficiently
  • Implement other algorithms - they just need to extend the Solver abstract class to work with the frontend
  • Add a whatever city you want and it's coordinates to data/world.tsp!
Owner
Gary Sun
hi
Gary Sun
An educational AI robot based on NVIDIA Jetson Nano.

JetBot Looking for a quick way to get started with JetBot? Many third party kits are now available! JetBot is an open-source robot based on NVIDIA Jet

NVIDIA AI IOT 2.6k Dec 29, 2022
Web mining module for Python, with tools for scraping, natural language processing, machine learning, network analysis and visualization.

Pattern Pattern is a web mining module for Python. It has tools for: Data Mining: web services (Google, Twitter, Wikipedia), web crawler, HTML DOM par

Computational Linguistics Research Group 8.4k Jan 03, 2023
Code for MentorNet: Learning Data-Driven Curriculum for Very Deep Neural Networks

MentorNet: Learning Data-Driven Curriculum for Very Deep Neural Networks This is the code for the paper: MentorNet: Learning Data-Driven Curriculum fo

Google 302 Dec 23, 2022
Deep Q Learning with OpenAI Gym and Pokemon Showdown

pokemon-deep-learning An openAI gym project for pokemon involving deep q learning. Made by myself, Sam Little, and Layton Webber. This code captures g

2 Dec 22, 2021
Emblaze - Interactive Embedding Comparison

Emblaze - Interactive Embedding Comparison Emblaze is a Jupyter notebook widget for visually comparing embeddings using animated scatter plots. It bun

CMU Data Interaction Group 77 Nov 24, 2022
Implementation of UNet on the Joey ML framework

Independent Research Project - Code Joey can be cloned from here https://github.com/devitocodes/joey/. Devito and other dependencies such as PyTorch a

Navjot Kukreja 1 Oct 21, 2021
When are Iterative GPs Numerically Accurate?

When are Iterative GPs Numerically Accurate? This is a code repository for the paper "When are Iterative GPs Numerically Accurate?" by Wesley Maddox,

Wesley Maddox 1 Jan 06, 2022
Pseudo lidar - (CVPR 2019) Pseudo-LiDAR from Visual Depth Estimation: Bridging the Gap in 3D Object Detection for Autonomous Driving

Pseudo-LiDAR from Visual Depth Estimation: Bridging the Gap in 3D Object Detection for Autonomous Driving This paper has been accpeted by Conference o

Yan Wang 881 Dec 27, 2022
Next-gen Rowhammer fuzzer that uses non-uniform, frequency-based patterns.

Blacksmith Rowhammer Fuzzer This repository provides the code accompanying the paper Blacksmith: Scalable Rowhammering in the Frequency Domain that is

Computer Security Group @ ETH Zurich 173 Nov 16, 2022
A simple algorithm for extracting tree height in sparse scene from point cloud data.

TREE HEIGHT EXTRACTION IN SPARSE SCENES BASED ON UAV REMOTE SENSING This is the offical python implementation of the paper "Tree Height Extraction in

6 Oct 28, 2022
Towards Representation Learning for Atmospheric Dynamics (AtmoDist)

Towards Representation Learning for Atmospheric Dynamics (AtmoDist) The prediction of future climate scenarios under anthropogenic forcing is critical

Sebastian Hoffmann 4 Dec 15, 2022
Heterogeneous Deep Graph Infomax

Heterogeneous-Deep-Graph-Infomax Parameter Setting: HDGI-A: Node-level dimension: 16 Attention head: 4 Semantic-level attention vector: 8 learning rat

52 Oct 31, 2022
Predicting future trajectories of people in cameras of novel scenarios and views.

Pedestrian Trajectory Prediction Predicting future trajectories of pedestrians in cameras of novel scenarios and views. This repository contains the c

8 Sep 03, 2022
This is the source code of the solver used to compete in the International Timetabling Competition 2019.

ITC2019 Solver This is the source code of the solver used to compete in the International Timetabling Competition 2019. Building .NET Core (2.1 or hig

Edon Gashi 8 Jan 22, 2022
Flexible-Modal Face Anti-Spoofing: A Benchmark

Flexible-Modal FAS This is the official repository of "Flexible-Modal Face Anti-

Zitong Yu 22 Nov 10, 2022
Highly comparative time-series analysis

〰️ hctsa 〰️ : highly comparative time-series analysis hctsa is a software package for running highly comparative time-series analysis using Matlab (fu

Ben Fulcher 569 Dec 21, 2022
Machine learning algorithms for many-body quantum systems

NetKet NetKet is an open-source project delivering cutting-edge methods for the study of many-body quantum systems with artificial neural networks and

NetKet 413 Dec 31, 2022
Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs (CIKM 2020)

Karate Club is an unsupervised machine learning extension library for NetworkX. Please look at the Documentation, relevant Paper, Promo Video, and Ext

Benedek Rozemberczki 1.8k Jan 07, 2023
Testing and Estimation of structural breaks in Stata

xtbreak estimating and testing for many known and unknown structural breaks in time series and panel data. For an overview of xtbreak test see xtbreak

Jan Ditzen 13 Jun 19, 2022
[NeurIPS 2021] Garment4D: Garment Reconstruction from Point Cloud Sequences

Garment4D [PDF] | [OpenReview] | [Project Page] Overview This is the codebase for our NeurIPS 2021 paper Garment4D: Garment Reconstruction from Point

Fangzhou Hong 112 Dec 23, 2022