基于蜜蜂进化型遗传算法和蚁群系统表面贴装优化的研究 56页

西安建筑科技大学硕士学位论文基于蜜蜂进化型遗传算法和蚁群系统的表面贴装优化研究专业：信号与信息处理硕士生：孙有田指导教师：王超学副教授董惠副教授摘要当代社会电子技术飞速发展，电子信息产业已发展为当今社会不可或缺的产业之一，在国防、工业及社会生活等各方面发挥着日益重要的作用。电子制造业是电子信息产业的基础，表面贴装技术（SMT）作为电子先进制造技术中的重要部分，它的发展受到了世界各国的重视。在表面贴装技术生产线中，贴片机是最核心的设备，而贴片机的生产效率一直是整个生产线的瓶颈，对于这一“瓶颈”设备的贴装过程进行合理的优化控制是提高SMT生产线的工作效率、缩短产品生产周期的主要方法之一。首先，本文对贴片机类型以及贴片机贴装工艺流程、影响因素等进行了详细分析，并据此建立了表面贴装技术的优化模型；结合蜜蜂进化型遗传算法和蚁群系统的优点，提出了一种串行结构的混合智能算法，即蜜蜂进化型遗传-蚁群算法BGAA，并针对该混合算法存在的运行速度较慢的问题，又提出了一种并行结构的基于蜜蜂进化型遗传算法和蚁群系统的混合智能算法BAHA，该算法通过两个种群的融合实现信息共享，采用了改进的OX的交叉算子，保留了优秀个体基因的排列顺序，并加入了局部搜索算子，在当代最优解附近进行了更加精细的搜索，引入信息素重置防止了混合算法陷入局部最优解的产生。通过对TSP问题仿真测试进行算法的有效性验证，并以6吸嘴的垂直旋转式贴片机为原型，针对表面贴装技术优化模型，利用BAHA对实际生产中使用的5种不同元器件个数和种类的PCB板的贴装顺序进行仿真优化计算。仿真测试表明，BAHA具有较好的全局搜索能力和收敛速度，能有效地解决表面贴装优化问题。关键字：表面贴装技术；贴片机；蜜蜂进化型遗传算法；蚁群系统；优化本课题受到国家自然科学基金（基金号：31170393）和西安建筑科技大学人才基金项目（基金号：RC0806）的资助。 西安建筑科技大学硕士学位论文2 西安建筑科技大学硕士学位论文ResearchofBeeEvolutionaryGeneticAlgorithmandAntColonySystemtoSurfaceMountTechnologyOptimizationMajor:SignalandInformationProcessingName:SUNYou-TianInstructor:WANGChao-Xue，DONGHuiABSTRACTWiththerapiddevelopmentofmodernelectronictechnology,electronicinformationindustryhasbeenoneoftheindispensableindustries.Inthemodernnationaldefense,modernindustrialandsociallife,electronicinformationindustryisplayinganincreasinglyimportantrole.Electronicmanufacturingisthefoundationofelectronicinformationindustry,surfacemounttechnology(SMT)asanimportantpartoftheadvancedmanufacturingtechnology,thedevelopmentofitgetstheworld"sattention.Intheelectronicassemblyline,themostandimportantequipmentisMulti-headSurfaceMountingMachine.Meanwhile,theMulti-headSurfaceMountingMachine"sproductionefficiencyhasbeenthebottleneckoftheentireelectronicassemblyline.TheoptimalofMulti-headSurfaceMountingMachineisareasonablewaytoincreaseproductivityandtoreduceproductioncycle.Atfirst,theassemblyplanningofsurfacemount-placementmachinewasanalyzed,andthenanintegratedoptimizationmodelwasfoundedaccording.Abeeevolutionarygenetic-antcolonyalgorithm(BGAA)wasproposedbycombiningwiththeadvantagesofbeeevolutionarygeneticalgorithmandantcolonysystem,whosestructurewasserial.Then,becauseBGAAwasslow,ahybridintelligentalgorithmusingparallelstructurebasedonbeeevolutionarygeneticalgorithmandantcolonysystem(BAHA)isproposed.Thekeyofthehybridintelligentalgorithmliesinimprovingtheconvergencespeedbythecombinationbetweenthetwopopulation；theimprovedOXcrossoveroperatorretainedthesequenceofthegoodgenes；alocalsearchoperatorwasintroduced，whichhasmoreelaboratesearchabilityintheneighborhoodoftheiteration-best;pheromoneresettingisusedtojumpfromlocaloptimalsolution.Thehybridintelligentalgorithmwastestedusingtravelingsalesmanproblems;by 西安建筑科技大学硕士学位论文makingthe6suctionnozzleverticalrotaryplacementmachinesasaprototype,thecomponentmountingsequenceproblemof5PCBcardswasemulatedbyBAHA.TheresultsshowthatBAHAhasgoodglobalsearchabilityandfastconvergencerate,andcouldslovetheproblemoptimizationofSMTeffectively.Keywords：surfacemounttechnology;surfacemount-placementmachine;beeevolutionarygeneticalgorithm;antcolonysystem;optimizationThispaperissupportedbyNationalNaturalScienceFoundation(No.31170393)andTalentsFoundationofXI’ANuniversityofarchitectureandtechnology(No.:RC0806).4 西安建筑科技大学硕士学位论文目录第一章绪论....................................................................................................................11.1SMT系统概述...................................................................................................11.2研究意义..........................................................................................................21.3研究现状..........................................................................................................31.4章节安排..........................................................................................................4第二章表面贴装技术概述............................................................................................62.1表面贴装技术的基本结构和工艺流程..........................................................62.2表面贴装技术的优点......................................................................................72.3贴片机的结构..................................................................................................82.4贴片机的分类................................................................................................102.5贴片机的贴装工艺流程................................................................................122.6影响贴片机贴装效率的因素........................................................................122.7优化模型........................................................................................................132.8本章小结........................................................................................................14第三章遗传算法和蚁群算法......................................................................................153.1遗传算法........................................................................................................153.1.1基本思想............................................................................................153.1.2遗传编码............................................................................................163.1.3适应度值计算....................................................................................163.1.4选择算子............................................................................................173.1.5交叉算子............................................................................................183.1.6变异算子............................................................................................193.1.7遗传算法的特点及不足....................................................................203.1.8蜜蜂进化型遗传算法........................................................................203.2蚁群算法........................................................................................................223.2.1基本思想............................................................................................223.2.2蚁群算法的特点及不足....................................................................243.2.3蚁群系统............................................................................................253.3本章小结........................................................................................................26第四章蜜蜂进化型遗传算法和蚁群系统构成的混合算法......................................274.1蜜蜂进化型遗传算法和蚁群系统构成的具有串行结构的混合算法........274.1.1改进的蜜蜂进化型遗传算法............................................................274.1.2改进的蚁群算法................................................................................284.1.3BGAA的算法流程.............................................................................29I 西安建筑科技大学硕士学位论文4.1.4算法验证............................................................................................304.1.5验证结论............................................................................................324.2蜜蜂进化型遗传算法和蚁群系统构成的具有并行结构的混合算法.........324.2.1改进的蚁群系统................................................................................334.2.2改进的蜜蜂进化型遗传算法............................................................344.2.3局部搜索............................................................................................364.2.4算法流程............................................................................................374.2.5算法验证............................................................................................374.2.6验证结论............................................................................................394.3BGAA与BAHA的对比...................................................................................394.4本章小结.........................................................................................................41第五章仿真实验...........................................................................................................425.1算法实现与仿真计算.....................................................................................425.2本章小结.........................................................................................................45第六章总结与展望.......................................................................................................47致谢.................................................................................................................................48参考文献.........................................................................................................................49作者在读硕士期间发表的研究成果.............................................................................52II 西安建筑科技大学硕士学位论文第一章绪论在当今社会，各种电子产品随处可见，不管是日常生活还是国防军用，电器都发挥着极其重要的作用。在电子管时代，人们只能人工手动焊接电子线路，主要产品为电子管收音机。20世纪40年代，由于晶体管诞生，人们尝试用晶体管代替电子管，印刷电路板的研制成功使得电子产品的体积更小巧，结构更紧凑。20世纪50年代，第一台波峰焊接机出现在英国，人们将晶体管之类的通孔元件插装在印制电路板上，再采用波峰焊接技术对通孔组件进行装联。波峰焊接技术的出现实现了电子产品的大规模工业化生产，对世界电子技术发展做出了巨大的贡献，半导体收音机以及黑白电视机代替了以往的电子管收音机，并迅速风靡全世界。20世纪60年代，无引线电子元件被应用于电子表产业，该类元件可直接焊接于印制板表面，这一尝试是走向“表面贴装技术”的第一步，对接下来的电子技术发展有着重大的影响。上世纪70年代开始，从一开始仅能集成几十个元件、逻辑功能简单的小型集成电路，到现在的能集成百万甚至上亿个元件、逻辑功能无比复杂的超大型集成电路，硅产业迅猛发展。同时，集成电路芯片的设计以及加工水平也不可同日而语。现代电子元件封装迅速向微型化、高性能、低成本等方向发展。传统人工插件方式的装配成本、产品大小重量和可靠性均已达到组装极限，无法满足现代高[1]水平电子产品的需要。1.1SMT系统概述表面贴装技术（SurfaceMountTechnology，SMT）是将表面贴装元件（无引脚或短引脚的元件）贴、焊到印刷电路板（PrintedCircuitBoard，PCB）表面规定位置上的电路贴装技术，所用的印刷电路板无需钻插装孔。首先在PCB板正确位置涂布焊锡膏，再将元器件一一放置在对应位置，然后对PCB板进行加热，焊锡膏融化再冷却后，元器件就焊接在了PCB板上，实现了元器件与PCB板两者之间的互联。20世纪70年代，日本电子行业敏锐地发现了SMT的未来广阔的发展前景，迅速推广SMT，对应的推出了SMT专用焊料（焊锡膏）和专用设备（如贴片机、再流焊炉、印刷机等）以及各种片式元件，不仅良好地完善了SMT体系，更为SMT[1]今后的发展打下了坚实的基础。20世纪80年代，SMT日渐完善并逐渐代替人工1 西安建筑科技大学硕士学位论文插件技术，利用SMT贴装得到的电子产品不仅体积小、性能好，而且价位低、相对性价比极高，因此SMT作为新的电子装联技术被广泛推广。不管是国防军用、还是在社会生活中，处处都有SMT的成果。SMT技术从诞生到改善乃至广泛应用仅用了40年的时间，却展示出了它非凡的发展前途以及创造力，它带来了电子装联技术的“第二次革命”。当今电子市场竞争愈加激烈，为了在竞争中保持优势，各国电子产品制造商都在寻求更新的方法以提高产品的生产效率，因此表面贴装技术的优化逐渐被人们所重视，这一现象也促使了SMT技术的普及和发展。贴片机作为SMT生产线中最核心关键的环节，其工作效率的高低关系着整条SMT生产线的生产效率。因此对贴片机贴装过程进行优化，缩短PCB板元器件贴装的时间，才能提高生产效率，降低成本，实现高效生产，从而更好的满足电子生产竞争的要求。1.2研究意义全球各国都十分重视SMT产业的发展，其中美国、日本、欧洲各国等科技发达国家的SMT技术研究及生产制造都走在世界前列。例如，松下、西门子等企业生产的贴片机基本占据了全球大部分的市场，他们所拥有的先进技术使得他们在电子产业竞争中立于不败之地。电子信息产业是我国的重要产业之一，每年生产销售规模都非常大，我国的电子产品远销海内外。但是在SMT产业的核心技术方面，我国仍落后于一些发达国家，我国电子生产商所用的核心设备一直需要从国外进口，这种情况十分不利于我国电子产业的发展，使得我国始终是一个电子生产大国，而不能成为电子科技发达大国。近些年来，我国开始加大对SMT产业的研究，以期能够为我国的电子产业创造更好的发展前景。SMT作为先进的电子联装技术，不仅可靠性好，而且效率高、成本低，非常适应当今社会电子产品大规模生产的需求。SMT生产线是各种设备组成的，贴片机是所有设备中最关键的一环，贴片机的工作效率直接决定了整条生产线的效率。由此可知，如何提高贴片机的贴片效率，是一个极为重要的研究课题，贴片机贴装优化也成为了研究表面贴装优化的核心问题。在早期，贴片设备结构简单，功能也非常单一，如仅有一个吸嘴工作等，随着不断改进，贴片机逐渐发展为多吸嘴多功能，结构复杂化，出现了拱架式、转盘式、转塔式等各种类型，这些新的发展使得贴装效率得到了巨大的提高，为表面贴装的优化提供了更多可研究的条件与挑战。2 西安建筑科技大学硕士学位论文本课题将使用一种结合蜜蜂进化型遗传算法和蚁群系统的混合智能算法来解决表面贴装技术的优化问题，优化思想为利用提出的新型混合算法寻找贴装过程中的最优路径以提高贴装效率，从而提高资源利用率，降低生产成本以及能量消耗，本课题具有较高的应用价值和宽广的发展前景。1.3研究现状SMT贴装过程优化可分为：喂料器分布优化、元器件拾取顺序优化、元器件[2-3][4-5]贴装顺序优化，这几个优化问题可看做复杂的NP-Hard问题，利用传统的优化方法难以求得最佳优化效果。针对表面贴装技术的优化问题，国内外多位学者运用不同方法对其进行研究。针对单吸嘴贴片机，元器件贴放顺序优化问题通常被看作是旅行商问题[6-8](TravelingSalesmanProblem，TSP)，文献利用传统的遗传算法对该问题进行了[9]研究并成功地得到了较好的成果；Tripak等人使用TSP问题模型，利用模拟退火[10]算法对该问题进行了求解；对于双动臂式贴片机，文献中用遗传算法较好的解决了两个动臂之间的协调与平衡问题，提高了贴片的贴装效率；对于转盘式贴片[11]机，Kumar等人利用启发式算法对该类贴片机贴装进行了优化，得到较好的结果，[12][13]其他学者则将遗传算法、2-opt局部搜索算法等应用于这一问题，实现该类智[14]能算法在转盘式贴片机上的有效应用；文献则使用了禁忌算法对元器件贴装顺[15]序的优化进行了尝试；M.O.Ball和M.J.Magazine则提出“邮递员”问题，针对该问题建立表面贴装技术优化模型，在实际生产中采用“s形”及“打字员”等启发[16][16]式方法实现该问题的优化；针对喂料器分配，文献中提出的贪婪商人算法针[17]对喂料器分配问题进行了有效的解决；文献提出将整个优化问题可以分成两个子问题，第一个子问题为喂料器分配问题，使用二次分配问题将其解决，第二个子问题元器件贴放顺序问题则通过非对称旅行商问题来解决，该子问题模型在以[18]后的研究工作中得到了有效地推广；文献中设计了一个专家系统，对供料器分配、元件贴放顺序等问题进行平衡优化，取得了很好的研究成果；对于转塔式贴[19][20]片机，Crama等人用一种迭代启发式算法对其进行贴装优化；Lee等人针对拱架式多铁头设备，对两个子问题分别采用动态规划算法和最短路径算法来解决。[21]国内对贴片机贴装工艺优化主要的研究成果有：文献中针对多功能贴片机，[22]提出一种手动优化方法；曾又姣等人使用遗传算法对元器件贴装技术进行优化，[23]得到较好的结果；闫红超等人在文献中针对拱架型贴装机，首先改进了遗传算3 西安建筑科技大学硕士学位论文法的适应值线性尺度，然后在此基础上融入模拟退火算法，缩短了PCB的装配时间，[24]优化效果较采用遗传算法或者邻近法更优；袁鹏等人在文献针对多吸嘴的拱架式贴片机，在供料器分配固定的情况下，使用伞布搜索算法优化表面贴装技术，[25]取得了较好的成果；杜轩等人对转塔式贴片机贴装过程建立了优化模型，提出二维符号编码方法，用元件编号描述元件贴装顺序，同时用喂料器编号描述元件布置，改进的遗传算法采用了并行结构，结合局部搜索，对贴装过程进行优化，[26]与其他方法相比较，该算法提高了印刷电路板的贴装效率；杜轩等人针对多动臂转塔式贴片机贴装过程优化又提出了一种分段二元实数编码方法，在一条染色体中同时描述了元件分配、供料器不知和元件贴取顺序，实例计算结果表明，该[27]算法能有效地优化多动臂转塔式贴片机贴装过程；文献中陈铁梅等人使用遗传算法和蚁群算法的混合算法对贴片机喂料器分配问题进行优化，将蚂蚁搜索的结果进行了遗传算法中的交换交叉和变异操作，有效地对元器件贴装顺序已定的条[28]件下的喂料器分配问题进行了优化；文献详细研究多头垂直旋转贴片机的构架特征以及工作流程，建立了符合该类贴片机的数学模型，在基础蚁群算法的基础上，引入两种不同功能的蚂蚁种类，对算法进行了改进，实验表明，该算法提高了贴片机的工作效率，对具有更多贴装头或吸嘴的贴片机贴装优化有一定的借鉴[29]意义；王君等人将分散搜索算法中的参考集引入到cunning蚁群中，提高算法的全局搜索能力，优化元件拾取贴装顺序，结果表明，该算法搜索的结果优于传统[30]cunning蚁群系统得到的解；并使用最近邻算法求解元器件的拾取贴装顺序并通过将其引到分散搜索的框架中求解喂料器分配问题，优化贴装效率。1.4章节安排本文在第一章绪论中首先简介了贴片机优化的研究背景、研究意义、研究现状等内容。第二章首先介绍SMT生产系统基本组成、工艺流程和贴片机的基本组成、分类、工艺流程等基础知识，进一步介绍了贴片机贴装优化问题，并对影响贴片机贴装效率的各种因素进行分析，提出表面贴装优化模型。第三章对遗传算法及蚁群算法的基本原理、算法流程进行了介绍，并讨论了算法的优缺点，详细介绍了蜜蜂进化型遗传算法和蚁群系统，为第四章提出混合智能算法做铺垫。第四章提出了两种改进的基于蜜蜂进化型遗传算法和蚁群系统的混合智能算4 西安建筑科技大学硕士学位论文法，并利用TSP问题对混合算法的实用性进行了测试和对比。第五章采用5种不同元器件个数和种类的PCB板数据，针对表面贴装优化模型进行仿真测试并进行分析。第六章总结与展望。5 西安建筑科技大学硕士学位论文第二章表面贴装技术概述随着全球的电子制造服务(ElectronicManufacturingServices，EMS)市场不断蓬勃地发展，电子行业之间的竞争越来越激烈，由此对PCB板的复杂度提高以及成本降低的要求越来越迫切，表面贴装技术在电子装联技术中的地位也越来越高。本章首先了解一下SMT生产系统基本组成、工艺流程和贴片机的基本组成、分类、工艺流程等基础知识，然后介绍贴片机贴装优化问题，并对影响贴片机贴装效率的各种因素进行分析，最后提出表面贴装优化模型。2.1表面贴装技术的基本结构和工艺流程表面贴装技术的基本结构可分为以下三个部分：1、设备，即运行SMT的硬件。设备包括印刷机、贴片机、焊接设备（波峰焊、再流焊、汽相焊机、激光设备）、焊点测试设备、清洗机、测试仪、维修站等。2、装联工艺，即运行SMT的软件。装联工艺包括贴装材料：焊锡膏与无铅焊料、黏结剂或贴片胶、助焊剂、导电胶；贴装印刷板：基本材料（有机玻璃纤维、陶瓷板、金属基板）和电路图型设计（图形尺寸大小设计、工艺性设计）；涂布工艺：锡膏精密印刷工艺、贴片胶精密点涂工艺及固化工艺；贴装方式：纯片式元件贴装（单面或双面）、SMD与通孔元件混装（单面或双面）；贴片工艺（最优化编程）；焊接工艺：波峰焊（助焊剂涂布方式：发泡、喷雾；双波峰、O型波、温度曲线的设定）和再流焊（红外热风式、N2保护再流焊、汽相焊、激光焊、通孔器件再流焊）；清洗技术：清洗剂与清洗工艺，清洗质量的评估；检测技术：焊点质量检测、在线测试、功能检测；防静电、生产管理。3、电子元器件。元器件包括关键技术（各种的开发与SMD制造技术）、产品设计（结构设计、端子形状、尺寸精度、可焊性）、包装（盘带式、标式、华夫盘、散装式）等。通常SMT单面组装的工艺流程步骤按顺序列为：上料、涂布（丝印或点胶）、贴片、再流焊、清洗、测试、下料。在组装过程中，不同步骤需要不同设备来完成，如上料需要自动上板机，点胶需要自动点胶机，贴片需要贴片机，下料需要自动下板机等各种组装测试仪器。SMT工艺流程如图2.1所示：6 西安建筑科技大学硕士学位论文图2.1SMT工艺流程其中，SMT根据焊接方式不同，具体可分为两种基本工艺流程。一种叫做锡膏—再流焊工艺，另一种叫做贴片—波峰焊工艺。两种工艺各有所长，在实际生产中，根据不同的元件或产品需要，选择不同的贴装工艺，有时会混合使用两种工艺，如PCB板一面使用锡膏—再流焊工艺焊接，另一面使用贴片—波峰焊工艺焊接。（1）锡膏—再流焊工艺简单、快捷，由该工艺生产出的产品体积小，重量轻。其工艺流程如图2.2所示：图2.2锡膏—再流焊工艺流程（2）贴片—波峰焊工艺利用双面板空间，较单板面贴装电子产品的体积大大减小，且在焊接过程中仍使用通孔元件，成本低廉。但对设备要求繁多，焊接过程中缺陷较多，通孔元件的存在使之无法实现高密度贴装。其工艺流程如图2.3所示：图2.3贴片—波峰焊工艺流程2.2表面贴装技术的优点1．贴装密度高与传统穿孔元件相比，片式元器件体积小，重量轻，因其无需穿孔，可高密度贴装。采用SMT得到的产品体积较传统插孔电子产品体积缩小为40%，重量仅为其25%。SMT贴装元件网格从开始的1.27mm发展到了如今的0.63mm网格，且已出现个别达0.5mm网格的安装元件，通孔安装元器件的网格为2.54mm，两相对比表明SMT实现了高密度贴装。2．可靠性高片式元器件一般不良焊点率不足百万分之一，远远低于传统穿孔元器件，因7 西安建筑科技大学硕士学位论文而片式元器件可靠性较高，且元器件体积小，抗震能力更强，十分有利于自动化生产。3．高频特性好片式元器件一般通过焊锡膏直接贴在PCB板上，因此通常无引线或者引线较短，因此寄生电感和寄生电容对整个电路的影响大大降低，充分提高了电路的高频特性。4．成本低首先，片式元器件不仅体积小，且可以高密度贴装，因此印制板所需面积相对减少，与采用通孔技术相比面积可下降91.6%；其次，SMT不需要钻插装孔，出现与电路板接触不足的情况大大降低，减少了返修费用，片式元器件由于体积小，利于大量运输存储；最后，片式元器件更新换代快，部分元件成本已下降到接近于通孔元器件。5．便于自动化生产实现通孔安装的精确自动化，相较于SMT贴片安装，复杂度高，必须扩大原印刷版面积，才不会造成自动插件过程中的元件损坏，同时，扩大印刷版面积也会造成成本增加，焊接过程中，接触不良的比率也会增加。SMT的自动贴装机的吸嘴小于元件面积，运动灵活，贴装精准，可实现高密度贴装。2.3贴片机的结构贴片机，又称为贴装机，是SMT生产设备中最核心、最复杂的一种，它的贴装效率直接影响整个生产线的工作效率。自动贴片机代替了传统人工放置元件的贴装方式，它的出现实现了高速度、高精度、自动化的贴装过程，适应了现代电子产业发展的趋势，使电子工业的发展取得了巨大的进步。贴片机由一开始的简单结构、单一功能改进到如今的复杂结构、多功能，适应了不同产品的需要，不论贴片机如何改进，其基本的结构必不可少，如底座（机架）、PCB定位工作平台、X-Y轴、视觉检测系统、喂料器和贴装头。贴片机的基本结构如图2.4所示。8 西安建筑科技大学硕士学位论文图2.4贴片机的结构1、底座（机架）底座（机架）对于贴片机相当于动物的骨架，起到支撑固定整个贴片机的作用，在底座的基础上安装其他所需部件，因此底座必须拥有足够的精度和韧性，才能保证贴片机的正常运行。根据加工方法，可分为整体铸造式底座和钢板焊接式底座两种，整体铸造式底座结构稳固，但加工要求高、成本也高，而钢板焊接式底座加工简单、成本较低，因此这种底座使用比较普遍。2、PCB定位工作平台PCB定位工作平台采用皮带机构，即流水线传送方式，PCB板上一工序完成后，传送带从上个位置将PCB板传送到贴片机贴装位置，在固定位置将PCB板固定，完成贴装程序后，PCB板由传送带送到下一个位置。3、X-Y轴X-Y轴上安装着贴装头，其运动可以带动贴装头到达预定的拾取位置和贴装位置。4、视觉检测系统视觉检测系统由相关的光学检测器件构成，通过光学检测到的元件和PCB板图像，识别贴装位置和元件角度等完成贴装需要的数据。5、喂料器喂料器位于PCB板固定位置的周围，用于提供各种元器件以便贴装，喂料器可分为带式、盘式、散装盒式等几种类型，是贴片机非常重要部件，对贴片机贴9 西安建筑科技大学硕士学位论文片过程的优化，喂料器分布优化也是必要的一部分。6、贴装头贴装头是拾取贴装元件的执行部件，贴装头上安有吸嘴，可将元件吸取，再通过X-Y轴的运动，贴装到准确位置。贴装头在贴片机诞生之初，仅为一个贴装头一个吸嘴，现在已发展为多贴装头多吸嘴的高级贴片机。2.4贴片机的分类贴片机根据不同的标准可分为多种类型。根据结构特点可分为拱架式贴片机、水平旋转式贴片机、垂直旋转式贴片机、双臂式贴片机等。1）拱架式：拱架式贴片机被看作为通用型贴装机，它是在原来的单吸嘴贴片机的基础上改进得到的，吸嘴数目增加为3个到8个，识别贴装位置使用的是光学对中，工作时依次拾取元器件，再依次贴放到对应位置。该类型贴片机贴装精度较高，使用广泛。拱架式贴片机结构如图2.5所示：图2.5拱架式贴片机结构2）水平旋转式：水平旋转式贴装机又称为转塔式贴装机，它的贴装头是水平圆形的，在边缘多个吸嘴均匀分布，贴装头位置固定，通过水平旋转使吸嘴运动，实现拾取贴装，拾取过程中，喂料器左右移动，将需要拾取的元件送到吸嘴下方，固定PCB板的工作台沿X-Y轴移动，令贴装位置准确的位于贴装吸嘴下方。在转塔运动过程中进行视觉对中。转塔式贴装机的结构与运动方式如2.6所示：10 西安建筑科技大学硕士学位论文图2.6转塔式贴装机结构3）垂直旋转式：垂直旋转式贴装机又称为转盘式贴装机，与水平旋转式不同的是，贴装头被固定在机械臂上，并垂直旋转，贴装头上装有多个吸嘴，运动方式与拱架式贴片机类似，喂料器和PCB板平台是固定不动的，视觉对中由光学相机完成。转盘式贴装机结构如图2.7所示：图2.7转盘式贴装机结构4）双动臂式：该类贴片机有两个装有贴装头的机械臂，可同时进行拾取贴装工作，能够极大地提高贴装效率，但相对的，针对这种贴片机的优化工作也复杂许多。双臂式贴装机的贴装头根据需要也有许多种类，图2.8所示是其中一种双臂转盘式贴装头。11 西安建筑科技大学硕士学位论文图2.8双动臂转盘式贴片机结构除了结构分类以外，根据贴装速度可以将贴片机分为低速贴片机、中速贴片机、高速贴片机以及超高速贴片机。根据功能分类可以将贴片机分为射片机、多工贴片机、高速多功能贴片机等。2.5贴片机的贴装工艺流程贴片机的贴装工艺流程可分为准备工作和贴装工作两个方面。准备工作有三点：1）确定PCB板贴装需要的数据，如需要的元件种类及数目、元件贴装位置及贴装角度等。2）确定喂料器分配问题。3）确定贴装过程中元器件的拾取以及贴装的顺序。贴装工作的过程为：将元器件按已确定的喂料器分配顺序排放在贴片机的一边或两边；然后根据已经确定的元器件的拾取贴放顺序，将贴装头移动到喂料器上方拾取所需的元器件，拾取完毕后，通过贴装头在X-Y轴上的运动，移动到PCB板上方，将元器件准确地贴到对应位置。贴装头上的元器件全部贴装完毕后，重新拾取元器件，通过反复操作，完成PCB板的贴装。在此过程中，贴装头每次拾取元器件然后进行贴放的过程都可以称作一个拾贴循环。2.6影响贴片机贴装效率的因素对于一块已经确定的PCB板，所需要的元器件种类及数目、贴装点坐标等都是已知的，贴装过程中有许多可能影响贴装效率的因素，比如假设贴装头拾取元12 西安建筑科技大学硕士学位论文件的时间是一个固定值，不同的元器件，体积重量不同，在吸嘴拾取后，会使贴装头的移动速度发生变化，由静止到加速再到匀速的过程也会发生变化；贴装过程中出现抛料需要重新拾取等情况也可能发生。在整个运动过程中，匀速运动的时间占了很大比率，为了简化优化计算，一般都会把问题设为每次吸嘴都会精准的拾取元器件，不会抛料，且整个过程是一个恒定匀速的过程。如今所使用的贴片机都拥有多吸嘴的贴装头，在拾取过程中，拾取多个元件，这些元件所放的位置，先拾取哪个，后拾取哪个，或者贴放过程中，先放哪个后放哪个都会影响到贴装头走过的路程，而整个过程是匀速的，因此路程越短，所用的时间也越短，贴装效率越高。由此可见，贴装效率主要受以下因素的影响：喂料器分配、每个贴放组需要的元件、贴放组内拾取贴放的顺序。2.7优化模型完成一块PCB板的贴装需要经过多个贴放循环，每次循环中，贴装头上的吸嘴在喂料器上依次拾取元器件，利用相机对元器件识别校正，然后贴装头移到PCB板上方将元器件贴到正确的位置。属于同一贴装循环的所有元器件组成的元器件组称为贴装组。为达到最大贴装能力，贴装组内元器件的数量通常等于贴装头上吸嘴的数目。因为吸嘴在拾取或者贴装过程中有停顿减速时间，贴装头移动速度也因元器件的体积重量等有所不同，且贴装时间主要取决于贴装头走过的路径长度，所以本文以贴装头走过的路程作为优化的目标。设模型的约束条件是：假定吸嘴能够成功拾取每一个元器件，贴装头移动过程中不存在抛料问题。整个贴装过程有N个贴装循环，即贴装头需要取料N次，每一个贴装循环的过程都是贴装头选取合适的元件，再依次将贴装头上的元件贴l到对应贴装点上。在第i个贴装循环中，贴装头走过的路程如公式（i2-1）所示：abcdllllliiiii（2-1）a式中，li为贴装头从上一轮贴装循环的结束位置到本轮贴装循环的第一个喂料bl器位置的路程长度，i是贴装头从本轮贴装循环的第一个喂料器位置到最后一个cl喂料器位置的路程长度，i是贴装头从本轮贴装循环的最后一个喂料器位置到本dl轮循环的第一个贴装位置的路程长度，i是从本轮循环的第一个贴装位置到最后一个贴装位置（即下一轮的开始位置）的路程长度。整个贴装过程的路程长度如公式（2-2）所示：13 西安建筑科技大学硕士学位论文NNabcdLlliilililiii11（2-2）A={a1,a2,…ai,…aN},B={b1,b2,…bi,…bN},C={c1,c2,…ci,…cN}，其中，ai为贴装循环i中需用的元件集合，bi贴装循环i中拾取循序，ci为贴装循环i中的贴装顺序，本文的贴装优化就是找到最好的A、B、C，得到最好的L；该模型的原型可以看做为带约束的TSP问题。2.8本章小结本章详细介绍了SMT工艺流程，阐述了SMT体系中最重要的设备贴片机的分类以及结构，并讨论了贴片机的工艺流程以及影响贴片机贴装效率的因素，提出了表面贴装优化模型。14 西安建筑科技大学硕士学位论文第三章遗传算法和蚁群算法对于解决表面贴装优化的问题，遗传算法和蚁群算法是应用比较多的两种算法，取得了比较好的优化效果，同时两种算法也存在一些缺点，下面对基本遗传算法和基本蚁群算法进行介绍：3.1遗传算法[31]遗传算法是由美国Michigan大学的Holland教授于20世纪60年代末基于达尔文的进化论和孟德尔的遗传学原理提出并创立的。遗传算法模拟了自然选择和遗传过程中发生的繁殖、交叉和变异现象，根据达尔文适者生存、优胜劣汰的进化原则，通过对群体反复进行选择、变异、交叉操作，不断生成新的群体，使种群不断进化，并进行全局搜索优化群体中的最优个体，以求得满足要求的最优解。3.1.1基本思想遗传算法采纳了自然进化的模型，如模拟自然界的选择、交叉、变异等。在算法运行的开始，对随机生成的种群初始化，种群规模为N，计算种群中每个个体的适应度值。然后开始产生下一代，利用个体适应度值按照某种规则选择个体，选择出的个体作为父代个体存在，父代个体交叉重组为子代个体，所有的子代个体按照设定的概率变异。子代个体经过计算适应度值后将父代个体取而代之组成新的种群，若新的种群不满足停止条件，则继续产生新的下一代，直到满足条件为止。标准遗传算法(NormalGeneticAlgorithm，简称GA)，可简称为遗传算法，其运行步骤如下所示：（1）选择编码策略，对搜索空间进行编码；（2）确定种群规模N、选择概率、交叉概率、变异概率等参数；（3）对应编码策略定义适应度函数f(x)；（4）随机产生初始种群，计算初始种群的适应度值；（5）运用选择算子得到父代个体，对父代个体进行交叉及变异操作，生成子代个体，组成新的种群；（6）判断是否达到停止条件，若已达到，停止算法，否则返回步骤（6）。遗传算法（GA）的流程图如图3.1所示15 西安建筑科技大学硕士学位论文图3.1遗传算法的流程图3.1.2遗传编码编码操作是将实际问题用染色体位串结构表示的操作，针对不同的问题，许多专家提出了不同的编码方式，如二进制编码、十进制编码、浮点数编码、树编码、乱序编码、自适应编码等多种编码方式，其中二进制编码和十进制编码是比较常用的编码方式。针对编码方案的设计，目前尚未形成一套严格完善的评价标准。必须针对不同的问题具体分析，选择相对合适的编码方式，如TSP问题采用路径表示的编码方式会利于理解和运算，而函数优化问题经常采用二进制编码方式来解决等。3.1.3适应度值计算“适应度”一词描述的是生物对于周围环境适应程度的一个量，引用到遗传算法中表示为解个体与最优解之间的契合程度。适应度越高代表该个体越接近最优解，遗传到下一代的几率越大；相反，适应度越低，该个体与最优解之间的契合度越低，遗传到下一代的几率越小。通过设定适应度函数对各个个体进行计算后定量评价。最优化问题通常是求解目标函数最小值，值越小代表适应度越高。16 西安建筑科技大学硕士学位论文遗传算法在选择操作中需要对个体适应度排序，并据此选择父代个体，因此适度函数的值必须为正值，且适应度值高易被选择。因此通常会把求最小值的问题转化为求最大值的问题来计算，即把目标函数转化成求最大值的函数后作为适应度函数来计算。3.1.4选择算子选择(Selection)又可称为复制(Reproduction)，是在种群中选择适应度值高的个体以进行下一步交叉操作的过程，遗传算法中进行选择操作的算子叫做选择算子；首先根据个体适应度值的高低，将染色体排序，适应度值越高，被选择的几率越大；反之几率越小。通过选择操作可以使种群中的个体不断向最优个体靠拢。常用的选择算子有以下几种：（1）轮盘赌选择轮盘赌选择方法是计算每个个体的适应度值，再计算适应度值的总和，最后计算出每个个体适应度值在总值中所占的比率，该比率即该个体被选中的概率。设种群规模为N，某个体i的适应度值为Fi，则个体i被选中的概率Pi如公式3-1所示。FipiN,iN1,2,...,Fjj1（3-1）（2）锦标赛选择锦标赛选择方法是从种群中随机选择出一定数量的个体，将其中适应度值最大的个体复制，重复执行该操作，直到被复制的个体数目达到预先确定的种群规模。锦标赛规模通常用q表示，因此也称作q-锦标赛选择。（3）精英选择精英选择方法一般配合轮盘赌选择方法或者锦标赛选择方法一起使用，通常是在当前个体中选取最优的两个个体，不经过交叉和变异直接复制到下一代。使用该选择算子在算法结束时的最终结果是迭代过程中出现的适应度值最高的个体。（4）最优保留策略最优保留策略是指当前最优个体不进行交叉变异操作，而是直接复制到下一代并替换掉子代个体中的最差个体。（5）随机联赛选择随机联赛选择是一种模拟联赛规则的选择方法，每次选取几个个体中的最优17 西安建筑科技大学硕士学位论文个体复制到下一代，直到被复制的个体达到预先确定的规模。该选择方法的特点是由于个体之间比较时只比较适应度值大小，所以适应度值是正是负并无要求。3.1.5交叉算子交叉操作模仿的是自然界中有性繁殖的基因重组过程，通过交叉操作不仅父代个体所拥有的原有基因复制到下一代个体，而且能够生成更复杂基因。其过程是，首先确定进行交叉的两个父代个体；随即选择一个或多个位置作为交叉点；根据交叉概率pc对两个父代个体进行交叉，生成两个子代个体。比较常用的交叉算子有：（1）单交叉点法选择一个交叉点，子代在交叉点前面的基因从一个父代基因那里得到，后面的部分从另外一个父代基因那里得到，该方法既可以应用于二进制编码也可用于互换编码。如：交叉前，父代A：00000|01110000000010000父代B11100|00000111111000101交叉后，子代A：00000|00000111111000101子代B：11100|01110000000010000（2）双交叉点法选择两个交叉点，交叉点两边的基因不动，交叉点之间的基因互换，生成的两个个体为子代个体，该方法既可以应用于二进制编码也可用于互换编码。如：交叉前，父代A：00000|01110000|000010000父代B：11100|00000111|111000101交叉后子代A：00000|00000111|000010000子代B：11100|01110000|111000101（3）部分映射交叉部分映射交叉是指，选择两个交叉点，交叉点两边的基因先不动，将两交叉点之间的基因互换后，将两边基因中与互换基因段中相冲突的元素用另一父代个18 西安建筑科技大学硕士学位论文体的相应元素代替，该方法常用于互换编码，又称部分匹配交叉。如，交叉前，父代A：872|130|9546父代B：983|567|1420变为，872|567|9546983|130|1420交叉后，子代A：802|567|9143子代B：986|130|5427（4）顺序交叉法从父代个体中随机选择一个基因段，放到子代个体的对应位置；子代空余的位置按另一个父代个体的基因顺序进行填充，且不能与基因段中的元素冲突。如，交叉前，父代A：872|130|9546父代B：983|567|1420交叉后，子代A：985|130|6742子代B：821|567|30943.1.6变异算子在生物遗传和进化过程中，可能因为某些偶然因素（如辐射）使得细胞分裂复制时出现差错，从而使新生命的染色体中出现了不属于母体的基因，出现新的生物性状，这种现象成为变异。遗传算法的变异操作就是模拟的这一过程。常用的两种变异算子如下所示：（1）基本位变异算子基本位变异算子通常用于二进制编码，是指对交叉后产生的染色体位串中随机选择的一位或几位基因进行变异。若二进制编码染色体选中的基因值为0，则变异为1，反之若基因值为1，则变异为0。变异前，00000111000000001000019 西安建筑科技大学硕士学位论文变异后，000001110001000010000（2）逆转变异算子（用于互换编码）（源代码中使用类似此方法）逆转变异算子通常用于互换编码，是指在个体染色体位串中随机挑选两个变异点，然后将两个变异点之间的基因进行交换。变异前，1346798205变异后，12467983053.1.7遗传算法的特点及不足遗传算法有以下几种特点：（1）遗传算法的搜索过程是群体搜索，而不是个体搜索，这种搜索方式在整个问题空间中进行搜索，因此能够加大算法的全局搜索力度；（2）遗传算法通过目标函数值对求得的解进行评价，这种评价方式使得遗传算法广泛适用于多种问题的求解。（3）遗传算法每一次迭代只对被选的有限个体进行操作，但过程中处理的信息量远远高于种群的规模；（4）遗传算法代进化过程简单明了，运行方式以及实现步骤规范易懂，不管是简单的问题还是复杂的系统模拟或组合优化问题，遗传算法都十分适用；（5）遗传算法具有很强的鲁棒性；遗传算法在各种优化问题中应用广泛，但许多情况下遗传算法无法求得最优解。遗传算法具有比较强的鲁棒性和极好的全局搜索能力，但它运算时是对一个种群进行筛选组合，当种群规模较大时，无法考虑到每个解，操作不够精细，局部搜索能力不足。3.1.8蜜蜂进化型遗传算法蜜蜂作为自然界的园丁，具有着强大的繁殖力，它的繁殖方式不同于普通的有性生殖，每个蜂巢中的蜜蜂都拥有共同的母亲蜂王。蜂王是唯一发育完全并具有产卵功能的雌蜂，它拥有整个蜂巢中的最高地位以及最高待遇，在交配时期，雄蜂通过竞争获取交配机会；而当蜂巢中出现另一个发育完全的雌蜂时，两只雌蜂必须进行争斗，直到一方死亡，胜利的一方成为新的蜂王。蜜蜂进化型遗传算20 西安建筑科技大学硕士学位论文法（BEGA）从蜂蜜的交配繁殖过程获得启示，对遗传算法加以改进。该算法充分利用了拥有最优基因的蜂王对种群进化所起的作用，同时为了保持种群的多样性，引入了“混血”思想，即在蜜蜂繁殖过程中加入“外来种群”。基于提高遗传算法性能的目的，算法在模拟蜜蜂交配繁殖过程时对某些部分进行了取舍：工蜂在整个种族的作用是劳动，对繁殖过程无任何实质性影响，所以在种群构成中对这一概念舍弃；通过对种群最优解以外的个体进行选择作为雄蜂，进行下一步的交叉操作；随机产生部分新个体作为外来种群中的雄蜂进入交叉操作；种群中的最优个体作为蜂王，以概率与雄蜂进行交叉操作；蜂王更新时，失败的一方并非舍弃（死亡），而是作为普通雄蜂存在。蜜蜂进化型遗传算法的流程图如图3.2所示：图3.2蜜蜂进化型遗传算法的流程图[32]蜜蜂进化型遗传算法（BeeEvolutionaryGeneticAlgorithm，BEGA）的基本思想是：在种群A(t)中选出最优个体，并与上一代蜂王相比较，优胜者作为第t代蜂王，记为Queen，通过比例选择从种群A(t)选出N201个个体，并随机产生N12个新个体，然后，Queen分别与上述N2个个体（N2个被选个体和N12个随机个体共同组成）配对，这N2对个体经交叉、变异之后，21 西安建筑科技大学硕士学位论文获得子代种群B(t+1)，找出B(t+1)中的最优个体，记作Queen_New，比较Queen_New和Queen的适应度，若Queen_New更优，则B(t+1)记作A(t+1)成为新种群，Queen_New成为第t+1代蜂王，否则，Queen替换B(t+1)中的最差个体后，B(t+1)中记作A(t+1)，而第t+1代蜂王仍为Queen。蜜蜂进化型遗传算法不仅具有全局寻优能力强、鲁棒性强等优点，而且与基本遗传算法相比较具有更好的求解效率和求解效果；但其对反馈信息利用不够，种群很大且需解决的问题规模较大时，局部搜索能力不强，当求解到一定范围时容易做大量冗余迭代，求解效率不理想。3.2蚁群算法蚁群算法是一种模仿蚂蚁觅食行为的仿生优化算法。在自然界中，单只蚂蚁的行为简单，力量薄弱，但经过群体协作却能表现出超过群体规模的智慧与力量。针对这种现象，在20世纪90年代初，意大利学者M.Dorigo、V.Maniezzo、A.Colorini[33]等人提出了蚁群优化算法。该算法按照启发式思想，模仿蚂蚁的觅食行为，通过信息传媒—外激素（Pheromone）的诱发作用，逐渐收敛到问题的全局最优解。3.2.1基本思想经过长期研究，仿生学家发现：蚂蚁在走过的路径上会释放出一种特殊分泌物（信息素）来记录走过的路径，当碰到一个从未走过的路口时，会随机选择其中一条路径前行，并在该路径上释放出信息素。蚂蚁经过的路径越长，路径上信息量越小。以后到达的蚂蚁在该路口选择时，选择信息素浓度较高的路口的几率较大，这样就使信息素浓度较高的路径的浓度更高，使蚂蚁选择该路径的几率更大，如此形成了信息素的正反馈机制。最优路径的信息量随着走过蚂蚁的数量的增加会越来越大，其他路径上的信息素会随着时间流逝而挥发，这样逐渐地蚂蚁会集中到一条路径上，该路径就是蚂蚁寻找食物的最佳路径。即使在蚂蚁通过的路径上出现障碍物导致蚂蚁队形分散，经过一段时间，蚂蚁仍可以找到最优路径，可见在觅食过程中，虽然单只蚂蚁的力量有限，但蚁群整体能力较强，具有很高的自组织性，且能很快的适应环境变化。通过觅食行为不难看出个体与种群之间的协作关系，蚂蚁个体根据周围环境对路径做出选择，而蚂蚁选择哪条路径是由其内部模式决定的；在群体中，蚂蚁之间利用信息素和环境进行通信，再通过自组织过程可形成高度有序的群体行为。基本蚁群算法经常被用作解决TSP问题，本文TSP问题为代表对基本蚁群算22 西安建筑科技大学硕士学位论文法的基本流程进行介绍。设城市规模为n，蚂蚁种群规模为m，令dij（i，j=1，2，3，…，n）表示城市i和j之间的距离，ijt表示在t时刻城市i与j之间的路径上的信息素残留。蚂蚁k需要根据各条路径残留信息素以及路径长度来决定下一个到达的城市，用kptij表示蚂蚁k在t时刻从城市i去往城市j的概率，如则如公式3-2所示：ijttij,jJikptkijttij（3-2）ijjallowedk0,otherwiseα为信息素启发式因子，β为期望启发式因子，ij为城市i和j之间的残留信息素，ij为启发因子，是城市i和j之间距离的倒数，allowedk为候选城市集合，表示蚂蚁k未选择的城市，即下一步允许选择的城市集合。当蚂蚁k遍历了所有城市，再回到出发点时表示蚂蚁k完成了一次周游，蚂蚁k本次走过的路径便是TSP问题的一个解。当所有蚂蚁均完成一次遍历后，对各路径上的信息素进行更新，如公式3-3及3-4所示：ijt11ijtij（3-3）mkijij（3-4）k1其中01表示信息素的挥发系数，1表示信息素的保留系数，ij表k示本次迭代后增加的信息素量。表示第k只蚂蚁本次迭代留下的信息素。若蚂ijk蚁k本次迭代未经过路径（i，j），则的值为零。ij根据信息素更新策略的不同，DorigoM提出了三种基本蚁群算法模型，分别为Ant-Cycle模型、Ant-Quantity模型以及Ant-Density模型。k在Ant-Cycle模型中如公式3-5所示：ijQ,,若蚂蚁经过路径kijkLk（3-5）ij0,否则其中，Q为蚂蚁遍历一次释放的信息素总量。Lk表示蚂蚁k本次迭代走过的路径长度。k在Ant-Quantity模型中如公式3-6所示：ijQ,,若蚂蚁经过路径kijkdij（3-6）ij0,否则23 西安建筑科技大学硕士学位论文k在Ant-Density模型中如公式3-7所示：ijQk,,若蚂蚁经过路径ijk（3-7）ij0,否则由以上三个公式可知，Ant-Quantity模型及Ant-Density模型是利用局部信息更新路径上的信息素；而Ant-Cycle模型中利用的是全局信息。由于Ant-Cycle模k型中信息增量兼顾了全局，具有整体性，因此解决问题时在三个模型中性能最ij好，因此通常采用Ant-Cycle模型作为蚁群算法的基本模型。3.2.2蚁群算法的特点及不足蚁群算法的特点主要有以下几个方面：（1）蚁群算法具有自组织性。自组织和他组织的区分在于组织的指令取决于系统内部还是系统外部。蚁群算法充分体现了它的自组织性，算法初期蚂蚁个体无序的寻找解，经过迭代进化后，蚂蚁个体之间通过信息素传递的信息，开始向最优解附近靠拢，最终找到最优解。（2）蚁群算法具有并行性。蚁群算法利用多只蚂蚁同时进行搜索，搜索过程中，蚂蚁个体对下一个城市的选择仅受信息素以及路径长度的影响，与其他蚂蚁个体搜索过程无关。（3）蚁群算法具有正反馈特征。通过之前蚂蚁遍历留下的信息素对蚂蚁搜索进行指导，路径残留的信息素浓度越高越容易吸引蚂蚁从该路径经过。正反馈是蚁群算法的重要特征。（4）蚁群算法具有较强的鲁棒性。在搜索过程中，蚁群算法不需人工调整，不依赖初始路线。其次蚁群算法参数设定少且简单，容易掌握，易于广泛应用。蚁群算法也存在一些缺陷：（1）搜索时间较长。蚁群算法在运行的初期阶段，所有路径上的信息素差别很小，所以蚂蚁初期选择比较随机、杂乱无章，经过较长时间的进化，才可以体现出较优路径的信息素优势，进而使蚂蚁向较优路径靠拢，最终得到最优路径，完成这一进化过程需要较长时间。（2）易出现早熟停滞现象。蚂蚁初期搜索时主要靠城市间的距离来判断下一步选择，蚁群算法经过一段时间的迭代后，几条次优路径上的信息素浓度渐渐高于其他路径，蚂蚁在信息素的指导下向这几条路径集中，若某条次优路径的信息素过浓，则蚂蚁都集中到该路径上，则无法选出全局最优路径，出现早熟停滞现象。24 西安建筑科技大学硕士学位论文3.2.3蚁群系统蚂蚁系统(antsystem，AS)寻优过程较慢且极易陷于停滞，经过几年时间的改[34]进，在1997年M．Dorigo等人又提出了蚁群系统(antcolonysystem，ACS)，该算法是性能最好的蚁群优化算法之一。蚁群系统广泛应用于不同领域，一些学者在蚁群系统的基础上进行改进，或者与其他算法相结合，利用蚁群系统弥补其他算法性能上的不足，以达到更好的求解效果。下面以TSP问题为模型对ACS的基本流程进行介绍。蚁群规模为m。蚂蚁k下一个访问的城市要从蚂蚁k未访问过的城市中选取，蚂蚁k需根据当前城市到备选城市之间的路径长度和该路径的信息素值选取下一个城市。设蚂蚁k当前所在城市为i，按照状态转换规则选择下一个城市j，如公式3-8和3-9所示：在t时刻，当qq0时，stargmaxijijt（3-8）jallowedk否则，ijttijkttptijijij（3-9）jallowedk0,otherwise式中，α为信息素启发式因子，β为期望启发式因子，ij为城市i和j之间的信息素，ij为启发因子，是城市i和j之间距离的倒数，allowedk为候选城市集合，q是在[0,1]区间均匀分布的随机数，q0为设定的阈值。蚁群系统与基本蚁群算法另一个不同之处为更新信息素，蚁群系统的更新信息素分为局部更新与全局更新两种，蚂蚁k每经过一条路径，则按照公式3-10对该路径进行局部信息素更新：ijtt111ij1Q0（3-10）式中，Q0为初始信息素，ρ1为局部挥发因子。所有蚂蚁遍历后，选出m条路径中的最优路径，用该路径进行全局信息素更新，如公式3-11和公式3-12所示："ijtt1122ijij（3-11）1"()Lbest,ifijbestij（3-12）0,otherwise式中，ij为路径（i，j）的信息素，ρ2为全局挥发因子，Lbest为最优个体的适25 西安建筑科技大学硕士学位论文应度，best为最优路径。蚁群系统的流程如图3.3所示：图3.3蚁群系统流程图蚁群系统与基本蚁群算法相比，兼顾了局部搜索和全局搜索，提高了寻优能力以及收敛速度；由于初期信息素匮乏，算法初期寻优速度较慢，且问题规模较大时，也极易出现早熟停滞现象。3.3本章小结本章分别介绍了遗传算法和蚁群算法的基本知识，并分析了两种算法的优点及不足，详细介绍了蜜蜂进化型遗传算法和蚁群系统，为下一章提出混合智能算法做铺垫。26 西安建筑科技大学硕士学位论文第四章蜜蜂进化型遗传算法和蚁群系统构成的混合算法蜜蜂进化型遗传算法不仅具有全局寻优能力强、鲁棒性强的优点，而且与基本遗传算法相比较具有更好的求解效率和求解效果；但其对反馈信息利用不够，种群较大且维数较多时，局部搜索能力较弱，当求解到一定范围时容易做大量冗余迭代，求解效率不理想。蚁群系统通过信息素的积累反馈信息，最终收敛于最优解，具有较好的寻优能力，但由于初期信息素匮乏，算法初期求解速度较慢，也极易出现早熟停滞现象。本章提出了蜜蜂进化型遗传算法和蚁群系统串行和并行两种方式的混合智能算法，混合算法结合了蜜蜂进化型遗传算法和蚁群系统的优点，使算法既能利用蚁群系统对信息素进行学习积累，又能利用蜜蜂进化型遗传算法对蚁群系统初期信息素进行指导，兼顾全局搜索和局部搜索，有较高的求解速度和求解效果。4.1蜜蜂进化型遗传算法和蚁群系统构成的具有串行结构的混合算法本文对蜜蜂进化型遗传算法和蚁群系统进行混合，提出一种蜜蜂进化型遗传算法和蚁群系统构成的具有串行结构的混合算法，称之为蜜蜂进化型遗传—蚁群算法(BeeEvolutionaryGenetic-AntColonyAlgorithm，BGAA)，该算法在寻优过程中用改进的蜜蜂进化型遗传算法产生的较优解指导蚁群系统的信息素分布，然后利用蚁群算法的高效收敛优势和正反馈机制获得路径最优解；蜜蜂进化型遗传算法以总种群中的最优个体作为蜂王与雄蜂进行交叉操作，进化过程中加入的随机种群保持了种群多样性，提高了算法的勘探能力，防止了早熟现象的产生。运用蜜蜂进化型遗传算法得到的种群中最优个体（即蜂王Queen）更新全局信息素后进行蚂蚁搜索，缩短了蚁群系统初期搜索时间，提高了蚁群搜索的效率；利用蚁群系统的信息反馈和学习机制，提高了整个算法的收敛速度；同时用蚁群搜索的结果替换种群中的最差个体，在蜜蜂进化型遗传算法中加入信息反馈机制，防止了冗余迭代的产生。4.1.1改进的蜜蜂进化型遗传算法蜜蜂进化型遗传算法将种群中的最优个体作为蜂王Queen与被选个体（雄蜂）进行交叉操作，加强了对种群最优个体包含信息的利用，且在进化过程中引入了一个随机种群，提高了算法的勘探能力。BGAA的蜜蜂进化型遗传算法部分在此27 西安建筑科技大学硕士学位论文基础上，引入自适应交叉变异操作，有利于算法开采与勘探的平衡。种群pop(t)中最优个体，作为Queen；采用比例选择从总种群中选取N*u/2个个体，再随机生成N*(1-u)/2个个体，作为父代个体组成种群popa(t+1)，该种群规模为N/2，其中N表示BEGA的种群规模，N=NN-m，NN表示总种群规模，0≤u≤1；u若过小，容易引起种群退化，若过大，种群多样性降低，易陷入局部最优解，本文将u设置为0.5。将Queen与popa(t+1)中N/2个个体分别交叉变异，得到种群popb(t+1)，种群规模为N，找出种群popb中的最优解Queen_new，若Queen_new优于Queen，则Queen_new作为第t+1代Queen，否则Queen作为第t+1代Queen。交叉操作采用了自适应交叉算子，交叉概率如公式（4-1）所示：pcmaxt,pptccminpc1/tttmax(4-1)tppp,cccminmin式中，tPPPc为当前的交叉概率，cmax为最大交叉概率，cmin为最小交叉概率，t为当前进化代数，t为最大进化代数。交叉概率随着迭代次数增加而减小，并设tmax定自适应范围[P,P]，有利于算法开采和勘探能力的平衡。cmincmax改进的变异算子：算法中同样采用了自适应变异算子，变异概率如公式（4-2）为：pmmaxt,pptmmminpm1/tttmax(4-2)tppp,mmmminmin式中，tPPPm为当前的交叉概率，mmax为最大交叉概率，mmin为最小交叉概率，t为当前进化代数，t为最大进化代数。tmax4.1.2改进的蚁群算法蚂蚁k下一个访问的城市要从蚂蚁k未访问过的城市中选取，蚂蚁k需根据当前城市到备选城市之间的路径长度和该路径的信息素值选取下一个城市。设蚂蚁k当前所在城市为i，按照状态转换规则选择下一个城市j，如公式（4-3）和（4-4）所示：在t时刻，当qq时，0stargmaxijijt（4-3）jallowedk否则，28 西安建筑科技大学硕士学位论文ijttijkttptijijij（4-4）jallowedk0,otherwise式中，α为信息素启发式因子，β为期望启发式因子，ij为城市i和j之间的信息素，ij为启发因子，是城市i和j之间距离的倒数，allowedk为候选城市集合，q是在[0,1]区间均匀分布的随机数，q0为设定的阈值，本文将q0设为0.75。蚂蚁k每经过一条路径，则按照公式（4-5）对该路径进行局部信息素更新：ijtt111ij1Q0（4-5）Q0为初始信息素，ρ1为局部挥发因子。将总种群中最优个体选出并用该个体进行全局信息素更新，如公式（4-6）所示：1ijt1122ijt(),Lbestifijbest（4-6）式中，ij为路径（i，j）的信息素，2为全局挥发因子，Lbest为最优个体的适应度，best为最优路径。m个蚂蚁遍历后得到m条路径，将这m条路径作为m个个体，代替popb(t+1)中最差的m个个体，得到新的种群popc(t+1)，popc(t+1)作为pop(t+1)进入下一轮迭代。4.1.3BGAA的算法流程Step1参数初始化，信息素初始化；Step2随机生成初始种群pop(t)，其规模为N，令迭代次数t=0；Step3计算种群适应度，其中最优个体作为蜂王Queen；Step4如满足停止准则，输出结果并停止运行；否则，执行Step5；Step5t=t+1，采用比例选择从总种群中选取N*u/2个个体，再随机生成N*(1-u)/2个个体，作为父代个体组成父代种群popa(t)，该种群规模为N/2；Step6用蜂王与种群popa(t)中的N/2个个体分别以概率进行交叉操作；变异后生成子代种群popb，种群规模为N，最优个体为Queen_new；Step7比较Queen和Queen_new，更新Queen，并用Queen进行全局信息素更新；Step8进行蚂蚁搜索，蚂蚁每走一步，进行信息素的局部更新；Step9用蚂蚁经过的m条路径作为m个个体代替种群popb(t)中最差的m个个体组成种群popc(t)；29 西安建筑科技大学硕士学位论文Step10令pop(t)=popc(t)，种群规模为N，返回Step3。4.1.4算法验证旅行商问题（TravelingSalesmanProblem，TSP）是一个经典的组合优化问题，属于一种比较容易理解的NP-hard问题。TSP问题作为一个标准的测试问题，经常被用来测试算法的有效性，为一种新算法的实用性检测提供了很好的依据。关于TSP的描述：设有n座城市，一个旅行推销员从某城市出发，要经过其余n-1个城市后，回到出发的城市，在这个过程中，每个城市只能走一遍，他怎样选择最短路线？这就是著名的旅行商问题（TSP）。本文从TSP算例库（http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/）中选取了两个TSP问题即Oliver30问题以及eil51问题，对BGAA的有效性进行验证。在MATLABR2009a环境中，蚁群系统（AntColonySystem，ACS）、蜜蜂进化型遗传算法（BeeEvolutionaryGeneticAlgorithm，BEGA）和BGAA利用Oliver30问题以及eil51问题对算法的有效性进行仿真验证，分别独立测试50次，并将TSP30[35-36][35,37]问题的实验结果与文献给出的数据进行对比，而eil51的实验结果与文献给出的数据对比。相关参数设定为：蜜蜂进化型遗传算法种群规模N为100，交叉概率初值为0.9，变异概率初值为0.3，蚂蚁数目m=10，α=1，β=5，ρ1=0.1，ρ2=0.1。表4.1、表4.2关键字说明：Lbest为最优长度，NC为运算次数，Nc为出现当前最优解的次数，ns为出现最优解的迭代次数，La为平均路径，Lb为当前已知的最优解。Oliver30问题实验结果如表1所示。表4.1Oliver30问题实验结果算法LbestNCNcnsLaLb[35]文献423.7//52/[36]文献424.6100//ACS423.7502109429.8423.7BEGA426.9500124447.9BGAA423.7502241424.3由表4.1可知，在解决Oliver30问题的50次独立实验中，BGAA有22次能收敛到最优解423.7，路径如图4.1所示，且最快可在第41代收敛，算法所得结果的平均值为424.3；而ACS仅两次收敛于已知最优解423.7，最快在109代收敛，算法结果平均值为429.8；BEGA最优收敛于426.9，最快在124代收敛算法结果平均值为447.9。通过三个算法的对比可以看出，BGAA具有较好的收敛精度和稳定性；[35-36][35]通过与文献的对比可以看出，本文算法的收敛速度优于文献，其搜索性能30 西安建筑科技大学硕士学位论文[36]优于文献。1009080706050403020100020406080100图4.1Oliver30问题最优解路径在eil51问题中常用整数方式求解，即将城市间的距离长度四舍五入化为整数再求解，TSP算例库即用整数方式求解eil51问题，其最优解为426，路径如图4.2所示，实验结果如表4.2所示。表4.2eil51问题实验结果算法LbestNCNcnsLaLb[35]文献430.7///446.3[37]文献42651//442.4ACS432500299439.4426BEGA438500156441.0BGAA42650775434.5由表4.2可知，在50次独立实验中，BGAA有7次能收敛到最优解426，且最快可在第75代收敛；ACS、BEGA最优收敛于432和438，最快收敛代数分别为299、156，因此BGAA与两者相比在搜索的精度有了较大提升，收敛速度也有了较大的提高，且减少了冗余迭代；ACS、BEGA得到的平均值为439.4、441.0，通过与BGAA平均值434.5的对比，表明BGAA具有较好的稳定性；且保证搜索性能的[35,37]情况下与文献相比，BGAA的稳定性较优。31 西安建筑科技大学硕士学位论文706050403020100010203040506070图4.2eil51问题最优整数解路径4.1.5验证结论BGAA作为蜜蜂进化型遗传算法和蚁群系统构成的串行结构的混合智能算法，相对于单一的蜜蜂进化型遗传算法和蚁群系统，求解的精度有了很大的提升，且在求解过程中，减少了很多冗余迭代，提高了求解效率。通过与其他文献的算法结果进行对比，表明BGAA具有较好的稳定性。但由于算法使用了串行结构，算法单次迭代运行时间较长，整体运行速度略慢，需要进一步改进。4.2蜜蜂进化型遗传算法和蚁群系统构成的具有并行结构的混合算法BGAA具有较高的求解精度和稳定性，但算法整体运行时间较长，针对该问题，本文又提出了一种并行结构的基于蜜蜂进化型遗传算法和蚁群系统的混合智能算法（theHybridIntelligentAlgorithmbasedonBeeEvolutionaryGeneticAlgorithmandAntColonySystem，BAHA）。BAHA在寻优过程中，分别用改进的蜜蜂进化型遗传算法和改进的蚁群系统从两条路径进行搜索，生成两个种群，然后将两个种群合并构成新的总种群，由此实现两个种群间的信息共享；其中，蜜蜂进化型遗传算法以总种群中的最优个体作为蜂王与雄蜂进行交叉操作，进化过程中加入的随机种群保持了种群多样性，提高了算法的勘探能力，防止了算法早熟现象的发生。运用总种群中最优个体更新全局信息素后进行蚂蚁搜索，缩短了ACS初期搜索时间；同时利用ACS的信息32 西安建筑科技大学硕士学位论文反馈和学习机制，充分利用了两个种群的反馈信息，提高了算法的收敛速度；算法中加入了信息素重置操作，防止了算法陷入局部最优解。引入局部搜索算子，在每代最优解附近进行更加精细的搜索，进一步增强了算法的开采能力，达到了开采与勘探的平衡。算法具体实现如下所示：4.2.1改进的蚁群系统蚁群系统是意大利学者M.Dorigo于1997年提出的，该算法作为性能最好的蚁群算法之一，广泛应用于各个领域。本文在蚁群系统的基础上，引入了信息素重置操作，防止算法陷入局部最优解。将蚁群规模设为m，城市数目设为n。首先将蚂蚁随机放在初始位置，蚂蚁k所在的初始位置即蚂蚁k访问的第一个城市，蚂蚁k每访问一个城市，将该城市放入Tabu中，剩余城市则作为待访问城市。设蚂蚁k当前所在城市为i，蚂蚁k下一个访问的城市要从蚂蚁k未访问过的城市中选取，蚂蚁k需根据当前城市到备选城市之间的路径长度和该路径的信息素值选取下一个城市，即按照状态转换规则选择下一个城市j，如公式（4-7）和（4-8）所示：在t时刻，当qq时，0stargmaxijijt（4-7）jallowedk否则，ijttijkttptijijij（4-8）jallowedk0,otherwise式中，α为信息素启发式因子，β为期望启发式因子，为城市i和j之间的ij信息素，为启发因子，是城市i和j之间距离的倒数，allowed为候选城市集合，ijkq是在[0,1]区间均匀分布的随机数，q为设定的阈值，本文将q设为0.75。00每次迭代开始，从总种群POP中选出最优个体，即Queen并用该个体进行全局信息素更新，如公式（4-9）和（4-10）所示："ijtt1111ijij（4-9）1"()Lbest,ifijbestij（4-10）0,otherwise式中，为路径（i，j）的信息素，ρ1为全局挥发因子，Lbest为最优个体的适ij应度，best为最优路径。蚂蚁k每经过一条路径，则按照公式（4.11）对该路径进行局部信息素更新：33 西安建筑科技大学硕士学位论文ijtt112ij2Q0（4-11）Q为初始信息素，为局部挥发因子。02信息素重置设置：蚁群系统利用正反馈原理强化已找到的次优解，当迭代到一定代数后，次优解路径上的信息素不断得到强化，而其他路径上的信息素不断弱化，使得蚂蚁集中在几条次优解路径上，从而陷入了局部最优解。为了防止早熟现象的产生，BAHA加入重置信息素操作，即当总种群POP的最优个体Queen在连续20次迭代中没有变化时，将全部信息素重设为Q。04.2.2改进的蜜蜂进化型遗传算法蜜蜂进化型遗传算法将种群中的最优个体（蜂王Queen）与被选个体（雄蜂）进行交叉操作，增强了对最优个体基因的开采能力，选择雄蜂过程中引入随机种群这一操作可提高算法的勘探能力。本文在此基础上，引入自适应交叉变异操作，有利于算法开采与勘探的平衡，同时改进更新种群操作，保留优秀父代个体。改进的选择算子：采用轮盘赌选择从总种群POP中选取N*u/2个个体，再随机生成N*(1-u)/2个个体，作为父代个体组成种群POPb，该种群规模为N/2，其中N表示蜜蜂进化型遗传算法的种群规模，N=NN-m，NN表示总种群规模，0≤u≤1；u若过小，容易引起种群退化，若过大，种群多样性降低，易陷入局部最优解，本文将u设置为0.5。改进的蜜蜂进化型遗传算法选择过程如图4.3所示：总种群POP轮盘赌选择随机生成N*(1-u)/2N*u/2个个体个个体合并种群POPb图4.3改进蜜蜂进化型遗传算法选择过程改进的交叉算子：将总种群POP中的最优个体作为蜂王Queen与父代个体（雄蜂）进行交叉操作，充分利用总种群的共享信息，交叉得到的子代个体拥有蜂王的优秀基因，提高了较优个体占总个体的比例，且引入的外来种群（随机种群）提高了算法的勘探能力，防止种群多样性降低。交叉操作采用改进的OX顺序交叉算子，交叉方法以下面两个个体（父个体）34 西安建筑科技大学硕士学位论文为例说明（/*/表示交叉的部分）：父个体p1：(123/456/789)；父个体p2：(635/197/248)。将父个体p2的交叉部分复制到父个体p1交叉部分前，同时将父个体p1的交叉部分复制到父个体p2交叉部分前，得到中间个体：中间个体l1：（123/197/456789）；中间个体l2：（635/456/197248）。将中间个体插入的部分固定，对其余部分进行扫描，去掉与插入部分相同的城市码，即中间个体l1插入部分的城市码（197）固定，其余部分进行扫描，l1中第1、10、12个编码为城市码1、7、9，与插入部分城市码相同，去掉；同理，中间个体l2插入部分的城市码（456）固定，其余部分进行扫描，l2中第11、3、1个编码为城市码4、5、6，与插入部分城市码相同，去掉。扫描删除完成后即得到子个体为：子个体c1：(231974568)；子个体c2：(345619728)。交叉操作采用了自适应交叉算子，交叉概率如公式（4-12）所示：pcmaxt,pptccminp1/ttctmaxtppp,cccminmin(4-12)式中，tPPPc为当前的交叉概率，cmax为最大交叉概率，cmin为最小交叉概率，t为当前进化代数，t为最大进化代数。交叉概率随着迭代次数增加而减小，并设tmax定了自适应范围[P,P]，有利于算法开采和勘探能力的平衡。cmincmax改进的变异算子：算法中同样采用了自适应变异算子，变异概率如公式（4-13）为：pmmaxt,pptmmminp1/ttmtmaxtppp,mmmminmin(4-13)tPP式中，Pm为当前的交叉概率，mmax为最大交叉概率，mmin为最小交叉概率，tt为当前进化代数，tmax为最大进化代数。更新种群策略：为保留父代个体中的优秀基因，本文对种群更新进行了改进，在交叉变异操作后，得到的种群POPc规模为N，将种群POPb和种群POPc合并35 西安建筑科技大学硕士学位论文生成种群POPd，其种群规模为3*N/2，并从种群POPd中采用轮盘赌选取N个个体组成种群POPe，用蜂王替换POPe中最差个体，再将POPe与种群POPa合并生成总种群POP，其规模为N+m个，即NN个。更新种群过程如图4.4所示：图4.4更新种群过程4.2.3局部搜索每次迭代得到当代最优个体以后，采用局部搜索算子在当代最优解附近进行更精细的搜索，提高了算法的收敛效率，加快了算法的收敛速度。局部搜索方法有很多，如2-OPT算法、3-OPT算法等。在本文算法中局部搜索算子采用改进的3-OPT算法，方法如下：（1）假设d(X,Y)表示城市X和城市Y之间的距离，R表示最优个体中第i个城市，i城市数目为n，则从[1,n]之间随机选择3个点i，j，h，其中id(Ri，Rj)+d(Ri+1，Rj+1)，则将子集合{Ri+1,…,Rj}中元素反向排列，同理，若d(Rj，Rj+1)+d(Rh，Rh+1)>d(Rj，Rh)+d(Rj+1，Rh+1)，则将子集合{Rj+1,…,Rh}中元素反向排列；（2）将操作（1）重复五次；（3）然后对经过操作（2）后的路径进行微调，选择五个点w、w+1、w+2、w+3、w+4，其中，w为[1,n-5]之间某数，对中间三个数w+1、w+2、w+3进行全排列，每排列一次，计算从点w到点w+4的路径距离，如S1=d(Rw，Rw+1)+d(Rw+1，Rw+2)+d(Rw+2，Rw+3)+d(Rw+3，Rw+4)，依次算出S1、S2、S3、S4、S4，从中选取路径最小的一个排列，并将对应的点排列代替原来路径中的点排列。36 西安建筑科技大学硕士学位论文4.2.4算法流程BAHA流程如下所示：Step1参数初始化，信息素初始化，随机生成初始总种群POP，其规模为NN，令迭代次数t=0；Step2计算总种群适应度，选择最优个体作为蜂王；Step3如满足停止条件，输出最后结果并停止运行；否则，执行Step4；Step4t=t+1，用蜂王进行全局信息素更新；Step5进行蚂蚁搜索，蚂蚁每走一步，进行信息素的局部更新，所有蚂蚁遍历完后，蚂蚁经过的m条路径作为m个个体组成种群POPa；Step6采用轮盘赌选择从总种群中选取N*u/2个个体，再随机生成N*(1-u)/2个个体，作为父代个体组成父代种群POPb，该种群规模为N/2；Step7用蜂王与种群POPb中的N/2个个体进行交叉操作；变异后生成子代种群POPc，种群规模为N；Step8将种群POPb和种群POPc合并生成种群POPd，其种群规模为3*N/2，并从种群POPd中采用轮盘赌选取N个个体组成种群POPe；Step9将种群POPa和种群POPe合并更新总种群POP，种群规模为NN；Step10进行局部搜索以及信息素重置操作，返回Step2。4.2.5算法验证在MATLABR2009a环境中，ACS、BEGA和BAHA针对Oliver30问题以及eil51[35-37]问题对算法的有效性进行仿真验证，分别独立测试50次，并将实验结果与文献给出的数据进行对比。参数设定为：总种群规模NN=110，蜜蜂进化型遗传算法种群规模N为100，交叉概率初值为0.9，变异概率初值为0.3，蚂蚁数目m=10，α=1，β=5，ρ1=0.1，ρ2=0.1。表4.3、表4.4关键字说明，Lbest为最优长度，NC为运算次数，Nc为出现当前最优解的次数，ns为出现最优解的迭代次数，La为平均路径，Lb为当前已知的最优解，Oliver30问题实验结果如表4.3所示。表4.3Oliver30问题实验结果算法LbestNCNcnsLaLb[35]文献423.7//52/[37]文献424.6100//ACS423.7502109429.8423.7BEGA426.9500124447.9BAHA423.7503713424.037 西安建筑科技大学硕士学位论文由表4.3可知，在50次独立实验中，BAHA有37次能收敛到最优解423.7，且最快可在第26代收敛，算法最优解的平均值为424.0；与ACS、BEGA相比，BAHA[35-36]具有较好的收敛速度和稳定性；通过与文献的对比可以看出，BAHA的收敛速[35][36]度优于文献，其搜索性能优于文献。在eil51问题中常用整数方式求解得到的实验结果如表4.4所示。表4.4eil51问题实验结果算法LbestNCNcnsLaLb[35]文献430.7///446.3[37]文献42651//442.4ACS432500299439.4426BEGA438500156441.0BAHA426501252433.1由表4.4可知，在50次独立实验中，BAHA有12次能收敛到最优解426，且最快可在第52代收敛，算法最优解的平均值为433.1；与ACS、BEGA相比，BAHA在搜索的精度和速度上都有了较大提升，通过算法结果的平均值的对比，可以看出，BAHA具有较好的稳定性；且BAHA在保证搜索性能的情况下，其稳定性优于[35,37]文献。浮点数方式求解利用的是城市间的实际距离，因此采用浮点数方式求解问题更符合实际情况，目前文献对其研究较少，本文除了运用整数方式求解eil51问题外，同时对浮点数方式求解eil51问题也进行了仿真测试。浮点数表示城市间的距离时，得出其最优路径如图4.5所示。706050403020100010203040506070图4.5eil51问题最优浮点数解路径38 西安建筑科技大学硕士学位论文图4.5所示eil51问题路径的浮点数解为428.8718，其整数解为427。而图4.2所示路径的浮点数解为429.9833，其整数解为426。由此可知，当采用浮点数方式求解时，最优解为428.8718，最优路径如图4.5所示；采用整数方式求解时，最优解为426，最优路径如图4.2所示。4.2.6验证结论蜜蜂进化型遗传算法和蚁群系统构成的并行结构的混合算法（BAHA）通过两个种群的融合实现信息共享，提高了算法的收敛速度和初期寻优能力；采用改进的OX的交叉算子，使优秀个体基因的排列顺序得以保留；加入局部搜索算子，在当代最优解附近进行了更加精细的搜索，提高了算法收敛效率；算法中加入的信息素重置防止了局部最优解的出现。将BAHA的运行测试结果与ACS、BEGA及其他文献中的数据进行对比，可以看出，BAHA具有较好的收敛速度、寻优能力以及稳定性。4.3BGAA与BAHA的对比采用BGAA和BAHA解决Oliver30问题、eil51问题，分别独立运行50次，每次运行迭代100次，分别从最优长度Lbest，出现当前最优解的次数Nc，最快出现最优解的迭代次数ns，平均路径La以及运行完成的平均时间Tave五个方面进行对比。BAHA的总种群规模NN=110，BGAA与BAHA其他参数相同：蜜蜂进化型遗传算法种群规模N为100，交叉概率初值为0.9，变异概率初值为0.3，蚂蚁数目m=10，α=1，β=5，ρ1=0.1，ρ2=0.1。两种算法关于Oliver30问题和eil51问题的运行结果对比如表4.5所示：表4.5BGAA与BAHA计算结果比较问题tsplib最优解算法LbestNcnsLaTave/sBGAA423.72241424.328.79Oliver30423.7BAHA423.73713424.03.15BGAA426775434.534.28eil51426BAHA4261252433.14.53由表4.5可知，在解的质量方面，BGAA和BAHA收敛到的最优解均是TSP数据库中已知的该问题最优解；在得到最优解的次数方面，BGAA解决两个问题时运行50次分别获得22次和7次最优解，BAHA获得了37次和12次最优解，说明BAHA的寻优能力略优于BGAA；BAHA收敛到最优解所需要的最小迭代次39 西安建筑科技大学硕士学位论文数也比BGAA所需要的次数有所减少，说明BAHA相比于BGAA能够有效的减少冗余迭代，提高求解效率；两个算法求得的平均路径的对比，表明BAHA稳定性优于BGAA；BGAA平均一次完成运行的时间分别为28.79s、34.28s，而BAHA平均每次完成运行时间分别为3.15s、4.53s，通过对比可知在算法运行速度方面，BAHA远优于BGAA。进化曲线分别如图4.6和图4.7所示。540BAHABGAA520500/mm480路径长度460440420020406080100迭代次数图4.6Oliver30问题最优解进化曲线560BAHA540BGAA520/mm500480路径长度460440420020406080100迭代次数图4.7eil51问题最优解进化曲线由图4.6和图4.7可知，在保证搜索性能的情况下，BAHA寻优速度优于BGAA；40 西安建筑科技大学硕士学位论文且在相同迭代次数时，BAHA得到的解始终优于BGAA。综上所述，以上实验结果表明，BGAA和BAHA均能收敛于全局最优解，具有较好的寻优能力，而从收敛速度以及稳定性方面来看，BAHA明显优于BGAA。4.4本章小结本章针对蜜蜂进化型遗传算法和蚁群系统的优点和缺点，提出了串行结构的混合算法BGAA和并行结构的混合算法BAHA；混合智能算法利用蚁群系统对信息素进行了学习积累，同时利用蜜蜂进化型遗传算法对蚁群系统初期信息素进行指导，兼顾了全局搜索和局部搜索。本章以两种旅行商问题对混合算法的有效性和可行性进行了测试，并对两种混合算法的结果进行了对比；由对比结果可知，两种算法均具有较好的寻优能力，其中，BAHA的整体性能优于BGAA。41 西安建筑科技大学硕士学位论文第五章仿真实验5.1算法实现与仿真计算以6吸嘴垂直旋转式贴片机为原型，针对贴片机优化模型，对实际生产中使用的5种不同元器件个数和种类的PCB板的贴装顺序进行优化计算。将n个元器件分组，每个组中元器件可以被同种吸嘴吸取，按分组所含元器件多少对喂料器位置进行布置，元器件多的分组放到离PCB板近的区域，反之放到较远的区域，如图5.1中所示，区域1所放的分组元器件最多，其次是区域2、区域3；而在最中间的区域中，按照每种元器件个数的多少，将元器件从中心到两边依次排列，如图5.1中的区域1内部元器件的分布，个数多的元器件放中间，个数少的放两边；在右边区域中，按照每类元器件个数的多少，将不同元器件由左到右排列，如图5.1所示，区域2中个数多的元器件放左边，个数少的放右边；左边区域排列方式与右边区域相反，如图5.1所示的区域3。喂料器分配优化如图5.1所示。PCB板区域3区域1区域2少多少多少多少少多少图5.1喂料器优化示意图贴片机有6个吸嘴，为达到最高贴装效率，贴装组元件数量为6。设贴装过程中每个吸嘴每次拾取一个元件，且不存在抛料的问题。喂料器分配完毕后，开始元器件贴装过程，每个贴装循环需确定需要贴装的6个位置以及这6个位置所需元件的拾取和贴装的顺序，垂直旋转式贴片机的贴装头在拾取和贴装时不需要考虑两个吸嘴之间的移动距离，因此每个贴装循环所走的路程由拾取元件的路程、贴装元件的路程以及拾取和贴装位置之间的距离决定。在MATLABR2009a环境中进行仿真实验，分别采用蚁群系统（AntColonySystem，ACS）、蜜蜂进化型遗传算法（BeeEvolutionaryGeneticAlgorithm，BEGA）和BAHA独立运行50次，相关参数设定为：总种群规模NN=110，蜜蜂进化型遗传算法种群规模N为100，交叉概率初值为0.9，变异概率初值为0.3，蚂蚁数目42 西安建筑科技大学硕士学位论文m=10，α=1，β=5，ρ1=0.1，ρ2=0.1。优化结果如表5.1所示。表5.1实例数据实验结果标ACSBEGABAHA元件个数元件种类号/mm/mm/mm12152575.02563.32563.323184305.74325.44264.6354196755.06873.66618.449024114671298611366511027146781638314524由表5.1可知，在元器件较少时，三种算法对不同元器件数量和种类的PCB板的贴装顺序进行优化计算得到的最优解差距较小，甚至在第一个PCB板的计算中出现结果相同的情况，但随着元件数量及种类的增加，BAHA求得的最优解与其他算法的最优解差距逐渐增加。以第2个和第5个PCB板为例，优化第2个PCB板的贴装顺序时，ACS、BEGA与BAHA得出的贴装头走过的距离分别是4305.7mm、4325.4mm和4264.6mm，优化结果的差距分别为41.1mm和60.8mm，优化第5个PCB板的贴装顺序时，元件个数增加为110，元件种类为27，采用BAHA得到的路径与ACS和BEGA相比路径差距分别为154mm和1859mm，由此可知，BAHA能够更有效地缩短贴片机贴装路径，并且随着问题规模的加大，这种缩短优势更加明显。对5种PCB板贴装顺序优化计算的进化曲线如图5.2和图5.3所示。图5.2(A-C)表示利用BAHA、BEGA和ACS三种算法分别对第1-3个PCB板优化得到的进化曲线；图5.3(A-B)表示第4和第5个PCB板的进化曲线。2850BAHA2800BEGAACS2750/mm2700路径长度265026002550050100150200迭代次数（A）PCB板1进化曲线43 西安建筑科技大学硕士学位论文5400BAHA5200BEGAACS5000/mm4800路径长度460044004200050100150200迭代次数（B）PCB板2进化曲线10000BAHA9500BEGAACS9000/mm85008000路径长度750070006500050100150200迭代次数（C）PCB板3进化曲线图5.2PCB板1-3的进化曲线由图5.2(A)可知，元件个数为21，元件种类为5时，BAHA和BEGA均能收敛到最优解，ACS的优化结果略大于最优解，其中BAHA在第10代收敛，收敛速度明显优于其他两个算法；在图5.2(B-C)中，BAHA的优化结果与其他两种算法的优化结果差距逐渐增加，且可以看出，ACS寻优能力较强，但易陷入局部最优解，而BEGA产生大量的冗余迭代，搜索效率较低。对于PCB板4和PCB板5的仿真实验，BEGA在200代未得到最优解，且优化结果远大于其他两种算法得到的优化结果，因此图5.3只对BAHA和ACS两种算法的进化曲线进行了对比。44 西安建筑科技大学硕士学位论文4x101.19BAHA1.18ACS1.17/mm1.16路径长度1.151.141.13050100150200迭代次数（A）PCB板4进化曲线4x101.51BAHA1.5ACS1.49/mm1.48路径长度1.471.461.45050100150200迭代次数（B）PCB板5进化曲线图5.3PCB板4和PCB板5的进化曲线由图5.3可知，BAHA有效地解决了早熟的问题，且得到的最优解远优于ACS。从图5.2和图5.3可以看出，BAHA具有较好的全局搜索能力，能够有效地缩短贴装路径，提高贴装效率。5.2本章小结本章以6吸嘴垂直旋转式贴片机为例，介绍了贴片机贴装工艺优化算法的仿真与实现。通过对实际PCB数据的仿真实验，表明基于蜜蜂进化型遗传算法和蚁群系统的智能混合算法（BAHA）比单一的蜜蜂进化型遗传算法或蚁群系统更加适45 西安建筑科技大学硕士学位论文合贴片机的路径优化。BAHA能够取得更优的解，且随着PCB板贴装复杂度的增加，BAHA的优势更加明显。46 西安建筑科技大学硕士学位论文第六章总结与展望贴片机工作效率能否提高，是关系到整个表面贴装生产线效率提高的瓶颈问题。因此，提高SMT生产线的贴装效率，重点是对贴片机的贴装过程的调度优化。本文在仔细分析贴片机贴装工艺流程的基础上，建立了表面贴装技术的优化模型。对蜜蜂进化型遗传算法和蚁群系统进行研究，根据两种算法的优点及缺点，取长补短，提出串行结构的混合智能算法，即蜜蜂进化型遗传—蚁群算法(Beeevolutionarygenetic-antcolonyalgorithm，BGAA)，以及并行结构的基于蜜蜂进化型遗传算法和蚁群系统的混合智能算法(theHybridIntelligentAlgorithmbasedonBeeEvolutionaryGeneticAlgorithmandAntColonySystem，BAHA)，并通过TSP问题对算法的有效性和寻优能力进行仿真测试及对比，测试及对比结果表明，BGAA与BAHA都具有较好的全局搜索能力和收敛速度；其中，BAHA运行时间、稳定性等方面略优于BGAA。最后，本文以6吸嘴的垂直旋转式贴片机为原型，针对贴片机贴装过程优化模型，利用BAHA对实际生产中使用的5种不同元器件个数和种类的PCB板的贴装顺序进行优化计算。仿真计算结果表明，基于蜜蜂进化型遗传算法和蚁群系统的智能混合算法（BAHA）比单一的蜜蜂进化型遗传算法或蚁群系统更加适合贴片机的路径优化。BAHA运算结果波动性小、鲁棒性高，克服了在问题规模较大的情况下BEGA冗余迭代过多以及ACS易早熟的缺点，在相同条件下（如使用同样的贴片机），得到了质量较高的解，提高了搜索性能的稳定性，具有良好的指导意义和较好的实用价值。本文提出的贴片机贴装优化模型是针对单台贴片机的，同时对单台贴片机的贴装过程进行了优化，而在实际的生产过程中，电子产品的贴装工艺是由多台贴片机及其他设备构成的，各台设备之间互相协作完成贴装工作。在今后的研究中，可以针对多台贴片机贴装平衡问题进行研究，将PCB板贴装生产线的生产负荷合理地分配给多台贴片机，使SMT生产效率最大化。47 西安建筑科技大学硕士学位论文致谢本论文是在导师王超学老师和董惠老师悉心指导下完成的，从论文的选题、研究、撰写到定稿，都得到了王老师和董老师的细心细致的指导。在此，作者向两位老师表示由衷的感谢，希望两位老师身体健康，工作顺利！在读研期间，王老师在学业上对我悉心指导，严格要求；在生活上对我无私帮助。王老师高深的学术造诣和认真严谨的为人风格使我终身受益。王老师不仅让我学到了很多专业知识，还让我明白了很多为人处世之道，再次向老师表示感谢！本文的完成得到了吕志奇、潘正茂两位同门的帮助，在此一并向他们表示最诚挚的谢意！同时感谢信息与控制工程学院和研究生院各位领导和老师给予作者的帮助！感谢父母对作者的培养与支持！48 西安建筑科技大学硕士学位论文参考文献[1]闫红超．基于遗传模拟退火算法的PCB贴装工艺优化研究．[西安电子科技大学论文]．西安：西安电子科技大学，2006．[2]KumarR，HaominLi．IntegerProgrammingapproachtoPrintedcircuitboardassemblytimeoptimization[J]．IEEETransonComponents，Packaging,andManufacturingTechnology，Nov，1995，(18)：720－727．[3]KAltinkemer，BKazaz，M.Koksalan，ect．Optimizationofprintedcircuitboardmanufacturing：Integreatedmodelingandalgorithms[J]．EuropeanJournalofOperationalResearch.2000，11(124)：409－421．[4]BURKEEK，COWLINGPI，RALFK．Newmodelsandheuristicsforcomponentplacementofthe1999IEEEInternationalConferenceonInformation[J]．IEEE．1999：133－140．[5]AyobM，KendallG．Asurveyofsurfacemountdeviceplacement[J]．EuropeanJournalofOperationalResearch，2008，186：893－914．[6]TeckSangLoh，SatiehTSBukkapatnam，DMEMDEURIS，ete．AgeneticalgorithmofsequentialpartassignmentforPCBassembly.[J]．Computer&IndustrialEngineering.2001，40(4)，pp．293－307．[7]LEUMC，WONGH，JIZ.Planningofcomponentplacement/insertionsequenceandfeedersetupinPCBassemblyusinggeneticalgorithms[J]，JournalofElectionicPackaging，TransacationoftheASME．1993，115(4)，pp．424-432.[8]KHOOLP，NGTK．Ageneticalgorithm-basedplanningsystemforPCBcomponentPlacement[J]．InternationalJournalofProductionEconomics．1998,，54(3)，pp.293-307.[9]BallMO，MagazineMJ．SequencingofInsertioninPrintedCircuitBoardAssembly[J]．OperationsReseareh．1988，vol.36，no.2，pp.192-201．[10]PaulWrothach，PaulSheng．IntegratingEnvironmentalObjectivesintheoperationalPlanningofPrintedCircuitBoardAssembly[J]．IEEETransactionsOnElectionicsPackagingManufacturing．1999，vol.22，no.2，PP.118－123.[11]TirpakThomasM，NelsonPeterC．AswaniAmitkumarJ．OptimizationofRevolverHeadSMTMachineusingAdaptiveSimulatedAnnealing(ASA)．IEEE/CPMT，InternationalElectronicsManufacturingTechnologySymposium，2000：214-220．[12]SunDS，LeeTE，KimKH．Componentallocationandfeederarrangementforadual-gantry49