This is code associated with talks, workshops, and a blog post I have written about heuristic optimization algorithms. This repository contains the code needed to run four algorithms -- a hill climber, simulated annealing, Metropolis-coupled MCMC, and a genetic algorithm -- to find good solutions to the travelling salesperson problem. The code is written in a modular way that is meant to make it easy to adapt to other optimization problems. This code is written in Python3; for a Python2 implementation, see this repository.
An overview of the directory:
- InitMutFit.py contains functions to initialize, mutate, select, and calculate fitness for solutions.
- HC.py, SA.py, MCMCMC.py, and GA.py contain implementations of a hill climber, simulated annealing, MCMCMC, and a genetic algorithm, respectively.
- TravelingSalesperson.py is a wrapper for all of the specific implementations of the problem. This is a fairly generic wrapper that can be fitted to different optimization problems.
- TSPcommandline.py is a command line wrapper for TravelingSalesperson.py.
- Visualizations.py provides some functions to display how the
different algorithms performed. All
.txtfiles in theExampleOutputfolder can be used in these visualizations.
This code requires the following modules:
- copy
- math
- os
- pylab
- random
- scipy
- sys
If you run into any problems, please submit an issue!