禁忌搜索算法TSA 旅行商问题TSP python

import math

import random

import numpy as np

import matplotlib.pyplot as plt

from mpl_toolkits.mplot3d import Axes3D

import sys

from numpy.matlib import rand

from matplotlib.artist import getp

import copy

from test.test__locale import candidate_locales

from cProfile import run

import city

import scipy.stats as stats

def greedy():

    #通过贪婪算法确定初始r值，也就是初始信息素浓度

    sum = 0.0

    #必须实例化一个一个赋值，不然只是把地址赋值，牵一发而动全身

    dis = [[0 for col in range(n)] for raw in range(n)]

    for i in range(n):

        for j in range(n):

            dis[i][j] = distance[i][j]

    visited = []

        #进行贪婪选择——每次都选择距离最近的

    id = 0

    for i in range(n):

        for j in range(n):

            dis[j][id] = sys.maxsize

        minvalue = min(dis[id])

        if i != 29:

            sum += minvalue

        visited.append(id)

        id = dis[id].index(minvalue)

    sum += distance[0][visited[n-1]]

    return visited

#构建初始参考距离矩阵

def getdistance():

    for i in range(n):

        for j in range(n):

            x = pow(city_x[i] - city_x[j], 2)

            y = pow(city_y[i] - city_y[j], 2)

            distance[i][j] = pow(x + y, 0.5)

    for i in range(n):

        for j in range(n):

            if distance[i][j] == 0:

                distance[i][j] = sys.maxsize

#计算总距离

def cacl_best(rou):

    sumdis = 0.0

    for i in range(n-1):

        sumdis += distance[rou[i]][rou[i+1]]

    sumdis += distance[rou[n-1]][rou[0]]

    return sumdis

#初始设置

def setup(methods=1):

    global best_route

    global best_distance

    global tabu_time

    global current_tabu_num

    global current_distance

    global current_route

    global tabu_list

    #得到初始解以及初始距离

    if methods==1:

        current_route = greedy()

    else:

        current_route = random.sample(range(0, n), n)

    best_route = copy.copy(current_route)

    #函数内部修改全局变量的值

    current_distance = cacl_best(current_route)

    best_distance = current_distance

    #置禁忌表为空

    tabu_list.clear()

    tabu_time.clear()

    current_tabu_num = 0

    return current_distance

#交换数组两个元素

def exchange(index1, index2, arr):

    current_list = copy.copy(arr)

    current = current_list[index1]

    current_list[index1] = current_list[index2]

    current_list[index2] = current

    return current_list

#得到邻域候选解

def get_candidate():

    global best_route

    global best_distance

    global current_tabu_num

    global current_distance

    global current_route

    global tabu_list

    #存储两个交换的位置

    exchange_position = []

    temp = 0

    #随机选取邻域

    while True:

        current = random.sample(range(0, n), 2)

        #print(current)

        if current not in exchange_position:

            exchange_position.append(current)

            candidate[temp] = exchange(current[0], current[1], current_route)

            if candidate[temp] not in tabu_list:

                #print(temp)

                candidate_distance[temp] = cacl_best(candidate[temp])

                temp += 1

            if temp >= 200:

                break

    #得到候选解中的最优解

    candidate_best = min(candidate_distance)

    best_index = candidate_distance.index(candidate_best)

    current_distance = candidate_best

    current_route = copy.copy(candidate[best_index])

    #与当前最优解进行比较

    if current_distance < best_distance:

        best_distance = current_distance

        best_route = copy.copy(current_route)

    #加入禁忌表

    tabu_list.append(candidate[best_index])

    tabu_time.append(tabu_limit)

    current_tabu_num += 1    

#更新禁忌表以及禁忌期限

def update_tabu():

    global current_tabu_num

    global tabu_time

    global tabu_list

    del_num = 0

    temp = [0 for col in range(n)]

    #更新步长

    tabu_time = [x-1 for x in tabu_time]

    #如果达到期限，释放

    for i in range(current_tabu_num):

        if tabu_time[i] == 0:

            del_num += 1

            tabu_list[i] = temp

    current_tabu_num -= del_num

    while 0 in tabu_time:

        tabu_time.remove(0)

    while temp in tabu_list:

        tabu_list.remove(temp)

def draw():

    result_x = [0 for col in range(n+1)]

    result_y = [0 for col in range(n+1)]

    for i in range(n):

        result_x[i] = city_x[best_route[i]]

        result_y[i] = city_y[best_route[i]]

    result_x[n] = result_x[0]

    result_y[n] = result_y[0]

    print(result_x)

    print(result_y)

    plt.xlim(0, 100)  # 限定横轴的范围

    plt.ylim(0, 100)  # 限定纵轴的范围

    plt.plot(result_x, result_y, marker='>', mec='r', mfc='w',label=u'Route')

    plt.legend()  # 让图例生效

    plt.margins(0)

    plt.subplots_adjust(bottom=0.15)

    plt.xlabel(u"x") #X轴标签

    plt.ylabel(u"y") #Y轴标签

    plt.title("TSP Solution") #标题

    plt.show()

    plt.close(0)  

def solve(runtime=500):

    getdistance()

    setup()

    for i in range(runtime):

        get_candidate()

        update_tabu()

def TSA_TSP(runtime):

    '''遗传算法、禁忌搜索算法和微粒群算法收敛速度的对比'''

    getdistance()

    setup()

    a = []

    for j in range(runtime):

        get_candidate()

        update_tabu()

        a.append(best_distance)

    return a

def TSA_better(runtime):

    '''遗传算法、禁忌搜索算法和微粒群算法收敛速度的对比'''

    global tabu_limit

    getdistance()

    setup()

    a = []

    for j in range(runtime):

        tabu_limit = int(100*(j/runtime)+1)

        get_candidate()

        update_tabu()

        a.append(best_distance)

    return a

def main():

    global city_x, city_y, distance, n, tabu_limit, tabu_list, tabu_time, current_tabu_num, candidate, candidate_distance

    global best_route, best_distance, current_distance, current_route

    if(1):

        city_x = []

        city_y = []

        a = dict.values(city.china)

        a = list(a)

        for i in range(100):

            city_x.append(a[i][0])

            city_y.append(a[i][1])

        # 城市数量

        n = len(city_x)

        distance = [[0 for col in range(n)] for raw in range(n)]

        #禁忌表

        tabu_list = []

        tabu_time = []

        #当前禁忌对象数量

        current_tabu_num = 0

        #禁忌长度，即禁忌期限

        tabu_limit = 50

        #候选集

        candidate = [[0 for col in range(n)] for raw in range(200)]

        candidate_distance = [0 for col in range(200)]

        #最佳路径以及最佳距离

        best_route = []

        best_distance = sys.maxsize

        current_route = []

        current_distance = 0.0

        getdistance()

        setup()

    k = 6

    if k==1:

        '''不同初始样本对结果的影响'''

        init = []

        x = []

        y = []

        for i in range(20):

            print(i)

            getdistance()

            x.append(i)

            init.append(setup(methods=2))

            for epoch in range(500):

                get_candidate()

                update_tabu()

            y.append(best_distance)

        r,p = stats.pearsonr(init,y)  # 相关系数和P值

        print('相关系数r=%.3f,p值=%.3f'%(r,p))

        plt.figure(figsize = (6,6))  # 图片像素大小

        plt.scatter(init,y,color="blue")  # 散点图绘制

        plt.grid()  # 显示网格线

        plt.xlabel('init')

        plt.ylabel('result')

        plt.show()  # 显示图片

        plt.plot(x,init,color='blue',label='init_distance')

        plt.plot(x,y,color='red',label='result_distance')

        plt.xlabel('times')

        plt.ylabel('distance')

        plt.title('The effect of the initial route on the distance')

    elif k==2:

        '''禁忌表长度对于结果的影响'''

        x = []

        y = []

        for i in range(10,200,10):

            print(i)

            distance = [[0 for col in range(n)] for raw in range(n)]

            #禁忌表

            tabu_list = []

            tabu_time = []

            #当前禁忌对象数量

            current_tabu_num = 0

            #候选集

            candidate = [[0 for col in range(n)] for raw in range(200)]

            candidate_distance = [0 for col in range(200)]

            #最佳路径以及最佳距离

            best_route = []

            best_distance = sys.maxsize

            current_route = []

            current_distance = 0.0

            getdistance()

            setup()

            tabu_limit = i # 禁忌长度

            for j in range(2500):

                get_candidate()

                update_tabu()

            x.append(i)

            y.append(best_distance)

        plt.plot(x,y)

        plt.xlabel('Tabu_len')

        plt.ylabel('distance')

        plt.title('The effect of the length of tabu list on the distance')

    elif k==3:

        '''不同禁忌表长度的情况下的最佳迭代次数'''

        x = []

        y = []

        for i in range(1,21):

            distance = [[0 for col in range(n)] for raw in range(n)]

            #禁忌表

            tabu_list = []

            tabu_time = []

            #当前禁忌对象数量

            current_tabu_num = 0

            #候选集

            candidate = [[0 for col in range(n)] for raw in range(200)]

            candidate_distance = [0 for col in range(200)]

            #最佳路径以及最佳距离

            best_route = []

            best_distance = sys.maxsize

            current_route = []

            current_distance = 0.0

            getdistance()

            setup()

            tabu_limit = i*10

            best = []

            for epoch in range(25000):

                get_candidate()

                update_tabu()

                best.append(best_distance)

                if(epoch>500 and len(set(best[epoch-500:epoch]))==1):

                    break

            x.append(tabu_limit)

            y.append(epoch-500)

            print(tabu_limit,epoch-500)

        plt.plot(x,y)

        plt.xlabel('tabu_len')

        plt.ylabel('best_epochs')

        plt.title('The best number of epochs in different length of tabu list')

    elif k==4:

        '''遗传算法与禁忌搜索算法在不同迭代次数上的比较'''

        from 遗传TSP import GA_TSP

        i = 500

        epoch = [x for x in range(1,i+1)]

        plt.plot(epoch,TSA_better(i),color='red',label='Better')

        plt.plot(epoch,GA_TSP(epochs=i),color='blue',label='GA')

        plt.plot(epoch,TSA_TSP(i),color='red',label='TSA')

        plt.xlabel('epochs')

        plt.ylabel('distance')

        plt.title('The effect of the difference methods on the distance')

    elif k==5:

        '''禁忌长度自适应改进算法与标准算法的对比'''

        i = 1500

        epoch = [x for x in range(1,i+1)]

        plt.plot(epoch,TSA_TSP(i),color='blue',label='Simple')

        plt.plot(epoch,TSA_better(i),color='red',label='Better')

        plt.xlabel('epochs')

        plt.ylabel('distance')

        plt.title('The different arithmetic')

    elif k==6:

        '''遗传算法与禁忌搜索算法在不同城市规模上的比较'''

        epoch = []

        GA = []

        TSA = []

        for scale in range(20,151,10):

            from 遗传TSP import GA_TSP

            city_x = []

            city_y = []

            a = dict.values(city.china)

            a = list(a)

            for i in range(scale):

                city_x.append(a[i][0])

                city_y.append(a[i][1])

            # 城市数量

            n = len(city_x)

            distance = [[0 for col in range(n)] for raw in range(n)]

            #禁忌表

            tabu_list = []

            tabu_time = []

            #当前禁忌对象数量

            current_tabu_num = 0

            #禁忌长度，即禁忌期限

            tabu_limit = 50

            #候选集

            candidate = [[0 for col in range(n)] for raw in range(200)]

            candidate_distance = [0 for col in range(200)]

            #最佳路径以及最佳距离

            best_route = []

            best_distance = sys.maxsize

            current_route = []

            current_distance = 0.0

            getdistance()

            setup()

            epoch.append(scale)

            TSA.append(min(TSA_better(1000)))

            GA.append(min(GA_TSP(scale=scale,epochs=5000+scale*100)))

            print(scale)

        plt.plot(epoch,GA,color='blue',label='GA')

        plt.plot(epoch,TSA,color='red',label='TSA')

        plt.xlabel('city_scale')

        plt.ylabel('distance')

        plt.title('The effect of the scale of cities on the distance')

    plt.legend()

    plt.show()

if __name__=="__main__":

    main()

禁忌搜索算法TSA 旅行商问题TSP python的相关教程结束。