The metropolis_hastings algorithms simply estimate a distribution using the Metropolis-Hastings algorithm. The two different versions just estimate two different distributions. The code in 'metropolis_hastings.py' estimates a normal PDF, starting at a value far from the PDF's mean. 'metropolis_hastings2.py' uses the Metropolis-Hastings algorithm to estimate an asymmetric PDF.
The twoD_cities class is designed to construct a two dimensional traveling salesman problem. It does this by generating an user-specified number of cities on a 2-D grid of user-specified size. The class can find a brute-force solution to the traveling salesman problem too, but there's a hard-coded cap for the maximum number of cities for which it will implement the brute-force solution. The class also plots the cities and any path specified by the user (if a brute force solution has been found, this gets plotted by default).
This solves the traveling salesman problem using a simple simulated annealing algorithm. Running main() will find a solution and compare it to the brute force solution, if the brute force solution is allowable (brute force solver is capped since number of paths grows as (n-1)!).
Calling either of the Metropolis-Hastings scripts will show you the true underlying distribution with a red curve and a histogram of the sampled distribution in green. A tiny blue histogram shows where the algorithm walked during burn-in. Run the scripts with a simple call to python:
python metropolis_hastings.py
and
python metropolis_hastings2.py
The 2-D cities code can be run by calling
python twoD_cities.py
This will generate a random distribution of cities and plot them. It also shows the shortest path one can take to visit all of the cities. This solution was found via a brute force algorithm.
The simulated annealing algorithm approximately solves the traveling salesman problem generated by twoD_cities.py. By calling
python simulated_annealing.py
you will see a brute force solution plotted, as well as the solution found by simulated annealing. The route distance and "temperature" are also shown plotted as a function of the annealing iterations.