 Modeling and Simulation 建模与仿真, 2013, 2, 9-13 http://dx.doi.org/10.12677/mos.2013.22002 Published Online May 2013 (http://www.hanspub.org/journal/mos.html) PCB Assembly Optimization Based on Ant Colony Algorithm* Xuan Du, Hongw e i Ca o, C hong Guan College of Mechanical & Material Engineering, China Three Gorges University, Yichang Email: xdu@ctgu.edu.cn Received: Mar. 22nd, 2013; revised: Apr. 2nd, 2013; accepted: Apr. 8th, 2013 Copyright © 2013 Xuan Du et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unre- stricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract: The component placement sequence and feeder arrangement are the critical factors determining assembly time of chip shooter (CS) machine. In addition, the different size of component and different arrangement strategy affect the feeder arrangement and component placement sequence. Based on the engineering analysis, an integrated optimiza- tion model of printed circuit board (PCB) assembly for CS machine is established. Accord ing to the parallel placement character of CS machine, “Max-Min Ant Colony Algorithm with Communication function” is designed based on tradi- tional Ant Colony Algorith m. The idea that two ants with different duties collaborate to solve the optimization pro blem is presented. Guide ants optimize placement sequence while executant ants optimize feeder arrangement according to the components placement sequence. The component placement sequence and feeder arrangement are optimized simul- taneously. Keywords: Component Placement Sequence; Feeder Arrangement; Ant Colony Algorithm; Chip Shooter Machine; PCB Assembly Optimization 基于蚁群算法的 PCB 组装过程优化* 杜 轩，曹宏伟，关 冲 三峡大学机械与材料学院，宜昌 Email: xdu@ctgu.edu.cn 收稿日期：2013 年3月22 日；修回日期：2013 年4月2日；录用日期：2013 年4月8日 摘 要：在转塔式贴片机的印制电路板(PCB)组装过程中，元件贴装顺序和装载有不同类型元件的供料器在供料 架上的布置是影响转塔式贴片机贴装时间的主要因素。在分析实际工程应用的基础上，建立了转塔式贴片机上 PCB 组装的集成优化模型，对蚁群算法进行了改进，提出了相互通信的最大–最小蚂蚁算法，用两种不同职能 的蚂蚁相互协作，以元件组装顺序来驱动供料器布置，引导蚂蚁实现元件贴装顺序的优化，而执行蚂蚁根据引 导蚂蚁选择元件的结果来实现供料器布置优化。算法可对元件贴装顺序和供料器的布置进行同时优化，从而提 高转塔式贴片机上 PCB 组装的效率。最后通过实例验证了算法的有效性。 关键词：元件贴装顺序；供料器布置；蚁群算法；转塔式贴片机；PCB 组装优化 1. 引言 随着电子产品组装技术的发展，表面贴装技术 (SMT)正在成为印刷电路板(PCB)电路组装技术的主 流。SMT 能够使产品结构更加紧密，组装速度更快。 为了减少电子元件贴装过程中PCB 的装配时间，提高 生产效益，PCB 组装的优化问题便受到了人们越来越 多的关注[1-3]。单台贴片机上的 PCB 组装过程优化主 要包括以下两个子问题：电子元件的贴装顺序问题； *基金项目：湖北省教育厅自然科学研究重点项目(D20121306)，三 峡大学科研基金(KJ2010B020)。 Copyright © 2013 Hanspub 9  基于蚁群算法的 PCB 组装过程优化 装载不同类型电子元件的供料器在供料架上的布置 问题(简称为供料器布置问题)。这 2个子问题中，元 件的贴装顺序可视为旅行商问题(TSP)，供料器布置问 题可视为二次分配问题(QAP)[3,4]。目前，国内外学者 采用不同的方法来解决元件贴装顺序和供料器布置 问题。文献[5]实现了供料器布置优化，文献[6-8]实现 了元件组装顺序优化，文献[9,10]利用遗传算法实现了 元件组装顺序和供料器布置优化。由于蚁群算法在求 解TSP和QAP 问题方面具有良好的适应性，近年来 在此类优化问题中得到了广泛应用[11]。在实际的 PCB 组装过程中，元件组装顺序和供料器布置之间联系紧 密，互相影响，且依赖于具体的装配设备和技术环境， 因此建立一个能描述复杂工程实际情况的贴装过程 集成优化模型，并用合适的方法来实现高效求解是目 前的一个研究热点。 本文以 PCB 自动化组装常用的高速组装设备— —转塔式贴片机为研究对象，分析了转塔式贴片机的 运动机构，建立了转塔式贴片机贴装过程的集成优化 数学模型，并在模型中描述了 PCB 组装过程中元件尺 寸和同一供料器多次布置等工程实际问题对供料器 布置和元件贴装顺序的影响，用改进的蚁群算法实现 了转塔式贴片机的贴装过程中元件贴装顺序和供料 器布置的集成优化。 2. 转塔式贴片机结构 PCB 自动化组装的贴片机类型较多，各自具有不 同的运动机构，本文所讨论的转塔式贴片机是一种高 速组装设备，在组装过程中同时进行元件的贴装和拾 取，适合小型元件的大批量组装。其结构如图 1所示， 转塔式贴片机有一个可以移动的供料架，供料架上有 多个供料槽，装载有不同类型元件的供料器放置在不 同的供料槽位置上；有一个装载 PCB 的工作台，能够 实现 x-y 方向移动；还有一个可旋转的转盘，转盘上 装有多个贴装头，贴装头通过上下运动来实现元件的 拾取和贴装，每一个贴装头上有几个不同型号的吸 嘴，根据元件的尺寸大小，可以自动更换不同的吸嘴。 在PCB 组装过程中，三个运动机构的同时运动，根据 事先编制好的程序，同时实现元件的拾取与贴装。 3. 转塔式贴片机贴装过程模型 在一个元件的贴装过程中，转塔式贴片机并行运 转盘 供料槽 供料架 供料架移动方向 PCB工作台 PCB 板 贴装头 元件拾取位置 元件贴装位置 X方向 Y 方 向 Figure 1. Diagram of chip shooter machine 图1. 转塔式贴片机运动机构示意图 动机构的时间包括PCB 工作台沿 x-y 方向移动的时 间，供料架的移动时间和转盘旋转时间，其中最长的 一个决定了这个元件的贴装时间，而 PCB 上全部元件 贴装时间的总和就是PCB的组装时间。解决 PCB组 装过程优化问题的目标就是减少PCB 的组装时间，以 提高贴片机的效率。这类贴片机的优化问题为 MBTD (Moving-Board-with-time-Delay)问题[1]。 由于 PCB、供料槽和转盘同时移动，元件贴装顺 序的问题和供料槽的布置问题相互联系，传统的TSP 和QAP 模型不能很好地表达 MBTD 问题中的元件贴 装顺序和供料器布置，如果2个问题各自独立求解， 则必须以另一个问题的解为前提。为了实现转塔式贴 片机的贴片过程优化，必须建立包含元件贴装顺序和 供料器布置问题的集成优化模型，一般以减少PCB 的组装时间为目标，对其进行优化。具体优化数学模 型可用一个整数规划模型表示为： 1 11 221 111111 min , max p NN tij js is ij NNNPLL f hktih tjk is Mjs M sijthk r Tt tx x tx xxx t (1) 满足约束： 11 1, 1 NN is is is xx (2) Copyright © 2013 Hanspub 10  基于蚁群算法的 PCB 组装过程优化 1 1 L tih h x (3) 1 1 L tjk k x (4) , 1, 2,,;1, 2,,;1, 2,, 1,2, ,;1,2, ,;1,2, , ijPL iNjNsN tPhLk L 4. 改进蚁群算法的设计 蚁群算法对旅行商问题和二次分配问题具有很 好的适应性，因此在求解这一类问题中得到了很好的 应用。通过对CS 贴片机贴装过程的分析，由于元件 组装顺序优化及供料器布置优化两个子问题间相互 联系，相互影响，因此更加大了问题求解的难度。本 文通过对蚁群算法的改进，提出了基于相互通信的蚂 蚁算法，用元件的选择来驱动供料器位置的选择。引 入蚂蚁对概念，蚂蚁对中的一只蚂蚁负责元件的贴装 顺序的选择，另一只蚂蚁为每个元件进行供料槽编号 的匹配选择，他们是通过信息交流来完成任务的。改 进的蚂蚁算法引入了蚂蚁交流协作的模式，可将元件 贴装顺序和供料器布置同时优化，从而实现转塔式贴 片机上电子元件组装过程优化。具体的算法结构如图 2所示。 4.1. 蚂蚁分类 算法将蚂蚁分为引导蚂蚁和执行蚂蚁两种职能 的蚂蚁，来完成不同的子任务，从而完成总体任务。 以下来介绍蚂蚁的分类和它们之间的协作方式。 1) 引导蚂蚁的任务是选择贴装元件，给执行蚂蚁 发送引导信息。引导蚂蚁的路径是元件的贴装顺序。 2) 执行蚂蚁的任务是接受引导信息，选择供料 槽，并反馈所选择的供料槽的信息。执行蚂蚁来确定 供料槽的布置，它的路径是与引导蚂蚁选择的元件匹 配的供料器位置顺序。 4.2. 参数初始化 将一个引导蚂蚁和一个执行蚂蚁视为一个蚂蚁 对。将蚂蚁对初始化：执行蚂蚁按元件编号随机选择 一个元件 i，执行蚂蚁按供料槽编号随机选择一个供 料槽 j。 初始化种群 迭代次数Nc=Nc+1 蚂蚁引导者K1=0 修改引导者禁忌表 修改执行者禁忌表 蚂蚁执行者K2=0 蚂蚁引导者K1=K1+1 蚂蚁执行者K2=K2+1 按照元件状态转移 概率选择元件 按照供料槽状态转 移概率选择供料槽 输出程序结果 进行路径上信息量更新 K1>蚂蚁对总数m K2>蚂蚁对总数m 满足结束条件？ 结束 NN NN YY Y Figure 2. Flow of algorithm 图2. 算法流程图 令时间 0t 和循环次数N设置最大循环次 数CM N两两元件间的信息量 ij 初始时刻使 为 0 C， ， 在 AX 令t 0 ij const const 为一个相对大的常数。经过 一次循环后，令 ， max max11 1, ij g b T 。 4.3. 蚂蚁通信原则 通信过程分为两步： 第一步：引导蚂蚁每选择一个元件 i，就向执行 蚂蚁发送一条信息，信息内容包括：本次选择元件的 编号 i；上次选择元件的编号 i；编 号 为i的元件的类 型Yi；和 i Y 对应的供料槽的编号 。 Yi n 第二步：执行蚂蚁按照引导蚂蚁传递的信息内容 进行供料槽的选择，然后将 返回给引导蚂蚁。 Yi n 引导蚂蚁结合元件之间的信息素和选择元件的 启发因子按编号选择贴装元件，执行蚂蚁根据信息内 容结合元件与供料槽之间的信息素和选择供料槽的 Copyright © 2013 Hanspub 11  基于蚁群算法的 PCB 组装过程优化 启发因子，为元件选择匹配的供料槽。引导蚂蚁的状 态转移概率为： allowed ,allowed 0, else k ij ij k kis is ij s tt j tt Pt 式中：表示 t时刻引导蚂蚁 k由元件i转移到元 件j的转移概率；表示在 t时刻元件 i和元件j 之间的信息量的大小；启发函数 k ij Pt ij t 1 ij ij nt TT；TTij 表示 PCB 工作台从元件i的贴装位置移动到元件 j的 贴装位置的运动贴装定位时间；allowedk表示可以选 择的元件集合，如果选择了元件 i，将其放入禁忌表 tabuk中。 执行蚂蚁的状态转移概率为： allowed ,allowed k ij ij k ij k is is s tt qt j tt 式中：表示在 t时刻执行蚂蚁 k由供料槽 i转移 到供料槽 j的转移概率； k ij qt ij t 表示在 t时刻供料槽 i 和供料槽 j之间的信息量的大小。 在转塔式贴片机的元件组装过程中，根据各运动 机构的情况，可将其分为三个阶段。第一阶段是指在 组装开始的时候，对最先组装的 M/2 个元件，通过转 盘转动和供料架的移动拾取元件，而工作台不动，此 时启发函数 1 ij ij tTF ；TFij 表示从编号为 i的供料 槽移动到编号为 j的供料槽所需的时间；第二阶段是 转盘拾取了 M/2 个元件后，转盘、供料架和工作台同 时运动，此时启发函数 1 ijcj j tTTTF ，TTcj 表示 PCB 工作台从上一个元件移动到和供料槽 j所对应的 元件 cj的位置所需要的时间，TFj表示从上一个供料 槽移动到编号为 j的供料槽所需要的时间；第三阶段 是指组装结束阶段，最后组装的 M/2 个元件，元件已 经拾取，只是通过转盘的转动和工作台的移动组装元 件，供料架不动，因此转移概率在此不起作用。 4.4. 路径信息更新策略 通过蚂蚁对之间的相互交流，引导蚂蚁可以获得 每次元件的贴装顺序以及每个元件相对应的供料槽 的编号。这为路径上的信息素更新提供了条件。路径 信息量更新完全由引导蚂蚁来完成，它要完成两部分 信息量的更新，更新部分及其更新规则如下： 1) 元件选择路径上信息量的更新 b est 1 ijij ij tn t 式中，当最好的蚂蚁对在本次循环中经过元件 ,ij 时， best 1ib ij QT 否则为 0。Q1表示元件间信息素的 强度，Tib 为最好蚂蚁对完成贴装优化的时间。 2) 元件与供料槽匹配关系的信息量更新 元件与供料槽匹配关系的信息量更新主要是由 供料架移动时间和 PCB 工作台移动时间的差值与总 的贴装时间共同决定的。 b est 1ij ij tn t b est ij 与元件组装顺序有关，且体现了节约时间的理 念，供料器和工作台运动时间差异越小，元件与供料 槽之间匹配关系的信息素就增加的越多。 5. 计算实例分析 首先利用本文提出的改进遗传算法(IGA)，对文 献[1]中提供的计算实例进行了计算，计算结果如图 3 所示。曲线 A为一种元件只在供料架上放置一次的计 算结果，曲线 B为装载有 4、9、10 三种元件的供料 器分别放置两次的计算结果。 结果显示，本文所提出的基于通信的蚂蚁算法能 实现元件贴装顺序和供料器布置的集成优化，得到的 优化结果 27.25 s，要优于文献[10]中采用的传统遗传算 法和混合遗传算法得到的优化结果 33.58 s和27.58 s。 A B 遗传代数 0 1000 2000 35 70 0 Figure 3. Result of calculation 图3. 实例计算结果 Copyright © 2013 Hanspub 12  基于蚁群算法的 PCB 组装过程优化 Copyright © 2013 Hanspub 13 6. 结束语 塔式贴片机的运动机构进行了分析。在 转塔 参考文献 (References) Planning of component place- ment/insertion sequence and feeder setup in PCB assembly us- 本文对转 式贴片机的贴装过程优化中，同时考虑了元件贴 装顺序问题和供料器布置的问题，并考虑了 PCB 组装 中元件尺寸及不同布置策略对供料器布置的影响。建 立了转塔式贴片机贴装过程的集成优化模型，用改进 的蚁群算法实现了元件贴装顺序和供料器布置的集 成优化。通过实例的比较，证明采用基于相互通信的 蚂蚁算法，能很好的解决转塔式贴片机贴装过程优化 中，元件组装顺序和供料器布置两个复杂组合优化问 题的集成优化，并能得到较好的优化结果，有利于提 高PCB 的组装效率。同时也为复杂工程实际问题的优 化提供了一种较好的方法。 [1] M. C. Leu, H. Wong and Z. Ji. ing genetic algorithm. Journal of Electronic Packaging, 1993, 115(4): 424-432. [2] K. P. Ellid, F. J. Vites and J. E. Kobza. Optimizing the perform- ance of a surface mount placement machine. IEEE Transactions on Electronics Packaging Manufacturing, 2001, 24(3): 160-170. [3] W. Ho, P. Ji. A genetic algorithm approach to optimizing com- ponent placement and retrieval sequence for chip shooter ma- chines. International Journal of Advanced Manufacturing Tech- nology, 2006, 28(5-6): 556-560. [4] E. Duman, I. Or. The quadratic assignment problem in the con- text of the printed circuit board assembly process. Computer and Research, 2007, 34(1): 163-179. [5] 田福厚, 李少远. 贴片机喂料器分配的优化及其遗传算法求 解[J]. 控制与决策, 2005, 20(8): 955-958. [6] 袁鹏, 刘海明, 胡跃明. 基于伞布搜索法的贴片机贴装顺序 优化算法[J]. 电子工艺技术, 2007, 28(6): 316-320. [7] 曾又姣, 金烨. 基于遗传算法的贴片机贴装顺序优化[J]. 计 算机集成制造-CIMS. 2004, 10(2): 206-209. [8] 闫红超, 姜建国. 一种基于改进混合遗传算法的贴片机装配 工艺优化方法[J]. 微电子学与计算机, 2006, 23(6): 213-216. [9] W. Ho, P. Ji. An integrated scheduling problem of PCB compo- nents on sequential pick-and-place machines: Mathematical models and heuristic solutions. Expert Systems with Applica- tions, 2009, 36(3): 7002-7010. [10] W. S. Chen, C. C. Chyu. A hybrid genetic algorithm for solving feeder arrangement and placement sequencing decisions in PCB assembly. http://machinevision.iem.yzu.edu.tw/pcb2002/paper/A2.pdf [11] 唐秋华等. 基于改进蚁群算法的装配序列规划研究[J]. 机械 设计与制造, 2012, 5: 42-44. |