TSP使用禁忌搜索问题与列表

Question

我有一些代码，我正在为我的课程做准备。我的想法是用禁忌搜索来解决一个旅行推销员搜索问题。我已经在我的代码中做的是随机生成一个城市列表（基于用户的输入-他想要多少个城市，程序在开始时问的问题），我可以计算每个城市之间的距离（我假设，销售人员可以直接从一个城市出发）另一个）。在

我的问题是，禁忌搜索。我的想法是有一个默认路径，只要按顺序访问所有城市，它们就生成了（第47行，变量名：domyslne）。然后我得到了它，我交换了两个随机的城市，并计算了路线的长度。这里是棘手的部分： 我无法集中精力获取禁忌和所有的条件，我想要（它可能是一组嵌套循环）。我想得到两个表：tabu（我存储最后检查的X个组合）和tabulen（在tabu表中存储相应路径的长度）。接下来，我渲染一条新路线并计算其长度。如果禁忌已经达到了它的最大大小X，并且新路由的长度小于当前存储的最大值，我们将从禁忌列表中移除最大值，并用新的值替换它，我刚才渲染的那个。最后，在Y循环这样的命令（目前默认设置为6，但我想做的像城市的平方数之类的），我从禁忌表得到最短的路线，并将其作为一个解决方案。我不知道如何使它正常工作，我希望我能得到一些帮助。提前非常感谢！在

import math
from pprint import pprint
from random import *


def odleglosci(a1, a2, b1, b2):
    w1 = a1 - b1  # wspolrzedne X (roznica)
    w2 = a2 - b2  # wspolrzedne Y (roznica)

    w1k = w1 * w1  # kwadrat wwspolrzednych X
    w2k = w2 * w2  # kwadrat wspolrzednych Y

    suma = w1k + w2k  # suma kwadratow
    return round(math.sqrt(suma), 2)  # pierwiastek z sumy kwadratow, zaokraglony do 2 miejsca po przecinku


def path_length(cities, path):
    cities_pairs = zip(path, path[1:])
    consecutive_distances = [odleglosci(cities[a][0], cities[a][1], cities[b][0], cities[b][1]) for (a, b) in
                             cities_pairs]
    return round(sum(consecutive_distances), 2)


def generate_city_coordinates(cities_count):
    axis_range = range(cities_count * 5)
    return tuple(zip(sample(axis_range, cities_count), sample(axis_range, cities_count)))


def calculate_distances(city_coordinates):
    result = []
    for city in city_coordinates:
        city_distances = []
        for other_city in city_coordinates:
            distance = odleglosci(city[0], city[1], other_city[0], other_city[1])
            city_distances.append(distance)
        result.append(city_distances)
    return result


if __name__ == '__main__':
    ilosc = int(input("Podaj ilosc miast:"))

    wielkosc = 10 * ilosc

    miasta = generate_city_coordinates(ilosc)

    domyslne = []  # domyslna sciezka
    domyslneniep = domyslne  # domyslne niepelne, bez powtorzonego pierwszego elementu na ostatnim miejscu
    for i in range(0, ilosc):
        domyslne.append(i)

    domyslne.append(domyslne[0])
    print("Domyslna sciezka:")
    print(domyslne)

    print("wspolrzedne miast:")
    print(miasta)

    print("odleglosci miedzy miastami:")
    wszodl = calculate_distances(miasta)  # wszystkie odleglosci
    pprint(wszodl)
    print("dlugosc domyslnej sciezki:")
    print(path_length(miasta, domyslne))

    tabu = []
    tabulen = []
    tabu.append(domyslne)

    iteracje = 6  # ilosc iteracji algorytmu TABU

    for i in range(1, iteracje):
        g = randint(0, ilosc - 1)
        j = randint(0, ilosc - 1)
        while (j == g):
            j = randint(0, ilosc - 1)  # dwie rozne wartosci, do zamieniania na liscie
        print("G:", g, "J:", j)
        nowatablica = domyslneniep
        nowatablica[g], nowatablica[j] = nowatablica[j], nowatablica[g]
        ost = int(len(nowatablica)) - 1
        nowatablica[ost] = nowatablica[0]
        print(nowatablica)
        print(path_length(miasta, nowatablica))

Answer 1

好吧，我想好了。下面是声明tabu table时要替换的正确代码

tabu = []
tabuval = []        #wartosci tabi
print(len(tabuval))
tabu.append(domyslne)           #([domyslne,(path_length(miasta, domyslne))])
tabuval.append(path_length(miasta,domyslne))
iteracje = 10000  # ilosc iteracji algorytmu TABU

for i in range(1, iteracje):
    g = randint(0, ilosc - 1)
    j = randint(0, ilosc - 1)
    while (j == g):
        j = randint(0, ilosc - 1)  # dwie rozne wartosci, do zamieniania na liscie
    #print("G:", g, "J:", j)
    nowatablica = domyslneniep
    nowatablica[g], nowatablica[j] = nowatablica[j], nowatablica[g]
    ost = int(len(nowatablica)) - 1
    nowatablica[ost] = nowatablica[0]
    #print("twoja nowa tablica:",nowatablica)
    x = path_length(miasta, nowatablica)
    if (len(tabu)<5):
        tabu.append(nowatablica[:])
        #print(tabu)
        #print(x)
        tabuval.append(x)
    elif (len(tabu) == 5 and x < max(tabuval)):
        if nowatablica in tabu:
            pass
        else:
            poz = tabuval.index(max(tabuval))
            tabu[poz] = nowatablica
            tabuval[poz] = x
print(tabu)
print(tabuval)
optpoz = tabuval.index(min(tabuval))
print("Najoptymalniejsza znaleziona sciezka to:", tabu[optpoz])
print("Jej dlugosc to:", tabuval[optpoz])