-2

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
Sid Jones
  • 55
  • 1
  • 1
  • 10
  • Use more descriptive variable names in future. Tracking what `ap, rn, l, ln, alpha, T, T_min, n, i` are is a nightmare. And don't shorten the `random` module to `rd` for gods sake! Anyway, I don't understand how you think you can store the data without creating a list? Why don't you want to do that? – FHTMitchell Dec 14 '17 at 16:34
  • I thought I might be able to store it as a temp variable or something. Do you have any idea how I may do it with a list then? – Sid Jones Dec 14 '17 at 16:48
  • Have edited my code to make it more reasonable. And I want to avoid that to reduce space complexity. – Sid Jones Dec 14 '17 at 17:01

1 Answers1

0

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
FHTMitchell
  • 11,793
  • 2
  • 35
  • 47
  • The problem I was having was that the best_solution being produced wasn't actually the best tour, despite the best_solution_cost being the best tour cost. I have no idea why this is happening. I have used your improved code to make it more readable, but the problem of the best_solution not actually being the best persists. If I were to print(best_solution) in its if statement, the last print IS the best_solution, but the one returned ISN'T. – Sid Jones Dec 14 '17 at 18:04
  • Well that is almost certainly a problem with your `tour_length` function. . I think you should go and check that. The logic you've presented here is pretty sound. What measure are you using to say that `best_solution` is not in fact the best? `best_solution` **must** have the lowest `best_solution_cost` – FHTMitchell Dec 14 '17 at 18:08
  • How can it be a problem with the tour_length function when that is what determines the best_solution? When i print best_solution, the final print is different to that which is returned. When I check the tour length of the final print, it is the same as the best_solution_cost. For some reason what is being returned is different to the final print of best_solution. It is also in NONE of the prints. If possible, i'd like to assign that final print to a variable and then store that but that's probably not possible. – Sid Jones Dec 14 '17 at 18:21
  • Well yeah... the final `solution` is not necessarily the best. That is the nature of the optimisation algorithm. There is a finite chance that `solution` will not improve when it encounters a better `neighbour` but that `neighbour` can still replace `best_solution` if it has a lower cost. `best_solution` will *always* have the lowest `solution_cost`. I think you need to go away and think about what the algorithm is doing. – FHTMitchell Dec 14 '17 at 18:31
  • I don't know if that's the reason. My algorithm is producing worse/similar results to just generating a random tour - are you sure I'm storing `best_solution` correctly? I created an array `best_solutions = []` and did `best_solutions.append(best_solution)` in the if statement, and the resultant array is just an array of solution – Sid Jones Dec 14 '17 at 18:37
  • I mean, what did you expect when you appended a solution to a list? – FHTMitchell Dec 14 '17 at 18:38
  • To be honest I just want to keep the best_solutions somewhere, and thought I could do that. How should I go about it? – Sid Jones Dec 14 '17 at 18:41
  • Pretty much what you've been doing... `if neighbour_cost < solution_cost: best_solutions.append(neighbour)` (and initialise `best_solutions=[]` before the loop). – FHTMitchell Dec 14 '17 at 18:43
  • I'm genuinely so confused. I did this, and then did `print(best_solutions)` just below appending it, and the FINAL print IS the best solution. I just want this, without having to print every previous best solution. But when I do the print OUTSIDE the loop, before the return, it's COMPLETELY different - much, much worse. This is completely going over me. – Sid Jones Dec 14 '17 at 18:52
  • I think i accidentally edited your post (or at least tried to) - my bad! i've added example prints of best_solutions for you to see, as well as where i've appended etc.. – Sid Jones Dec 14 '17 at 19:06
  • You're reinitialising the list each time you go through the loop – FHTMitchell Dec 14 '17 at 19:08
  • I know that, but even if I were to initialise the list before any loop the list just consists of loads of repeat best_solutions. The final part of the list is still the best solution. I suppose I should just do best_solutions[-1][0] or whatever, but it takes up A LOT of space - ill edit in the print. – Sid Jones Dec 14 '17 at 19:13
  • Well forget the list then, just print on each iteration where `best_solution` changes. Don't do both... What you have posted is impossible. Are you sure the code and results you have there is **exactly** what you have in your editor. Because my bet is you are returning `solution`, not `best_solution`. – FHTMitchell Dec 14 '17 at 19:14
  • How can I just print the LAST best_solution - is that not possible? It is **exactly** what is in my editor. I genuinely have no idea why when best_solution is returned it just seems like a random solution. – Sid Jones Dec 14 '17 at 19:17
  • Wait, do `generate_neighbour` or `tour_length` mutate their arguments in any way? Like if I do: `def f(x): x.sort(); x = [2,3,1]; f(x); print(x)` then `x` is different? Why not just post these functions too? – FHTMitchell Dec 14 '17 at 19:19
  • I've added them. By the way best_solutions before the loop doesn't change anything - it still contains just the bad result (seemingly random result). – Sid Jones Dec 14 '17 at 19:22
  • Oh wow. I don't know whether to laugh or cry but I had no idea that was a thing. Sorry you had to supervise me learning the hard way. – Sid Jones Dec 14 '17 at 19:29
  • Yeah it's an efficiency thing. Anything dynamic (that is, something that isn't an `int`, `float`, `complex`, `str`, `bytes`, `tuple`, `frozenset` or subclass of) can be manipulated by the functions they are passed to. You need to be careful about it. And don't worry, I do this for fun after all. Just send that sweet accepted answer my way! Further reading: https://stackoverflow.com/questions/8056130/immutable-vs-mutable-types – FHTMitchell Dec 14 '17 at 19:32