## TPS——模拟退火算法
### 1.问题设置
编码选择:采用路径编码,即直接对路径进行编码(1,2,3,4,5...)
状态产生函数:采用互换操作,随机交换两个不同的位置。
使用状态接受函数,避免局部极小。
城市选取:在二维平面上随机产生【10】个点,作为十个城市。用两个点之间的直线距离,模拟两个城市之间的路径长度。
### 2.算法
算法步骤同作业一。
【算法步骤】
【1】给定初始温度,随机产生状态
【2】循环
【2.1】循环
【2.1.1】产生新的状态(在算法实现当中是随机产生)
【2.1.2】按概率选取该新解
【2.1.3】直到满足抽样稳定准则
【2.2】退温
【3】直到算法满足终止准则
【4】打印输出结果
### 3.实验
为了测试算法的稳定性和普遍性,固定十个点,某次初始化图下图所示。以是否达到最优衡量原则。
![](https://www.writebug.com/myres/static/uploads/2021/10/25/0fd7e82f99966f4a566092ed62f63272.writebug)
最优解图所示:
![](https://www.writebug.com/myres/static/uploads/2021/10/25/d5bff9d57773a559669cd2bf3cb35202.writebug)
对应的最优值:268.41249391617663
下面进行二十次实验:
| 实验次数 | 路径长度 | 是否最优 | 实验次数 | 路径长度 | 是否最优 |
| -------- | --------- | -------- | -------- | --------- | -------- |
| 1 | 268.41249 | 是 | 11 | 268.41249 | 是 |
| 2 | 282.22378 | 否 | 12 | 268.41249 | 是 |
| 3 | 268.41249 | 是 | 13 | 268.41249 | 是 |
| 4 | 268.41249 | 是 | 14 | 340.89995 | 否 |
| 5 | 268.41249 | 是 | 15 | 268.41249 | 是 |
| 6 | 311.08761 | 否 | 16 | 282.22378 | 否 |
| 7 | 289.77342 | 否 | 17 | 268.41249 | 是 |
| 8 | 268.41249 | 是 | 18 | 268.41249 | 是 |
| 9 | 268.41249 | 是 | 19 | 282.22378 | 否 |
| 10 | 268.41249 | 是 | 20 | 268.41249 | 是 |
结果统计:
| 平均性能 | 277.31035899999995 |
| -------- | ------------------ |
| 最佳性能 | 268.41249 |
| 最差性能 | 311.08761 |
| 方差 | 326.03503971499896 |
其中有几个不是最优值的,限在了局部最优,比如下面的情况:
![](https://www.writebug.com/myres/static/uploads/2021/10/25/6a959a19cbf6a03fb94a25817638e017.writebug)
### 4.典型变化曲线
![](https://www.writebug.com/myres/static/uploads/2021/10/25/a518a5e0060d935bc162c4c3b4b93e11.writebug)
### 5.最优解对应的解
![](https://www.writebug.com/myres/static/uploads/2021/10/25/c1c22350379101176e42daea9863cf66.writebug)
### 6.模拟退火在组合优化当中的特点
通过本次实验可以看出,模拟退火算法对初值不是很敏感,即随机初值都可以达到较好的优化结果。同时算法也具有很好的稳定性,随机分布的十个城市以及随机分布的初始解,都可以达到较好的优化效果。但本次实验也发现,算法对初始温度以及终止条件比较敏感。
### 7.实验体会
在运筹学当中动态规划的方法求积TSP问题,其计算过程类似于枚举,计算量很大。相比之下,使用智能优化算法,显著减小了计算量,且能在大多数情况下得到不错的解,这在实际问题求解当中是很有好处的。
没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
收起资源包目录
100012880-基于Python TPS模拟退火算法.zip (4个子文件)
tpsmaster
LICENSE 1KB
TSP.doc 164KB
SA-TSP.py 2KB
README.md 3KB
共 4 条
- 1
资源评论
神仙别闹
- 粉丝: 2676
- 资源: 7664
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功