《基于蚁群算法的自动锁螺丝机路径优化方法》由会员分享，可在线阅读，更多相关《基于蚁群算法的自动锁螺丝机路径优化方法（9页珍藏版）》请在金锄头文库上搜索。
1、基于蚁群算法的自动锁螺丝机路径优化方法摘 要：文章是介绍蚁群算法的应用，随着自动化技术的高速发展，自动锁螺丝机也被广泛的使用，然而对螺丝锁付路径没有得到合理的利用，针对目前螺丝锁付机器对螺丝锁付路径没有进行合理规划的问题，使用传统蚁群算法对螺丝锁付路径进行优化， 结合实际应用问题，通过模拟实验的方式，去调整群算法的参数设置，得到比较优化的结果。并给出了螺丝锁付优化路径图；实验表明该针对锁付路径的合理布局，螺丝锁付效率得到显著提高。 关键词：路径优化；蚁群算法；锁螺丝机 Abstract： This paper is to introduces the application of ant co
2、lony algorithm in the field of automation. With the rapid development of automation technology， the automatic locking screw machine is widely used. However， the screw locking method has not been used rationally. The algorithm of the ant colony algorithm is used to optimize the screw locking path， an
3、d the method of simulation is used to adjust the parameter setting of the group algorithm， and the result of comparison optimization is obtained. And the optimal path of screw lock is given. The experiment shows that the efficiency of screw locking is improved greatly.Keywords： path optimization； an
4、t colony algorithm； lock screw machine 1 自动锁螺丝机路径问题描述 本文以 XY-table 型自动锁螺丝机为基准，设定每个螺?z孔为一个工位，则路径问题可以用数学图（Graph）来表示：V=c1，c2，c3，ci，cn；i=1，2，.n 是所有工位的集合，ci 表示第 i 个工位，n 表示工位的数目 E=（r，s）：r，sV；表示所有工位之间的集合； C=rrs：r，sV；是所有工位之间连接的成本度量（工位之间距离） 。 一个路径最优问题可以表达为： 求解遍历图 G=（V，E，C） ，所有的节点一次都回到起始节点，使得到连接这些节点路径成本最低1。 2
5、 蚁群算法简介 蚁群算法是对自然界蚂蚁的寻找路径的方式进行模拟得到的一个仿生物算法，是由意大利学者 Marco Dorigo， Vittorio Maniezzo， Alberto Colorni 提出的一种模拟进化算法。 图 1 所示，一个真实的蚁群从蚁巢出发到寻找食物的最佳路程，不论有无障碍，蚁群总是可以找到从最优的路径。 （a）没有蚂蚁从 A 到 F（b）有障碍物的情况，蚂蚁到障碍物有不同的选择，而且选 B 或者选 C 是等概率的 （c）更多的蚂蚁选择 B 到目的。 蚂蚁在运动的过程中，可以在它自己所经过的路径一种信息传递的物质，被称之为信息素（pheromone）2是一种生物学激素，另
6、外一蚂蚁同样可以感知到这种生物学激素，并且指导蚁群行进的方向。因此，大量的蚂蚁组成的这种群体行为可以表现出一种信息正反馈，当某一路径的蚂蚁越多，信息素浓度越大，被后续蚂蚁感知的概率就越高，因此选择该路径的直到整个种群找到最佳的路径。 为了更清晰的解释蚁群算的原理，先模拟一下蚂蚁搜索食物的具体过程。以图 2 为例说明，蚂蚁搜索食物的过程，信息素的浓度变化的过程，同时也是算法模拟的核心部分。 图 2 所示，ABF、ACF 都表示蚂蚁的行进路程并且设定ACF 的路程是 ABF 的两倍， （a）表示单次行走， （b）表示一个来回的示意图。设定每只蚂蚁的速度相同，目的地在 F，蚂蚁从 A 点出发可以选择
7、 A-B-F 或 A-C-F 路径。 设定以相同的时间行每一步， （a）图中，蚂蚁从 A 出发走 ABF 路线时，时间到达目的 F 用时记为 1 个单位时间，而走 ACF 路线同样的单位时间到 C，只走完路程的一半。经过 2 倍单位时间的情况，走 ABF 路线的蚂蚁到达终点拿到食物又返回蚁巢，而走 ACF 路线的蚂蚁到达目的地。设定每只蚂蚁经过一处所留下的信息素为一个单位。经过 4 个单位时间后，所有从 A 出发的蚂蚁都取到食物并且返回，此时 ABF 路径已经往返了两次，每一处留下的信息素为 4个单位，而经过 ACF 路线值往返了一趟，每一处的信息素为 2 个单位，其比值为 2：1。寻找食物的
8、过程继续进行，蚁群在 A 处派出蚂蚁，按照信息素的指导，ABF 路线增加一只（共 2 只） ，ACF 上仍未一只，再次进 4 个时间单位，ABF和 ACF 两条路径的信息素单位累计为 12 和 4，比值为3：1，按照以上规则继续，ABF 上增一只（共 3 只）而且ACF 上仍然只有一只，再次经过 4 个时间单位，信息素的比值会变成 4：1。继续进行，最终所有的蚂蚁会放弃 ACF 路线，而选择 ABF 路线。这个就是信息素的正反馈效应3。 3 算法的应用 假定算法中需要用到的机器蚂蚁数量为 m，并且每个蚂蚁都用自己的内存，内存中有一个禁忌表（Tabu）用来存储蚂蚁已经到访过的位置，表示在以后的搜
9、索中将不再会访问禁忌表中的标记，同时还有一个允许访问的工位标记表（Allowed）来存储蚂蚁可以访问的工位；另外还有一个矩阵（Delta）用来存储蚂蚁在一个循环中所经过的路径的信息素，所有工位之间的信息素用矩阵 pheromone 表示。最短路径 bestLength，最佳路径为 bestPath；设定 NC_max为最大迭代次数。 3.1 初始化过程 设定在开始时刻，bestLength 初始化为一个非常大的数（正无穷）4，bestPath 数组为空。Allowed 表中加入所有的工位节点并且设置所有蚂蚁的 Delta 矩阵为 0，Tabu表为空。随机选取它们的起始位置，在 Tabu 表中加
10、入初始工位（随机选取）节点，并且 Allowed 中去掉该节点。 3.2 算法在运行时选择下一个节点 算法要求遍历每个工位节点，选择下一个节点只能从Allowed 表中某一概率（公式 1）搜索到，每次选择到哪个工位节点，则把该工位节点加入到 Tabu 表，同时也必须从Allowed 表中删除该节点，对于每只机器蚂蚁来说该过程重复（n-1）次，遍历所有的节点。此时，将初始节点加入到Tabu（禁忌）表中，Tabu 表中这个时候的元素个数为n+1（n 位螺丝孔个数） ，Allowed 表中的标记全部清空，不允许任何节点被访问。 下一步按照（公式 2）计算每只机器蚂蚁的 Delta 矩阵值并保存，最后
11、计算出最佳路径，先比较每个蚂蚁的路径长短，然后和 bestLength 比较，如果其长度比 bestLength 小，则需要把该值赋值给bestLength，并且把 Tabu（禁忌）赋值给 BeatPath，即为最佳路径8911。 3.4 结束条件 如果达到最大代数 MAX_GEN，算法终止，转到第（5）步（输出最优值） ；否则，重新初始化所有的蚂蚁的 Delt矩阵所有元素初始化为 0，Tabu 表清空，Allowed 表中加入所有的城市节点10。随机选择它们的起始位置（也可以人工指定） 。在 Tabu 中加入起始节点，Allowed 中去掉该起始节点，重复执行（2） ， （3） ， （4）步
12、。 4 蚁群算法流程图 如图 3 所示，蚁群算法的简要流程： 5 基于蚁群算法对螺丝锁付路径的优化模拟 为了提高自动锁螺丝机的锁付效率，节省锁付时间，现使用蚁群遗传算法对自动螺丝机锁付的工件的 30 个螺丝孔螺丝路径进行路径优化，其中 30 个螺丝孔的工位坐标为 45.2，14.15；76.85，9.49；107.42，18.4；178.31，130.62； 140.6，10.33；168.74，9.11；175.93，48.37；196.92，132.6；150.3，142.16；140.96，133.49； 138.94，101.42；125.1，89.6；124.53，70.13；99.
13、96，61.23；97.41，78.1；77.6，92.35；49.88，54.29； 74.82，30.16；80.11，36.06；94.78，28.46；8.83，53.96； 27.46，86.3；29.4，114.1；38.76，86.59；41.34，122.96； 62.45，132.3；83.99，118.96； 109.5，125.92； 136.26，118. 4；170.2，95.1； ?设置： 实验中，蚂蚁的最佳数目选择问题由 Dorigo M 等提示了设计思路，由于实现过于复杂，本次实验采用相对比较简单的方式，即问题规模大致是蚂蚁数目的 1.5 倍时，蚁群算法的全局收
14、敛性和收敛速度比较好7。由于目标为30，所有本次实验的蚂蚁的个数设定 m=20，最大循环次数NC_MAX=300。 蚁群算法中各参数的作业是紧密耦合的，其中对算法性能起着关键作用的是信息素启发式因子？琢，期望启发式因子？茁和信息素挥发因子？籽三个参数。信息强度 Q对算法的影响有赖于上述 3 个参数的配置以及对算法模型的选取，Q 对算法性能的影响情况显然有较大的差异12，本文采用的是 ant-cycle 模型，试验是改变一个参数，其它参数不变的策略来探讨参数设置对蚁群算法的性能的影响，默认设置参数为？琢=1，？茁=1，？籽=0.3，Q=100，每组数据实验 10 次取平均值。实验得到的模拟结果如
15、表 1所示。 说明：在表 1 中，平均值表示将 10 次运行中每次得到的最短路径长度的平均值，最优值表示 10 次运行路径中的最小值，最差值表示 10 次运行得到的最大值，差值表示实验得到的最优与最差值字之间的差值。 分析表 1 得到以下可以参考的结论，最佳参数配置是？琢=1，？茁=5，？籽=0.3；在该蚁群算法中，？琢=1 其它为默认值时，所得到的平均值比其它值得到的结果要好，此时差值是最小的，这说明解结果稳定且符合目标要求，？茁=5 解的质量最高，超过 5 时，接结果远离最优，对应信息素挥发因子？籽值在 0.10.5 之间变化不大，取整0.3 时接的结果质量最优。最优结果如图 4 所示。
16、以上分析是迭代 300 次运行下的试验结果，试验时还增加了不是最佳配置运行试验，结果表明，对于不是最优配置的实验，即使是增加运行次数得到的结果也不会有明显的改善。 因此，可以？琢=1，？茁=5，？籽=0.3 最优配置为参考来结果不同目标实验结果，得到最优解，对于不同目标实验结果如表 2 所示。 6 结论 在目标个数不超过 20 个时不需要修改参数，就能快速的得到最优的结果，而且收敛次数很低。超过 20 个目标需要根据实际情况来微调？茁或者？籽的系数来得到最优的结果；实验验证在实际的应用中根据不同的目标需求需要具体分析才能得到最优的结果。 参考文献 1Othon Michail，Paul G. Spirakis. Traveling salesman problems in temporal graph
