软时间约束的TSP问题_greatdajiezi的博客-程序员秘密

技术标签：笔记软时间约束TSP

软时间约束的TSP问题

一、问题简化

l: 城市数

：从城市i到城市j的运输成本

：0-1变量，0代表路线中没有i->j,1代表有

：从i->j花费时间

：到达j的时间

: 规定允许到达j的最早时间

：规定允许离开j的最晚时间

: 早到，等待时间惩罚值

: 晚到，推迟时间惩罚值

目标函数：

注：中第一部分：不考虑约束的成本；第二部分：早到的惩罚项；第三部分：晚到惩罚项

二、算法介绍

1. Memetic算法

与遗传算法类似，但在交叉和变异步骤增加了局部搜索。加速了迭代速度，每次求出较优解，优化种群结构，可以避免早熟现象，但有可能陷入局部最优。可以通过调整变异操作进行优化。

2. 编码方式

采取排列编码，如{3，1，4，5，2，（3）}代表5个城市的经历顺序。

3. 适应度函数设计

目标函数要取的是最小值。那么我们的适应度函数可以设计为：

或

用第一种设计时maxvalue不方便设置，因为根据不同单位有可能本身就有很大的值出现；推荐使用第二种设计，因为实际的TSP问题中权值都是正值，所以都是正值，此时c可以随意取。

4. 交叉变异策略

单点交叉：选择一个交叉点，子代的从初始位置出发的部分从一个基因复制，然后在另一个基因中扫描，如果某个位点在子代中没有，就把它添加进去。如：
部分匹配交叉：先随机产生两个交叉点，定义这两点间的区域为匹配区域，并用交换两个父代的匹配区域。
顺序交叉：从父代Ａ随机选一个编码子串，放到子代Ａ的对应位置；子代Ａ空余的位置从父代Ｂ中按Ｂ的顺序选取（与己有编码不重复），同理可得子代Ｂ。即单点交叉→两点交叉
循环交叉：CX同OX交叉都是从一个亲代中取一些城市，而其它城市来自另外一个亲代，但是二者不同之处在于：OX中来自第一个亲代的编码子串是随机产生的，而CX却不是，它是根据两个双亲相应位置的编码而确定的。

由于顺序交叉可以有效得保留父代一部分序列并且融合不同序列得有序结构，推荐使用顺序交叉法。

变异操作：以概率任取两个节点进行交换。

5. 局部搜索策略

Step1: 设置参数P，生成随机数p=random(0,1)

Step2: 若p < P , 使用贪婪法（可以使用贪婪倒位算子）进行局部搜索优化；否则，使用递归弧插入算子进行局部优化。

Step3：改变参数P来调节两种算子权重，回到第一步

注：贪婪倒位算子：如一个体I={ 6，5，3，7，2，4，1，9，8,(6)}

随机选择一个城市，如选取了3，与3相邻的是5和7，取二者中距离3较远者比如是5.
从与3不相邻的城市中选择与之最接近的城市，比如是1
对所选取的两个城市节点相邻（不含3）的编码进行倒位，得到新的个体I’={ 9，1，3，7，2，4，5，6，8,(6)}

递归弧插入算子：同样假设个体为{6，5，3，7，2，4，1，9，8,(6)}

i（这里是6）为初始节点，选取另一节点j满足j ≠ i.next，比如选择了2；设置count=0
调整顺序使i与j相连，删去6->5,7->2即删去i的下个节点a，j的上个节点b，并使i成为j的下个节点. 计算 ,并设置count=count+1.
再从j~i之间的节点上选择两个节点（m,n）≠（i，j），比如这里选择了（1，8），满足 $\triangle _{1}>\triangle _{2}$ ,其中 $\triangle _{2}=c_{ma}+c_{bn}-c_{mn}$ .如果成功找到了（m,n），就进入步骤d；否则进入步骤e.
连接（i,j）,(m,a),(b,n),删除（i,a），（b,j），（m,n）,此时个体变为{i,j,…,m,a,..,b,n,…,(i)}. 比如如果上述假设步骤的各个节点满足，此时个体变为{6,2,4,1,5,3,7,8,(6)}
若count=2，则终止调整，返回个体（认为是最优）；否则返回步骤b重新调整

本文链接：https://blog.csdn.net/greatdajiezi/article/details/89493630

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

【transformer】【pytorch】TransFG代码【Scheduler.py】_transfgu代码解读_剑宇2022的博客-程序员秘密

LambdaLR类：torch.optim.lr_scheduler作用是，可以自定义学习率学习曲线，官方代码如下：lass LambdaLR(_LRScheduler): """Sets the learning rate of each parameter group to the initial lr times a given function. When last_epoch=-1, sets initial lr as lr. Args: optim

Unity学习踩坑_wuyunxi的博客-程序员秘密

using UnityEngine;using System.Collections.Generic;public class MapManager : MonoBehaviour { public GameObject[] OutWallArray; public GameObject[] FloorArray; public GameObject[] wallArray; pu

安装mysqldb遇到c1083问题的解决办法_whorus1的博客-程序员秘密

今天帮同事部署Monkey平台的测试环境，部署完成后执行分析日志的脚本时总是报错，后来发现是由于他的电脑上没有安装mysqldb。于是安装mysqldb，但是在build的过程中总是报错，报错信息如下： _mysql.c(34) : fatal error C1083: Cannot open include file: ‘config-win.h’: No such file or di

PC端对应手机端网页面的脚本_weixin_33770878的博客-程序员秘密

为什么80%的码农都做不了架构师？>>> ...

Spring Boot 中文乱码问题解决方案汇总_weixin_33971977的博客-程序员秘密

使用 Spring Boot 开发，对外开发接口供调用，传入参数中有中文，出现中文乱码，查了好多资料，总结解决方法如下：第一步,约定传参编码格式不管是使用httpclient，还是okhttp，都要设置传参的编码，为了统一，这里全部设置为utf-8第二步，修改application.properties...

Java生成缩略图开源项目Thumbnailator_小飞鹤的博客-程序员秘密

Thumbnailator 是一个为Java界面更流畅的缩略图生成库。从API提供现有的图像文件和图像对象的缩略图中简化了缩略过程，两三行代码就能够从现有图片生成缩略图，且允许微调缩略图生成，同时保持了需要写入到最低限度的代码量。同时还支持根据一个目录批量生成缩略图。 http://code.google.com/p/thumbnailator/ 版本：thumbnailator-