TSP, algorithm gets stuck in local minimum

Question

I am struggling to implement a program based on simulated annealing to solve the traveling salesman problem. All solutions I got are not satisfying and i have no clue how to improve my implementation. Obviously I'm not focusing on benchmarks, but only on finding the visually acceptable shortest path. If anyone might enlighten me I would be thankful.

# weight function, simple euclidean norm
def road(X,Y):
    sum = 0
    size = len(X) -1
    for i in range(0,size):
        sum +=math.sqrt((X[i]-X[i+1])**2 + (Y[i]-Y[i+1])**2)

    return sum   

def array_swap(X,Y,index_1,index_2):
    X[index_1],X[index_2] = X[index_2],X[index_1]
    Y[index_1],Y[index_2] = Y[index_2],Y[index_1]


def arbitrarty_swap(X,Y):
    ran = len(X)-1
    pick_1 = random.randint(0,ran)
    pick_2 = random.randint(0,ran)

    X[pick_1],X[pick_2] = X[pick_2],X[pick_1]
    Y[pick_1],Y[pick_2] = Y[pick_2],Y[pick_1]

    return pick_1, pick_2

N = 40

X = np.random.rand(N) * 100
Y = np.random.rand(N) * 100


plt.plot(X, Y, '-o')
plt.show()


best = road(X,Y)
X1 = X.copy()
Y1 = Y.copy()

#history of systems energy   
best_hist = []
iterations = 100000
T = 1.02
B = 0.999

for i in range(0,iterations):
    index_1, index_2 = arbitrarty_swap(X,Y)
    curr = road(X,Y)
    diff = (curr - best)
    if diff < 0 :
        best = curr
        best_hist.append(best)
        array_swap(X1,Y1,index_1,index_2)
    elif math.exp(-(diff)/T) > random.uniform(0,1):
        best_hist.append(curr)
        T *=B
    else:
        array_swap(X,Y,index_1,index_2)

https://i.sstatic.net/A6hmd.png

Oxfordshire

Hi Michał what does it mean when the solution is not visually satisfying? Could you post some screenshots of the bad results? – Wolves

Sure, just updated the link below the code section. – Typesetting

Answer 1

I didn't run your code, but one thing I'd try is changing the SA implementation. Currently, you have 100,000 iterations in one loop. I would break that into two. The outer loop controls the temperature and the inner loop is different runs in that temperature. Something like this (pseudo code):

t=0; iterations=1000; repeat=1000
while t <= repeat:
    n = 0
    while n <=iterations:
        # your SA implementation.
        n += 1 # increase your iteration count in each temperature
    # in outer while, 
    t += 1
    T *= B

Homerus

Answer 2

Your algorithm is correct. You are using a geometric cooling schedule, only a single loop is required.

Simulated Annealing does not guarantee finding a "global minima" (e.g. avoiding sub optimal results), it only allows you to escape "local minima". A large TSP will will have many "local minima" so you can "jump out" of a local minima with SA accepting "poorer" solutions based on the acceptance criteria that you have implemented, however it does not guarantee eventually finding the global.

TSP is a "NP Hard", so is very hard to solve. Remember, SA requires you to "initialise" the solution with a starting candidate. It is better to improve this starting point to get a better result from SA (e.g. you're already in a better local minima and can improve more on the start hopefully).

There are a large number of research papers on this topic discussing varied ways of solving TSP and SA has been known for some decades, you can find examples of SA "solving" TSP on the web, but there are many "better" approaches than SA, some developed specifically for TSP. SA is a meta heuristic and can be used on many solutions.

I'm using it on a thesis to solve a problem similar to Job Shop Scheduling (JSSP), but have used a separate algorithm to find a good starting point, which is then improved by SA. It currently typically performs 100 times better than SA alone, so I'm reasonably happy with it.

Acervate

Answer 3

It seems to work,

but without debug info it is really difficult to find good parameters.

• Make sure to always lower the temperature, not depending on a acceptance or note.
• For each iteration, do N(=500) repetitions. By doing this, you can choice a more normal cooling factor like 0.8 or 0.95, and you have better control on the cooling.
• In each repetition, print the number of accepted states. You want 90%> early, and <10% or <1% when temperature is low.

Also, you had not enough iterations to find a good solution.

With this is already gets much better, so your scheme is correct but you need to tweak the parameters a bit.

#history of systems energy   
best_hist = []
iterations = 50000
T = 500
B = 0.999


for i in range(0,iterations):
    index_1, index_2 = arbitrarty_swap(X,Y)
    curr = road(X,Y)
    diff = (curr - best)
    if diff < 0 :
        best = curr
        best_hist.append(best)
        array_swap(X1,Y1,index_1,index_2)
    elif math.exp(-(diff)/T) > random.uniform(0,1):
        best_hist.append(curr)        
    else:
        array_swap(X,Y,index_1,index_2)
    if i % 1000 == 0:
        print(T)
    T *=B

Cry