单目标松鼠 TSP 实验报告
背景:
单目标松鼠算法应用于 TSP 问题当中,首先应该解决的是,原来的松鼠算法主要应用
于解决连续性的函数问题,而对于 TSP 问题来说,问题的解应该是离散的,也就是说相较
于原来的连续的浮点数解来说,我们需要将松鼠的解修改为离散的字符串形式的城市路由路
径链,在这种背景下,我们需要对原来的松鼠算法进行修改,比如在松鼠的初始化过程中解
的初始化以及 fitness 值的计算,还有松鼠在跳跃过程中的自变量的变化方式(次优和普通
都与最优的交叉变异,最优不动),以及松鼠算法相较于原来的单目标函数型松鼠算法来说,
季节条件应该如何选择和控制(现在是 GA 的变异)。
解决思路:
通过参考相关的利用遗传算法来解决 TSP 问题的思路,我们对松鼠算法解决 TSP 问题
进行了以下的修改,如生成字符串形式的路径链来作为松鼠算法的算子,通过字符串的交换
来实现松鼠在跳跃过程当中的位置变化行为,通过类似于遗传算法的变异条件的设置将松鼠
算法的季节变化设定为随机性的取值行为。
问题:(再跑 7-8 个)
att48
实验结果:
理想情况:10628
Ps:由于时间问题这里的 SSA 使用的是 10000 代数据(甚至没有 10000 代,因为我也不知
道这货跑 10000 代得多长时间,大部分是我看差不多就停下来了),GA 使用的是 100000 代
数据,之所以不使用 10000 代,是因为 GA 够快,同时 10000 代跑出来的数据没法看,太烂
了,基本在 14000 左右
这里的 att48 产生了变化,因为原来那个博主为了让他的数据能够好看一些,他在距离的计
算上做了点手脚,但是实际上对于 att48 两个算法表现都不够好。
评论0