基于混合算法的民机数字化装配生产计划研究

张 玮，李艳军 ，江天玥

(1.南京航空航天大学民航学院，江苏 南京 211100)(2.南京理工大学经济管理学院，江苏 南京 210094)

近年来，我国民机装配技术水平逐步提高[1]。现代飞机装配管控过程都具有周期长、不确定性高、组织协调难度大的特点[2]，而民机相较于军机装配过程更加复杂，数字化技术的进步带动了民机装配方式的进步。在优化方法方面，遗传算法具有良好的局部搜索寻优能力和较强的鲁棒性，但也有容易陷入局部最优的缺点；模拟退火算法以一定的概率接受较差值，从而跳出局部最优，但其效率低，对初值有较强的依赖性。目前针对民机装配现场调度问题的研究比较少，且多为单目标优化，针对民机装配现场管控的编码方式和染色体交叉变异方式不够完善。本文针对民机数字化装配现场管控的实际需求，将标准的遗传算法进行改进，并加入退火过程，设计出改进的遗传与模拟退火混合算法，并对多目标民机装配生产调度模型进行优化计算。

1 需求分析

民机数字化装配生产计划的制定需要考虑以下几个特点：多项目并行、多约束条件[3]、多调度目标[4]、高度离散性[5]。

2 模型建立

2.1 问题描述

2.2 约束条件

假设：1)不同的工件之间不存在紧前约束，同一工件的工序之间存在紧前约束；2)一架工装在同一时刻仅可装配一道工序；3)不可打断一道工序的装配；4)忽略工件在工装上的装卸时间；5)物料资源充足。约束条件量化如下：

Sjk+xijk×tijk≤Cjk,i=1,2,…,m;j=1,2,…,n;k=1,2,…,kj

(1)

Cjk≤Sj(k+1),j=1,2,…,n;k=1,2,…,kj-1

(2)

Cjk≤Cmax,j=1,2,…,n

(3)

Sjk+tjk≤Shl+W(1-yijkhl),i=1,2,…,m;j,h=1,2,…,n;k=1,2,…,kj;l=1,2,…,kh

(4)

rj≤Sijk≤dj-tijk,i=1,2,…,m;j=1,2,…,n;k=1,2,…,kj

(5)

2.3 目标函数

1)工装最大作业负荷f1最小,即：

(6)

2)最大完工时间f2最小,即：

(7)

对上述目标函数加权得到目标函数gx，即：

gx=w1f1+w2f2

(8)

式中：w1,w2>0,w1+w2=1。

3 混合算法的设计与实现

3.1 改进遗传算法

1)编码与解码。根据民机数字化装配现场的实际情况，采用双层编码方法。一层编码代表工序的排序，另一层编码代表选择的工装编号，且上下两层编码长度相等。编码方式如图1所示。

图1 编码图示

以某民机装配企业的生产现场为例，其装配作业时间表见表1。

表1 装配作业时间表

由此得到工装与工序的关联矩阵J0和时间矩阵T0：

(9)

(10)

解码过程是，按编码规则将基因转换为工序Ojk，根据J0和T0求出该工序对应的工装和装配时长，按模型约束条件规则将工序工装组合排序，形成生产计划。

2)适应度函数设计。本文选择下界构造法[7]构造适应度函数，适应度函数Fit(x)为：

(11)

式中：c为目标函数界限保守估计值。

3)改进交叉算子。工序之间存在工艺约束，为保证交叉后种群不出现非法个体以及计算过程的可控性，交叉方式如下：随机选择第n个工件，保持该工件所有工序的基因不变，其他工序的基因按顺序交叉。例如：随机产生一个不大于工装总数的整数，假设是1，工件1的所有工序基因保留，工件2和3的工序基因依次交换，得到子代染色体，如图2所示。由于工序和工装存在对应关系，为保证工装交叉后不出现非法解，工装交叉操作跟随工序交叉同时进行。

图2 工序染色体交叉操作示例

4)改进变异算子。根据编码解码规则，为避免种群中存在大量重复个体，工序变异时选取一个基因，将其插入该基因位置与前一个相同编码之间的任意位置，后移其他基因。例如：随机生成一个不大于染色体长度的整数5，父代基因位置5代表工序O22，将其变异到O21后面的任意位置3，得到子代染色体，如图3所示。

图3 工序染色体变异操作示例

工装染色体变异采取单点变异方式，在该道工序可选择的其他工装里随机选取一个替换。例如：随机生成一个不大于染色体长度的整数2，染色体上第二位的基因为1，即工装M1，该工序可选择的工装有[M1,M2,M3]，随机选择除M1外的工装，例如M2，则该位基因变为2。变异过程如图4所示。

图4 工装染色体变异操作示例

5)改进选择算子。将比例选择与最佳个体保留结合，形成复合种群选择方法，具体方法是：在0～1之间产生一个随机数random，即若状态a满足：

(12)

则选择状态a进行复制。式中：sizepop为种群大小，fb为个体的适应度值。

3.2 改进的遗传与模拟退火混合算法(GASA)设计

与遗传算法寻优的方式不同，模拟退火算法根据Metorpolis接受准则[8]在计算过程中以概率P接受比较差的解，可使计算过程跳出局部收敛，实现全局寻优。Metorpolis接受准则：状态从A变为B时，对应的系统能量由Fit(A)变为Fit(B)，此时系统从A到B能够接受的概率P为：

(13)

混合算法流程：1)设置初始参数。2)编码，确定目标函数。3)生成初始种群，计算个体适应度Fit。4)初始化遗传迭代计数变量z=0。5)进行初始种群的交叉、变异、选择操作，产生新种群，并计算新种群中每个个体适应度Fit'。6)计算新个体与父代个体的适应度差值ΔE=Fit'-Fit，若ΔE≥0，则接受新个体，淘汰父代个体，若ΔE<0，则以概率P接受新个体。7)判断z是否达到最大迭代次数，若是则转到步骤8；否则令z=z+1，并转向4)。8)判断是否满足算法终止条件，即当前温度Tk是否小于终止温度Tend，若是则终止算法得到全局最优解，否则执行退火降温操作，即Tk+1=qTk，同时令k=k+1，并转到4)，其中q为冷却系数。

4 仿真结果与分析

以某企业飞机功能系统装配作业为例，进行仿真计算，其装配作业调度表见表2。

表2 装配作业调度表

参数初始化：sizepop=100，迭代次数为100，工装交叉概率Pc1=0.9，工装变异概率Pm1=0.01，工序交叉概率Pc2=0.6，工序变异概率Pm2=0.01，c=80，q=0.9，初始温度T0=100，Tend=1，w1=0.4，w2=0.6，连续进行20次仿真实验，最优解调度方案甘特图如图5所示。

图5 飞机功能系统安装生产计划优化方案甘特图

优化后的总装配时长为26 h，根据实地调研，该企业飞机功能系统安装约需要8～10个工作日，所以本文的优化方法是可行的；工装作业负荷为3，处于比较平衡的状态，改善了企业生产闲忙不均的问题；20次实验中的两次算法寻优曲线如图6所示，平均收敛代数约为退火过程的15代左右，且20次试验中每次计算结果差别不大，比较稳定。另外，改变算法的参数也基本不会影响计算结果。

图6 算法寻优曲线

运用标准遗传算法和本文的改进遗传算法对相同的模型分别计算20次，与本文的改进GASA混合算法相比较，3种算法的优化效果与计算能力对比见表3。通过对比可以看出，改进GASA优化效果更好，计算速度更快，且在20次实验中，改进GASA计算结果比另外两种方法更稳定。

表3 3种算法的计算效果对比

5 结束语

本文将多个目标进行归一化处理，构建多约束多目标的民机装配生产调度模型；针对民机数字化装配现场管控的实际情况设计出改进的遗传与模拟退火混合算法，以某民机装配企业为例，进行仿真与求解，实验结果显示，改进的GASA混合算法优化效果较好、计算速度较快，且计算结果更加稳定，对民机数字化装配现场管控中的生产计划优化具有一定的指导意义。