根据应用场景,假设对多个木板执行一样的打孔操作,那么当对一块模板完成任务后不需要再返回起始点,可以逆着规划航路直接打孔,回到起始点后可以再完成下一木板的打孔操作,提高应用效率。这种应用情形和TSP问题不一样的地方是路径不闭环,最后不需要直接回到起始点。
基本蚁群算法最早是用来求网络中的最短回路的,因此可以通过增加一个连接网络输入节点与输出节点的虚边,在搜索过程中规定必须经过虚边,变遍历所有节点的最短路径问题为最短回路问题。根据蚁群算法的搜索原理,设虚边的权小于或等于网络所有边权的最小值即可符合上述要求。
本文引入出发点和目标点间的虚边,在搜索过程中要求必须经过虚边,变遍历所有节点的最短路径问题为最短回路问题,设虚边的权小于或等于网络所有边权的最小值。
可行性分析
为客观地验证多任务孔的路径规划系统的有效性,评价路径规划系统中算法的性能和优缺点,本文针对路径规划系统的环境模型、两孔之间的路径规划和多任务孔间的路径规划算法进行验证。
本文主要使用Python语言对算法进行快速实现,Python语言开发效率优于C++语言,可以快速实现和验证算法的优缺点,但是Python是解释型语言,运行效率慢。C++语言一般是Python运行效率的5~10倍,所以Python语言的运行时间除以5,一般不小于C++语言的实现时间。
遍历所有节点的最短路径仿真结果
3维的最短路径仿真结果
本文提供上述仿真的源代码,因为目前实现的代码是一种比较理想的场景,和实际应用场景仍有比较大的差距,希望提出建议,共同完善!附github上的源代码 下一步优化
在路径规划问题抽象模型基础上,本文利用蚁群算法求解遍历所有任务孔的最短路径。基本蚁群算法在处理该类问题时会出现收敛速度慢且容易陷入局部最优解的缺陷,下一步可以对信息素和信息素挥发系数进行了改进,采用一种动态自适应调整信息素和挥发因子的蚁群算法,以求在路径规划方面获得更好的效果。
在“改进的智能蚁群算法在TSP问题中的应用”文献中,动态自适应调整信息素和挥发因子的策略可以描述为:传统蚁群算法中,往往会出现信息素分布过度集中在某一条路径,使得大多数蚂蚁仅通过此一条路径,导致早熟的现象;或者是信息素分布过度分散到各个路径中,使得蚂蚁搜索最优路径耗时相对较长而减缓收敛速度。本文采用自适应的信息素调节机制,使得信息素分布相对均匀,从而使算法跳离局部最优解。另外,信息素挥发系数直接关系到蚁群算法的全局搜索能力及其收敛速度,动态调整信息素挥发系数具有很明显优势,不仅可以加快收敛速度,而且能够提高搜索质量。
在三维路径规划中,点与点之间的最短路径实现效率相对较低,可以优化启发式函数,采用C++语言实现,提高运算速度。