python用禁忌搜尋算法實作TSP旅行商問題

使用python禁忌搜尋算法實作TSP旅行商問題

計算智能課程作業，使用python實作禁忌搜尋算法實作TSP旅行商問題

問題簡介：

給定一系列城市和每對城市之間的距離，求解通路每一座城市一次并回到起始城市的最短回路。它是組合優化中的一個NP困難問題。

代碼如下：

#!/usr/bin/python
#_*_ coding:utf-8 _*_  
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.mlab import dist
from matplotlib.artist import getp
import copy
from test.test__locale import candidate_locales
from cProfile import run


#初始三十個城市坐标
city_x = [41,37,54,25,7,2,68,71,54,83,64,18,22,83,91,25,24,58,71,74,87,18,13,82,62,58,45,41,44,4]
city_y = [94,84,67,62,64,99,58,44,62,69,60,54,60,46,38,38,42,69,71,78,76,40,40,7,32,35,21,26,35,50]
#城市數量
n = 30
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

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():
    global best_route
    global best_distance
    global tabu_time
    global current_tabu_num
    global current_distance
    global current_route
    global tabu_list
    #得到初始解以及初始距離
    #current_route = random.sample(range(0, n), n) 
    current_route = greedy()
    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

#交換數組兩個元素
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:
                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():
    getdistance()
    runtime = int(input("疊代次數："))
    setup()
    for rt in range(runtime):

        get_candidate()
        update_tabu()
    
    print("目前距離：")
    print(current_distance)
    print(current_route)
    print("最優距離：")    
    print(best_route)
    print(best_distance)
    draw()    
    
if __name__=="__main__":
    solve()
    
           

實作效果