基于蚂蚁算法的PCB板路径优化研究,1,基于蚂蚁算法的PCB板路径优化研究,参考文献,基于蚂蚁算法的PCB板路径优化研究,2,模型背景,在印刷电路板PCB焊接生产、故障检测以及维修过程中，现行以人工方式为主的路径规划方法缺乏严格的数学论证，以致经常导致自动化作业顺序不合理的情况，导致生产周期过长，影响整条生产线的生产。 如何根据PCB板焊接的实际工作情况以及通用路径规划技术寻求一种高效的路径规划解决方案，已成为PCB板制造业中的一个重点,基于蚂蚁算法的PCB板路径优化研究,3,模型假设,本模型中采取从CAD文件提取焊点信息，通过逐点焊接的方式控制系统驱动工作台移动 当待焊焊点到达激光半点位置时，系统按给定的加热功率以及时间输出激光 当一个焊点焊接完毕后再移动下一个焊点，直至所有焊点焊接完毕。,基于蚂蚁算法的PCB板路径优化研究,4,模型假设,假设每次焊接的效率达到最高 显然当焊点的焊接规范给定后，全部焊接时间决定于总的行走路线,基于蚂蚁算法的PCB板路径优化研究,5,模型建立,在焊接PCB板工作过程中，焊接从最原始位置出发，途径各个焊点，最终回到原始位置，完成一个工作循环，这与TSP旅行商问题的数学模型一致。,基于蚂蚁算法的PCB板路径优化研究,6,TSP旅行商模型,旅行商从驻地出发，经过所有目的地后再次返回原地，应如何安排其旅行路线才能使旅行距离最小。,基于蚂蚁算法的PCB板路径优化研究,7,模型求解,本模型中我们采用蚁群算法（ACS）即：在算法的初始时刻，将m只蚂蚁随机放到n座城市，然后蚂蚁同时由一个城市到另一个城市，逐步完成搜索过程。整个算法的迭代过程以N为刻度，1=N=Nmax(Nmax为最大迭代次数)。在每次迭代中，以t为刻度，0=t=n,蚂蚁k（k=1,2,3，m）根据概率转换规则选择下一个城市，由此可以生成一个由n个城市组成的行动路线，并伴有信息素的更新。,基于蚂蚁算法的PCB板路径优化研究,8,影响蚂蚁转移到下一城市的因素,1 禁忌列表（tube） 禁忌表是为了避免蚂蚁重复走进同一个城市的一个数据结构。 设tubek为蚂蚁k的禁忌表，则蚂蚁k在经过城市i以后，就将该城市加入到自己的禁忌表tubek中，表示下一次不能再选择城市i。用tubek(s)示禁忌表中第s个元素，也即蚂蚁所走过的第s个城市；完成一次周游后，即遍历n个城市后，清空禁忌表。,基于蚂蚁算法的PCB板路径优化研究,9,2 能见度 定义为距离的倒数。=1/d。 两个城市的距离越近，能见度越高，被选择的愿望越大，由此引导蚂蚁的搜索。这种信息是固定不变的，称为启发信息。,基于蚂蚁算法的PCB板路径优化研究,10,3 信息素 当蚂蚁由城市i选择城市j后算法将在ij路径上遗留信息素，是一种动态的全局信息，代表了由城市i到j的获知性愿望。反映了蚂蚁在解决问题过程中的经验积累和向其他蚂蚁学习的能力。 信息素有增加和减少两方面。挥发机制是为了避免残留信息素过多导致残留信息淹没启发信息。,基于蚂蚁算法的PCB板路径优化研究,11,局部信息素更新,局部信息素更新的作用是使已选的边对后来的蚂蚁具有较小的影响力，从而使蚂蚁对没有被选中的边有更强的探索能力。 在ACS算法中，当蚂蚁从城市i转移到城市j后，边ij上的信息素量按下式进行更新：,其中0为常数，(0,1)为可调参数。,基于蚂蚁算法的PCB板路径优化研究,12,全局信息素更新,针对全局最优解所属的边按下式进行更新：,其中Lgb为当前最好解的长度，为信息素蒸发系数。,基于蚂蚁算法的PCB板路径优化研究,13,转换规则：,在ACS算法中，蚂蚁使用伪随机比率选择规则选择下一座城市。即对位于城市i的蚂蚁k，以概率q0移动到城市l，其中l为使il (t)*il 达到最大的城市。该选择方式意味着蚂蚁将以概率q0将最大可能的城市选入蚂蚁所构造的解；除此之外，蚂蚁以(1-q 0) 的概率按下式选择下一座城市j。在ACS算法中，蚂蚁的状态转移公式为：,基于蚂蚁算法的PCB板路径优化研究,14,其中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当前的可行城市集合。,基于蚂蚁算法的PCB板路径优化研究,15,上述四个因素控制着蚂蚁系统实现路径选择和信息素更新策略，两者相互配合，实现模型的正负反馈机制，促使人工蚂蚁收敛于最优解。,基于蚂蚁算法的PCB板路径优化研究,16,基于蚂蚁算法的PCB板路径优化研究,17,ACS算法可以表述如下：在算法的初始时刻，将m只蚂蚁随机地放到n座城市，同时，将每只蚂蚁的禁忌表的第一个元素设置为它当前所在的城市。此时各路径上的信息素量相等，设ij (0)= C （C为一较小的常数）。接下来，每只蚂蚁根据路径上残留的信息素量和启发式信息（两城市间的距离）独立地选择下一座城市。,基于蚂蚁算法的PCB板路径优化研究,18,蚁群算法的参数,信息素的相对重要程度； 启发式因子的相对重要程度； 信息素蒸发系数（(1-)表示信息素的持久性系数）； Q蚂蚁释放的信息素量。,基于蚂蚁算法的PCB板路径优化研究,19,结果分析,经过对PCB板的焊接路径优化，最终仿真结果比为优化的生产时间少15S，使得该PCB板的生产效率得以提高，同时也证明基于蚁群算法的PCB板路径规划方法是有效地,基于蚂蚁算法的PCB板路径优化研究,20,模型不足及改进,未考虑焊枪和工件或夹具的干涉问题 这方面可以增加虚焊点修正的方法加以解决,