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
MNE: Magnetoencephalography (MEG) and Electroencephalography (EEG) in Python

MNE-Python MNE-Python software is an open-source Python package for exploring, visualizing, and analyzing human neurophysiological data such as MEG, E

MNE tools for MEG and EEG data analysis 2.1k Dec 28, 2022
Build a small, 3 domain internet using Github pages and Wikipedia and construct a crawler to crawl, render, and index.

TechSEO Crawler Build a small, 3 domain internet using Github pages and Wikipedia and construct a crawler to crawl, render, and index. Play with the r

JR Oakes 57 Nov 24, 2022
Code release for "COTR: Correspondence Transformer for Matching Across Images"

COTR: Correspondence Transformer for Matching Across Images This repository contains the inference code for COTR. We plan to release the training code

UBC Computer Vision Group 360 Jan 06, 2023
Gif-caption - A straightforward GIF Captioner written in Python

Broksy's GIF Captioner Have you ever wanted to easily caption a GIF without havi

3 Apr 09, 2022
DSEE: Dually Sparsity-embedded Efficient Tuning of Pre-trained Language Models

DSEE Codes for [Preprint] DSEE: Dually Sparsity-embedded Efficient Tuning of Pre-trained Language Models Xuxi Chen, Tianlong Chen, Yu Cheng, Weizhu Ch

VITA 4 Dec 27, 2021
A numpy-based implementation of RANSAC for fundamental matrix and homography estimation. The degeneracy updating and local optimization components are included and optional.

Description A numpy-based implementation of RANSAC for fundamental matrix and homography estimation. The degeneracy updating and local optimization co

AoxiangFan 9 Nov 10, 2022
This is the repo for Uncertainty Quantification 360 Toolkit.

UQ360 The Uncertainty Quantification 360 (UQ360) toolkit is an open-source Python package that provides a diverse set of algorithms to quantify uncert

International Business Machines 207 Dec 30, 2022
Code for "Primitive Representation Learning for Scene Text Recognition" (CVPR 2021)

Primitive Representation Learning Network (PREN) This repository contains the code for our paper accepted by CVPR 2021 Primitive Representation Learni

Ruijie Yan 76 Jan 02, 2023
Direct Multi-view Multi-person 3D Human Pose Estimation

Implementation of NeurIPS-2021 paper: Direct Multi-view Multi-person 3D Human Pose Estimation [paper] [video-YouTube, video-Bilibili] [slides] This is

Sea AI Lab 251 Dec 30, 2022
Impelmentation for paper Feature Generation and Hypothesis Verification for Reliable Face Anti-Spoofing

FGHV Impelmentation for paper Feature Generation and Hypothesis Verification for Reliable Face Anti-Spoofing Requirements Python 3.6 Pytorch 1.5.0 Cud

5 Jun 02, 2022
Reference PyTorch implementation of "End-to-end optimized image compression with competition of prior distributions"

PyTorch reference implementation of "End-to-end optimized image compression with competition of prior distributions" by Benoit Brummer and Christophe

Benoit Brummer 6 Jun 16, 2022
Official implementation of the paper 'Efficient and Degradation-Adaptive Network for Real-World Image Super-Resolution'

DASR Paper Efficient and Degradation-Adaptive Network for Real-World Image Super-Resolution Jie Liang, Hui Zeng, and Lei Zhang. In arxiv preprint. Abs

81 Dec 28, 2022
《Improving Unsupervised Image Clustering With Robust Learning》(2020)

Improving Unsupervised Image Clustering With Robust Learning This repo is the PyTorch codes for "Improving Unsupervised Image Clustering With Robust L

Sungwon Park 129 Dec 27, 2022
A repository for the updated version of CoinRun used to collect MUGEN, a multimodal video-audio-text dataset.

A repository for the updated version of CoinRun used to collect MUGEN, a multimodal video-audio-text dataset. This repo contains scripts to train RL agents to navigate the closed world and collect vi

MUGEN 11 Oct 22, 2022
General Multi-label Image Classification with Transformers

General Multi-label Image Classification with Transformers Jack Lanchantin, Tianlu Wang, Vicente Ordóñez Román, Yanjun Qi Conference on Computer Visio

QData 154 Dec 21, 2022
Vision-Language Transformer and Query Generation for Referring Segmentation (ICCV 2021)

Vision-Language Transformer and Query Generation for Referring Segmentation Please consider citing our paper in your publications if the project helps

Henghui Ding 143 Dec 23, 2022
yolov5目标检测模型的知识蒸馏(基于响应的蒸馏)

代码地址: https://github.com/Sharpiless/yolov5-knowledge-distillation 教师模型: python train.py --weights weights/yolov5m.pt \ --cfg models/yolov5m.ya

52 Dec 04, 2022
This is the code for Compressing BERT: Studying the Effects of Weight Pruning on Transfer Learning

This is the code for Compressing BERT: Studying the Effects of Weight Pruning on Transfer Learning It includes /bert, which is the original BERT repos

Mitchell Gordon 11 Nov 15, 2022
PyTorch implementation for the paper Pseudo Numerical Methods for Diffusion Models on Manifolds

Pseudo Numerical Methods for Diffusion Models on Manifolds (PNDM) This repo is the official PyTorch implementation for the paper Pseudo Numerical Meth

Luping Liu (刘路平) 196 Jan 05, 2023
Customizable RecSys Simulator for OpenAI Gym

gym-recsys: Customizable RecSys Simulator for OpenAI Gym Installation | How to use | Examples | Citation This package describes an OpenAI Gym interfac

Xingdong Zuo 14 Dec 08, 2022