This is my code for simulated annealing to solve the travelling salesman problem. The comments should describe what's going on. For some reason, the algorithm prints out the best tour LENGTH it finds, but not the actual tour itself. If I were to add a
print(solution)
under
if ap>=rd.random()
the last tour it prints would be the best tour, every time. How do I go about accessing that tour? Preferably without creating an array.
def simulate_annealing(cityMat):
#generate a random tour
solution = genRandom(cityMat)
#get its length
solution_cost = getTourLength(solution, cityMat)
#set initial temperature
temperature = 1.0
#set limit to iterate to
limit = 100
#set final temperature
min_temperature = 0.00001
#set cooling rate
cooling_rate = 0.90
# variable for best solution
best_solution = solution
best_solution_cost = solution_cost
while temperature > min_temperature:
for i in range(1, limit + 1): # use for loops when you can
#generate neighbour tour
neighbour = genNeighbour(solution)
neighbour_cost = getTourLength(neighbour, cityMat)
#get probability of accepting new tour
probabilty_of_acceptance = acc_prob(
solution_cost, neighbour_cost, temperature
)
best_solutions = []
#####
if neighbour_cost < solution_cost:
best_solutions.append(neighbour)
print(best_solutions) #could just print best_solution see the print below (and where the actual best solution is)
best_solution = neighbour
best_solution_cost = neighbour_cost
#####
# switch if random value greater than probability
if probabilty_of_acceptance >= rd.random():
solution = neighbour
solution_cost = neighbour_cost
#cool temperature
temperature *= cooling_rate
return best_solution_cost, best_solution
[[16, 11, 13, 6, 25, 8, 14, 17, 15, 23, 21, 10, 22, 20, 19, 7, 12, 0, 3, 2, 5, 4, 9, 24, 1, 18]]
[[16, 11, 13, 6, 25, 8, 14, 17, 15, 23, 21, 10, 22, 20, 19, 12, 7, 0, 3, 2, 5, 4, 9, 24, 1, 18]]
[[16, 11, 13, 6, 25, 8, 14, 17, 23, 15, 21, 10, 22, 20, 19, 12, 7, 0, 3, 2, 5, 4, 24, 9, 1, 18]]
[[16, 11, 6, 14, 8, 25, 13, 17, 23, 10, 15, 22, 21, 12, 20, 7, 0, 19, 4, 5, 24, 9, 3, 2, 1, 18]]
[[14, 11, 8, 16, 6, 25, 13, 10, 12, 15, 17, 23, 5, 20, 22, 4, 0, 21, 19, 24, 9, 7, 2, 18, 1, 3]]
[[14, 11, 8, 16, 6, 25, 13, 10, 12, 15, 17, 23, 20, 5, 22, 4, 21, 0, 19, 24, 9, 7, 2, 18, 1, 3]]
[[14, 11, 8, 6, 25, 16, 13, 10, 12, 15, 17, 23, 22, 20, 5, 4, 21, 0, 19, 24, 9, 7, 2, 1, 18, 3]]
[[15, 25, 6, 10, 21, 12, 4, 22, 7, 14, 23, 13, 11, 8, 16, 5, 2, 0, 3, 24, 9, 1, 18, 19, 20, 17]]
[[7, 1, 0, 21, 5, 23, 25, 2, 15, 16, 12, 22, 6, 20, 19, 24, 3, 10, 9, 4, 8, 17, 18, 13, 14, 11]]
[[7, 1, 0, 5, 21, 23, 25, 2, 15, 16, 12, 22, 24, 6, 20, 19, 3, 10, 9, 4, 17, 8, 13, 18, 14, 11]]
[[7, 1, 0, 5, 21, 23, 25, 2, 15, 16, 12, 22, 24, 6, 20, 19, 3, 10, 9, 4, 8, 17, 13, 18, 14, 11]] #THIS IS THE BEST SOLUTION
(1980, [25, 2, 10, 22, 20, 6, 7, 24, 16, 8, 15, 1, 14, 23, 21, 5, 3, 0, 12, 19, 4, 11, 13, 17, 18, 9])
def getTourLength(tour, cityMat):
cityLen = len(tour)
tourLength = []
for k in range(0,cityLen-1):
tourLength.append(cityMat[tour[k]][tour[k+1]])
tourLength.append(cityMat[tour[cityLen-1]][tour[0]])
cost = sum(tourLength)
return cost
def genNeighbour(tour):
ranSwap = rd.randint(0,len(tour)-2)
tour[ranSwap], tour[ranSwap+1] = tour[ranSwap+1], tour[ranSwap]
return tour
I've made your code much more readable. You should really check out PEP8 since you break most of the accepted style forms. Is this all you want, a way to store the best solution? You weren't very clear...
import random
def simulate_annealing(city_matrix):
#generate a random tour
solution = generate_random(city_matrix)
#get its length
solution_cost = tour_length(solution, city_matrix)
#set initial temperature
temperature = 1.0
#set limit to iterate to
limit = 100
#set final temperature
min_temperature = 0.00001
#set cooling rate
cooling_rate = 0.90
# variable for best solution
best_solution = solution
best_solution_cost = solution_cost
while temperature > min_temperature:
for i in range(1, limit + 1): # use for loops when you can
#generate neighbour tour
neighbour = generate_neighbour(solution)
neighbour_cost = tour_length(neighbour, city_matrix)
#get probability of accepting new tour
probabilty_of_acceptance = acceptance_probability(
solution_cost, neighbour_cost, temperature
)
#####
if neighbour_cost < solution_cost: # I assume we can compare these
best_solution = neighbour
best_solution_cost = neighbour_cost
#####
# switch if random value greater than probability
if probability_of_acceptance >= random.random():
solution = neighbour
solution_cost = neighbour_cost
#cool temperature
temperature *= cooling_rate
# change this how you see fit (print or whatever)
return best_solution_cost, best_solution
Edit: right I've got it. It's a classic python gotchya. You are editing the current array in place, so it will change every time you generate a new neighbour. You need to copy tour like so.
def genNeighbour(tour):
tour_copy = tour.copy() # or tour[:]
ranSwap = rd.randint(0,len(tour)-2)
tour_copy[ranSwap], tour_copy[ranSwap+1] = tour[ranSwap+1], tour[ranSwap]
return tour_copy