基于改进NSGA-II算法求解混流装配线平衡问题*

罗利飞，吴永明,b,c，黄海松，徐艳霞，张 晗

(贵州大学 a.现代制造技术教育部重点实验室；b.贵州省公共大数据重点实验室；c.机械工程学院，贵阳 550025)

0 引言

混流装配线平衡是指在已有生产条件下，两种或两种以上的产品在同一条装配线上生产，合理地利用现有资源，低成本、高效率、最大可能地满足市场多个客户的生产需求，混流装配线具有复杂的生产工艺且生产批量小、高频率地变换产品，换装成本高。因此，混流装配线的生产计划组织柔性要求较高[1]。

当前关于混流装配线方面的研究成果较多，基本概括为两类，一是考虑某些特定因素的建模研究，如李金霖等[2]建立装配线人工成本和维护平衡所需加班成本的混流装配线多目标模型，龚轲等[3]考虑作业元素之间的兼容性，建立有相同作业工艺条件或者需要到相同设备作业的元素放在同一工作站的模型，吴永明等[4]考虑产品需求变化、装配工艺及技术进步、设备更新等动态变化，建立了实现混流装配线演进平衡模型。第二类为侧重对模型的求解方式方法研究，分为仿真和算法求解，如蒋南云等[5]运用Flexsim仿真软件对混流装配线进行建模仿真求解，韩煜东等[6]设计了基于自然数序列和拓扑排序的改进遗传算法。张则强等[7]提出了已知基于优先权的粒子群算法，设计一种基于模拟退火抽样机制的混合粒子群算法。

从现有研究文献看，虽然混流装配线平衡问题的研究已趋于成熟，但混流装配线平衡随着设备、市场、技术的变化演进，并不能对混流生产系统组织问题有完美的解决，必须考虑到混流装配线平衡以外的其他因素，本文考虑如何在满足客户和市场要求的基础上，兼顾装配线平衡和物料平准化的要求，合理制定车间生产计划，建立混流装配线平衡与物料配送双问题优化模型，设计了基于生态策略的NSGA-II算法，该算法提出了生态种群的捕获竞争，定义了环境变化时种群采取生态策略对环境进行突变，在进化过程中有效地增加和控制种群的多样性，最后通过实例验证算法和模型的有效性。

1 模型构建

问题描述：混流装配线有S个工作站完成M种产品的装配作业，这些产品装配结构类似、工艺相近，每种产品包含工序N，qa为第a种产品所占需求产品的比例，qb为第b种产品所占总需求产品的比例，tmk表示第m种产品k道工序的作业时间，Gia为第a种产品第i道工序的物料所需量，Tk表示第k个工作站的装配时间。

数学模型为：

F=min(SI,D,P)

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

其中，S表示工作站数，K表示配送物料的车辆数，li为配送中心到第i个工作站的距离，xij为决策变量，表示第j辆车配送第i个工作站的物料，若是，xij=1，否则，xij=0，Gi表示工作站i的所需物料，Q表示运输物料的小车最大装载量，dij为工作站i到工作站j的距离，式(2)为第一个目标函数，是使得各工作站中产品的平均单件作业时间的均方差最小，即各工作站的加权平均负荷均衡；式(3)表示车辆运输的最短路径，式(4)表示最小车辆利用率最大，式(5)每个物料点都能得到配送且只能由一辆车完成，式(6)为每辆车配送路线上物料和不超载，式(7)表示每辆车都从配送中心出发，式(8)表示每辆车配送完后返回配送中心。约束条件(9)指出变量下标i，j的取值范围。

2 算法设计

2.1 基本算法

对于多目标优化问题的求解，一般是将多目标转化为单目标或者采用多目标进化算法进行求解，但是多目标转化单目标有一定的缺点：可能造成所求解为非可行解，NSGA-II[8]是目前优化效果不错的一种元启发式多目标智能算法，通过快速非支配排序，可以使算法复杂度降低，能加快算法的运行，同时通过采用精英策略，在进化过程中，父代的优秀个体可以保留到子代中，不但能提升种群的多样性，而且优秀个体的遗传使得算法结果的精确性得到优化，最后拥挤度和拥挤度比较算子，对pareto曲面的均匀性大大提高。但NSGA-II存在侧重于全局的广域搜索，局域搜索深度较差的缺点，本文在保留原有精髓：精英保留策略、快速非支配排序合拥挤度比较算子情况下引进生态策略对算法局域搜索进行改进。

2.2 编码设计

传统的二进制编码对连续装配线问题的求解比较复杂，对运算速度也有一定的影响，尤其在搜索空间较大时尤显缓慢，本文采用由(0～1)的随机数组成的编码[9]，编码及解码过程：

Step1：每条染色体随机生成(0～1)之间的随机数；

Step2：对作业顺序图进行遍历，找到无紧前的装配任务放入集合TS中；

Step3：集合中作业元素对应染色体的随机数，比较随机数的大小；

Step4：排列对应随机数大的作业元素后，去掉已排列的作业元素，跳转Step3。

某装配线作业任务顺序如图1所示，对应的染色体编码及解码见表1，排列顺序见图1。

图1 某装配线作业任务顺序图

编号(任务)1234567对应染色体(0～1)数0.78230.65420.84530.32580.69420.75320.6985解码1、TS={1},解码作业元素R={1};2、TS={2,3,6},解码元素R={3};......7、TS={7},解码元素R={7}。解码任务排列1365247

2.3 拥挤度计算以及改进

拥挤度是指在群体中的给定个体的周围个体的密度[10]。结合装配线模型，以及NSGA-II计算拥挤度的缺点，拥挤距离采用空间上的欧几距离，即：

(10)

式中，f1,f2,f3分别为两个子目标函数。

拥挤度改进后计算流程如图2所示。

图2 拥挤度计算过程

2.4 生态进化策略

生态策略(ecological strategy)是自然界的生物在根据环境变化后对环境适应时形成的一种进化策略。

2.4.1 环境变化检测算子

(11)

其中，t表示迭代数，‖‖表示欧式距离，若s(t,k)≥0.5，则认为环境之间存在了变化，即环境t与k为非相似环境。

2.4.2 竞争算子

设有两个染色体C1=(x1,x2,....xm)和C2=(x1,x2,...,xm)，如果满足条件x属于C1，存在x属于C2，y>x,则表示染色体中y捕食掉x，否则x捕食掉y，然后混合后得到新的染色体中C3=(l1,l2,...,lm)。

将生态竞争算子引入后，种群所经过的进化过程为选择、交叉、变异、竞争和再选择，个体与个体之间有内部竞争和种群间竞争，增加种群的有效多样性，而且得到的子个体都是符合非支配的，加速子种群向Pareto前沿进化，促进整个种群收敛。

2.5 混合变异

混合变异是将高斯变异(gaussian Mutation,GM)、柯西变异(Cauchy Mutation,CM)、Lateral变异(Lateral Mutation，LM)三种变异因子相结合，根据各个变异的关联性及多优化目标的影响程度来选择变异因子。GM表达式如下：

(12)

其中，N(0,1)为均值为0，方差为1的正态分布，sg为变异长度，ωg为[0,fgau(0)]中随机数。

CM基于柯西密度函数：

(13)

其执行过程为：

(14)

其中，εk是柯西随机变量，sc为柯西变异步长，ωc为[0,fcau(0)]中随机数。

LM定义为：

(15)

其中,l属于(1,m)之间,且l≠k,α是(0,1)之间的随机数。

LM可以加快收敛速度，但是易使所有的个体最终收敛局部最优解，而GM和CM可以克服这个缺点，避免算法出现局部最优。变异过程如图3所示。

图3 变异过程

2.6 改进算法的求解步骤

基于生态策略的改进NSGA-II具体过程如下：

(1)种群初始化及参数设置：设定种群数pop，迭代次数Gen。

(2) 0～1编码对应非支配排序并计算拥挤度。

(3)选择算子，根据正态随机数决定交叉还是混合变异，进行环境检测判断是否进行竞争，若需竞争根据捕食原则替换染色体，合并种群非支配排序后得到N个体，并与上一代进行环境检测进行竞争。

(4)重新选取拥挤度大的个体。编解码对应具体作业任务。

(5)判断父代种群是否满足终止条件，若是，结束，否则，跳转到(3)。

流程图如图4所示。

图4 基于生态策略的NSGA-II算法流程图

3 实例分析

某混流装配车间有1个物料配送中心，载重为Q=11的物料车辆若干，现已知物料配送中心与各工作站的距离见表和各工序的作业时间及物料需求量见表2和表3，两种产品的比例为qa=0.42，qb=0.58，设计节拍为CT=94。

图5 装配线作业任务顺序图

工序号ta /stb /s工序号ta /stb /s1020141302777715555537373161920490821737058888189497662019131373602009080202120209666622474710252523928211555524413712777125500135959

表4 工作站距离(m)

算法参数如下：种群规模pop=100,交叉概率Pc=0.9,变异概率Pm=0.1，进化100代最后得到若干非劣解，求解结果如图6所示。

图6 Pareto解

算法工作站数站间均衡系数物料配送路径和最小车辆装载率车辆平均装载率NSGA-II方案11413.14246550.33%79.46%方案21511.58647942.87%65.253%改进NSGA-II方案11411.16941640.18%88.32%方案21412.499842162.18%89.54%

图7 方案1工序条形图

图6灰色星型点为迭代100次后都能得到Pareto最优解，表5为选取NSGA-II改进与没改进时选取的两个解，从表看出相对原算法有一定的优势且改进后收敛性更好，从Pareto解可以看出解对站间均衡系数、物料配送路径及车辆装载率的选择要基于具体实际生产在某目标的选取，对企业生产具有一定的参考意义。

4 结论

在分析混流装配线平衡问题和物料路径配送问题后，本文提出混流装配线平衡和物料配送综合模型，该模型对混流装配线的第一类问题进行优化的同时，使配送物料路径得到优化，克服制造系统装配与物料配送出现不配套等问题。根据生态策略设计了一种基于生态策略的改进NSGA-II，算法重点采用生态策略去应对环境的变化，对个体进行竞争防止陷入“早熟”，通过实例求解表明，改进后的算法相对标准算法具有更佳的收敛能力及保持多样性能力，全局寻优能力也有所提高，效率与可靠性进一步提升，对于装配线平衡问题具有较好的求解效果.如何更好地评价该算法的性能，这将是下一步要做的工作。