王蒙蒙，俞 洋
（江苏理工学院 电气信息工程学院，江苏 常州 213001）
现如今芯片在社会发展中的地位愈发重要，极大推动了电子信息技术的发展[1]。而在工业生产过程中，在封装芯片之前需要对其进行特定的摆盘以便于后续的封装。由于芯片具有体积微小、质量要求严格、生产量大等特点，若使用传统的人工摆盘，不仅会存在很高的错误率，还会极大影响摆盘效率。企业想以更快的速度满足客户的需求，对芯片摆盘环节进行优化研究，缩短摆盘时间，具有极其重要的意义。芯片摆盘优化的核心是摆盘路径的规划，这类问题的关键就是在一定约束下找出最优路径。通常采用的方法是启发式算法，包括：蚁群算法[2]、粒子群算法[3]、遗传算法[4]、模拟退火算法[5]等。
本文针对芯片摆盘存在的问题，提出了一种新的芯片摆盘方法，提高了芯片摆盘的效率。本方法通过改进蚁群算法存在的缺陷[6-9]，利用遗传算法寻找出较优路径集合，改进信息素更新方式，采用精英蚂蚁策略保证蚁群算法前期最优解的搜索质量，同时对生成的信息素值进行限定。其次，为了提高适应蚁群搜索的能力，采用自适应信息素挥发因子代替自定义挥发因子，合理地调整信息素浓度。最后，添加了路径交叉检测与消除来进一步提高每一次迭代得到的最优解的质量。将改进的算法应用到芯片摆盘问题中，通过实验证明了新的算法对芯片摆盘效率的提升作用。
1.1 问题描述
通过机械手完成将振动盘中的芯片摆放到芯片胚盘中的任务，已知在摆盘过程中，振动盘位置、芯片型号、芯片放置位置等信息存在以下3 点约束：（1）每个芯片位置只能走访一次；
（2）机械手一次性最多抓取三个芯片；
（3）机械手只能从起点芯片放置盘位置出发，最后要返回到芯片放置盘位置。
本问题的目标是在满足上述约束条件下，找出一条路径最短的路线，将振动盘中的芯片全部摆放完。
1.2 建立模型
根据上述问题描述，结合芯片摆盘的实际问题进行分析，本文在已有研究的基础上，将芯片封装时的摆盘路径问题抽象为旅行商售货问题（TSP）的一种拓展延伸，构建一种以路径最短为目标的优化数学模型。芯片在待摆盘前会被放置于振动盘中，振动盘在摆盘时会停止振动，且其中只会有同一型号的芯片存在，本文以ATA6662 型号芯片为目标物料建立数学模型。
在振动盘a中，有N个待摆盘芯片，可以记作为n=1,2,3,...,N-1，N，待摆盘芯片的位置记作为l=1,2,...,i,j,L。芯片与芯片之间的距离可表示为：
式（1）表示欧氏距离[10]，其中（x，y）代表芯片的坐标；
n∈N表示振动盘中所有待摆盘芯片；
i，j∈L表示待摆盘芯片的位置；
dij表示两个芯片之间的距离。后文用Yaij表示振动盘a中先摆放i再摆放j；
Zia表示从振动盘a的i位置吸取芯片；
C表示机器一次最多抓取芯片的个数。
本模型忽略摆放到芯片放置盘中的具体位置之差，仅将其放置盘视为一个坐标点，且摆放次序也是从左往右、从上到下。将摆盘的最短路径作为目标函数，目标函数为：
约束条件如下：
式（2）为目标函数，式（3）确保每个芯片只抓取一次，式（4）中用Pijk表示是否访问过芯片i和芯片j，取1 表示访问过，反之则没有访问。将机械手k经过的所有芯片位置距离进行累加，从中选取距离最短的路径作为所要求得的最优解。式（5）和（6）声明每个位置只经过一次，且只有一个前任和后继，式（7）表示机器一次最多抓取3 个芯片。
蚁群算法是由Marco Dorigo 博士于1992年提出的，其通过观察蚂蚁觅食行为而得到灵感，在针对组合优化问题的研究中，呈现出了颇为优秀的效果。
2.1 构建路径
假设将各个蚂蚁随机放置在不同的位置，要求每只蚂蚁k访问完每一个城市且不重复，直至所有蚂蚁访问结束。在此期间蚂蚁选择的下一个访问城市遵循选择路径规则和信息素分布规则，选择的概率表示为：
其中：
式（8）中i、j分别为两个节点，τij(t)为t时刻由i到j的信息素浓度；
公式（9）中ηij(t)为从节点i到节点j的期望值。根据公式可知，节点距离越小，信息素浓度越大，该节点被选择的概率越大。
2.2 更新信息素
在每一轮蚂蚁遍历完所有城市后，为了防止寻优过程中路径上信息素积累过多，从而导致覆盖还未访问的城市的情况，需要对信息素进行更新处理，表达式如下：
式中：初始信息素为0；
ρ为挥发系数，取值范围为0～1；
Δτij为信息素增加量；
Q为常量；
Dk表示蚂蚁k访问过的路径长度。
本文针对传统蚁群算法作如下改进：一是调整信息素更新的方式；
二是改进信息素挥发因子ρ；
三是为防止所寻求出来的最优路径存在交叉，进行路径交叉消除。
3.1 改进信息素更新
在信息素更新方面做了如下调整：
（1）基于遗传算法产生初始信息素分布；
（2）采用精英蚂蚁策略代替传统信息素更新规则；
（3）限制信息素范围。
3.1.1 基于遗传算法产生初始信息素
为解决缺乏初始信息素的情况，提出先利用遗传算法快速寻找出较优路径集合，然后根据适应度的大小进行排序，选择适应度值较大的前40%个体产生信息素，作为蚁群算法的初始信息素。由式（13）和式（14）得到初始信息素分布情况。
式中：M为种群数量；
Dm为个体m所走过的路径长度；
S为一个常量。
3.1.2 精英蚂蚁策略
针对信息素更新使得信息素累积较快导致陷入局部最优的情况，调整信息素更新方式。传统的蚁群算法中，当蚂蚁遍历完所有城市后路径上的信息素随着时间的推移会按照一定规则进行挥发，但在此过程中容易造成算法陷入局部最优的问题。因此，针对该问题提出改进信息素更新规则，采用精英蚂蚁策略，当一次迭代后全部蚂蚁都已经走完自己的路径后，选择出最短路径的个体，让其再一次重复信息素的更新过程，这样可以使得信息素更新更加合理。公式（15）～（17）为信息素更新。
式中：Dk表示蚂蚁k所走过的路径长度；
Dbestk表示精英蚂蚁所走的最优路径；
Δτij为初始信息素值。
3.1.3 限制信息素范围
针对后期信息素积累过多导致陷入局部最优的情况，本文根据MMAS 思想，对信息素的取值范围进行限制。
信息素最大值τmax的设置是根据式（10）和式（18）计算化简而来，其中Dbestroute为尚未更新的最优解，Dnowbestroute为当前迭代中最优解，每次迭代τmax(t)都会根据当前路径最优解与信息素挥发因子变化而变化。信息素最小值τmin是根据遗传算法所获得的初始信息素值而设置的。
3.2 改进信息素挥发因子
以往的蚁群算法中信息素挥发因子是通过人为设定一个介于0～1 之间的值，若ρ设置过小，容易导致太早就收敛，最优解的全局性降低；
若ρ设置过大，会造成算法收敛速度慢[11]。由此可以发现人为设定值存在不确定性，导致信息素分布并不合理，影响了算法的精确性。因此本文提出信息素因子自适应策略，增加了蚂蚁搜索路径的任意性。
当搜寻到的新路径越短，则Dnowbestroute值越小，那么T的值会越大，ρ的值也就会越大。
算法的初期是寻优阶段，考虑到全局寻优，因此需要ρ大一些，保证信息素含量控制的尽量低一些，提高算法的全局搜索能力，减轻信息素早期的诱导能力。在后期随着寻优阶段的结束，需要加快算法的收敛速度，因此要求ρ小一些，保证信息素含量尽量高一些，增强算法的收敛能力。
3.3 路径交叉消除
在求解芯片摆盘最优路径的过程中会出现所求得路径存在着交叉，并非最优路径。针对这一问题提出了路径交叉消除[12]，进一步提高最优解的质量。
3.3.1 路径交叉检测
判断路径是否存在交叉，可类比于判断两条线段是否有交点。设存在线段i→i+1 与j→j+1，两条线段的端点分别为(Xi,Yi)、(Xi+1,Yi+1)、(Xj,Yj)、(Xj+1,Yj+1)，可得这两条线段的方程为：
令
当r(D)=2，r(A)=2 时，说明方程组存在解，再判断该解是否在线段范围内，即：
若皆满足，则确定存在路径交叉。
3.3.2 交叉消除
当路径i→i+1 与j→j+1 存在交叉，其中i+1 首先利用遗传算法求出较优路径[13]，产生蚁群算法所需要的初始信息素，解决蚁群算法缺乏初始信息素的问题。 机械手从芯片放置盘处出发，计算其转移概率PKij确定从i点转移到j点处，并判断机械手抓取是否达到最大抓取容量C，若未达到最大容量，则返回到芯片放置盘处，保留本次的行经路线，并再重新创建一条新路径，更新当前的位置； 根据禁忌表中的数据判断是否已经遍历完所有芯片所在位置，若已经全部途经过，则机械手返回起始位置处，结束本次迭代； 在每轮迭代结束后，利用路径交叉检测判断最优路径中是否存在交叉，若存在，则进行路径交叉消除，并只更新最优路径上的信息素，代替传统信息素更新方式。 判断是否已经达到最大迭代次数，若判断为真，则结束算法运行，并输出最优解； 图1 改进蚁群算法流程 针对芯片封装环节中的摆盘问题，对提出的改进蚁群算法的芯片摆盘进行实验仿真分析。使用MATLAB 作为仿真工具，随机设置了31 个坐标，其中一个为芯片胚盘位置，作为起始点，其余坐标为振动盘中待摆盘芯片位置，如图2所示。设置改进的蚁群算法的各个参数值，蚁群算法中的蚂蚁数量设置为80，最大迭代次数设置为150，保证寻优的同时也缩短算法运行时间。经测试得，将信息素重要系数设置为1 时，搜索性能最好。启发函数系数的初始值设置为5，信息素启发因子初始值设置为0.8 时，可以保证信息素的合理分配，提高算法的全局寻优能力。 图2 胚盘及芯片位置分布 图2标注的起点是芯片所需摆放到的胚盘位置，其余30个坐标为芯片所在的位置坐标。分别使用蚁群算法、文献[7]中算法和改进后的蚁群算法进行搜索遍历，并对这三种算法的最优路径进行对比。 图3为传统蚁群算法搜索遍历的最优路径，其最短距离为389.644 7。图4为文献[7]算法下的最优路径，其最短距离为376.711 4。图5为改进融合后的遗传-蚁群算法搜索遍历的最优路径，其最短距离为368.589 1。 图3 传统蚁群算法下的最优路径 图4 文献[7]算法下的最优路径 图5 改进蚁群算法下的最优路径 对比三种算法的实验结果，如图6的最优路径对比图所示，可知使用改进后的蚁群算法所得到的最优路径距离最短。 图6 算法最优路径 由表1中的数据可知，改进的蚁群算法在最优路径距离方面，较传统蚁群算法提高了5.4%，较文献[7]算法提高了2.16%； 表1 实验算法数据 结合芯片生产中的实际情况，对芯片摆盘问题进行分析，本文提出了改进蚁群算法的芯片摆盘路径规划。为了避免算法陷入局部最优，提高算法的全局搜索能力，本文从如下方面对蚁群算法进行改进： （1）先利用遗传算法求出较优路径，然后根据适应度的大小进行排序，选择适应度值较大的个体产生初始信息素，解决蚁群算法缺乏初始信息素的问题； （2）改进信息素挥发因子，采用自适应信息素挥发因子来代替人为设定固定值，合理地调整信息素挥发因子的大小，增强蚁群搜索的能力。 （3）针对最优解中存在路径交叉问题，添加了路径交叉检测与消除，对所求得最优解进一步进行优化。 本文通过MATLAB 工具进行仿真，从定点出发遍历搜索完所有点再回到起始点。实验结果表明，改进融合的蚁群算法较传统蚁群算法，最优解距离减少了5.4%；3.4 算法描述
反之则机械手移动到下一个待抓取芯片处并更新局部信息素。
否则，机械手继续计算状态转移寻找下一个芯片，重复上述步骤。
反之继续进行下一轮迭代。改进后的蚁群算法的流程如图1所示。
在最优迭代点上，均比其他两种算法提早寻找到最优解，验证了改进后算法的性能更优。
并改进信息素更新方式，每次迭代只使用最优路径的信息素值，同时对信息素值设置了限定的区间。
较文献[7]算法最优解距离减少了2.16%，在寻找最优解和前期搜索效率方面都要优于传统算法，提高了芯片摆盘的效率，验证了本算法的有效性。
