【算法】禁忌算法+TSP问题 python代码

news/2024/5/4 0:35:23/文章来源:https://blog.csdn.net/qq_51669241/article/details/129529728

一、禁忌算法的概念
二、相关名词解释
- 1、禁忌对象（Tabu Object，TO）
- 2、禁忌表（Tabu List，TL）
- 3、禁忌期限（Tabu Tenure，TT）
- 4、藐视准则（Aspiration Criteria，AC）
- 5、终止准则
三、算法基本流程
四、TSP问题
主要步骤：
python代码

一、禁忌算法的概念

禁忌搜索是属于模拟人类智能的一种优化算法，它模仿了人类的记忆功能，在求解问题的过程中，采用了禁忌技术，对已经搜索过的局部最优解进行标记，并且在迭代中尽量避免重复相同的搜索（但不是完全杜绝），从而获得更广的搜索区间，有利于寻找到全局最优解。
在这里插入图片描述

二、相关名词解释

1、禁忌对象（Tabu Object，TO）

指禁忌表中被禁的那些变化元素。
例如在旅行商问题（TSP）中可以将交换的城市对作为禁忌对象，也可以将总路径长度作为禁忌对象。

2、禁忌表（Tabu List，TL）

用来存放（记忆）禁忌对象的表。它是禁忌搜索得以进行的基本前提。禁忌表本身是有容量限制的，它的大小对存放禁忌对象的个数有影响，会影响算法的性能。

3、禁忌期限（Tabu Tenure，TT）

也叫禁忌长度，指的是禁忌对象不能被选取的周期。
禁忌期限过短容易出现循环，跳不出局部最优。
紧急期限过长会造成计算时间过长。

4、藐视准则（Aspiration Criteria，AC）

也称为特赦规则。当所有的对象都被禁忌之后，可以让其中性能最好的被禁忌对象解禁，或者当某个对象解禁会带来目标值的很大改进时，也可以使用特赦规则。

在这里插入图片描述

5、终止准则

三种方法：

给定最大迭代步数。
设定某个对象的最大禁忌频率。
设定适配值的偏离幅度。

在这里插入图片描述

三、算法基本流程

四、TSP问题

已知一个旅行商问题为四城市（a，b，c，d）问题，城市间的距离如矩阵D所示，为方便起见，假设邻域映射定义为两个城市位置对换，而始点和终点城市都是a。请分析使用禁忌搜索算法求解该问题的前面三代的过程与主要步骤。

在这里插入图片描述

主要步骤：

在这里插入图片描述

python代码

1、导入包。

import time
import numpy as np
import random

2、设置禁忌算法的参数数值。
禁忌长度为2。

# m城市个数  best全局最优  tl初始禁忌长度
# time 迭代次数, spe特赦值
# tabu禁忌表
# best_way 最优解 now_way当前解
# dis两点距离
global m, best, tl
global time, spe
best = 4.0
m= 4
tl = 2
spe= 2
time = 100
tabu = [[0] * (m) for i in range(m)]
best_way =[0] * m
now_way = [0] * m
dis = [[0] * (m) for i in range(m)]

3、生成初始解。

def rand(g):vis = [0]*mfor i in range(m):vis[i] = 0;g[0] = 0  # 必定要从第一个城市a出发vis[0] = 1on = 1while on < m:te = random.randint(1, m - 1) # 随机选择一个城市if(vis[te] == 0):vis[te] = 1g[on] = teon += 1

4、计算解t的路线长度。

def get_value(t):ans = 0.0for i in range(1, m):ans += dis[t[i-1]][t[i]]ans += dis[t[i-1]][t[i]]return ans

5、将当前解复制到最优解数组。

def cop(a,b):for i in range(m):a[i] = b[i]

6、初始化禁忌表，计算初始解的路径值。

def init():global bestfor i in range(m):for j in range(m):tabu[i][j] = 0  #初始化禁忌表rand(now_way)           #生成初始解作为当前解now = get_value(now_way)cop(best_way, now_way)best = now

7、禁忌算法。

def slove():global best, nowtemp = [0] * m       # 中间变量记录交换结果a = 0                # 记录交换城市下标b = 0ob_way = [0] * mcop(ob_way, now_way)ob_value = get_value(now_way)    # 暂存邻域最优解for i in range(1, m):            # 搜索所有邻域for j in range(1, m):if(i + j >= m): break;if(i == j): continue;cop(temp, now_way)temp[i], temp[i + j] = temp[i + j], temp[i]value = get_value(temp)if(value <= best and tabu[i][i + j] < spe): # 如果优于全局最优且禁忌长度小于特赦值cop(best_way, temp)best = valuea = ib = i + j         #更新全局最优且接受新解cop(ob_way, temp)ob_value = valueelif(tabu[i][i + j] == 0 and value < ob_value): # 如果优于邻域中的最优解则接受新解cop(ob_way, temp)ob_value = valuea = ib = i + jcop(now_way, ob_way)  # 更新当前解for i in range(m):    # 更新禁忌表for j in range(m):if(tabu[i][j] > 0):tabu[i][j] -= 1tabu[a][b] = tl  #重置a，b两个交换城市的禁忌值

8、主函数：

if __name__ == '__main__':dis = np.array([[0, 1, 0.5, 1],[1, 0, 1, 1],[1.5, 5, 0, 1],[1, 1, 1, 0]])init()                                # 数据初始化for i in range(time):                 # 控制迭代次数slove()print("路线总长度： ", round(best,3))   # 打印最优解距离保留三位小数print("具体路线： ", best_way)