基于蚂蚁算法的PCB板路径优化研究.ppt

1、在基于蚂蚁算法的PCB板路径优化研究、参考文献、模型背景、印刷板PCB的焊接生产、故障检测及维护过程中，目前以人工方式为主的路径修订方法缺乏严格的数学论证，导致自动化作业顺序不合理，生产周期过长，生产线如何基于PCB板焊接的实际工作状况和通用路径修订技术寻求有效的路径修订解决方案已成为PCB板制造业的关键。 模型假设：本模型从CAD文件中提取焊接点信息，采用逐次焊接方式控制系统驱动表的移动，模型假设，假设各焊接的效率达到最高，给出焊接点的焊接规范后，所有焊接时间由总行走路线决定，模型制作，焊接PCB 焊接从最原始位置出发，经过各焊接点，最终回到原始位置，完成一个工作周期，这与TSP旅行者问题的

2、数学模型一致。TSP旅行模式、旅行者应从驻地出发，经过所有目的地再次登机，如何安排旅行路线使旅行距离最小。 模型求解，本模型采用蚁群算法(ACS )，在算法初期，将m只蚂蚁随机放置在n个城市，然后蚂蚁同时从一个城市向另一个城市，逐步完成搜索过程。 整个算法的迭代过程加上n，其中1=N=Nmax(Nmax是最大迭代次数)。 每次迭代时刻t，其中0=t=n，蚂蚁k (k=1，2，3，m )根据概率转换规则选择下一个城市，从而生成由n个城市组成的行为路径，并且可以伴随信息素更新。 影响蚂蚁向下一个城市迁移的因素，1禁忌列表(tube )禁忌表是为了避免蚂蚁重复进入同一城市的一个数据结构。 把tube

3、k作为蚂蚁k的禁忌表，表示蚂蚁k在通过城市I后，除了自己的禁忌表tubek之外，其次不能选择城市I。 当用tubek(s )表示禁忌表的第s个要素，即蚂蚁经过的第s个城市的一次旅行结束后，即巡视n个城市后，将禁忌表清空。 2可见性被定义为距离的倒数。=1/d。 两城市距离越近，可见性越高，选择的愿望越大，导致蚂蚁的搜索。 这样的信息是一定的，被称为启发信息。 3信息素蚂蚁从城市I选择城市j时，算法在ij路径上留下信息素，是动态的全局信息，表示从城市I到j的智力愿望。 反映了蚂蚁在解决问题过程中的经验积累和来自其他蚂蚁的学习能力。 信息素既有增加也有减少。 挥发机制是为了使残留信息素过多，使残留

4、信息不会淹没启发信息。 局部信息素更新和局部信息素更新的作用是减小所选边缘对后续蚂蚁的影响，以使蚂蚁对未选择的边缘具有更强的搜索能力。 在ACS算法中，当蚂蚁从城市I移动到城市j时，边ij上的信息素量用下式进行更新：其中，0是常数，(0，1 )是可变残奥计。 全局信息素更新根据全局最优解所属的边的以下公式进行更新： 其中，Lgb是当前最佳解的长度，是信息素蒸发系数。转换规则：ACS算法中，蚂蚁使用伪随机比率选择规则选择下一个城市。 也就是说，位于城市I的蚂蚁k以概率q0移动到城市l，其中l是il (t)*il最大的城市。这种选择方式意味着蚂蚁选择概率q0最有可能的城市作为蚂蚁制造的解，而且蚂蚁

5、以(1-q 0)的概率按照下式选择下一个城市j 在ACS算法中，蚂蚁的状态迁移式在这里，q0(0，1 )表示常数，q (0，1 )表示随机数，iu (t )表示时刻t的城市I和城市u之间的信息素，iu表示城市I和城市u之间的启发式因子，表示启发式因子在选择下一个城市之前随机生成q，如果q的值在定数q0以下，从城市I可以执行的所有城市中找到iu (t) iu最大的城市，即下一个选择的城市。 如果随机数q大于q0，按下面的公式选择下一个城市。 其中Jk(i )是蚂蚁k现在可执行的城市集合。 上述四个因素控制蚂蚁系统实现路径选择和信息素更新策略，两者合作实现模型的正负反馈机制，使人工蚂蚁收敛于最优解。 ACS算法可以表示为在算法的初始点，将m只蚂蚁随机地放置在n个城市，并将每只蚂蚁的禁忌表的第一个元素设置为当前所在的城市。 此时，每条路径上的信息素的量相等，并且ij (0)=C (C是小常数)。 其次，各蚂蚁从路径上残留的信息素量和启发式信息(两城市间的距离)独立选择下一个城市。 蚁群算法的关残奥表信息素的相对重要性启发式因子的相对重要性信息素的蒸发系数(1- )表示信息素的持久性系数q蚂蚁释放的信息