一种求解贴片机贴装优化问题的种群初始化方法及系统

技术领域

本发明涉及贴片装置技术领域，尤其涉及一种求解贴片机贴装优化问题的种群初始化方法及系统。

背景技术

多头拱架式贴片机的贴装时间对整体生产线的生产效率具有重要影响。为了便于分析影响贴装时间的因素，假设贴装一块有n个元件、C种元件类型的PCB基板贴装，需要经过D个取贴循环，取贴循环的元件组内元件个数为：

式(1)中D

式(2)中贴装过程优化问题的最优解信息应包括下列基本信息：①送料槽与送料器对应分配位置，②取贴循环内的元件拾取顺序，③取贴循环内的贴装头分配和吸取顺序，和④元件贴装顺序共4个方面。式(2)的最优解通常以整数编码组成的序列来表示。

举例来说，假设送料槽总数为20个，送料器使用总数为5个，贴装头数量为H＝5(编号为1～5)，贴装元件数量为n＝20(编号为1～20)，且各贴装头的吸嘴均可吸贴任意元件，则一个可行解的编码表示如图1所示。

图1中所示的一个可行解的编码由送料槽分配编码、元件贴装序列、贴装头分配和贴装头吸取顺序共4个子序列构成，该可行解共有4个取贴循环，其中在元件贴装序列中{6,9,14,1,17}为第1个取贴循环吸取的元件编号，表示H1吸取6号元件所在的送料槽，H2吸取9号元件所在的送料槽，H3吸取14号元件所在的送料槽，H4吸取1号元件所在的送料槽，H5吸取17号元件所在的送料槽，贴装头吸取顺序是H1和H2第一次吸取且可同时吸取元件，H3第二次吸取，H4为第3次吸取，H5为第4次吸取，其他取贴循环以此类推。根据4个方面的整数编码，才能准确计算得到式(2)的总移动距离。综上所述，根据编码长度(送料槽总数+3*n)关系式，当计算20个元件的贴装总路径最优化解时，则编码长度为80，这种常规方法造成编码长度冗长，在一定程度造成了计算复杂大，计算效率低等缺点，因此将影响贴装头的有效贴装。

在求解多头拱架式贴片机贴装过程优化问题时，群智能优化算法具有求解质量高的优点，但采用常规的如遗传算法、蚁群算法等群智能优化算法求解，需初始化种群，初始种群通常采用随机生的方式，尽管保证了种群的多样性，但对属于NP问题的贴装过程来说，采用随机种群无异于大海捞针。如果使初始种群本身就能够集中到最优邻近区域，会加快搜索速度。此外，随着问题规模扩大并且各项系数在较大范围取值时，将耗费大量的求解时间，这将缺乏实用性。因此，求解贴装效率问题时，初始化解质量直接影响整个计算的寻优速度和最优解精度。

发明内容

基于背景技术存在的技术问题，为提升群智能算法求解多头拱架式贴片机的贴装优化计算效率和最优解的精度，本发明提出了一种求解多头拱架式贴片机贴装优化的初始化种群构造方法。

一种求解贴片机贴装优化问题的种群初始化方法，包括如下步骤：

S1：基于吸取等级表初始化贴装头分配方案和贴装头吸取顺序，所述吸取等级表是以每次取贴循环中，贴装头同时吸取元件数最多为目标所构建的等级表；

S2：基于最近邻算法初始化元件贴装顺序；

S3：基于贴装头分配方案、贴装头吸取顺序、元件贴装顺序计算得到元件的贴装总距离，实现贴装头取贴循环移动距离最小。

进一步地，在步骤S1：基于吸取等级表初始化贴装头分配方案和贴装头吸取顺序中，包括：

S11：初始化待吸取元件的贴装头数量和送料槽分配表，所述送料槽分配表包括送料槽编号、每个送料槽中的元件类型以及每个送料槽中元件总数；

S12：贴装头从送料槽起始编号开始，根据贴装头当前位置，计算可同吸的贴装头数目；

S13：判断可同吸的贴装头数目是否等于贴装头总数，若是，则贴装头吸取完成，进入步骤S16；若不是，则进入步骤S14；

S14：贴装头以一定步长移动到下一个送料槽，根据贴装头当前位置，计算可同吸的贴装头数目，进入步骤S13，直至完成所有送料槽编号位置的贴装头同吸数目记录，进入步骤S15；

S15：根据贴装头在各送料槽编号位置下的同吸数目，查找最大的同吸数目位置，若最大同吸数目位置下的最大同吸数目小于贴装头数目，则表示吸取位置未完成，那么重置已吸取的贴装头为不可吸取状态，其他贴装头为待吸取状态，进入S11，直至所有贴装头完成元件吸取；

S16：根据贴装头完成贴装的吸取次数，在吸取等级表中查找确认吸取等级，得到贴装头分配方案、贴装头吸取顺序、以及贴装头在送料槽上吸取的起始位置和结束位置。

进一步地，在步骤S2：基于最近邻算法初始化元件贴装顺序中，包括：

S21：随机初始化一组贴装头吸取顺序；

S22：基于步骤S1得到的各个贴装头上的元件类型和各个贴装头吸取结束后位置；

S23：根据初始化的贴装头吸取顺序，计算所有相同元件类型距离其中一贴装顺序的贴装头的欧式距离；

S24：基于最近邻算法，选择距离所述贴装头最近的元件编号，并更新元件信息表，所述元件信息表包括元件编号、元件贴装位置和元件类型；

S25：根据元件信息表更新贴装头到最近相同元件的贴装位置，进入步骤S22至S24，计算距离下一个贴装顺序的贴装头最短的元件编号，并更新元件信息表，直至完成所有贴装顺序的贴装头到最近相同元件的贴装位置的更新，最终得到元件贴装顺序编号。

进一步地，所述吸取等级表中设定吸取等级数值越小，则在每次取贴循环中，贴装头同时吸取元件数越多，最优吸取等级数值为1。

一种求解贴片机贴装优化问题的种群初始化系统，包括贴装头初始化模块、元件贴装顺序初始化模块和计算模块；

贴装头初始化模块用于基于吸取等级表初始化贴装头分配方案和贴装头吸取顺序，所述吸取等级表是以每次取贴循环中，贴装头同时吸取元件数最多为目标所构建的等级表；

元件贴装顺序初始化模块用于基于最近邻算法初始化元件贴装顺序；

计算模块用于基于贴装头分配方案、贴装头吸取顺序、元件贴装顺序计算得到元件的贴装总距离，实现贴装头取贴循环移动距离最小。

进一步地，所述贴装头初始化模块包括第一初始化模块、第一同吸贴装头计算模块、同吸判断模块、第二同吸贴装头计算模块、查找和重置模块、吸取等级确认模块；

第一初始化模块用于初始化待吸取元件的贴装头数量和送料槽分配表；

第一同吸贴装头计算模块用于贴装头从送料槽起始编号开始，根据贴装头当前位置，计算可同吸的贴装头数目；

同吸判断模块用于判断同吸的贴装头数目是否等于贴装头总数，若是，则贴装头吸取完成，进入吸取等级确认模块；若不是，则进入第二同吸贴装头计算模块；

第二同吸贴装头计算模块用于贴装头以一定步长移动到下一个送料槽，根据贴装头当前位置，计算可同吸的贴装头数目，进入同吸判断模块，直至完成所有送料槽编号位置的贴装头同吸数目记录，进入查找和重置模块；

查找和重置模块用于根据贴装头在各送料槽编号位置下的同吸数目，查找最大的同吸数目位置，若最大同吸数目位置下的最大同吸数目小于贴装头数目，则表示吸取位置未完成，那么重置已吸取的贴装头为不可吸取状态，其他贴装头为待吸取状态，进入第一初始化模块，直至所有贴装头完成元件吸取。

吸取等级确认模块用于根据贴装头完成贴装的吸取次数，在吸取等级表中查找确认吸取等级，得到贴装头分配方案、贴装头吸取顺序、以及贴装头在送料槽上吸取的起始位置和结束位置。

进一步地，元件贴装顺序初始化模块包括随机初始化模块、获取模块、第一距离计算模块、元件信息表更新模块和元件贴装顺序更新计算模块；

随机初始化模块用于随机初始化一组贴装头吸取顺序；

获取模块用于基于贴装头初始化模块得到的各个贴装头上的元件类型和各个贴装头吸取结束后位置；

第一距离计算模块用于根据初始化的贴装头吸取顺序，计算所有相同元件类型距离其中一贴装顺序的贴装头的欧式距离；

元件信息表更新模块用于基于最近邻算法，选择距离所述贴装头最近的元件编号，并更新元件信息表，所述元件信息表包括元件编号、元件贴装位置和元件类型；

元件贴装顺序更新计算模块用于根据元件信息表更新贴装头到最近相同元件的贴装位置，进入获取模块至第一距离计算模块，计算距离下一个贴装顺序的贴装头最短的元件编号，并更新元件信息表，直至完成所有贴装顺序的贴装头到最近相同元件的贴装位置的更新，最终得到元件贴装顺序编号。

一种计算机可读储存介质，所述计算机可读存储介质上存储有若干获取分类程序，所述若干获取分类程序用于被处理器调用并执行如上所述的优化方法。

本发明提供的一种求解贴片机贴装优化问题的种群初始化方法及系统的优点在于：本发明结构中提供的一种求解贴片机贴装优化问题的种群初始化方法及系统，并用该方法可以求解多头拱架式贴片机贴装优化的高质量初始化种群，该初始化种群构造方法得到的参数包括了贴装头分配方案、贴装头吸取顺序和送料槽分配表以及元件贴装序列，满足了如图1所示的期望解所有信息，即可准确计算得到贴装总距离，此外每组贴装头在完成一次贴装后，通过最近邻算法，得到下一送料槽编号和元件编号，实现了每组的贴装顺序是随机的，保证了种群的多样性，因此可提升利用群智能算法求解多头拱架式贴装过程优化的计算效率和最优解的精确度。

附图说明

图1为本发明贴装优化期望解对应的传统编码部分组成方式示意图；

图2为本发明一种求解贴片机贴装优化问题的种群初始化方法的步骤示意图；

图3为贴片机的贴装示意图；

图4为贴装头组合吸取的吸取等级表示意图。

具体实施方式

下面，通过具体实施例对本发明的技术方案进行详细说明，在下面的描述中阐述了很多具体细节以便于充分理解本发明。但是本发明能够以很多不同于在此描述的其他方式来实施，本领域技术人员可以在不违背本发明内涵的情况下做类似改进，因此本发明不受下面公开的具体实施的限制。

如图2至4所示，本发明提出的一种求解贴片机贴装优化问题的种群初始化方法，包括如下步骤S1至S3：

S1：基于吸取等级表初始化贴装头分配方案和贴装头吸取顺序，所述吸取等级表是以每次取贴循环中，贴装头同时吸取元件数最多为目标所构建的等级表；

步骤S1通过构建吸取等级表并初始化贴装头，实现了快速计算贴装头在一个取贴循环中，贴装头同时吸取元件数最多的原则，当贴装头同时吸取元件数越多，则完成元件贴装过程所需的贴装头的吸取移动次数越小；因此所述吸取等级表可以实现快速计算贴装头在不同送料槽位置的最少吸取次数，吸取等级数值越小，则表示贴装头同时吸取元件数越多，贴装头吸取次数越少，最优吸取等级数值为1，即所有贴装头1次同吸即可完成吸取任务，最差吸取等级为即各贴装头无同吸动作，需依次移动到对应送料槽位置，再完成执行吸取操作。如图4所示，以贴装头总数是5为例，最优的吸取任务是5个贴装头1次同时吸取元件，贴装头在吸取过程中移动总距离和总吸取元件动作时间最短，吸取效率高，故设置吸取等级为1，同理，当5个贴装头5次吸取完成任务时，贴装头移动路径和吸取元件动作时间最长，吸取效率低，则设置吸取等级为7，依次类推，构建了如图4所示的以贴装头同时吸取元件数最多为目标的吸取等级表。

S2：基于最近邻算法初始化元件贴装顺序；

最近邻算法基本思想是任意选择起点，构造路径时每一次选择最近的未行走过的顶点作为下一个路径点，直至遍历所有路径点再回到起点路径点，得到一个解。

S3：基于贴装头分配方案、贴装头吸取顺序、元件贴装顺序计算得到元件的贴装总距离，实现贴装头取贴循环移动距离最小。

在本申请中，，所述送料槽分配表包括送料槽编号、每个送料槽中的元件类型以及每个送料槽中元件总数，因此在计算贴装总距离时，通过贴装头分配方案、贴装头吸取顺序、元件贴装顺序、送料槽分配表即可完成计算。

本优化方法的基本原理是：首先在吸取元件过程中，为了避免贴装头盲目随机地选择送料槽位置吸取送料槽中的元件，提出以贴装头同时吸取元件数最多为目标，设计了一种贴装头的吸取等级表，可快速计算得到贴装头分配方案和贴装头吸取顺序。在贴装元件过程中，以移动距离最短为目标，设计了一种随机初始化元件贴装顺序为前提条件，根据贴装头吸取顺序，利用最近邻算法计算距离当前贴装头最近的元件编号，以此类推，直到贴装头完成所有元件的贴装移动，即可得到元件贴装顺序编号。至此，该初始化种群方法得到的信息包括了计算贴装总距离的所有信息：送料槽编号、贴装头分配方案、贴装头吸取顺序、元件贴装顺序，通过所得到的这些信息，所计算的贴装总距离最小，贴装头取贴循环移动距离最小，因此实现了对多头拱架式贴片机贴装过程的优化。

在如图1所示的贴片机贴装中，传统贴装中由于编码冗长，存在计算效率低和最优解精确度差的缺陷，随着元件数量的增加，这种缺陷将更加突出。根据步骤S1至S3得到，本申请中的优化方法所得出参数包括了贴装头分配方案、贴装头吸取顺序、送料槽分配表以及元件贴装序列，满足了如图1所示的期望解所有信息，即可准确计算得到元件的贴装总距离，根据贴装总距离最小的原则，即可实现贴片机贴装的优化。因此本申请借助种群初始化的随机生成方式，结合了最近邻算法，使得每组的贴装顺序是随机的，保证了种群的多样性，同时随机生成的方式，避免了编码的冗长，提高了计算效率和最终得到最优解的精确度。

进一步地，在步骤S1：基于吸取等级表初始化贴装头分配方案和贴装头吸取顺序中，包括：

S11：初始化待吸取元件的贴装头数量和送料槽分配表，所述送料槽分配表包括送料槽编号、每个送料槽中的元件类型以及每个送料槽中元件总数；

由于所述送料槽分配表包括送料槽编号、每个送料槽中的元件类型和每个送料槽中的元件总数，因此贴片机在使用前，对送料槽分配表中的参数进行遍历获取，可以直接得到送料槽分配表中的当前参数，为后续的贴片参数优化提供了一个参数基础。

S12：贴装头从送料槽起始编号开始，根据贴装头当前位置，计算可同吸的贴装头数目；

S13：判断可同吸的贴装头数目是否等于贴装头总数，若是，则贴装头吸取完成，进入步骤S16；若不是，则进入步骤S14；

对于可同吸的贴装头数目是否等于贴装头总数时，参考吸取等级表可知，当前吸取等级为1，吸取完成。对于贴装头同吸数目小于贴装头总数时，则表明当前贴装头并未完成吸取，所以贴装头将继续移动以完成元件贴装。

S14：贴装头以一定步长移动到下一个送料槽，根据贴装头当前位置，计算可同吸的贴装头数目，进入步骤S13，直至完成所有送料槽编号位置的贴装头同吸数目记录，进入步骤S15；

贴装头每以一定步长移动到下一个送料槽，贴装头完成一次同吸数目记录，即移动几次，表示贴装头要完成本次贴片所需要吸取元件的次数。贴装头以步长为m进行移动到下一个送料槽，m可以根据实际情况进行设置，本说明书中设定值为1。

S15：根据贴装头在各送料槽编号位置下的同吸数目，查找最大的同吸数目位置，若最大同吸数目位置下的最大同吸数目小于贴装头数目，则表示吸取位置未完成，那么重置已吸取的贴装头为不可吸取状态，其他贴装头为待吸取状态，进入S11，直至所有贴装头完成元件吸取；

S16：根据贴装头完成贴装的吸取次数，在吸取等级表中查找确认吸取等级，得到贴装头分配方案、贴装头吸取顺序、以及贴装头在送料槽上吸取的起始位置和结束位置。

在步骤S11至S16中，根据贴装头在上一位置的贴装情况，计算下一位置的贴装情况，可以实时实现对整个贴装装置的贴装参数优化；因为在整个元件贴装过程中，贴装优化的目标是使总的取贴循环移动距离最小，因此经过步骤S11至S16得到的贴装头分配方案和贴装头吸取顺序，进入步骤S2，利用最近邻算法得到元件贴装序列，实现总的取贴循环移动距离最小。

进一步地，在步骤S2：基于最近邻算法初始化元件贴装顺序中，包括：

S21：随机初始化一组贴装头吸取顺序；

S22：基于步骤S1得到的各个贴装头上的元件类型和各个贴装头吸取结束后位置；

S23：根据初始化的贴装头吸取顺序，计算所有相同元件类型距离其中一贴装顺序的贴装头的欧式距离；

S24：基于最近邻算法，选择距离所述贴装头最近的元件编号，并更新元件信息表，所述元件信息表包括元件编号、元件贴装位置和元件类型；

S25：根据元件信息表更新贴装头到最近相同元件的贴装位置，进入步骤S22至S24，计算距离下一个贴装顺序的贴装头最短的元件编号，并更新元件信息表，直至完成所有贴装顺序的贴装头到最近相同元件的贴装位置的更新，最终得到元件贴装顺序编号。

在每次检索完成一个元件编号后，更新元件信息表，直至所有元件编号均被检索完成。在每次贴装时，贴装头基于最近邻算法，并结合随机初始化的贴装头的吸取顺序，选择距离贴装头最近的元件编号进行贴装，得到元件贴装顺序编号。

一种求解贴片机贴装优化问题的种群初始化系统，包括贴装头初始化模块、元件贴装顺序初始化模块和计算模块；

贴装头初始化模块用于基于吸取等级表初始化贴装头分配方案和贴装头吸取顺序，所述吸取等级表是以每次取贴循环中，贴装头同时吸取元件数最多为目标所构建的等级表；

元件贴装顺序初始化模块用于基于最近邻算法初始化元件贴装顺序；

计算模块用于基于贴装头分配方案、贴装头吸取顺序、元件贴装顺序计算得到元件的贴装总距离，实现贴装头取贴循环移动距离最小。

进一步地，所述贴装头初始化模块包括第一初始化模块、第一同吸贴装头计算模块、同吸判断模块、第二同吸贴装头计算模块、查找和重置模块、吸取等级确认模块；

第一初始化模块用于初始化待吸取元件的贴装头数量和送料槽分配表；

第一同吸贴装头计算模块用于贴装头从送料槽起始编号开始，根据贴装头当前位置，计算可同吸的贴装头数目；

同吸判断模块用于判断同吸的贴装头数目是否等于贴装头总数，若是，则贴装头吸取完成，进入吸取等级确认模块；若不是，则进入第二同吸贴装头计算模块；

第二同吸贴装头计算模块用于贴装头以一定步长移动到下一个送料槽，根据贴装头当前位置，计算可同吸的贴装头数目，进入同吸判断模块，直至完成所有送料槽编号位置的贴装头同吸数目记录，进入查找和重置模块；

查找和重置模块用于根据贴装头在各送料槽编号位置下的同吸数目，查找最大的同吸数目位置，若最大同吸数目位置下的最大同吸数目小于贴装头数目，则表示吸取位置未完成，那么重置已吸取的贴装头为不可吸取状态，其他贴装头为待吸取状态，进入第一初始化模块，直至所有贴装头完成元件吸取。

吸取等级确认模块根据贴装头完成贴装的吸取次数，在吸取等级表中查找确认吸取等级，得到贴装头分配方案、贴装头吸取顺序、以及贴装头在送料槽上吸取的起始位置和结束位置。

进一步地，元件贴装顺序初始化模块包括随机初始化模块、获取模块、第一距离计算模块、元件信息表更新模块和元件贴装顺序更新计算模块；

随机初始化模块用于随机初始化一组贴装头吸取顺序；

获取模块用于基于贴装头初始化模块得到的各个贴装头上的元件类型和各个贴装头吸取结束后位置；

第一距离计算模块用于根据初始化的贴装头吸取顺序，计算所有相同元件类型距离其中一贴装顺序的贴装头的欧式距离；

元件信息表更新模块用于基于最近邻算法，选择距离所述贴装头最近的元件编号，并更新元件信息表，所述元件信息表包括元件编号、元件贴装位置和元件类型；

元件贴装顺序更新计算模块用于根据元件信息表更新贴装头到最近相同元件的贴装位置，进入获取模块至第一距离计算模块，计算距离下一个贴装顺序的贴装头最短的元件编号，并更新元件信息表，直至完成所有贴装顺序的贴装头到最近相同元件的贴装位置的更新，最终得到元件贴装顺序编号。

本领域普通技术人员可以理解：实现上述方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成，前述的程序可以存储于一计算机可读取存储介质中，该程序在执行时，执行包括上述方法实施例的步骤；而前述的存储介质包括：ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，根据本发明的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明的保护范围之内。