Cell Division Genetic Algorithm for Component Allocation Optimization in Multifunctional Placers
Cell Division Genetic Algorithm for Component Allocation Optimization in Multifunctional Placers
复制标题
DOI：
10.1109/tii.2021.3069459
复制
发表时间：
2022-01-01
影响因子：
12.3
通讯作者：
Gao, Huijun
中科院分区：
文献类型：
--
作者：
Li, Zhengkai;Yu, Xinghu;Gao, Huijun
迄今为止，在多功能贴片机中优化印刷电路板组件（PCBA）优化的所有目标仍然是一个艰巨的挑战。本文将原来的PCBA优化问题转化为一个新定义的元件分配问题，该问题决定了每个拾取和放置（PAP）周期中每个头处理的元件类型。组件分配问题是一个二次三维分配问题（Q3AP），有效地结合了所有主要目标的优化。有可能一个磁头处于空闲状态，因此分配的二维位置是不确定的。我们提出了细胞分裂遗传算法（CDGA）来解决这样一个复杂的Q3AP。CDGA分配一个组成单元作为基本单元。每个第一代元件单元包含相同类型的安装点。设计了一种细胞染色体解码启发式算法来确定下一个分配头。通过这样做，减少了问题的维数，因此，传统的遗传算法可以用于搜索由当前代单元形成的最优组件分配。当通过分配当前小区不再能够找到更好的分配时，执行小区划分操作以将每个小区划分成两个新小区。新的单元用于下一轮的GA搜索，进一步优化分配从两个方面：更好地平衡喷嘴变化和PAP周期的最小化，更灵活地最大化与不确定位置的同时拾取。CDGA持续工作，直到当前细胞不能带来任何改善。在使用工业样品的模拟和实验中，与最近的两项研究和广泛使用的多功能砂矿机韩华SM482 PLUS的内置优化器相比，该算法显着减少了PCBA时间，证明了其有效性和优越性。
Optimizing all the objectives of the printed circuit board assembly (PCBA) optimization in a multifunctional placer remains a formidable challenge till now. This article converts the original PCBA optimization problem to a newly defined component allocation problem, which decides the component-type handled by each head per pickup-and-place (PAP) cycle. The component allocation problem is a quadratic 3-D assignment problem (Q3AP) and effectively combines the optimization of all the main objectives. It is possible that one head stays idle, so the assigning 2-D locations are uncertain. We propose the cell division genetic algorithm (CDGA) to solve such a complex Q3AP. The CDGA allocates a component cell as the basic unit. Each of the first-generation component cells contains the mounting points of the same type. A cell chromosome decoding heuristic is designed to determine the next assigning head. By doing so, the problem dimension is reduced, so the conventional GA can be used for searching the optimal component allocation formed by the current-generation cells. When a better allocation can no longer be found by allocating the current cells, the cell division operation is performed to divide each cell into two new cells. The new cells are used in the next round of GA searching, which further optimizes the allocation from two perspectives: better balancing the minimization of nozzle changes and PAP cycles, more flexibly maximizing the simultaneous pickups with the uncertain locations. The CDGA works continuously until the current cells cannot bring any improvement. In simulations and experiments using the industrial samples, the proposed algorithm significantly reduces the PCBA time compared to two recent studies and the built-in optimizer of the widely used multifunctional placer, Hanwha SM482 PLUS, which demonstrates its effectiveness and superiority.