松鼠TSP实验报告-10181
需积分: 0 103 浏览量
2022-08-08
22:02:39
上传
评论
收藏 75KB DOCX 举报
单目标松鼠 TSP 实验报告
背景：
单目标松鼠算法应用于 TSP 问题当中，首先应该解决的是，原来的松鼠算法主要应用
于解决连续性的函数问题，而对于 TSP 问题来说，问题的解应该是离散的，也就是说相较
于原来的连续的浮点数解来说，我们需要将松鼠的解修改为离散的字符串形式的城市路由路
径链，在这种背景下，我们需要对原来的松鼠算法进行修改，比如在松鼠的初始化过程中解
的初始化以及 fitness 值的计算，还有松鼠在跳跃过程中的自变量的变化方式（次优和普通
都与最优的交叉变异，最优不动），以及松鼠算法相较于原来的单目标函数型松鼠算法来说，
季节条件应该如何选择和控制（现在是 GA 的变异）。
解决思路：
通过参考相关的利用遗传算法来解决 TSP 问题的思路，我们对松鼠算法解决 TSP 问题
进行了以下的修改，如生成字符串形式的路径链来作为松鼠算法的算子，通过字符串的交换
来实现松鼠在跳跃过程当中的位置变化行为，通过类似于遗传算法的变异条件的设置将松鼠
算法的季节变化设定为随机性的取值行为。
问题：（再跑 7-8 个）
att48
实验结果：
理想情况：10628
Ps：由于时间问题这里的 SSA 使用的是 10000 代数据（甚至没有 10000 代，因为我也不知
道这货跑 10000 代得多长时间，大部分是我看差不多就停下来了），GA 使用的是 100000 代
数据，之所以不使用 10000 代，是因为 GA 够快，同时 10000 代跑出来的数据没法看，太烂
了，基本在 14000 左右
GA 算法表现
最佳长度五次
11398
11653
11451
11200
11364
SSA 算法表现：
最佳长度五次
11161
11230
11133
11330
11088（完全跑完了）
评论0