计算智能-禁忌搜索算法求解旅行商问题研究

实现论文

《禁忌搜索算法求解旅行商问题研究》
链接：https://pan.baidu.com/s/1scdDvKvUviEVEeQC8fweRg
提取码:k38b

实验目的

旅行商问题(TSP) 是一类有代表性的已被证明具有 NPC 计算复杂性的组合难题 , 它的提法是 : 给定 N 个城市 , 有一旅行商从某一城市出发 , 访问各城市一次且仅有一次后回到原出发城市 , 要求找出一条最短 的巡回路径. 该问题等价于 N 个点的圆排列 , 其路径数为 (N - 1) ! / 2. 若按穷举法求解 , 即使用每秒运 算一亿次的巨型机对只有 20 个城市TSP 求解 , 也需搜索 350 年之久[1 ] . 由于 TSP 代表一类组合优化问 题 , 在实际工程中有许多应用 , 如电子地图、交通诱导、VLSI 单元布局、ATM 分组交换网等. 因此 , 利 用各种先进算法(如 SA 和 GA) 对 TSP 类似的问题进行求解就成为一个值得关注的问题. 事实上 , 只要能找到能用于实际问题的“亚优解”(Sub2Optimal Solution)即可. 禁忌搜索算法在这一领域中已显示出强大的优越性 , 正日益受到重视 , 它所得到的亚优解往往优于传统算法得到的局部极值解 , 加之搜索效率高 , 已受到广泛欢迎. 本文针对 TSP 问题的特点 , 设计了禁忌搜索算法的一种有效实现形式 , 实验表明 , 这一方法具有良好的收敛性和较高的搜索效率.

基本思路

禁忌搜索(Tabu Search ,简称 TS) 技术是一种亚启发式搜索技术[2 ] , 由 Glover 在 1986 年首次提出 , 进而形成一套完整算法[3 ,4 ] . 所谓禁忌就是禁止重复前面的工作. 为了回避局部邻域搜索陷入局部最优的主要不足 , 禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点 , 在下一次的搜索中 , 利用禁忌表中的信息不再或有选择地搜索这些点 , 以此来跳出局部最优点. 就好比人的短时记忆 , 走过的路不再重复或有选择地重复 ; 同时“遗忘”又使得这些禁止是弱禁止 , 即在一定的时间之后这些禁止将失效 , 最终达到全局优化之目的.

基本流程

(1) 解的领域映射为 22opt , 即固定起点城市 , 后面的每两个城市进行对换 , 邻域中的元素个数为 C2n + 1 ;
(2) 目标函数定义为巡回路径的城市间距离之和 , 目标函数亦作为评价函数 ;
(3) 禁忌对象定义为目标函数所求得的目标值 ;
(4) 禁忌长度(tabu-length) 随具体问题而定 ;
(5) 从邻域中选最佳的 tabu-length + 1 个元素作为候选集 ;
(6) 为提高解的质量 , 防止出现循环 , 应用了特赦规则. 本文的特赦规则定义为 : 当当前最优解未下降的次数超过给定值时 , 则特赦禁忌表中的最优解 , 将其作为下一次迭代的初始解 ;
(7) 终止规则为 : 程序运行超过给定最大迭代步数 , 或特赦次数超过给定最大特赦次数 ;
(8) 为增强搜索空间的多样性 , 本文应用了多初始点策略 , 即分别以每一个城市作为初始点进行搜索. 实验表明 , 能以较大概率达到最优解或亚优解.

代码实现

import random
import math

def N(x):
  data=x.copy()
  newdata=[]
  for i in range(1,len(data)-1):
    for j in range(i+1,len(data)):
      data[i],data[j]=data[j],data[i]
      newdata.append(data)
      data=x.copy()
  
  return newdata    


def f(data,coordinate):
  dis=0
  for i in range(1,len(data)):
    dis+=math.sqrt((coordinate[data[i]-1][0]-coordinate[data[i-1]-1][0])**2+\
                   (coordinate[data[i]-1][1]-coordinate[data[i-1]-1][1])**2)
  dis+=math.sqrt((coordinate[-1][0]-coordinate[0][0])**2+\
                   (coordinate[-1][1]-coordinate[0][1])**2)
  return dis

if __name__ == "__main__":
  coordinate=[[0.4 ,0.4439],[0.2439,0.1463],[0.1707,0.2293],[0.2293,0.7610],[0.5171,0.9414]\
              ,[0.8732,0.6536],[0.6878,0.5219],[0.8488,0.3609],[0.6683,0.2536],[0.6159,0.2623]]
  
  x=[i  for i in range(1,11)]
  random.shuffle(x)
  totalx=[]
  totalx.append(x)
  totaldis=[]
  totaldis.append(f(x,coordinate))
  dis=f(x,coordinate)
  teshe=10
  tesheflag=0
  flag=0
  time=100
  tabulength=5
  while flag<time:
    newdata=N(x)
    n=[]
    C=[]
    Cn=[]
    for i in range(len(newdata)):
      n.append(f(newdata[i],coordinate))
    for i in range(tabulength):
      C.append(newdata[n.index(min(n))])
      Cn.append(min(n))
      newdata.remove(newdata[n.index(min(n))])
      n.remove(min(n))
    newx=C[Cn.index(min(Cn))]
    totalx.append(newx)
    totaldis.append(f(newx,coordinate))
    if newx >= x :
      tesheflag+=1
    if tesheflag == 5:
      x=totalx[totaldis.index(min(totaldis))]
    else:
      x=newx.copy()
    dis=f(x,coordinate)
    flag+=1
  print("当前最优解:",x)
  print("距离为",dis)

实验结果