TS禁忌搜索算法求解TSP问题(Java实现)
2021/7/27 11:06:19
本文主要是介绍TS禁忌搜索算法求解TSP问题(Java实现)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
文章目录
- 一、TSP问题
- 二、禁忌搜索算法
- 1.算法简介
- 2.算法思路
- 3.终止条件
- 4.算法图解
- 5.Java代码
- 总结
- 1.算法优缺点
- 2.改进建议
一、TSP问题
TSP问题（Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题可以分为两类，一类是对称TSP问题（Symmetric TSP），另一类是非对称问题（Asymmetric TSP）。所有的TSP问题都可以用一个图（Graph）来描述：
二、禁忌搜索算法
1.算法简介
禁忌（Tabu Search）算法是一种亚启发式(meta-heuristic)随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。
2.算法思路
1、在搜索中，构造一个短期循环记忆表-禁忌表，禁忌表中存放刚刚进行过的 |T|（T称为禁忌表）个邻居的移动，这种移动即解的简单变化。
2、禁忌表中的移动称为禁忌移动。对于进入禁忌表中的移动， 在以后的 |T| 次循环内是禁止的，以避免回到原来的解，从而避免陷入循环。|T| 次循环后禁忌解除。
3、禁忌表是一个循环表，在搜索过程中被循环的修改，使禁忌表始终保持 |T| 个移动。
4、即使引入了禁忌表，禁忌搜索仍可能出现循环。因此，必须给定停止准则以避免出现循环。当迭代内所发现的最好解无法改进或无法离开它时，算法停止。
3.终止条件
1.禁忌对象：可以选取当前的值（cur）作为禁忌对象放进tabu list，也可以把和当前值在同一“等高线”上的都放进tabu list。
2.为了降低计算量，禁忌长度和禁忌表的集合不宜太大，但是禁忌长度太小容易循环搜索，禁忌表太大容易陷入“局部极优解”。
3.上述程序段中对best_so_far的操作是直接赋值为最优的“解禁候选解”，但是有时候会出现没有大于best_so_far的，候选解也全部被禁的“死锁”状态，这个时候，就应该对候选解中最佳的进行解禁，以能够继续下去。
4.终止准则：和模拟退火，遗传算法差不多，常用的有：给定一个迭代步数；设定与估计的最优解的距离小于某个范围时，就终止搜索；当与最优解的距离连续若干步保持不变时，终止搜索；
5.邻域：系统总是在初始点的邻域搜索可能解的,因而必须定义适合的邻域空间,如果解空间存在一个最优解X*,初始搜索点为S0,那么如果S0不存在到达X*的通路,就会使搜索陷入S0的邻域的局部最优解。可以证明如果邻域满足对称性条件，则在假设禁忌表足够长的情况下必然可搜索到全局最优解。
4.算法图解
5.Java代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
/*
** Create by: WSKH
Date:2021-07-26
Time:20:27
*/
public class TabuSearchAlgorithm_TSP {
public final int MAX_GEN = 3000;//最大的迭代次数(提高这个值可以稳定地提高解质量，但是会增加求解时间)
public final int N = 100;//每次搜索领域的个数(这个值不要太大，太大的话搜索效率会降低)
public final int len = 20;//禁忌长度
public int cityNum ;//城市数量，手动设置
public int[][] tabooList;//禁忌表
public int[] Ghh;//初始路径编码
public int[] bestGh;//最好的路径编码
public int[] LocalGh;//当前最好路径编码
public int[] tempGh;//存放临时编码
public double[][] dist;//距离矩阵
public int bestT;//最佳的迭代次数
public double bestEvaluation;//最优解
public double LocalEvaluation;//每次领域搜索的最优解（领域最优解）
public double tempEvaluation;//临时解
public List<Integer[]> pointList = new ArrayList<>();//每个城市的坐标
public int t;//当前迭代
public Random random;//随机函数对象
public int l = 0;//当前禁忌表长度
//外部调用接口
public void Run() throws Exception {
long startTime = System.currentTimeMillis();
initVar();
TabuSearch();
long endTime = System.currentTimeMillis();
System.out.println("求解用时："+(endTime-startTime)/1000.0+"秒");
}
//禁忌搜索主函数
public void TabuSearch(){
//开始迭代，停止条件为达到指定迭代次数
while (t<=MAX_GEN){
//当前领域搜索次数
int n = 0;
LocalEvaluation = Double.MAX_VALUE;
while (n <= N){
//得到当前编码Ghh的邻居编码tempGh
tempGh = generateNewGh(Ghh.clone(),tempGh.clone());
//判断其是否在禁忌表中
if(!judge(tempGh)){
//如果不在
tempEvaluation = evaluate(tempGh);
if(tempEvaluation < LocalEvaluation){
//如果临时解优于本次领域搜索的最优解
//那么就将临时解替换本次领域搜索的最优解
LocalGh = tempGh.clone();
LocalEvaluation = tempEvaluation;
}
n++;
}
}
if(LocalEvaluation < bestEvaluation){
//如果本次搜索的最优解优于全局最优解
//那么领域最优解替换全局最优解
bestT = t;
bestGh = LocalGh.clone();
bestEvaluation = evaluate(bestGh);
}
Ghh = LocalGh.clone();
//加入禁忌表
enterTabooList(LocalGh.clone());
t++;
//System.out.println("第"+t+"代：bestEvaluation = "+bestEvaluation);
}
//求解完毕
System.out.println("最佳迭代次数:"+bestT);
System.out.println("最佳长度为:"+bestEvaluation);
System.out.println("最佳路径为:");
for (int i = 0; i < bestGh.length; i++) {
System.out.print(bestGh[i]+"-->");
}
System.out.println(bestGh[0]);
}
//加入禁忌队列
public void enterTabooList(int[] tempGh){
if(l<len){
//如果当前禁忌表还有空位，则直接加入即可
tabooList[l] = tempGh.clone();
l++;
}else{
//如果禁忌表已经满了，则移除第一个进表的路径，添加新的路径到禁忌表末尾
//后面的禁忌编码全部向前移动一位，覆盖掉当前第一个禁忌编码
for (int i = 0; i < tabooList.length-1; i++) {
tabooList[i] = tabooList[i+1].clone();
}
//将tempGh加入到禁忌队列的最后
tabooList[tabooList.length-1] = tempGh.clone();
}
}
//判断路径编码是否存在于禁忌表中
public boolean judge(int[] tempGh){
int count = 0;
for (int i = 0; i < tabooList.length; i++) {
for (int j = 0; j < tabooList[i].length; j++) {
if(tempGh[j]!=tabooList[i][j]){
count++;
break;
}
}
}
return count!=tabooList.length;
}
//领域交换，生成新解(随机指定数组中的两个数，不包括首尾，然后让这两个数进行位置互换，达到生成一个新路线的作用)
public int[] generateNewGh(int[]Gh,int[]tempGh) {
int temp;
//将Gh复制到tempGh
tempGh = Gh.clone();
int r1 = 0;
int r2 = 0;
这段代码(r1==0||r2==0)是为了保证起点不受改变，如果有固定的起点的话，可以使用这几行代码
// while (r1==r2||(r1==0||r2==0)){
// r1 = random.nextInt(cityNum);
// r2 = random.nextInt(cityNum);
// }
while (r1==r2){
r1 = random.nextInt(cityNum);
r2 = random.nextInt(cityNum);
}
//交换
temp=tempGh[r1];
tempGh[r1]=tempGh[r2];
tempGh[r2]=temp;
return tempGh.clone();
}
//生成一个初始解
public int[] getInitGh() throws Exception {
//固定起点为地点数组的第一个元素
Ghh[0] = 0;
//记录已生成的点
List<Integer> indexList = new ArrayList<>();
indexList.add(0);
//随机生成其余点
for (int i = 1; i < Ghh.length; i++) {
while (true){
int r = random.nextInt(cityNum);
if(!indexList.contains(r)){
//只有当地点不重合时才添加进列表，保证初始解中没有重复的地点
indexList.add(r);
Ghh[i] = r;
break;
}
}
}
System.out.println("初始解："+Arrays.toString(Ghh));
return Ghh.clone();
}
//计算两点之间的距离（使用伪欧氏距离，可以减少计算量）
public double getDistance(Integer[] place1,Integer[] place2){
//伪欧氏距离在根号内除以了一个10
return Math.sqrt((Math.pow(place1[0]-place2[0],2)+Math.pow(place1[1]-place2[1],2))/10.0);
//return Math.sqrt((Math.pow(place1[0]-place2[0],2)+Math.pow(place1[1]-place2[1],2)));
}
//初始化变量
public void initVar() throws Exception {
cityNum = pointList.size();//城市数量为点的数量
tabooList = new int[len][cityNum];//禁忌表
Ghh = new int[cityNum];//初始路径编码
bestGh = new int[cityNum];//最好的路径编码
LocalGh = new int[cityNum];//当前最好路径编码
tempGh = new int[cityNum];//存放临时编码
dist = new double[cityNum][cityNum];//距离矩阵
//初始化距离矩阵
for (int i = 0; i < dist.length; i++) {
for (int j = 0; j < dist[i].length; j++) {
if(i==j){
//对角线为0
dist[i][j] = 0.0;
}else{
//计算i到j的距离
dist[i][j] = getDistance(pointList.get(i),pointList.get(j));
}
}
}
//初始化参数
bestT = 0;
t = 0;
random = new Random(520);
Ghh = getInitGh();
//复制当前路径编码给最优路径编码
tempGh = Ghh.clone();
bestGh = tempGh.clone();
bestEvaluation = evaluate(bestGh);
tempEvaluation = evaluate(tempGh);
LocalEvaluation = Double.MAX_VALUE;
}
//评价函数
public double evaluate(int[] path){
double pathLen = 0.0;
for (int i = 1; i < path.length; i++) {
//起点到终点途径路程累加
pathLen += dist[path[i-1]][path[i]];
}
//然后再加上返回起点的路程
pathLen += dist[path[0]][path[path.length-1]];
return pathLen;
}
}
--------------------------------------------------------------------------
结果展示：
（一）不固定起点：
初始解：[0, 21, 33, 13, 46, 36, 14, 40, 12, 6, 34, 44, 2, 35, 43, 38, 26, 15, 23, 42, 17, 25, 39, 32, 22, 19, 29, 20, 45, 7, 31, 4, 11, 47, 1, 8, 28, 37, 10, 3, 18, 30, 5, 24, 27, 41, 16, 9]
最佳迭代次数:2844
最佳长度为:12206.89917444571
最佳路径为:
40-->15-->21-->2-->33-->28-->4-->47-->41-->9-->34-->44-->23-->31-->38-->20-->12-->46-->19-->32-->45-->35-->5-->36-->18-->16-->26-->42-->29-->27-->6-->17-->43-->30-->37-->8-->7-->0-->39-->14-->11-->10-->22-->13-->24-->25-->3-->1-->40
求解用时：0.227秒
（二）固定起点
初始解：[0, 21, 33, 13, 46, 36, 14, 40, 12, 6, 34, 44, 2, 35, 43, 38, 26, 15, 23, 42, 17, 25, 39, 32, 22, 19, 29, 20, 45, 7, 31, 4, 11, 47, 1, 8, 28, 37, 10, 3, 18, 30, 5, 24, 27, 41, 16, 9]
最佳迭代次数:2679
最佳长度为:11883.359590041817
最佳路径为:
0-->7-->21-->15-->40-->28-->1-->25-->3-->34-->44-->9-->23-->41-->4-->47-->33-->2-->39-->14-->27-->5-->36-->18-->16-->26-->42-->29-->19-->46-->20-->31-->38-->12-->24-->13-->22-->10-->11-->32-->45-->35-->6-->17-->43-->30-->37-->8-->0
求解用时：0.193秒
补充：以上使用的是tsplib上的数据att48，这是一个对称TSP问题，城市规模为48，其最优值为10628。tsplib地址：http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/
总结
1.算法优缺点
优点：
1、容易理解，容易实现，具有较强的通用性；
2、局部开发能力强，收敛速度很快。
3.相比于数学规划，动态规划等精确算法而言，在大规模问题上具有更好的
效果。
缺点：
1、全局开发能力弱，只能搜索到局部最优解；
2、搜索结果完全依赖于初始解和邻域的映射关系。
2.改进建议
禁忌搜索算法是一种随机算法，其求解带有偶然性，可以通过启发式的生成新解规则，来提高算法随机求解的效率，常见的有贪婪规则，精英规则等。
注：参考链接
[1] https://blog.csdn.net/cc098818/article/details/99869166
[2] https://blog.csdn.net/wangqiuyun/article/details/8816463
[3] https://baike.baidu.com/item/%E7%A6%81%E5%BF%8C%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95/6436980?fr=aladdin
这篇关于TS禁忌搜索算法求解TSP问题(Java实现)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-12-23线下车企门店如何实现线上线下融合？
- 2024-12-23鸿蒙Next ArkTS编程规范总结
- 2024-12-23物流团队冬至高效运转，哪款办公软件可助力风险评估？
- 2024-12-23优化库存，提升效率：医药企业如何借助看板软件实现仓库智能化
- 2024-12-23项目管理零负担！轻量化看板工具如何助力团队协作
- 2024-12-23电商活动复盘，为何是团队成长的核心环节？
- 2024-12-23鸿蒙Next ArkTS高性能编程实战
- 2024-12-23数据驱动：电商复盘从基础到进阶！
- 2024-12-23从数据到客户：跨境电商如何通过销售跟踪工具提升营销精准度？
- 2024-12-23汽车4S店运营效率提升的核心工具
