Задача коммивояжера с использованием имитации отжига [Python] - PullRequest
Новая
       43

Задача коммивояжера с использованием имитации отжига [Python]

0 голосов
/ 07 декабря 2018

Ниже приведена программа, написанная мной на python для задачи коммивояжера с использованием метода имитации отжига.Я не могу заставить сеть Хопфилда сходиться и получить соответствующую матрицу тура.Я не могу понять, где проблема или что я делаю неправильно.Это любое из значений параметров или любое уравнение, которое я написал неправильно.Любое понимание и помощь будут высоко ценится.Спасибо вам большое!Я был в этом в течение двух дней, и я не могу понять, где я иду не так.

Возможные места для проблем:

  1. Я заметил, что дельта C (изменение стоимости) слишком велико.И поэтому значение Ai всегда составляет 0,5.Вот почему значения для counter1 и counter2 примерно одинаковы.

  2. Возможно, штраф рассчитывается неправильно, но я несколько раз проверял математику и не смог найти ошибку.

  3. Значение температуры 

    import time
startTime = time.time()
import random
import numpy as np
import math
import copy

# Function to caluculate penalty. Returns total penalty and the penalty matrix
def calcPenalty(tour, distance):
    cost = 0
    penalty = np.zeros([10, 10])
    for i in range(len(tour)):
        for j in range(len(tour)):
            # Penalty to skip a city
            if np.sum(tour[i, :]) == 0:
                penalty[i][j] = penalty[i][j] + ((A/2)*(N - (tour[i, :].dot(weight[i, :].T))))
            # Penalty to skip a day
            if np.sum(tour[:, j]) == 0:
                penalty[i][j] = penalty[i][j] + ((B/2)*(N - (tour[:, j].dot(weight[:, j].T))))
            # Penalty for visiting multiple city
            if np.sum(tour[i, :]) > 1:
                penalty[i][j] = penalty[i][j] + (tour[i, :].dot(weight[i, :]) - 1)*C/2
            # Penalty for visiting same city multiple days
            if np.sum(tour[:, j]) > 1:
                penalty[i][j] = penalty[i][j] + (tour[:, j].dot(weight[:, j]) - 1)*D/2
            # Distance penalty
            for k in range(10):
                if i == k:
                    penalty[i][j] += 0
                else:
                    if j == 0:
                        penalty[i][j] = penalty[i][j] + (distance[i][k]*tour[i][j] * tour[k][j+1])*E/2
                    elif j == 9:
                        penalty[i][j] = penalty[i][j] + (distance[i][k]*tour[i][j] * tour[k][j-1])*E/2
                    else:
                        penalty[i][j] = penalty[i][j] + (distance[i][k]*tour[i][j] * (tour[k][j+1] + tour[k][j-1]))*E/2
    costMatrix = penalty
    cost = np.sum(penalty)
    return cost, costMatrix

# Defining Input
distance = np.array([[0,   0,   0,   0,   0,   0,   0,   0,   0,   0],
                 [118,   0,   0,   0,   0,   0,   0,   0,   0,   0],
                 [146, 119,   0,   0,   0,   0,   0,   0,   0,   0],
                 [39, 116,  68,   0,   0,   0,   0,   0,   0,   0],
                 [53,  65, 104,   9,   0,   0,   0,   0,   0,   0],
                 [85,  65, 148,  15,  31,   0,   0,   0,   0,   0],
                 [23,  16,  98,  20,  29,  55,   0,   0,   0,   0],
                 [146,  70, 146,  90, 110,   5,  42,   0,   0,   0],
                 [47,  62,   9, 103,  84,  39,  78,  14,   0,   0],
                 [47, 100,  19, 107,  43,  27,  87,   3, 124,   0]])

tourMatrix = np.array([[0, 0, 1, 1, 0, 0, 0, 1, 1, 1],
         [0, 1, 1, 1, 0, 1, 1, 0, 0, 0],
         [0, 1, 1, 0, 0, 0, 1, 0, 0, 0],
         [0, 1, 0, 1, 1, 0, 1, 0, 0, 1],
         [1, 0, 0, 1, 0, 1, 0, 1, 1, 1],
         [1, 0, 1, 0, 0, 1, 1, 1, 0, 0],
         [0, 1, 0, 0, 0, 1, 0, 0, 1, 1],
         [0, 0, 1, 1, 1, 0, 1, 1, 1, 1],
         [1, 1, 0, 1, 0, 0, 1, 1, 0, 1],
         [0, 0, 0, 0, 0, 1, 1, 0, 1, 1]])

tour = np.array([[0, 0, 1, 1, 0, 0, 0, 1, 1, 1],
            [0, 1, 1, 1, 0, 1, 1, 0, 0, 0],
            [0, 1, 1, 0, 0, 0, 1, 0, 0, 0],
            [0, 1, 0, 1, 1, 0, 1, 0, 0, 1],
            [1, 0, 0, 1, 0, 1, 0, 1, 1, 1],
            [1, 0, 1, 0, 0, 1, 1, 1, 0, 0],
            [0, 1, 0, 0, 0, 1, 0, 0, 1, 1],
            [0, 0, 1, 1, 1, 0, 1, 1, 1, 1],
            [1, 1, 0, 1, 0, 0, 1, 1, 0, 1],
            [0, 0, 0, 0, 0, 1, 1, 0, 1, 1]])
print("HERE")
print(tourMatrix)
weight = np.ones([10, 10])
alpha = 0.995
temperature = 100
# weights
A=300
B=300
C=200
D=200
E=300
N = 13
counter1 = 0
counter2 = 0

print("------------------------------------------------------------------------------")
print("Initial Tour Matrix is:")
print(tour)
print("------------------------------------------------------------------------------")
print("Initial Distance Matrix is:")
print(distance)
print("------------------------------------------------------------------------------")

for index in range(10000):
    # Get the Initial Cost
    initialCost, initialCostMatrix = calcPenalty(tour, distance)
    # print("Initial cost is:")
    # print(initialCost)
    # Flip a bit and check for cost
    rx = np.random.randint(10)
    ry = np.random.randint(10)
    tour[rx][ry] = 0 if tour[rx][ry] else 1
    # Calculate the cost after flipping a bit
    intCost, intCostMatrix = calcPenalty(tour, distance)
    # print("Cost after flipping bit is:")
    # print(intCost)
    # print("------------------------------------------------------------------------------")

k = math.exp( - abs( intCost - initialCost ) / temperature  )    
Ai = 1/(1 + math.exp(k))
# print(Ai,k)
if Ai <= np.random.rand(1):
    tour[rx][ry] = 0 if tour[rx][ry] else 1
    counter1+=1
else:
    counter2+=1
temperature *= alpha

print("Number of 1's initially:")
print(tourMatrix)
print(np.sum(tourMatrix))
print()
print(tour)
print()
print("Number of 1's in the end:")
print(np.sum(tour))
print()
print("Time it took to run the code:")
print(time.time() - startTime)
print()
print(counter1)
print(counter2)
...