% !Mode:: "TeX:UTF-8"

\chapter{表面组装过程中生产线的负载平衡算法}[Workload balancing algorithm for the assembly line in surface assembly process]

\section{引言}[Introduction]

% === 研究内容和研究意义 ===
在第3--4章中，本文已对并列式贴片机的组装过程优化算法开展了深入的研究。
为进一步提升组装效率，制造商通常会将多个贴片机级联成生产线，而此过程涉及到生产线的负载平衡问题。
负载平衡算法研究的是如何平衡多台贴片机之间的生产任务，通过调整元件在生产线上分配的贴片机，提升生产线中瓶颈设备的组装效率。
负载平衡的结果决定了贴片机的生产任务，而贴片机的组装过程效率又用于评估负载平衡分配的结果，两个问题之间的耦合性增加了问题求解的难度。
解空间的庞大性以及评估解质量的复杂性是表面组装生产线负载平衡优化任务的主要难点，本章将从组装元件的分配策略以及组装时间的估计两个角度开展研究，提出表面组装生产线的负载平衡算法。
% 生产线负载平衡问题对算法的搜索效率提出了较高的要求。高效率的迭代搜索是算法求解复杂优化问题的关键，而贴片机的组装过程优化用时较长，在有限的时间内不足以全面评估所有负载平衡分配的结果来获取准确组装时间。因此，本章提出一种基于多特征融合集成时间预测的超启发式表面组装生产线负载平衡算法，有效地提升了表面组装生产线的组装效率。


超启发式算法是一类解决复杂优化问题的通用算法，其通过高层次启发式来管理和操作一系列底层启发式算子，实现对大规模组合优化问题的寻优\cite{tansel_hyper_heuristic_2024}，在复杂问题求解中展现出强大的适应性、有效性和可扩展性。
% 被广泛应用于路径规划\cite{wang_explaining_2024}、车辆调度\cite{chen_cooperative_2023}、流水车间规划\cite{zhao_estimation_2023}等多个领域。
算法由高层启发式和底层启发式构成。
其中，高层启发式不依赖于具体问题，直接管理和操纵底层启发式算法，通常具有通用的求解结构和较高的求解效率；
底层启发式算子的设计可根据问题特性，融合领域知识和专家经验等，构造多样化的搜索算子，以进一步提升算法的寻优能力。
% 此外，底层启发式可扩展延伸集成更多的底层算子，使得超启发式算法具有较强的灵活性和可扩展性。
超启发式算法通过决策底层算子的执行顺序，实现了对问题分阶段求解，并可根据解决方案的评估价值，调整底层算子操作的执行顺序。
在表面组装过程中，贴装点分配构成了负载平衡的基本决策环节，超启发式算法通过确定不同阶段分配给生产线贴片机的贴装点元件类型和数量，得到了不同的负载分配解决方案。


高效率的迭代搜索是算法求解复杂优化问题的关键，而执行贴片机的组装过程优化用时较长，在有限的时间内不足以全面评估所有负载平衡分配的结果来获取准确组装时间。
% 解的质量影响着超启发式算法的搜索方向，生产线的负载平衡和贴片机的组装过程优化作为相对独立的问题，在可接受的时间代价内，无法通过完全执行贴片机的优化来评估生产线负载平衡解的质量，因此需要运用时间估计器评估解的质量。
以机器学习为基础的时间估计器在各类产能预测问题中被广泛应用且具有较高的准确度，特别是在处理复杂、非线性以及多变量交互影响的估计问题上，其优势尤为明显。估计器通过学习历史数据的模式，自动调整模型参数，具备一定的泛化能力，并可以实现实时或接近实时的时间估计，适用于表面组装过程时间估计问题。


\section{问题分析}[Problem analysis]

生产线的平衡优化通过对各工序的作业内容、时间和效率的分析，改进或调整其中瓶颈工序的作业顺序，以实现机器工作负载的平衡，在过去已有较为充分的研究\cite{boysen_assembly_2022}。
表面组装生产线负载平衡问题可被视为一类特殊的生产线平衡优化问题，电路板上元件组装可被视为不同的生产工序。
优化算法将元件分配至不同的贴片机完成装配过程，同类型的元件可被分配到多台贴片机以提高装配效率。
表面组装生产线的负载平衡优化更为复杂之处在于装配时间的计算。生产线的效率取决于各贴片机的组装过程效率，以及贴片机类型、可用工具、待组装元件的类型和贴装点数，而贴片机的组装过程效率则与组装任务的元件类型、贴装点数和组装过程的调度优化算法相关。
为了实现较高的求解效率，在组装生产线的平衡问题中，解的质量评估无法直接依赖于贴片机表面组装过程优化算法的执行结果，而是需要通过快速的预测算法进行评估。可以认为，组装生产线平衡问题本质上是两个子问题的组合——元件分配算法和组装时间估算器的设计。图\ref{ch5:figure:line-opt-structure}展示了组装生产优化中相关的输入/输出和主要决策问题。

\vspace{0.5em}
\begin{figure}[H]
	\centering
	\includegraphics[scale=0.925]{chapter5/line-opt-structure.eps}
	\bicaption[ch5:figure:line-opt-structure]{}{表面组装生产线负载平衡优化问题框架}{Fig. $\!$}{\centering Framework of load balancing optimization problem for surface assembly lines}
\end{figure} 

% 影响生产线效率和制约因素
表面组装生产线通常由印刷机，贴片机，回流焊和光学检测机等多种设备组成，其中，贴片机的组装时间最长，决定了整条生产线的效率。本文在第2章中已讨论了影响表面组装过程装配效率的因素，包括贴片机的拾贴周期数、元件拾取次数、吸嘴更换次数和贴装点数等组装效率指标。贴片机分配的元件的类型、贴装点数以及对应的吸嘴类型都会对组装效率指标产生较大的影响。
元件分配算法用于确定贴片机上各类型元件的贴装点数，对于元件贴装点可重复分配的情形，贴装点的布局会对贴装移动路径产生影响，不同贴装点的分配结果同样会对生产线的组装效率产生影响。
此外，表面组装生产线优化还涉及一系列约束，包括可用工具约束、贴片机类型约束和组装优先级约束。可用工具约束指的是供料器、吸嘴和其他可用组装工具的数量有限，直接限制了特定类型元件可分配贴片机的数量上限，而贴片机类型约束则适用于不同类型贴片机在生产线上协作组装的情形，必须由特定机器完成某一类元件的装配。受限于不同类型的元件高度、尺寸各不相同，表面组装生产线通常也存在优先级约束。


% 元件分配和时间估算的难度
表面组装生产负载平衡问题中，元件不同的组合分配方案数量庞大，设计高效率的搜索方法寻找高质量的解对生产线优化至关重要。
而且随着问题规模的扩大，其求解的运算量也会迅速增加，即使是小规模的数据也需要大量的计算资源。
启发式搜索算法已在组合优化问题中展现出较强的全局搜索能力，基于问题特征的搜索规则与超启发式算法结合，可以有效提升解的质量。
表面组装过程优化通常需要较长的时间才能获取准确时间，即使是求解第3章中具有关键效率的贴片头任务分配算法，大量分配结果的组装过程运算的时间也较长，不适用于具有较大解空间的表面组装生产线优化问题中。
在估算装配时间时，时间估计器必须考虑到并列式贴片机的特殊机械结构对组装效率的影响，分析影响组装效率的关键因素，设计提取数据特征，以提高组装时间的估计准确度。
贴片机组装数据的元件类型、贴装点数均会对拾取效率、吸嘴更换等指标产生影响，传统的基于贴装点数量的线性拟合方法已不再适用。
非线性的神经网络时间估计器已能解决特征项较多的拟合问题，通过进一步融合多个具有组装特性的特征参数，能实现快速、准确的表面组装时间估计。

\section{算法框架}[Algorithmic framework]

以多特征融合集成估计器为基础的超启发式表面组装生产线负载平衡算法流程如图\ref{ch5:figure:solution-framework}所示，负载平衡以进化算法为基本框架，底层启发式和组装时间估计器则是算法的主要组成部分。
元件分组策略用于将同类型元件的贴装点划分为多个元件组，元件组是进行贴片机负载分配的最小单位，元件组分配先后顺序在不同的种群中随机生成以增加搜索的多样性。
群体初始化用于确定底层启发式算子的组合方式和执行顺序，群体中个体的基因对应一个底层启发式算子，算子则根据不同的策略确定元件组分配的贴片机。
更进一步，底层启发式算子可被分为数据驱动与目标驱动启发式，前者根据数据的基本参数进行分配，后者则基于组装过程子目标的比较结果进行分配。
组装时间的估计基于Bagging集成学习器，其通过融合组装过程的多个特性准确估计组装时间，用于计算种群迭代个体的适应度。
在迭代过程中，下一代的个体依据适应度进行加权随机选择，进化过程则以个体基因的截断交叉和突变完成。
超启发式元件组分配确定了各类型元件分配的贴装点数量，自适应聚类分组用以确定贴装点分配的贴片机。
多个群体的最佳解决方案作为候选解，进行表面组装过程优化确定准确装配时间，以降低时间估计器误差对最终结果产生的影响。

\begin{figure}[H]
	\centering
	\includegraphics[scale=0.95]{chapter5/solution-framework.eps}
	\bicaption[ch5:figure:solution-framework]{}{基于多特征融合集成组装时间估算器的超启发式优化算法流程}{Fig. $\!$}{\centering Flowchart of hyper heuristic optimization algorithm based on multifeature fusion ensembled assembly time estimator}
\end{figure} 


\section{基于超启发式的表面组装生产线元件分配算法}[Hyper-heuristic-based component allocation algorithm for surface assembly line]

\subsection{底层启发式算子}[Low-level heuristic operators]

底层启发式是超启发式算法的基本组成，启发式算子根据当前待分配元件的吸嘴类型、贴装点数等参数确定其分配的贴片机。其中，待分配元件类型和数量为预先设定的。本文将底层分配启发式进一步划分为数据驱动和目标驱动启发式。特别说明的是，底层启发式算子设计旨在平衡各贴片机间的工作负载，其在评估分配指标时仅对各贴片机的某项指标的相对大小进行比较，而对评估的绝对准确性不做要求。两类启发式算子的设计如下所示：

\subsubsection{数据驱动的底层启发式}

基于数据驱动的启发式与贴装点、元件类型和吸嘴类型相关，
其分别将元件分配到已分配贴装点数最少、元件类型数最少、吸嘴类型数最少、元件类型和吸嘴类型数最小之比的贴片机上。
在数据驱动的启发式算子中，分配贴装点数与贴装次数直接相关，是直接决定组装效率的因素之一。将元件组分配给元件类型少的贴片机，则有助于构成更多的同步拾取；将元件组分配给吸嘴类型少的贴片机，可用于规避吸嘴更换动作，提升整体的组装效率；元件类型数-吸嘴类型数之比则为平衡同步拾取与吸嘴更换的相互影响，单一类型吸嘴对应的元件过多会限制其同步拾取的构造，增加贴片头任务分配的可行解数，间接导致搜索空间变大，获得高质量解的难度也随之增大。


\subsubsection{目标驱动的底层启发式}

目标驱动的底层启发式与表面组装过程装配效率影响因素相关，通过分析和比较关键子目标的值作为元件分配的基础。元件组分配的贴片机取决于子目标的相对大小，而无需确定子目标的具体值。启发式计算的子目标值旨在平衡各贴片机之间的工作负载。目标驱动的子目标包括拾贴周期数、吸嘴更换数和元件拾取次数，其与各类吸嘴分配的拾贴头数相关。基于第3章提出的算法\ref{ch3:algorithm:model-initialize}，可确定各类型吸嘴对应的贴片头数，记已分配给贴片机 $m$ 的吸嘴类型 $j$ 的对应的贴片头数为 $\pi_{jm}$。


目标驱动的底层启发式的实现如下：

\begin{enumerate}
	\item[1)] \emph{最少周期启发式}：将元件分配到拾贴周期数最少的贴片机$\hat{m}$上，即：
	\begin{equation}
		\hat{m} = {\arg \min}_{m \in M} \max_{j \in J} \left( \sum_{i \in I} \sum_{k \in K} \sum_{h \in H} \left( \mu_{ij} \cdot x_{ikhm} \right) / \pi_{jm} \right)
		\label{ch5:equation:min-cycle}
	\end{equation}
	组装任务的吸嘴类型单一时，最少周期启发式同时是最少贴装点分配启发式。在处理组装任务的有多种吸嘴类型时，算子在计算拾贴周期数时，禁用了贴片头的吸嘴更换动作，以各类型吸嘴分配的贴装点数均分贴片头得到的最大周期数作为评定标准，能平衡不同类型吸嘴分配点数，进而降低拾贴周期和吸嘴更换数。

	\item[2)] \emph{最少吸嘴更换启发式}：将元件分配到吸嘴更换数最小的贴片机$\hat{m}$上，
	\begin{equation}
		\hat{m} = {\arg \min}_{m \in M} \sigma \left( \left\{ \overbrace{\sum_{i \in I} \sum_{k \in K} \sum_{h \in H} \left( \mu_{ij} \cdot x_{ikhm} \right) / \pi_{jm}, \cdots}^{\text{共 $\pi_{jm}$ 项}} \mid j \in J \right\} \right)
	\end{equation}
	
	其中 $\sigma\left( \cdot \right)$ 表示集合的均方差。吸嘴更换和元件拾取次数存在关联，对吸嘴更换的判定依据主要为不同类型吸嘴分得的贴装点数。算子以各类型吸嘴分得的贴片头数，对其已分配的贴装点均分分组，并根据分组后组间贴装点的均方差值评估吸嘴更换可能性，均方差越大、对应的贴片机更有可能发生吸嘴更换。	

	\item[3)] \emph{最少拾取启发式}：将元件分配给拾取元件次数最小的贴片机。不同于前两种目标驱动启发式， 贴片机的拾取次数直接计算比较困难。算法\ref{ch5:algorithm:least-pickup}提出了一种分级贪心启发式的同步拾取次数估算的方法。
	算法根据各类吸嘴分配的贴片头数量，按贴装点数量递减的顺序将元件分配到吸嘴类型一致的贴片头。确定当前分配元件$i$对应的吸嘴$j$，记吸嘴$j$已分配的贴片头数为$\mathcal{A}_j$，当其分配满所有可用贴片头后，进入下一周期$c$进行分配，令吸嘴当前分配周期索引$\mathcal{L}_j$增加1，同时记录各个周期分配的贴装点数的最大值$\mathcal{K}_c$。算法结果中（同步）拾取次数等于各周期内分配到贴片头的元件对应的最大贴装点数之和。
\end{enumerate}

\begin{algorithm}
	\small
	\AlgoBiCaption{分级贪心启发式同步拾取计算算法}{Level greedy heuristic simultaneous pick-up calculation algorithm}
	\label{ch5:algorithm:least-pickup}
	
	\Input{吸嘴对应的贴片头数$\pi$，元件对应的贴装点数$\psi$和贴片机索引$m$}
	\Output{拾取次数}
	令 $\mathcal{L}$ 为大小 $1 \times \left| J \right| $ 的向量，$\mathcal{A}$ 为大小 $1 \times \left| J \right| $ 的向量，$\mathcal{K}$ 为 $1 \times  \sum_{i \in I} \psi_i $ 全为0的向量; \\
	按贴装点数 $\psi_i$ 降序排列元件索引 $i \in I $;\\
	\For {$i \in I$} 
	{
		$j \leftarrow \sum_{j^\prime \in J} \mu_{ij^\prime} \cdot j^\prime$ ;\tcp{分配元件对应的吸嘴类型}
		\If { $\mathcal{A}_j$ \rm{\textbf{mod}} $\pi_{jm} = 0$ }
		{
			$\mathcal{L}_j \leftarrow \mathcal{L}_j + 1 $; \tcp{当前周期吸嘴的贴片头分配已满，开始分配下一周期}
		}
		\tcc{更新当前分配周期的最大分配点数和已分配贴片头数}
		$c \leftarrow \mathcal{L}_j  $，
		$\mathcal{K}_c \leftarrow \max \left(\mathcal{K}_c, \psi_i \right)$，$\mathcal{A}_j \leftarrow \mathcal{A}_j + 1$ ;\\
	}
	输出元件拾取次数 $\sum_{c = 1}^{c =\sum_{i \in I} \psi_i }  \mathcal{K}_c$
\end{algorithm}

上述的底层启发式规则用于确定元件组分配的贴片机，在分配过程中，底层启发式在评估不同贴片机的指标时如果出现相同的值，算子将先按贴片机已分配的贴装点数最少、再按贴片机组装先后顺序的规则进行元件组分配。


\subsubsection{组装任务的元件分配过程}

如前所述，元件组是算法进行分配的最小单位，将同类型元件划分为多个元件组有助于贴片机之间的协作生产，平衡贴片机间的工作负载，进而提升组装效率。
然而，由于生产线在拾贴元件的过程中同时受到可用贴片机、组装优先级和可用工具等条件的限制，直接按上述规则进行分配将导致负载平衡的解不可行。
本节从元件分配优先级处理和可用组装工具限制两个角度对底层启发式算子进行完善。

1）\emph{元件分配优先级的处理}

不同于传统的生产线，表面组装生产线不存在复杂的优先级约束关系。
组装过程中的优先级约束通常指元件尺寸小、高度低或精度要求低的元件的组装顺序需要先于其它元件，以保证元件组装位置的准确性。
在实际生产中，不同类的元件通常被划为若干优先级组，按分组的优先级顺序进行组装作业。
分配过程对元件组装优先级处理主要分为两个阶段。
在第一阶段中，算法\ref{ch5:algorithm:component-priority}根据生产线的贴片机数、元件的贴装点数等参数，按贴装点在贴片机间进行均分的设定分组，并在此基础上调整允许偏差界限，确定了优先级约束下不同元件的可分配贴片机索引集合$\widetilde{M}^{\rm PR}$。按组装优先级限制元件可分配的贴片机索引，有助于平衡贴片机之间的负载，提升优先级约束下的搜索效率。

\vspace{0.6em}
\begin{algorithm}[H]
	\small
	\AlgoBiCaption{优先级约束下的元件可分配贴片机构造算法}{Assignable surface mounters constructive algorithm for component under priority constraint}
	\label{ch5:algorithm:component-priority}
	
	\Input{组装优先级分组$\mathcal{I}$，元件的贴装点数$\psi$，贴片机负载分配允许偏差$\varsigma$}
	\Output{元件可分配贴片机索引集合$\widetilde{M}^{\rm PR}$}

	按组装先后顺序对元件优先级分组$\mathcal{I}_q$进行排序，$q \in Q$，按贴装点数非递减的顺序对$\mathcal{I}_q$组内元件$i$进行排序，$i \in \mathcal{I}_q$ ; \\
	
	令元件优先级约束的可分配贴片机索引集合$\widetilde{M}^{\rm PR} \leftarrow \varnothing$，记录已遍历元件的贴装点数 $C\leftarrow 0$ ;\\
	
	\For {遍历元件优先级组内的元件$i \in \mathcal{I}_q$，$q \in Q$}
	{
		\For {遍历组装线的贴片机$m \in M$}
		{
			\If{$m \cdot \sum_{i^\prime \in I} \psi_{i^\prime} / \left| M \right| - \varsigma \leq C $ \rm{\textbf{and}} $ C  \leq m \cdot \sum_{i^\prime \in I} \psi_{i^\prime} / \left| M \right| + \varsigma$}
			{
				\tcc{已遍历的贴装点数在贴片机的贴装点均分的允许偏差范围内}
				\vspace{0.1em}
				$\widetilde{M}^{\rm PR} \leftarrow \widetilde{M}^{\rm PR} \cup \left\{ m \right\}$，$C \leftarrow C + \psi_i$ ; \\
			}
		}
	}
	
\end{algorithm}
\vspace{0.6em}

在第二阶段中，分配算子需依据待分配的元件组和既定的优先级约束关系，对元件组的负载平衡分配结果进行调整。
算法\ref{ch5:algorithm:component-priority}确定了优先级约束下的元件可分配贴片机索引集，但其无法完全保证解的可行性。
由于不同优先级的元件可分配至相同的贴片机完成组装作业，因此元件的可分配贴片机索引集$\widetilde{M}^{\rm PR}$间会有同一贴片机。
为满足组装过程的优先级约束，根据各贴片机所分配元件的最高与最低优先级，本节引入了链式置换规则来优化元件组合的分配过程。

在具体实现过程中，对于当前待分配的元件，算法依据其分配目标贴片机进行比对：若前置贴片机的最低优先级高于当前元件的优先级，则将当前元件与前置贴片机的元件进行交换；类似地，若后置贴片机的最高优先级低于当前元件的优先级，则与后置贴片机的元件进行互换。
重复上述操作，直至生产线上所有已分配的元件均满足优先级约束关系。
在选择被置换的元件时，算法根据待分配元件的吸嘴类型和贴装点数，按照如下规则进行：若被置换出的贴片机已分配元件中存在同类型吸嘴的元件，则优先选择与当前待分配元件贴装点数最接近的元件进行交换；若不存在同类型吸嘴的元件，则从吸嘴对应已分配元件类型最多的类别中，选择与待分配元件组贴装点数最接近的元件进行置换。
此规则旨在最大限度地减少因元件置换而引起的贴片机间组装效率的变化，从而保持生产线上贴片机之间的负载平衡状态。


2）\emph{可用组装工具的限制}

可用贴片机约束限制了元件可分配的贴片机集合，底层启发式算子需在可用贴片机集合中完成分配。可用贴片机集合受到元件已分配贴片机和可用工具数的限制，元件供料器可用数等限制了元件可分配的贴片机数，记$\widetilde{r}_{im}$表示贴片机$m$是否已分配元件$i$的组装任务，记元件$i$的可用供料器数为$\phi_i$，则分配过程中可用组装工具限制的可分配贴片机索引集$\widetilde{M}^{\rm TL}$计算如式\eqref{ch5:equation:allocable-machine}所示，其在元件负载平衡分配的过程中被动态调整。
\begin{equation}
	\widetilde{M}^{\rm TL}_i =
	\begin{cases}
		 M & \sum_{m \in M} \widetilde{r}_{im} < \phi_i \\
		\left\{ m \mid \widetilde{r}_{im} > 0, m \in M \right\} & \sum_{m \in M} \widetilde{r}_{im} \geq \phi_i
	\end{cases}
	\label{ch5:equation:allocable-machine}
\end{equation}

组装分配优先级和可用组装工具确定的可分配贴片机索引集共同确定了元件组可分配的贴片机。


\subsection{可重复元件分配策略}[Duplicated component allocation strategy]\label{duplicate-allocation-section}

元件配备多个可用供料器用以提升组装效率，引出元件可重复分配的问题。当同类型元件的物料有多个可用供料器时，元件可分配至多个贴片机协同完成组装过程。元件分配的供料器数依据第3章中提出的算法\ref{ch3:algorithm:avl-feeder}确定。元件可重复分配策略包括进行元件分配前的分组策略和完成元件分配后的贴装点分配策略，具体为：

1）\emph{可重复元件分组策略}

贴装点分组是辅助决策贴片机分配的元件贴装点数的主要方式，分组后的元件组是超启发式分配的基本单位。
贴装点的分组数并不仅取决于可用供料器数，而且与贴装点数有关。过少的分组数会压缩搜索解的搜索空间，导致算法无法搜索到高质量的解，无法平衡不同的贴片机之间的工作负载；过多的分组数则会导致搜索效率下降。记元件$i$可用的供料器数为$\phi_i$，对应的分组基准为$\hat{\phi}_i$，分组基准的计算方式如式\eqref{ch5:equation-div}，其中$\varepsilon$为分组基准系数。贴装点数超过该分组基准的元件将被分配到一个元件组，各元件组的贴装点数均不超过分组基准，元件组是超启发式进行元件分配的最小单位。
\begin{equation}
	\hat{\phi}_i =  \max \left( \varepsilon \cdot \phi_{i^\prime} \cdot \psi_{i} / \sum_{i^\prime \in I} \psi_{i^\prime}, \phi_i \right) \quad \forall i \in I
	\label{ch5:equation-div}
\end{equation}


2）\emph{可重复元件贴装点的分配策略}

超启发式算法仅确定贴片机分配到的各类型元件的贴装点数，而贴装点的布局会对组装效率产生较大的影响，不同的贴装点分配方案同样限制着生产线组装效率的提升。
元件可重复分配策略研究的另一方面就是对贴装点-贴片机的分配结果进行优化。
包括本文在内的多数主流研究均将贴片机的表面组装过程划分为拾取过程和贴装过程两部分，而拾取过程优化通常与贴装点的分布位置关联度较低。
算法\ref{ch5:algorithm:cluster-point}提出了一种基于聚合聚类启发式的可重复元件贴装点分配策略，其充分考虑了贴装点的位置分布特性和贴片头线性分布的特性，将位置集中的贴装点分配给同一台贴片机，能有效缩短表面组装移动路径长度，从而进一步提升贴片机的组装效率。


\begin{algorithm}[!hbt]
	\small
	\AlgoBiCaption{可重复元件贴装点分配的聚合聚类算法}{Aggregated clustering algorithm for placement points of duplicated component}
	\label{ch5:algorithm:cluster-point}
	
	\Input{元件的可用供料器数$\phi$，贴装点的位置$\left( X_p, Y_p \right)$，$p \in P$，元件-贴片机的分配结果$r$，贴片头元件分配$\mathcal{C}$和周期分配结果$\mathcal{W}$}
	\Output{机器分配的贴装点$\overline{\mathcal{P}}$}
	令贴片机$m$已分配的贴装点集 $\mathcal{P}_m \leftarrow \varnothing$，贴片机$m$的贴片头$h$已分配元件$i$的贴装点数$\Lambda_{ihm} \leftarrow 0$，元件贴装的贴片头偏移$\overline{h}_{im} \leftarrow 0$，$i \in I$，$h \in H$，$m \in M$ ;\\
	% 令贴片机$m$的贴片头$h$已分配元件$i$的贴装点数$\Lambda_{ihm} \leftarrow 0$，元件贴装的贴片头偏移$\overline{h}_{im} \leftarrow 0$ ;\\
	\For{$m \in M$} 
	{
		\For{$i \in \left\{ i^\prime \mid r_{{i}^\prime m} = 1, \phi_{i^\prime} = 1, i^\prime \in I \right\}$}
		{
			% $\mathcal{U}_{im} \leftarrow \left|\left\{ p \mid \eta_{ip}=1,p\in P \right\} \right| $,
			 $\mathcal{P}_m \leftarrow \mathcal{P}_m \cup \left\{ p \mid \eta_{ip}=1,p\in P \right\}$ ; \tcp{确定各贴片机的固定分配点}	
		}
		\For{$k \in K$}
		{
			\For{$h \in H$}
			{
				记$i = \mathcal{C}_{khm}$，有$\Lambda_{ikm} \leftarrow \Lambda_{ikm} + \mathcal{W}_{km}$，

				$\overline{h}_{im} \leftarrow \left( 1 - \mathcal{W}_{km} / \sum_{h \in H} \Lambda_{ihm} \right) \cdot \overline{h}_{im} + \mathcal{W}_{km} \cdot \left( h - 1 \right) /  \sum_{h \in H} \Lambda_{ihm}   $ ;\\
			}
			
		}
		 $\mathcal{X}_m \leftarrow  \sum_{p \in \mathcal{P}_m} \left( X_p - \sum_{i \in I} \eta_{ip} \cdot \overline{h}_{im} \right) / \left| \mathcal{P}_m \right| $, $\mathcal{Y}_m \leftarrow  \sum_{p \in \mathcal{P}_m} Y_p / \left| \mathcal{P}_m \right| $;  \tcp{设置贴片机$m$的分配中心点}
	}
	\While{\bf{true}}
	{
		$\overline{\mathcal{X}} \leftarrow \mathcal{X}$， $\overline{\mathcal{Y}} \leftarrow \mathcal{Y}$，$\overline{\Lambda} \leftarrow \Lambda$，
		$\overline{\mathcal{P}} \leftarrow \mathcal{P}$  ; \\
		\For{$i \in \left\{ i^\prime \mid \theta_{i^\prime} > 1, i \in I \right\} $}
		{
			\For {$p \in \left\{ p^\prime \mid \eta_{ip^\prime} = 1,   p^\prime \in P \right\} $}
			{
				\tcc{计算待分配贴装点的贴片机和贴片头索引}
				$\left(\hat{m}, \hat{h} \right) \leftarrow \arg \min_{m \in M, h \in H} \left\{ \left(\overline{\mathcal{X}}_{m} - X_p + \left(h - 1\right) \cdot \rho \right)^2 +
				\left(\overline{\mathcal{Y}}_{m} - Y_p \right)^2 \mid  \right.$
				$ \left. \overline{\Lambda}_{ihm} > 0 \right\}$ ，
				$\overline{\mathcal{P}}_{\hat{m}} \leftarrow \overline{\mathcal{P}}_{\hat{m}}\cup \left\{ p \right\} $，$\overline{\Lambda}_{ihm} \leftarrow \overline{\Lambda}_{ihm} - 1$，$\hat{h} \leftarrow \hat{h} - 1$;
				
				\tcc{更新已分配的贴装点参数和贴片机的分配中心位置}
				$\overline{\mathcal{X}}_{\hat{m}} \leftarrow \overline{\mathcal{X}}_{\hat{m}} + \left(X_p - \overline{\mathcal{X}}_{\hat{m}} - \hat{h} \cdot \rho \right) / \left| \overline{\mathcal{P}}_{\hat{m}} \right|$，	
				$\overline{\mathcal{Y}}_{\hat{m}} \leftarrow \overline{\mathcal{Y}}_{\hat{m}} + \left(Y_p - \overline{\mathcal{Y}}_{\hat{m}}  \right) / \left| \overline{\mathcal{P}}_{\hat{m}} \right|$;
			}
		}

		\If{$\sum_{m \in M} \left( \left| \overline{\mathcal{X}}_m - \mathcal{X}_m \right| +\left| \overline{\mathcal{Y}}_m - \mathcal{Y}_m \right| \right) \leq 10^{-3} $}
		{
			\tcc{贴片机的分配中心位置未发生变化，退出搜索过程}
			\textbf{break};
		}
	}
\end{algorithm}


可重复元件贴装点的分配策略的输入为贴片机$m$在周期组$k$中贴片头$h$拾贴的元件类型为$\mathcal{C}_{khm}$，以及对应的拾贴周期数$\mathcal{W}_{km}$。据此，可确定各贴片机组装作业过程中，不同类型元件的贴装偏移量$\overline{h}_{im}$，其是元件组贴装点分配的基准。
对于仅有单一供料器提供的元件的贴装点，其被分配至同一台贴片机，结合组装该类型元件贴片机的贴装偏移量$\overline{h}$，可确定各贴片机的初始中心点，
而尚未分配任何贴装点的贴片机的初始中心点将被随机设定。
算法分配的基本单位由贴片机进一步具体到贴片头，根据贴片头任务分配结果，可确定其拾贴元件$i$对应的贴装点数$\Lambda_{ihm}$。随后，元件的贴装点按最近邻原则，在负载平衡结果的约束下，分配到距离中心点最近的贴片机-贴片头索引对$\left(\hat{m}, \hat{h}\right)$，并在分配过程中动态调整中心点。
算法不断重复上述过程，直至所有中心点的位置趋于稳定。

\subsection{超启发式优化算法}[Hyper-heuristic optimization algorithm]

在基于进化算法的超启发式架构中，个体的编码直接映射至一个底层的启发式操作算子。
元件组作为同类型元件分配的基本单位，其分配顺序影响着负载平衡的结果。
为适应复杂的分配需求，个体的基因长度随机生成。
底层启发式算子与元件组相对应，当个体基因长度小于元件组数时，元件分配的过程将循环访问个体基因。
个体的基因长度以及底层启发式算法的基因组合均在初始化阶段随机生成，以确保搜索的全面性和随机性。
在进化流程中，算法依据适应度进行加权随机选择，确定参与交叉和变异的个体。
% 超启发式的交叉和变异算子的操作过程如图\ref{ch5:figure:operation}所示。
对于交叉操作，相关个体的基因将分别随机选择一个插入段交换基因段；对于变异操作，则在个体基因中随机选择一个插入点，插入一段随机生成的基因。二者在完成操作后，算法均会对基因长度超出元件组数的部分截断处理，以确保后续迭代过程中不会因为无效的基因段导致搜索的盲目性。

% \begin{figure}[H]
% 	\centering
% 	\includegraphics[scale=1]{chapter5/crossover-mutation.eps}
% 	\bicaption[ch5:figure:operation]{}{进化过程中的交叉和变异操作示意图}{Fig. $\!$}{Schematic representation of crossover and mutation operations in evolutionary process}
% \end{figure} 

底层启发式操作算子与元件分配顺序直接相关，同时对启发式算子执行顺序和元件分配顺序编码，会增加编码的复杂性，导致算法难以找到算子和元件分配间的规律，进而增加了寻找高质量解的搜索时间。因此，本章并未将元件分配顺序作为基因编码的组成部分。对超启发式底层算子执行顺序的优化能将多数元件分配顺序优化到一个相对高质量的解。
在算法设计时，超启发式采用多种群的优化方案，既可以实现并行搜索，又避免了单一元件组分配顺序在有限次迭代内无法获得高质量的解。
不同种群迭代的最佳解决方案在估算的组装时间通常较接近，而应用多种群的方案可进一步筛选高质量的解，通过在少数候选解上执行表面组装过程优化算法获得更准确的装配时间。
在具体实施时，算法将优先在估计的组装时间较长的贴片机上运行组装过程优化算法，以进一步提升运行效率。

\section{基于多特征融合的集成表面组装时间估计器}[Surface assembly time ensemble estimator based on multifeature fusion]

\subsection{数据的生成与准备}[Data generation and preparation]

组装数据用于组装时间估计器模型的训练过程。估计器通过处理和分析数据，学习其特征并建立预测模型。生产数据的数量、质量和多样性直接影响着时间估计器预测的性能和效果，更多的训练数据意味着网络能学习到更为复杂的特性，从而提升神经网络的泛化性能。高质量的数据通常噪声少，结果准确，有助于网络更准确地学习。对于表面组装过程问题，直接获取大量的实际生产数据较为困难，且生产数据的组装时间不可避免的受到噪声的影响。在实际应用中，本章以贴片机软件内置的组装过程模拟器，计算生产数据的组装过程用时，以获得更为准确的预测模型。

在数据生成方面，用以训练的数据兼顾吸嘴类型单一到多样，不同元件的贴装点数相近到不等，贴装点分布位置随机分布的特点进行生成，避免贴装点布局对预测结果产生偏差，进而影响整体的预测效果。
在训练模型之前，有必要检测并清除可能影响机器学习模型的异常值，偏离中心位置的点会增加训练结果的不确定性。本章运用四分位距的规则（Interquartile Range Rule，IRR）\cite{li_predicting_2020}检测和剔除异常值，其中装配时间$\mathcal{T}$大于 $\mathcal{T}_3 + 1.5 \cdot \left( \mathcal{T}_3 - \mathcal{T}_1 \right)$或小于 $\mathcal{T}_1 - 1.5 \cdot \left( \mathcal{T}_3 - \mathcal{T}_1 \right)$的数据点会被移除，$\mathcal{T}_1$ 和 $\mathcal{T}_3$ 分别代表第一四分位数和第三四分位数。


\subsection{组装过程的特征提取}[Feature extraction of assembly process]
特征选择是预测拟合问题的关键步骤，其对于提高模型的准确性、可解释性和计算效率都至关重要。特征提取涉及从生产数据中选择对于预测组装时间最有用或最具代表性的特征，其与表面组装过程优化算法相关。组装过程的复杂性使某些生产过程特性难以被揭示，因而本章提出一种基于集成学习框架的多特征数据融合时间估计器，将数据的基本参数和估计的性能指标参数等同时作为网络输入数据。其中，启发式算法用于评估性能指标，提高拟合精度。用于训练和测试的数据特征主要包含以下内容：
\begin{itemize}
	\item 贴装点数、元件类型数和吸嘴类型数
	\item 贴装区域的长度、宽度和面积
	\item 预估的拾贴周期数、拾取次数、吸嘴更换次数等子目标
	\item 各类型元件对应的吸嘴类型编码和贴装点数
\end{itemize}


\begin{algorithm}[htb]
	\small
	\AlgoBiCaption{吸嘴更换次数评估启发式算法}{Heuristic algorithm for estimating the number of nozzle changes}
	\label{ch5:algorithm:nozzle-change}
	
	\Input{吸嘴的贴片头数 $\pi$，元件的贴装点数 $\psi$}
	\Output{吸嘴更换次数 $\iota^{*}$}
	令 $\mathcal{H}^{\rm{PT}} $ 为 $1 \times \left| H \right|$ 的全0向量， $\mathcal{H}^{\rm{NZ}}$ 为 $1 \times \left| H \right|$ 的向量; \tcp{分别表示贴片头上的贴装点数和吸嘴类型数}
	
	令 $V \leftarrow 0$，$V^{*} \leftarrow \infty$， $\iota^{*} \leftarrow 0$; \tcp{分别表示评估指标、最优评估指标和对应的吸嘴更换次数}
	
	\While{$V \leq V^{*}$} {
		令吸嘴组$\mathcal{Z}_{j}$为大小$1 \times \pi_j$ 的元素值为 $ \sum_{i \in I}  \psi_i \cdot \mu_{ij} / \pi_j$ 的向量，  $\forall j \in J$; \\
		\For {$n \in \mathcal{Z}_j, j \in J$} 
		{
			
			$h \leftarrow \arg \min_{h^\prime \in H} \left\{\mathcal{H}^{\rm{PT}}_h \right\}$，
			$\mathcal{H}^{\rm{NZ}}_h \leftarrow j$， $\mathcal{H}^{\rm{PT}}_h \leftarrow \mathcal{H}^{\rm{PT}}_h +  n$ \tcp{分配吸嘴组至各贴片头}
		}
		$V \leftarrow \max_{h \in H} \mathcal{H}^{\rm{PT}}_h$ \tcp{设置拾贴周期数}
		\While{\rm{\textbf{true}}} {
			\tcc{平衡已分配贴装点数最多的贴装和最少的贴片头}
			$h_1 \!  \leftarrow \! \arg \max_{h \in H} \mathcal{H}^{\rm{PT}}_h$ ， $ h_2 \! \leftarrow \! \arg \min_{h \in H} \mathcal{H}^{\rm{PT}}_h $ ;\\
			\If { $\mathcal{H}^{\rm{NZ}}_{h_1} = \mathcal{H}^{\rm{NZ}}_{h_2}$ }
			{
				\textbf{break};
			}
			\tcc{比较周期减少与吸嘴更换的加权值，确定最优方案}
			$\mathcal{H}_1 \leftarrow \left\{ h \mid \mathcal{H}^{\rm{NZ}}_h = \mathcal{H}^{\rm{NZ}}_{h_1} , h \in H \right\} $，
			$\mathcal{H}_2 \leftarrow \left\{ h \mid \mathcal{H}^{\rm{NZ}}_h = \mathcal{H}^{\rm{NZ}}_{h_2} , h \in H \right\} $;
			
			\If {$ T^{\rm{CY}} \cdot \left( \mathcal{H}^{\rm{PT}}_{h_1} - \mathcal{H}^{\rm{PT}}_{h_2} \right) > T^{\rm{NC}} \cdot \left( \left| \left| \mathcal{H}_2 \right| - \left| \mathcal{H}_1 \right| \right| \right)  $ }
			{
				\textbf{break};
			}
			\tcc{计算吸嘴更换数和吸嘴更换后的分配结果}
			$\iota \leftarrow \left| \left| \mathcal{H}_2 \right| - \left| \mathcal{H}_1 \right| \right|$，$V \leftarrow V - T^{\rm{CY}} / T^{\rm{NC}} \cdot \left( \mathcal{H}^{\rm{PT}}_{h_1} - \mathcal{H}^{\rm{PT}}_{h_2} \right) + \iota $，
			$\hat{\mathcal{H}}^{\rm{PT}} \leftarrow \mathcal{H}^{\rm{PT}}$; \\
			\For{$h \in \mathcal{H}_1 \cup \mathcal{H}_2$}
			{
				$\mathcal{H}^{\rm{PT}}_h \leftarrow \sum_{h^{\prime} \in \mathcal{H}_1 \cup \mathcal{H}_2} \hat{\mathcal{H}}^{\rm{PT}}_{h^{\prime}} / \left( \left| \mathcal{H}_1 \right| + \left| \mathcal{H}_2 \right| \right)$， $\mathcal{H}^{\rm{NZ}}_h \leftarrow \mathcal{H}^{\rm{NZ}}_{h_1}$;\ \\
			}			
		}
		\tcc{增加吸嘴组数目，重新进行分配}
		\If { $V < V^{*}$ }
		{
			$V^{*}  \leftarrow  V$，$\iota^{*}  \leftarrow \iota$， $\pi_{j} \leftarrow \pi_{j} + 1$，其中$j = \arg \max_{j \in J} \psi_j / \pi_j $;
		}
	}
\end{algorithm}

生产数据的基本参数类型包含贴装点数、元件类型数、吸嘴类型数和电路板尺寸等与组装信息密切相关的数据，同时包含组装过程优化的子目标等性能参数。与底层启发式为了满足任务负载均衡的设计不同，用于拟合特征更侧重于估计结果的准确性。
目标项在编码过程中主要用于反映组装过程优化算法的性能，
在目标数据特征中，拾贴周期数可参照式\eqref{ch5:equation:min-cycle}，根据贴装点数和吸嘴分配的贴片头数确定，应用算法\ref{ch5:algorithm:least-pickup}可进一步确定评估的同步拾取次数，算法\ref{ch5:algorithm:nozzle-change}则提出了一种吸嘴更换计算启发式。

吸嘴更换计算启发式首先将具有相同吸嘴类型的元件的贴装点均分形成不同的吸嘴组，其中吸嘴$j$对应的吸嘴组集合记为$\mathcal{Z}_j$。
吸嘴组按照贴片头工作平衡的原则进行分配，算法先从空吸嘴头开始，依次分配给已分配贴装点数量最少的贴片头。
初次分配完成后，算法平衡贴片头上的贴装点，并评估均分后整体指标的变化。如果均分后减少的拾贴周期带来的效率提升大于增加吸嘴更换带来的效率损失，那么此次均分是有效的，重复均分过程直至出现无效的操作。随后，增加平均贴装点数最多的吸嘴的分组数，重复上述操作过程，并记录搜索过程中加权值最优对应的吸嘴更换次数，直到总体效率没有增加为止。


\subsection{集成学习估计器的结构设计}[Structure design of the ensemble learning estimator]

\begin{figure}[!bt]
	\centering
	\includegraphics[scale=0.825]{chapter5/neural-network.eps}
	\bicaption[ch5:figure:network-structure]{}{基于集成学习的多特征融合组装时间估计器结构}{Fig. $\!$}{Structure of ensemble learning-based multifeature fusion assembly time estimator}
\end{figure} 

集成学习通过结合多个学习器的预测结果提供了一种提高预测性能的学习范式，可以降低模型的泛化误差。在机器学习算法中，全连接神经网络以其简单的结构、高效的运算速度、强大的特征提取能力等优势，在数据拟合和预测等领域中发挥着重要作用。本章中，融合多数据特征的Bagging集成学习器用于估计表面组装时间；集成学习共由5个基模型并行训练，其中的基模型采用具有双隐藏层的全连接神经网络，并取基模型输出结果的平均值作为最终组装时间预测结果。
在估计器的输入数据的编码上，分为基本数据类型，目标数据类型和扩展数据类型三部分。其中，基本数据类型包含元件类型数、吸嘴类型数和贴装点数；目标数据类型则采用前一节估算的同步拾取数、吸嘴更换数等特征；扩展数据类型则包含不同元件的吸嘴类型、元件类型等参数。在扩展数据类型中，各吸嘴、元件类型的编码按贴装点数降序进行编号。
图\ref{ch5:figure:network-structure}展示了估计器的输入参数和基本结构。估计器的输入数据设定为足够长的编码，以确保不同数据输入的一致性，并用零补充冗余位。最终的输出结果则采用标准化的单位时间贴装点数进行归一化处理。



\section{实验设计}[Experimental design]

为说明本章提出的基于多特征融合集成时间估计器的超启发式组装线优化（Hyper-Heuristic Assembly Line Optimization based on Multifeature Fusion Ensemble Estimator，HHALO-MFEE）算法的实际效果，本节将对比分析组装时间估计器的拟合精度，将生产线负载平衡算法的运行结果同模型的性能指标加权最优解进行比较，最后将HHALO-MFEE同主流的相关研究进行比较。
对比实验中参数设置和程序运行配置同第3--4章相同。表\ref{ch5:table:exp-para}列出了超启发式元件分配和多特征融合集成组装时间估计器的基本参数。10组随机生成的元件分配序列用于迭代搜索元件分配的最优解，种群的个体数为20，种群迭代的总次数为100，交叉和变异发生的概率为60\%和10\%。超启发式元件分配过程中，元件分组基准的系数$\varepsilon=1.5$。组装时间估计器的基模型时采用双中间层的全连接神经网络，各层的神经元个数为1000，网络的不同层中使用相同的Relu作为激活函数，并运用Adam梯度下降算法自适应地调整学习率。


\begin{table}[H]
	\small
	\centering
	\small
	\bicaption[ch5:table:exp-para]{}{神经网络和超启发式算法的参数}{Table $\!$}{Parameters of neural networks and hyper-heuristic algorithm}

	\begin{tabular}{p{3cm}<{\centering}p{4.25cm}p{2.25cm}<{\centering}}
		\toprule
		方法 & \makecell[c]{参数} & 设定值 \\
		\midrule
		\multirow{4}{*}{超启发式} & 种群大小 & 10  \\
		& 个体数 & 20  \\
		& 交叉率 | 变异率 & 0.6 | 0.1  \\
		& 迭代次数 & 100   \\
		\cmidrule(lr){1-3}
		
		\multirow{2}{*}{神经网络} & 学习率& $10^{-5}$  \\
		& 迭代次数 & 8000  \\
		\bottomrule		
	\end{tabular}
\end{table}

在实验数据选取上，15组来自实际表面组装生产线的数据用于评估生产线负载平衡算法的实际效果，其中前5组小规模数据用于模型对比验证，后10组大规模数据用于算法效果对比，数据的基本参数包括元件类型数、吸嘴类型数、贴装点数和可用供料器数。当可用供料器数多于元件类型数时，元件可重复分配至不同的贴片机完成组装任务。三条不同的表面组装生产线用于比较算法的实际效果，
% 生产线的组成如图\ref{ch5:figure:real-assembly-line}所示，
其中\emph{L}1、\emph{L}2和\emph{L}3分别配备有2、3 和 4 台贴片机。
本节仅以各优化算法在一般应用场景下的实际效果作对比分析，不计组装优先级、可用贴片机等约束。
% 本节比较提出算法在实践中的最优效果，因而优先级约束、可用贴片机约束等条件不在比较过程中被考虑。
由于元启发式算法和部分对比算法结果的随机性，所有比较指标均取10次运行的平均值作为最终结果。


\subsection{组装时间估计器的对比实验}[Comparative experiments on the assembly time estimators]

如前所述，MFEE的训练数据和测试数据均为随机生成，组装任务的拾贴顺序采用第3--4章提出的表面组装过程优化算法。通过运行贴片机内置的模拟器，估计组装过程的运动和动作用时，结合电机参数、机械运动特性等获取更为准确的组装时间。
表\ref{ch5:table:data-para}列出了训练数据和测试数据的样本数、异常比、均值等组装时间相关的参数，二者具有相似的分布特性，数据的异常值是通过IRR检测和剔除的。贴装点的分布位置随机生成避免点稀疏或集中的分布特征对拟合方法泛化性能的影响。

\begin{table}[H]
	\centering
	\small
	\bicaption[ch5:table:data-para]{}{训练数据和测试数据的参数}{Table $\!$}{Parameters of training data and testing data}

	\begin{tabular}{p{1.4cm}p{1.4cm}<{\centering}p{1.4cm}<{\centering}p{1.4cm}<{\centering}p{1.4cm}<{\centering}p{1.4cm}<{\centering}p{1.4cm}<{\centering}p{1.4cm}<{\centering}}
		\toprule
		& 样本数  & 异常比 & 平均值 & 中位数 & 最小值 & 最大值 & 均方差   \\
		\midrule
		训练集 & 2000 & 11.25 & 128.67 & 130.13 & 2.71 & 302.94 & 71.67  \\
		测试集	& 400 & 10.75 & 126.76 & 127.11 & 3.80 & 311.38 & 72.23  \\
		\bottomrule
	\end{tabular}
\end{table}

时间估计器的准确性会影响元件分配的搜索方向和最终解的质量。4种具有代表性的组装时间估计器用于和MFEE进行比较。本节所提出的组装时间估计器的准确度记为$E_1$，为说明提出的特征融合的有效性，具有相同结构的，以贴装点数、元件类型数、吸嘴数、电路板大小等基本参数为输入的神经网络的拟合准确度记为$E_2$。文献\inlinecite{guo_integrated_2012}和文献\inlinecite{toth_reconfiguring_2010}中提出的启发式估计器选取不同的特征对组装时间进行估计，其均采用线性拟合的方式进行估计，本节中以最小二乘法计算线性拟合的系数，组装时间估计的准确度分别记为$E_3$和$E_4$。在最新的研究中， 文献\inlinecite{li_predicting_2020}提出一种基于共生搜索的支持向量回归的集成学习算法，其时间估计准确度记为$E_5$。

表\ref{ch5:table:estimator-compare}列出了不同组装时间估计器在训练数据和测试数据的平均绝对误差和最大绝对误差。 组装时间估计器在测试数据上的表现可用于评价时间估计器的准确性。
可以看出，以神经网络为基础的组装时间估计器在准确度上更有优势，与输入基本参数的方法相比，所提出的MFEE方法将测试数据上获得的组装时间的平均绝对误差从 5.16\% 降低到 3.43\%。 基于启发式的线性回归拟合方法在预测效果上差于神经网络估计器，对估计特征的考虑不全面和自身结构的简单导致拟合结果不佳，平均绝对误差分别为 9.41\% 和 9.44\% 。 
基于共生生物搜索算法的支持向量回归算法尽管已经验证在组装车间生产线上对组装时间的预估结果更为准确，但由于其忽略了单个电路板的组装过程的特性，因此拟合精度最低。
需要指出，由于贴装点分布的随机性，本章提出的MFEE和用于对比的组装时间估计方法，在预测准确度上均存在误差。

\begin{table}[htbp]
	\centering
	\small
	\bicaption[ch5:table:estimator-compare]{}{多特征融合集成组装时间估计器和其他估计器的准确度比较}{Table $\!$}{\centering Comparison of the accuracy of the multifeature fusion ensemble assembly time estimator and other estimators}
	\begin{tabular}{p{1cm}<{\centering}p{5cm}<{\centering}p{1cm}<{\centering}p{1cm}<{\centering}p{1cm}<{\centering}p{1cm}<{\centering}p{1cm}<{\centering}}
		\toprule
		类别  & 参数 & $E_1$  & $E_2$ & $E_3$ & $E_4$ & $E_5$ \\
		\midrule
		\multirow{2}{*}{训练集} & 平均绝对误差 (\%) & 2.01 & 5.09 & 8.75 & 8.75 & 45.30 \\
		& 最大绝对误差 (\%) & 18.80 & 21.28 & 37.61 & 37.68 & 214.94 \\
		% Mean Square Error (\%) & & & & & \\
		\cmidrule(lr){1-7}
		\multirow{2}{*}{测试集} &平均绝对误差 (\%) & 3.43 & 5.16 & 9.41 & 9.44 & 45.99 \\
		& 最大绝对误差 (\%) & 16.57 & 18.65 & 27.65 & 28.82 & 183.98\\
		% Mean Square Error (\%) & & & &  &\\
		\bottomrule		
	\end{tabular}
\end{table}


\subsection{生产线元件分配算法的对比实验}[Comparative experiments on the line component allocation algorithms]

\subsubsection{同数学规划法比较}

数学规划法可以最优地求解小规模的组合优化问题，为说明本章提出的算法与理论最优值的差距，本节将其同第2章组装线负载平衡模型进行比较，该模型是通过提取影响表面组装过程效率的关键子目标建立的数学模型，建立模型的结果接近实际组装时间，模型的权重设定与第2章相同。在比较过程中，模型和所提出的算法均不计贴装点布局对装配效率的影响。表\ref{ch5:table:small-data-para}列出了用于比较的小规模电路板PCB数据组6，其元件类型数和对应点数均较少。模型和超启发式算法求解所得的加权性能指标分别记为$\mathcal{O}^{\rm{M}}$ 和 $\mathcal{O}^{\rm{H}}$ ，如表\ref{ch5:table:model-compare}所示。
同模型所得的最优解相比，超启发式负载平衡在3条生产线上同最优解的平均差距记为$\mathcal{G} = \left( \mathcal{O}^{\rm{H}} / \mathcal{O}^{\rm{M}} - 1 \right) \cdot 100 \% $，分别是7.28\% 、6.58\% 和 3.44\%。由此可见，超启发式算法在求解小规模数据时的性能接近模型求解的结果，而其更高的求解效率使得其可以应用于更大规模的组装数据的优化。

\begin{table}
	\centering	
	\small
	\bicaption[ch5:table:small-data-para]{}{小规模PCB组装生产线的数据参数}{Table $\!$}{Small-scale data parameters for PCB assembly lines}
	\begin{tabular}{p{3cm}<{\centering}p{1.5cm}<{\centering}p{1.5cm}<{\centering}p{1.5cm}<{\centering}p{1.5cm}<{\centering}p{1.5cm}<{\centering}}
	\toprule
	PCB & 6-1 & 6-2 & 6-3 & 6-4 & 6-5 \\
	\midrule
	元件类型数 & 4 & 4 & 5 & 5 & 5 \\
	吸嘴类型数 & 3 & 3 & 3 & 2 & 2\\
	贴装点数 & 28 & 34 & 34 & 30 & 30 \\
	可用供料器数 & 10 & 6 & 8 & 7 & 5 \\
	\bottomrule   
	\end{tabular}
\end{table}

\begin{table}
	\centering
	\small
	\bicaption[ch5:table:model-compare]{}{加权关键性能指标数学模型与超启发式负载平衡算法的比较}{Table $\!$}{\centering Comparison of weighted key metrics between mathematical model and hyper heuristic workload balancing algorithm}
	\begin{tabular}{p{1.6cm}<{\centering}p{0.9cm}<{\centering}p{0.9cm}<{\centering}p{1.2cm}<{\centering}p{0.9cm}<{\centering}p{0.9cm}<{\centering}p{1.2cm}<{\centering}p{0.9cm}<{\centering}p{0.9cm}<{\centering}p{1.2cm}<{\centering}}
		\toprule
		\multirow{2}{*}{生产线} & \multicolumn{3}{c}{\emph{L}1} & \multicolumn{3}{c}{\emph{L}2} & \multicolumn{3}{c}{\emph{L}3}  \\
		\cmidrule(lr){2-4} \cmidrule(lr){5-7} \cmidrule(lr){8-10}
		& $\mathcal{O}^{\rm{M}}$ &  $\mathcal{O}^{\rm{H}}$  & $\mathcal{G}$ (\%)  & $\mathcal{O}^{\rm{M}}$ &  $\mathcal{O}^{\rm{H}}$  & $\mathcal{G}$ (\%)  & $\mathcal{O}^{\rm{M}}$ &  $\mathcal{O}^{\rm{H}}$  & $\mathcal{G}$ (\%) \\
		\midrule
		6-1 & 2.585 & 2.626 & 1.59 & 1.758 & 1.837 & 4.49 & 1.676 & 1.813 & 8.17\\
		6-2 & 3.286 & 3.672 & 11.75 & 2.785 & 3.122 & 12.10 & 2.473 & 2.514 & 1.66 \\
		6-3 & 2.719 & 2.998 & 10.26 & 2.218 & 2.445 & 10.23 & 1.947 & 2.054 & 5.50
		\\
		6-4 &2.744 & 3.017 & 9.95 & 2.202 & 2.314 & 5.09 & 2.202 & 2.243 & 1.86
		\\
		6-5 & 2.933 & 3.017 & 2.86 & 2.432 & 2.456 & 0.99 & 2.432 & 2.432 & 0.00
		\\
		\midrule
		平均值 & & & 7.28 & & & 6.58 & & & 3.44  \\
		\bottomrule
	\end{tabular}
\end{table}



\subsubsection{同其它元件分配算法比较}

 生产线负载平衡的任务是将元件分配到生产线的贴片机中，以实现其中生产瓶颈的贴片机组装时间最小化的目标。
 本节将比较提出的HHALO和主流研究在实际生产中的表现，表\ref{ch5:table:large-pcb-data}列出了用于比较的大规模PCB数据组7的基本参数，用于对比的元件分配算法包括集成选择式分配启发式（Integrated Selective Allocation Heuristic，ISAH）算法， 混合重构式产线优化（Hybrid Reconfiguration Assembly Line Optimization，HRALO）算法以及组装线负载平衡求解器（Assembly Line Workload Balancing Solver，ALWBS）。
其中，ALWBS是某贴片机生产制造商于2022年发布的内置于生产线管理软件的负载平衡优化器；
HRALO算法以T\'{o}th等\cite{toth_reconfiguring_2010}提出的混合优化算法为基本框架，进一步结合了Mumtaz等\cite{mumtaz_hybrid_2020, zhong_multi-objective_2022}提出的PCB组装线优化中的混合蜘蛛猴算法的编码规则与搜索方式；
Guo 等\cite{guo_integrated_2012}提出的ISAH则是适用于表面组装生产线的基于进化的改进方法，其通过设计启发式算子搜索解的可行域，为 PCB 组装线优化提供实用有效的解决方案。HHALO、ALWBS和ISAH均提供了元件可重复分配的解决方案，HRALO则未给出解决方案，因此在对比实验中采用了\ref{duplicate-allocation-section}节所提出的分组策略。在贴片机组装过程优化方面，ALWBS通过内置程序优化表面组装过程，其余方法则采用第3--4章提出的表面组装过程优化方法。

 
 \begin{table}[H]
	\centering	
	\small
	\bicaption[ch5:table:large-pcb-data]{}{大规模PCB组装生产线的数据参数}{Table $\!$}{Large-scale data parameters for PCB assembly lines}
	\begin{tabular}{p{2.5cm}<{\centering}p{0.75cm}<{\centering}p{0.75cm}<{\centering}p{0.75cm}<{\centering}p{0.75cm}<{\centering}p{0.75cm}<{\centering}p{0.75cm}<{\centering}p{0.75cm}<{\centering}p{0.75cm}<{\centering}p{0.75cm}<{\centering}p{0.8cm}<{\centering}}
	\toprule
	PCB & 7-1 & 7-2 & 7-3 & 7-4 & 7-5 & 7-6 & 7-7 & 7-8 & 7-9 & 7-10 \\
	\midrule
	元件类型数 & 16 & 29 & 7 & 24 & 45 & 7 & 47 & 40 & 10 & 40\\
	吸嘴类型数 & 3 & 3 & 3 & 3 & 4 & 4 & 4 & 2 & 3 & 4 \\
	贴装点数 & 78 & 165 & 192 & 236 & 209 & 320 & 390 & 546 & 720 & 1510 \\
	可用供料器数 & 19 & 30 & 12 & 28 & 47 & 14 & 54 & 50 & 19 & 40\\
	\bottomrule   
	\end{tabular}
 \end{table}

 HHALO在不同的生产线配置上均取得的有益的效果，记其组装时间为$\mathcal{T}^{\rm{HHALO}}$，对比方法ALWBS、HRALO和ISAH的组装时间分别被记为$\mathcal{T}^{\rm{ALWBS}}$，$\mathcal{T}^{\rm{HRALO}}$和$\mathcal{T}^{\rm{ISAH}}$，表\ref{ch5:table:assembly-compare}列出了上述4种算法在不同组装生产线上的大规模电路板数据的负载平衡优化所得的装配时间，相较于此三种算法，本章所提出的HHALO算法适用于不同生产配置的并列式贴片机组装生产线，在组装效率上分别提高了 7.21\%，8.67\% 和 9.47\%。
随着生产线装配的贴片机数量的增加，负载分配的可行解空间也随之增加，而HHALO算法在搜索高质量的解的方面也更具优势。
由表可知，HHALO和同类型的工业软件中的ALWBS有着相近的表现，虽然存在少量数据的HHALO的解不如ALWBS，但HHALO整体上平均组装效率更优。
ISAH和HRALO均是基于进化算法的搜索框架，而其算子的设计相对简单，对并列式贴片机组装效率的影响因素考虑不足，加之对搜索到的解的时间评估也不准确，因而整体组装时间较长。

\begin{table}[!hb]
	\centering
	\small
	% \caption{超启发式组装线优化器与主流算法的装配时间比较}{Table~\ref{ch5:table:assembly-compare} Comparison of assembly time between the hyper-heuristic assembly line optimizer and mainstream algorithms}\label{ch5:table:assembly-compare}
	% ==========================================================
	\bicaption[ch5:table:assembly-compare]{}{超启发式组装线优化器与主流算法的装配时间比较}{Table $\!$}{\centering Comparison of assembly time between the hyper-heuristic assembly line optimizer and mainstream algorithms}
	\begin{tabular}{p{0.6cm}<{\centering}p{1cm}<{\centering}
		p{1.8cm}<{\centering}
		p{1.2cm}<{\centering}p{1.3cm}<{\centering}
		p{1.2cm}<{\centering}p{1.3cm}<{\centering}
		p{1.2cm}<{\centering}p{1.3cm}<{\centering}
	}
	\toprule 
	\multirow{2}{*}{PCB}& \multirow{2}{*}{产线} & HHALO & \multicolumn{2}{c}{ALWBS} & \multicolumn{2}{c}{ISAH} & \multicolumn{2}{c}{HRALO} \\ 
	\cmidrule(lr){3-3} \cmidrule(lr){4-5} \cmidrule(lr){6-7} \cmidrule(lr){8-9}
	&  & \makecell[c]{$\mathcal{T}^{\rm{HHALO}}$ \\ (s)} & \makecell[c]{$\mathcal{T}^{\rm{ALWBS}}$ \\ (s)} & $\mathcal{G}\left(\%\right)$ & \makecell[c]{$\mathcal{T}^{\rm{ISAH}}$ \\ (s)} & $\mathcal{G}\left(\%\right)$ & \makecell[c]{$\mathcal{T}^{\rm{HRALO}}$ \\ (s)} & $\mathcal{G}\left(\%\right)$ \\
	\midrule
	& \emph{L}1 & 10.14 	& 	12.91 	& 	27.36 	& 	10.91 	& 	7.57 	& 	14.97 	& 	47.62 \\
	7-1 & \emph{L}2 &	8.06 	& 	8.41 	& 	4.34 	& 	9.42 	& 	16.87 	& 	8.41 	& 	4.34 \\
	& \emph{L}3 & 6.21 	& 	6.56 	& 	5.68 	& 	7.17 	& 	15.39 	& 	6.83 	& 	10.03  \\
	\cmidrule(lr){1-9}
	& \emph{L}1 & 19.55 	& 	20.78 	& 	6.27 	& 	19.89 	& 	1.74 	& 	20.61 	& 	5.40 \\
	7-2 & \emph{L}2 & 14.28 	& 	14.75 	& 	3.29 	& 	14.93 	& 	4.57 	& 	14.75 	& 	3.29 \\
	& \emph{L}3 & 11.61 	& 	12.95 	& 	11.48 	& 	12.42 	& 	6.95 	& 	12.35 	& 	6.35 \\
	\cmidrule(lr){1-9}
	& \emph{L}1 & 21.15 	& 	21.19 	& 	0.17 	& 	23.39 	& 	10.57 	& 	23.18 	& 	9.59 \\
	7-3 & \emph{L}2 & 18.06 	& 	18.77 	& 	3.90 	& 	18.26 	& 	1.07 	& 	18.77 	& 	3.90 \\
	& \emph{L}3 & 12.59 	& 	14.44 	& 	14.72 	& 	14.92 	& 	18.54 	& 	14.72 	& 	16.93 \\
	\cmidrule(lr){1-9}
	& \emph{L}1 & 26.10 	& 	26.29 	& 	0.71 	& 	28.14 	& 	7.83 	& 	29.37 	& 	12.54 \\
	7-4 & \emph{L}2 & 17.85 	& 	18.66 	& 	4.50 	& 	19.17 	& 	7.40 	& 	18.66 	& 	4.50 \\
	& \emph{L}3 & 13.87 	& 	13.96 	& 	0.62 	& 	14.38 	& 	3.66 	& 	14.86 	& 	7.13 \\
	\cmidrule(lr){1-9}
	& \emph{L}1 & 27.86 	& 	32.32 	& 	16.03 	& 	33.48 	& 	20.18 	& 	32.57 	& 	16.93 \\
	7-5 & \emph{L}2 & 19.33 	& 	19.59 	& 	1.33 	& 	21.29 	& 	10.14 	& 	19.59 	& 	1.33 \\
	& \emph{L}3 & 15.35 	& 	15.79 	& 	2.88 	& 	16.89 	& 	10.05 	& 	16.66 	& 	8.58 \\
	\cmidrule(lr){1-9}
	& \emph{L}1 & 38.63 	& 	44.42 	& 	14.97 	& 	39.11 	& 	1.24 	& 	45.05 	& 	16.62 \\
	7-6 & \emph{L}2 & 26.53 	& 	27.91 	& 	5.22 	& 	27.34 	& 	3.07 	& 	27.91 	& 	5.22 \\
	& \emph{L}3 & 22.83 	& 	23.02 	& 	0.80 	& 	22.44 	& 	-1.72 	& 	24.22 	& 	6.08 \\
	\cmidrule(lr){1-9}
	& \emph{L}1 & 50.15 	& 	53.91 	& 	7.49 	& 	58.73 	& 	17.12 	& 	57.76 	& 	15.19 \\
	7-7 & \emph{L}2 & 34.12 	& 	36.93 	& 	8.25 	& 	40.79 	& 	19.55 	& 	36.93 	& 	8.25 \\
	& \emph{L}3 & 26.23 	& 	26.85 	& 	2.36 	& 	29.72 	& 	13.30 	& 	31.32 	& 	19.40 \\
	\cmidrule(lr){1-9}
	& \emph{L}1 & 71.32 	& 	73.96 	& 	3.69 	& 	72.02 	& 	0.97 	& 	75.09 	& 	5.28 \\
	7-8 & \emph{L}2 & 48.08 	& 	51.16 	& 	6.40 	& 	51.91 	& 	7.96 	& 	51.16 	& 	6.40 \\
	& \emph{L}3 & 39.42 	& 	40.18 	& 	1.92 	& 	40.28 	& 	2.18 	& 	42.76 	& 	8.47 \\
	\cmidrule(lr){1-9}
	& \emph{L}1 & 85.69 	& 	91.18 	& 	6.41 	& 	94.66 	& 	10.47 	& 	91.95 	& 	7.31 \\
	7-9 & \emph{L}2 & 60.91 	& 	63.91 	& 	4.93 	& 	66.08 	& 	8.48 	& 	63.91 	& 	4.93 \\
	& \emph{L}3 & 46.07 	& 	52.57 	& 	14.09 	& 	53.05 	& 	15.14 	& 	47.10 	& 	2.23 \\
	\cmidrule(lr){1-9}
	\multirow{3}{*}{7-10} & \emph{L}1 & 176.99 	& 	179.94 	& 	1.67 	& 	185.07 	& 	4.56 	& 	188.01 	& 	6.23 \\
	& \emph{L}2 & 117.93 	& 	125.79 	& 	6.66 	& 	128.07 	& 	8.59 	& 	125.79 	& 	6.66 \\
	& \emph{L}3 & 90.78 	& 	116.23 	& 	28.04 	& 	96.73 	& 	6.56 	& 	97.54 	& 	7.44 \\
	\midrule
	AVG & & & & 7.21 &  & 8.67 &  & 9.47 \\
	
	\bottomrule
	\end{tabular}
% 	% ==========================================================
\end{table}
% \vspace{-1.5em}
% \begin{longtable}{p{0.6cm}<{\centering}p{1cm}<{\centering}
% 		p{1.8cm}<{\centering}
% 		p{1.2cm}<{\centering}p{1.3cm}<{\centering}
% 		p{1.2cm}<{\centering}p{1.3cm}<{\centering}
% 		p{1.2cm}<{\centering}p{1.3cm}<{\centering}
% 	}
		
% 		\toprule 
% 		\multirow{2}{*}{PCB}& \multirow{2}{*}{产线} & HHALO & \multicolumn{2}{c}{ALWBS} & \multicolumn{2}{c}{HRALO} & \multicolumn{2}{c}{ISAH} \\ 
% 		\cmidrule(lr){3-3} \cmidrule(lr){4-5} \cmidrule(lr){6-7} \cmidrule(lr){8-9}
% 		&  & \makecell[c]{$\mathcal{T}^{\rm{HHALO}}$ \\ (s)} & \makecell[c]{$\mathcal{T}^{\rm{ALWBS}}$ \\ (s)} & $\mathcal{G}\left(\%\right)$ & \makecell[c]{$\mathcal{T}^{\rm{ISAH}}$ \\ (s)} & $\mathcal{G}\left(\%\right)$ & \makecell[c]{$\mathcal{T}^{\rm{HRALO}}$ \\ (s)} & $\mathcal{G}\left(\%\right)$ \\
% 		\midrule  
% 		\endfirsthead
% 		\multicolumn{9}{r}{续表\autoref{ch5:table:assembly-compare}}\\
% 		\multicolumn{9}{c}{(接上页)}\\
% 		\toprule
% 		\multirow{2}{*}{PCB}& \multirow{2}{*}{产线} & HHALO & \multicolumn{2}{c}{ALWBS} & \multicolumn{2}{c}{HRALO} & \multicolumn{2}{c}{ISAH} \\ 
% 		\cmidrule(lr){3-3} \cmidrule(lr){4-5} \cmidrule(lr){6-7} \cmidrule(lr){8-9}
% 		&  & \makecell[c]{$\mathcal{T}^{\rm{HHALO}}$ \\ (s)} & \makecell[c]{$\mathcal{T}^{\rm{ALWBS}}$ \\ (s)} & $\mathcal{G}\left(\%\right)$ & \makecell[c]{$\mathcal{T}^{\rm{HRALO}}$ \\ (s)} & $\mathcal{G}\left(\%\right)$ & \makecell[c]{$\mathcal{T}^{\rm{ISAH}}$ \\ (s)} & $\mathcal{G}\left(\%\right)$ \\
% 		\midrule
% 		\endhead
% 		\bottomrule
% 		\multicolumn{9}{c}{(接下页)}
% 		\endfoot
% 		\bottomrule
% 		\endlastfoot
% 		& \emph{L}1 & 10.14 	& 	12.91 	& 	27.36 	& 	10.91 	& 	7.57 	& 	14.97 	& 	47.62 \\
% 		7-1 & \emph{L}2 &	8.06 	& 	8.41 	& 	4.34 	& 	9.42 	& 	16.87 	& 	8.41 	& 	4.34 \\
% 		& \emph{L}3 & 6.21 	& 	6.56 	& 	5.68 	& 	7.17 	& 	15.39 	& 	6.83 	& 	10.03  \\
% 		\cmidrule(lr){1-9}
% 		& \emph{L}1 & 19.55 	& 	20.78 	& 	6.27 	& 	19.89 	& 	1.74 	& 	20.61 	& 	5.40 \\
% 		7-2 & \emph{L}2 & 14.28 	& 	14.75 	& 	3.29 	& 	14.93 	& 	4.57 	& 	14.75 	& 	3.29 \\
% 		& \emph{L}3 & 11.61 	& 	12.95 	& 	11.48 	& 	12.42 	& 	6.95 	& 	12.35 	& 	6.35 \\
% 		\cmidrule(lr){1-9}
% 		& \emph{L}1 & 21.15 	& 	21.19 	& 	0.17 	& 	23.39 	& 	10.57 	& 	23.18 	& 	9.59 \\
% 		7-3 & \emph{L}2 & 18.06 	& 	18.77 	& 	3.90 	& 	18.26 	& 	1.07 	& 	18.77 	& 	3.90 \\
% 		& \emph{L}3 & 12.59 	& 	14.44 	& 	14.72 	& 	14.92 	& 	18.54 	& 	14.72 	& 	16.93 \\
% 		\cmidrule(lr){1-9}
% 		& \emph{L}1 & 26.10 	& 	26.29 	& 	0.71 	& 	28.14 	& 	7.83 	& 	29.37 	& 	12.54 \\
% 		7-4 & \emph{L}2 & 17.85 	& 	18.66 	& 	4.50 	& 	19.17 	& 	7.40 	& 	18.66 	& 	4.50 \\
% 		& \emph{L}3 & 13.87 	& 	13.96 	& 	0.62 	& 	14.38 	& 	3.66 	& 	14.86 	& 	7.13 \\
% 		\cmidrule(lr){1-9}
% 		& \emph{L}1 & 27.86 	& 	32.32 	& 	16.03 	& 	33.48 	& 	20.18 	& 	32.57 	& 	16.93 \\
% 		7-5 & \emph{L}2 & 19.33 	& 	19.59 	& 	1.33 	& 	21.29 	& 	10.14 	& 	19.59 	& 	1.33 \\
% 		& \emph{L}3 & 15.35 	& 	15.79 	& 	2.88 	& 	16.89 	& 	10.05 	& 	16.66 	& 	8.58 \\
% 		\cmidrule(lr){1-9}
% 		& \emph{L}1 & 38.63 	& 	44.42 	& 	14.97 	& 	39.11 	& 	1.24 	& 	45.05 	& 	16.62 \\
% 		7-6 & \emph{L}2 & 26.53 	& 	27.91 	& 	5.22 	& 	27.34 	& 	3.07 	& 	27.91 	& 	5.22 \\
% 		& \emph{L}3 & 22.83 	& 	23.02 	& 	0.80 	& 	22.44 	& 	-1.72 	& 	24.22 	& 	6.08 \\
% 		\cmidrule(lr){1-9}
% 		& \emph{L}1 & 50.15 	& 	53.91 	& 	7.49 	& 	58.73 	& 	17.12 	& 	57.76 	& 	15.19 \\
% 		7-7 & \emph{L}2 & 34.12 	& 	36.93 	& 	8.25 	& 	40.79 	& 	19.55 	& 	36.93 	& 	8.25 \\
% 		& \emph{L}3 & 26.23 	& 	26.85 	& 	2.36 	& 	29.72 	& 	13.30 	& 	31.32 	& 	19.40 \\
% 		\cmidrule(lr){1-9}
% 		& \emph{L}1 & 71.32 	& 	73.96 	& 	3.69 	& 	72.02 	& 	0.97 	& 	75.09 	& 	5.28 \\
% 		7-8 & \emph{L}2 & 48.08 	& 	51.16 	& 	6.40 	& 	51.91 	& 	7.96 	& 	51.16 	& 	6.40 \\
% 		& \emph{L}3 & 39.42 	& 	40.18 	& 	1.92 	& 	40.28 	& 	2.18 	& 	42.76 	& 	8.47 \\
% 		\cmidrule(lr){1-9}
% 		& \emph{L}1 & 85.69 	& 	91.18 	& 	6.41 	& 	94.66 	& 	10.47 	& 	91.95 	& 	7.31 \\
% 		7-9 & \emph{L}2 & 60.91 	& 	63.91 	& 	4.93 	& 	66.08 	& 	8.48 	& 	63.91 	& 	4.93 \\
% 		& \emph{L}3 & 46.07 	& 	52.57 	& 	14.09 	& 	53.05 	& 	15.14 	& 	47.10 	& 	2.23 \\
% 		\cmidrule(lr){1-9}
% 		\multirow{3}{*}{7-10} & \emph{L}1 & 176.99 	& 	179.94 	& 	1.67 	& 	185.07 	& 	4.56 	& 	188.01 	& 	6.23 \\
% 		& \emph{L}2 & 117.93 	& 	125.79 	& 	6.66 	& 	128.07 	& 	8.59 	& 	125.79 	& 	6.66 \\
% 		& \emph{L}3 & 90.78 	& 	116.23 	& 	28.04 	& 	96.73 	& 	6.56 	& 	97.54 	& 	7.44 \\
% 		\midrule
% 		AVG & & & & 7.21 &  & 8.67 &  & 9.47
% \end{longtable}





\begin{figure}
	\centering
	\begin{minipage}{0.48\linewidth}
		\vspace{2pt}
		\centerline{\includegraphics[width=\textwidth]{chapter5/assembly-efficiency-L01.eps}}
		\centerline{\emph{L}1}
	\end{minipage}
	\begin{minipage}{0.48\linewidth}
		\vspace{2pt}
		\centerline{\includegraphics[width=\textwidth]{chapter5/assembly-efficiency-L02.eps}}
		\centerline{\emph{L}2}
	\end{minipage}
	\begin{minipage}{0.48\linewidth}
		\vspace{2pt}
		\centerline{\includegraphics[width=\textwidth]{chapter5/assembly-efficiency-L03.eps}}
		\centerline{\emph{L}3}
	\end{minipage}
	\vspace{3pt}
	\bicaption[ch5:figure:assmebly-boxplot]{}{不同方法的装配效率优化结果在三条印刷电路板装配线上的分布比较}{Fig. $\!$}{\centering Comparison of the distribution of assembly efficiency optimization results of different methods on three PCB assembly lines}
\end{figure}

此外，图\ref{ch5:figure:assmebly-boxplot}比较了不同优化算法在3条表面组装生产线上优化得到的装配时间的数据分配情况。在包含随机搜索算子的优化算法中，HHALO算法解的分布更为集中，且整体优于其他两种组装优化算法。
ISAH和HRALO作为基于进化搜索的优化算法，搜索过程中的随机算子扩大了算法的搜索范围，但也导致解的分布方差较大、输出的结果不稳定。
虽然ISAH部分解的质量优于HRALO的解，但ISAH的优化结果不稳定使其平均表现最差。
ALWBS作为工业优化求解方法，其内部采用了确定性的启发式优化方法，解的整体质量优于ISAH和HRALO，但不如本章提出的HHALO优化算法。
在多数情况下，HHALO算法单次运行得到的优化结果优于其他方法，即使单次运行存在质量相对较差的解，其与其他方法最优解的差距也相对较小。

\subsection{运行效率分析}[Analysis of solving efficiency]

求解效率是衡量算法性能的重要指标之一，特别是对于大规模组合优化问题，高效的求解效率有助于算法的部署推广。表\ref{ch5:table:solving-compare}比较了HHALO，ISAH和HRALO算法的求解时间，由于ALWBS未开源具体的实现方式，因此不在比较之列。由表可知，HRALO具有最高的求解效率，但其选用了相对简单的搜索方式，以较低的时间估计准确度为代价快速搜索。HHALO和ISAH均采用了更为复杂的时间预估方式，且在搜索过程中融入了更为多样的搜索算子，能实现对解空间更充分的搜索，获得解的质量更高，搜索时间在可接受的范围内。相比较而言，本章所提出的HHALO比ISAH搜索效率更高、解决方案的质量更好。此外，HHALO在评估候选解时调用表面组装过程优化算法造成了求解时间的增加，通过缩短单台贴片机的搜索时间或提升组装时间估计器的准确度，将有助于进一步提升算法的求解效率。

\begin{table}[ht]
	\centering
	\small
	\bicaption[ch5:table:solving-compare]{}{超启发式表面组装线优化算法与其他主流算法的求解时间比较}{Table $\!$}{\centering Comparison of solving times between hyper-heuristic surface assembly line optimization algorithms and other mainstream algorithms}
	\begin{tabular}{p{1.2cm}<{\centering}p{1cm}<{\centering}p{1cm}<{\centering}p{1cm}<{\centering}<{\centering}p{1cm}<{\centering}p{1.2cm}<{\centering}p{1cm}<{\centering}p{1cm}<{\centering}p{1cm}<{\centering}p{1cm}<{\centering}}
		\toprule
		& \multicolumn{3}{c}{HHALO} &  \multicolumn{3}{c}{HRALO} & \multicolumn{3}{c}{ISAH} \\
		\cmidrule(lr){2-4} \cmidrule(lr){5-7} \cmidrule(lr){8-10}
		PCB & \emph{L}1 (s) & \emph{L}2 (s) & \emph{L}3 (s) & \emph{L}1 (s) & \emph{L}2 (s) & \emph{L}3 (s) & \emph{L}1 (s) & \emph{L}2 (s) & \emph{L}3 (s) \\
		\midrule
		7-1 & 17.28  & 20.95  & 24.26  & 15.84  & 18.97  & 21.69  & 54.13  & 59.35  & 62.99  \\
		7-2 & 33.98  & 31.35  & 30.71  & 63.45  & 63.70  & 68.54  & 64.05  & 68.51  & 75.21  \\
		7-3 & 13.98  & 15.62  & 19.64  & 26.56  & 32.01  & 37.27  & 50.74  & 54.99  & 63.95  \\
		7-4 & 21.51  & 23.73  & 26.20  & 9.31  & 11.08  & 12.26  & 64.05  & 68.17  & 76.23  \\
		7-5 & 100.22  & 81.51  & 87.45  & 23.49  & 28.06  & 32.57  & 85.59  & 90.02  & 96.65  \\
		7-6 & 21.32  & 18.32  & 21.74  & 49.13  & 56.61  & 65.24  & 63.57  & 67.34  & 73.92  \\
		7-7 & 93.22  & 70.93  & 68.72  & 12.80  & 14.17  & 16.01  & 100.31  & 96.79  & 104.06  \\
		7-8 & 40.19  & 42.99  & 38.08  & 55.18  & 59.92  & 65.67  & 91.20  & 95.64  & 104.69  \\
		7-9 & 29.20  & 27.52  & 30.12  & 40.48  & 48.99  & 55.56  & 89.30  & 92.85  & 101.16  \\
		7-10 & 135.98  & 76.67  & 76.71  & 25.48  & 24.94  & 24.90  & 144.55  & 155.60  & 171.15 \\
		
		\bottomrule	
	\end{tabular}
\end{table}




\section{本章小结}[Summary of this chapter]

本章提出了基于多特征融合集成组装时间估计器的超启发式表面组装生产线负载平衡算法，将估计器的的高准确度与超启发式的大邻域搜索能力相结合，提供了高质量的解决方案。
本章分析了生产线的工作特性，设计了以进化算法为基本框架的超启发式负载平衡算法，通过多种群迭代增加搜索多样性，提出了数据驱动和目标驱动的元件分配底层启发式，并在分配过程中结合了组装优先级、可用组装工具等约束。对于元件可重复分配的情形，元件分组策略用于确定底层算子操作的基本对象，聚合聚类启发式用于确定贴装点分配的贴片机。估计器以集成学习为框架、以神经网络为基模型，在编码中融合了启发式估计的子目标等多维特征，用于估计组装时间。实验结果表明，本章提出的估计器的结果准确度更高，超启发式分配算法在处理小规模数据时与模型获得的最优解的质量接近；与其他主流研究相比，算法能在可接受的求解时间内获得装配效率更高和更为稳定的结果。