Hillclimbing algorithm for Travelling saleman problem

Hillclimbing_1.py

import math
import random

#Prints the solution path
def print_solution(solution,distances, cities):
    print "Path : "+cities[solution[0]]+"-->"+cities[solution[1]]+"-->"+cities[solution[2]]+"-->"+cities[solution[3]]+"-->"+cities[solution[4]]+"-->"+cities[solution[5]]
    print "Total Distance: "+str(solution_value(solution,distances,cities))

#Generate a random path through the cities
def random_solution():
    solution = [0]
    for i in range(5):
        next_city =  random.randint(1,5)
        while next_city in solution:
            next_city = random.randint(1,5)
        solution.append(next_city)
    return solution
    
#incremental change best solution by swapping around position of two cities
def incremental_change(original):
    solution = []
    for x in original:
        solution.append(x)
    idx1 = random.randint(1,5)
    idx2 = random.randint(1,5)
    while idx1 == idx2:
        idx2 = random.randint(1,5)
    temp = solution[idx1]
    solution[idx1] = solution[idx2]
    solution[idx2] = temp
    return solution

#Measure the distance of a path through the cities
def solution_value(solution, distances, cities):
    total = 0
    for i in range(len(solution)-1):
        city1 = solution[i]
        city2 = solution[i+1]
        if city1 > city2:
            temp = city1
            city1 = city2
            city2 = temp
        city1_name = cities[city1]
        city2_name = cities[city2]
        total =  total + distances[city1_name][city2_name]
            
    return total
        
#Names of Cities to traverse 
cities = [""]*6
cities[0] = "Origin"
cities[1] = "New York"
cities[2] = "St. John's"
cities[3] = "Paris"
cities[4] = "Perth"
cities[5] = "Nottingham"

#Distances between the cities
distances = {}
distances["Origin"] = {}
distances["Origin"]["New York"] = 300
distances["Origin"]["St. John's"] = 2
distances["Origin"]["Paris"] = 310
distances["Origin"]["Perth"] = 190
distances["Origin"]["Nottingham"] = 330

distances["New York"] = {}
distances["New York"]["St. John's"] = 300
distances["New York"]["Paris"] = 560
distances["New York"]["Perth"] = 830
distances["New York"]["Nottingham"] = 500

distances["St. John's"] = {}
distances["St. John's"]["Paris"] = 350
distances["St. John's"]["Perth"] = 200
distances["St. John's"]["Nottingham"] = 320

distances["Paris"] = {}
distances["Paris"]["Perth"] = 300
distances["Paris"]["Nottingham"] = 460

distances["Perth"] = {}
distances["Perth"]["Nottingham"] = 220

iteration_without_change = 0

#Actual hillclimbing algorithm
current_solution = random_solution()    #Begins by randomly generate a solution to problem ie a random path through the cities

while iteration_without_change < 10:    #Repeatedly try to find a better path through the citis until you haven't found a new path in 10 tries
    possible_solution = incremental_change(current_solution)    #Generate a candidate path/solution to be the new shortest path
    
    #If the new candidate path is actually shorter we make it our current path 
    if solution_value(possible_solution,distances, cities) < solution_value(current_solution,distances, cities):
        iteration_without_change = 0
        current_solution = possible_solution
    else:
        iteration_without_change = iteration_without_change + 1

#Print the current solution which should at this point contain the shortest path found so far
print_solution(current_solution,distances,cities)