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

一时失言乱红尘 2022-12-22 11:24 200阅读 0赞

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()