基于改进双种群遗传算法的装配线平衡优化研究

欧阳飞羽 王 巍

（东北林业大学机电工程学院，黑龙江 哈尔滨 150040）

装配线平衡优化问题是指在装配线上的工作站间合理分配任务，最大程度地提高生产效率和资源利用率[1]。但随着产品不断创新，装配线的复杂程度也不断提高，引起了学者们的广泛关注。为解决装配线平衡问题，常用的方法包括数学求解法、工业工程方法和智能算法等。在智能算法中，最常见的是启发式算法。

田广东等人以提高拆卸效率为目标，提出一种社会工程算法，结果表明该算法能有效优化拆解线平衡率[2]。李明等人通过改进遗传算法对多目标的装配线平衡问题进行求解，不仅考虑产线平衡率，还对平衡指数和生产节拍进行寻优[3]。

启发式算法虽然能对装配线平衡问题进行求解，但其运算速度较慢，求解过程中容易陷入某一个虚假的最优解中，导致结果并不理想。

基于此，该文对传统的单种群遗传算法进行改进，扩展单一种群成为双种群遗传算法，并在此基础上引入自适应算子改进遗传算法中的交叉过程，避免遗传算法在解决装配线平衡问题时无法精确寻优，以期能更好地解决实际问题。

1 问题描述与模型构建

可以根据不同的评价指标评估装配线平衡状况，并根据评估结果决定是否进行改善，针对不同的生产需求，选择的评估指标也不同[4]。

生产平衡率为实际生产时间与总可用时间的比率，表示任务在各工作站间的分配效率。生产平衡率越高，说明资源分配越有效，闲置时间越少，生产率越高，如公式（1）所示。

式中：P为生产平衡率；ti为完成每道工序所需要的标准时间；q为工作站的个数；CT为节拍时间，是每个工作站完成一个单位产品需要的最长时间。减少节拍时间，能最大限度地减少瓶颈，提高生产平衡率。

生产平衡率可以反映装配线的平衡状态。当生产平衡率低于60%时，说明整条装配线均未采用科学管理的生产方式，必须进行改进。当生产平衡率在60%～80%时，说明整条装配线采用了一定的科学管理方式，但平衡状态并不好。当生产平衡率在80%～90%时，整条产线的平衡状态已经有很大的改善，当生产平衡率大于90%时，说明装配线的平衡状态较好，能以最高的生产效率完成生产。

平滑指数可以量化不同工作站间周期时间的差异，通过工作站间工作时间的差异程度衡量平衡性。平滑指数越小，说明装配线越平衡；平滑指数越大说明装配线不平衡，工作站间的工作负载不均衡。

平滑指数能帮助识别装配线上的瓶颈工作站或不平衡因素，从而引导制定优化策略；通过调整工作任务分配，使平滑指数变小，可以让工作站间负载均衡，提高生产效率和质量稳定性。通过监控和调整平滑指数可以促进装配线的可持续发展，减少资源浪费，提高生产系统的整体效益。计算平滑指数如公式（2）所示。

式中：q为工作站数目；Ti为完成每个工作站内所有工序需要的标准时间；CT为节拍时间。

生产平衡率P为问题模型中对生产效率进行评估的指标，平滑指数SI用于评估负荷状态。为最大化生产平衡率且不损失生产效率，保证各作业工作站间生产负荷均衡，该文将生产平衡率和平滑指数2 个指标相结合，提出多目标的装配线平衡问题模型。该模型的目标函数如公式（3）所示。

式中：P0为未改进前的生产平衡率；SI0为未改进前的平滑指数。

通过多目标的装配线平衡问题模型，可以兼顾装配线的平衡状态和各工位的作业负荷，提高生产率。

2 描述双种群遗传算法

2.1 遗传算法改进策略

遗传算法是一种基于生物进化思想的优化算法，通过模拟自然选择、交叉和变异等操作搜索最优解。最早由John Holland 于1975 年提出，后来经过研究者们改进和扩展，成为一种强大的全局优化工具。

遗传算法的优点是不仅可以处理高维复杂问题，还可以并行计算，加速求解过程。然而，遗传算法也有缺点，其算法的性能高度依赖参数设置和编码方式，因此可能会陷入局部最优解，无法保证找到全局最优解[5]。

为改进遗传算法，研究者们提出许多改进策略。其中，双种群遗传算法是一种基于遗传算法的改进版本，引入2个种群，分别用于全局搜索和局部搜索，同时兼顾全局和局部搜索的能力，有效地平衡了搜索的广度和深度。由于双种群遗传算法在2 个并行的种群间进行交叉、突变和选择操作，因此可以更好地保持种群多样性，从而提高全局搜索能力，同时在2 个种群中搜索最优解，很大程度提高了计算效率。双种群遗传算法使用了2 个并行的种群，即使其中一个种群出现问题（例如丧失多样性），另一个种群也可以继续搜索。

双种群遗传算法通过引入双种群结构和相应的搜索策略，利用一种有效的方式改进标准的遗传算法，可以处理复杂、非线性、离散以及含有许多局部最优解的问题。

该文采用双种群遗传算法求解装配线平衡问题，同时在交叉和变异环节引入自适应算子，进一步对双种群遗传算法进行优化，更好地求解线平衡问题。

2.2 双种群遗传算法改进策略

为在搜索过程中更好地适应问题空间的特性，该文在双种群遗传算法的基础上引入了自适应算子，对遗传算法中的交叉和变异操作进行动态调整。

交叉是一种模拟生物繁殖的操作，通过从父母染色体中选取部分基因来产生新的后代。将自适应算子引入双种群遗传算法后，交叉概率不再固定，而是动态调整的，即自适应交叉率。自适应交叉率通常利用种群的平均适应度或最优个体的适应度。当种群的平均适应度较高时，可能需要降低交叉率保持当前的优解；反之，如果种群的平均适应度较低，可能就需要提高交叉率增加种群的多样性。

变异是通过随机改变染色体上的一个或多个基因产生新的解。引入自适应算子，变异率也会变成动态调整。自适应突变率通常利用种群的多样性。当种群有较高多样性时，可能需要降低突变率保证搜索的稳定性；反之，如果种群的多样性较低，可能需要提高突变率增加种群的多样性。

在遗传算法中，常用方法是基于种群的适应度值，引入自适应算子对交叉率和突变率进行动态更新[6]。关于染色体，该文采用公式（4）更新每个染色体的交叉率和突变率。

式中：ci为染色体的交叉率；cmin和cmax分别为交叉率的最小和最大允许值，一般来说为预先设定的常数，染色体变异率如公式（5）所示。

式中：mi为染色体的变异率；mmin和mmax分别为允许变异率动态调整的最小值和最大值，同样也是预先设定的常数。

公式（4）和公式（5）中的f1是染色体i的适应度值，用适应度函数直接计算得出；fmin和fmax分别为当前种群中的最小和最大适应度值。

高适应度值染色体为优秀解，为确保有效传递给后代，采用较低的交叉率和变异率，有助于保留优秀解，提高算法性能。相反，适应度较低的染色体可能需要更高的交叉率和变异率，增加多样性和搜索空间探索，提高发现更优解的概率。这样的策略平衡了保留优质解与探索搜索空间的需求，优化遗传算法的全局搜索性能。

同时，在问题求解初期，可以增加自适应算子的调节系数，以便能更好地提高算法的求解能力，在后期可以适当降低调节系数，增加收敛速度，提高算法的求解效率。

综上所述，引入自适应算子的遗传算法能更好地平衡搜索的全局性和局部性，从而提升搜索性能。

2.3 改进后的双种群遗传算法

双种群遗传算法是遗传算法的一种改进形式，设置2个并行的种群，在这2 个种群间进行交叉、突变和选择操作，提高搜索性能[8]。双种群遗传算法的具体运行过程如下：1）初始化。生成种群1 和种群2，对这2 个种群进行初始化，每个种群都由若干个染色体组成，这些染色体为可能的解决方案。该文采用顺序编码的方式，对装配线平衡问题进行种群初始化，将装配线的加工顺序初始化为种群中的染色体。2）适应度评估。计算2 个种群中的每个染色体对应的适应度值。适应度函数通常取决于特定的问题域，度量了一个染色体（或解决方案）的质量或优越性。该文采用复合的目标函数作为适应度值，如公式（3）所示。3）选择。根据染色体的适应度选择2 个种群中的染色体。该文采用轮盘赌作为选择策略，模拟自然界中适者生存的原则。在轮盘赌选择过程中，每个染色体被选中的概率与其适应度函数值成正比。计算染色体i被选中的概率Pi，如公式（6）所示。

式中：fi是染色体i的适应度值；∑fj是种群中所有染色体的适应度之和。

每个染色体占据的“轮盘”面积与其适应度值成正比。因此，适应度值较高的染色体有更大被选中的概率。该方式既能保证遗传优良基因，又能为低适应度的染色体提供生存机会，从而保证种群的多样性，避免算法过早陷入局部最优。4）交叉和变异。从2 个种群中选择的染色体经过交叉和变异操作生成新的染色体。该文引入自适应算子进行交叉和变异操作，更好地提升了算法的性能[9]。5）替换。在新一代中，使用新产生的染色体替换原来种群中一些适应度较低的染色体，达到不断优化种群的目的。6）迁移。在达到指定的迭代次数后，其中一个种群中适应度值最大的染色体会复制到另一个种群中，该群间染色体交换的过程被称为迁移。在种群1 中选取适应度值最高的染色体，染色体包括种群1 最好的基因信息，将选定的染色体从种群1 复制到种群2，使种群2 获得种群1 的优秀基因信息，同时，删除种群2 中适应度值最低的染色体，并计算种群2 中所有染色体的适应度值，更新种群状态。该文采用种群1、2 间的双向迁移，更好地促进种群间的基因信息交流，加快全局优化的进程。双种群遗传算法的迁移环节明显优于传统遗传算法，其目标是在2 个并行执行搜索过程的种群间进行基因信息的交流，以提高全局搜索能力，避免陷入局部最优的困局中。7）终止条件检查。如果满足终止条件，即达到最大迭代次数或找到满意解后，算法结束。否则，返回步骤2，并在新的种群重复上述过程。

改进后的双种群遗传算法流程如图1 所示。

图1 改进后双种群遗传算法流程图

3 装配线平衡优化验证

3.1 案例描述

装配线平衡优化问题的目标是使各工作站的负荷尽可能均衡，减少空闲时间和过载情况，从而提高整个装配线的生产效率[7]。通过改进双种群遗传算法对装配线问题进行求解，该文以某公司手机装配线为案例，验证改进后算法是否有效。

某公司手机装配线将现有的37 个作业任务分配在4 个工位中，通过作业标准时间研究，得到37 个工位的标准工作时间。某公司手机装配线的作业优先顺序关系如图2 所示。

图2 作业优先顺序关系图

根据作业优先关系顺序图，通过顺序编码的方式将各工序编码成为初始化种群，并通过改进后的双种群遗传算法进行求解。代入公式（1）和公式（2）可以计算得出，目前手机装配线的平衡率为388s，生产平衡率为68.81%，生产平滑指数为163.83。目前，生产平衡率在60%～70%，表示虽然该装配线现在具有一定的科学管理能力，但是装配线平衡状况不乐观，仍然需要进一步改进以达到产线平衡的状态。同时，生产平滑指数略高，表示目前产线中，4 个工作站间的作业负荷不均衡，容易对生产效率造成较大的负面影响。

3.2 案例求解

对某公司手机装配线进行分析，需要进一步优化产线平衡。该文采用改进后的双种群遗传算法对其进行优化，并与未改进的算法进行对比。所有试验均在Matlab 2021b中运行，每次试验独立运行30 次，结果见表1。

表1 改进后算法结果对比

由表1 可知，通过遗传算法对手机装配线进行平衡优化后，提升了生产平衡率。通过改进后的双种群遗传算法对装配线进行进一步优化，装配线的平衡率为92.86%，说明此时产线平衡状态较好，与传统的双种群遗传算法相比，改进后的算法更能提升生产平衡率。平滑指数下降说明装配线中各工作站间的工作负荷更均衡，与未改进的算法相比，改进后的双种群遗传算法使平滑指数下降更多。

因此，通过对某公司手机装配线平衡状况进行分析，验证改进后的双种群遗传算法能较好地解决装配线平衡问题，比未改进的算法性能更强。

4 结语

装配线平衡问题是生产过程中的重要问题，通过研究，能更好地提升产品的生产效率和创新能力。该文对装配线平衡问题进行分析，构建以产线平衡率和平滑指数为共同导向的问题模型，并通过改进双种群遗传算法，提高遗传算法的求解能力。通过对案例进行求解，与未改进的算法相比，改进后的双种群遗传算法能更好地解决装配线平衡问题。