基于变邻域遗传算法的RMS布局设计方法

管贤平

（江苏大学 现代农业装备与技术省部共建教育部重点实验室，镇江 212013）

0 引言

随着市场需求的多样化和个性化，能以较低成本快速响应市场需求的可重构制造系统（RMS）得到广泛关注[1]。布局设计问题是已知负载流量，根据给定系统可能的分布位置，确定各个工作站在车间的位置分布，以使得总物流成本最小化[2]。在可重构制造环境下，需要快速改变系统的构形，以适应不断变化的生产需求，对布局问题的求解时间和求解质量提出很高的要求。Meng等[3]提出可重构布局问题。本文针对基于AGV的RMS的布局设计要求，综合考虑AGV空载和负载路程，提出高效、求解质量高的变邻域遗传算法。

1 布局设计问题模型

本文作如下假设：每个工作站s有一个加载点Ps和一个卸载点Ds；车间中可分配的位置数量与待分配的工作站数量相等，每个位置只能分配一个工作站。AGV在工作站之间的路径段可双向行走。工作站w到工作站u之间的负载流量fwu给定，Ps、Dt之间的最短路径长度为LPsDt，工作站的单位重构成本为CR，系统上一生产周期的初始布局为工作站w到工作站u之间的空载流量为

决策变量为Hws。假如工作站w分配到位置s，则Hws＝1，否则为0。

布局设计问题的目标是最小化包括物流路程和工作站重构成本在内的总物流成本J：

其中Δw为工作站w是否重构的指示变量：

需要满足以下的约束条件：

位置约束：

流量约束：

布局设计问题是一个复杂的非线性规划问题，最优化方法难以求解大规模的问题，这里采用启发式方法：遗传算法（GA）。针对一般GA局部搜索能力的不足，提出变邻域遗传算法（VNS/GA）。

2 变邻域遗传算法

GA是一种有效的启发式方法，得到广泛应用[4,5]。GA方法是并行搜索，可以得到多个不同的较高质量的解，但是局部搜索能力较差，为此借鉴文献[5]的方法，在局部搜索中增加变邻域（VNS）搜索策略。根据GA的一般设计步骤，设计如图1所示的处理过程。

1） 染色体编码

GA的个体编码采用工作站排序编码的方法，编码长度等于工作站的数量NW。某个编码为：π＝(Wi1，Wi2， ，WiNW)，表示在位置Sk上分布的工作站为Wik。假设种群数量为Np，则种群可以表示为 Π ＝ (π1，π2， ，πNp)。

2） 适应度值计算

根据个体染色体编码计算其对应的总物流成本，将总成本的倒数作为个体的适应度值。

3） 交叉操作

染色体的交叉采用部分映射交叉的方法。在选定的两个位置中间的基因，其排序按照另一个体中的基因排序。

4） 变异操作

变异采用随机选择染色体的两个位置，交换这两个位置上的基因。

5） 选择操作

根据适应度值按轮盘赌的方式选择个体。

6） 小生境淘汰运算

比较个体编码之间的相似度，对编码距离较小的个体，其中适应度值更小的个体进行一定的排挤，即小生境淘汰运算。这为了产生较多的相异个体，避免种群过早收敛。

7） 变邻域搜索

由于GA的局部搜索能力较差，采用VNS局部搜索策略对产生的个体进行局部搜索，以提高解的质量。为了降低搜索时间，以一个较小的概率pv对个体进行搜索。

编码πi与πj之间的海明距离H π(πi，πj)定义为不同放置不同工作站的位置数量。对于一个编码π，其邻域定义为：

对某编码πi的VNS搜索过程如下：

（1）初始化： 根据海明距离定义邻域结构Nk，k＝1， ，kmax，设置局部搜索次数LSIt为停止条件。

（2）设置初始解为π＝πi,令l＝0。

（3）令k＝1。

（6）ifk≤kmax转 Step 4。

（7）ifl＜LSIt,l＝l＋1，转Step 3。

（8）Setπi＝π；

返回πi。

8） 停止条件

完成一定进化代数Ng后停止。

9） 参数设置

GAL算法的主要参数有：进化代数Ng，种群数量Np，交叉概率pc，变异概率pm，小生境参数h，变邻域搜索参数kmax，pv。经过一定尝试，将各个参数设置为：Ng＝150，Np＝20，pc＝0.8，pm＝ 0.2，h＝ max ([1，NW/8])，kmax＝ [NW/3]，pv＝ 0.1。

3 计算实例

为了验证所提出方法的效果，设计了工作站数量分别为9和15的两个计算实例。实例1采用穷举方法得到最优解。而实例2由于规模较大，不能得到最优解，只给出GA方法的运行结果。

对每个实例，首先假设在初始生产周期，在给定的初始负载流量表（称为流量表1）情况下，不考虑工作站重构成本，进行初始布局设计。然后假设系统在初始布局情况下，在新的生产周期，根据新的生产任务得到新的负载流量表（称为流量表2），进行新的生产周期的布局设计，这时需要考虑工作站的重构成本，针对不同重构成本进行算例的比较分析。

1） 实例 1

本实例的工作站数量为9，各位置布局如图2所示，流量表1如表1所示，流量表2如表2所示。首先采用穷举法，得到各种设置情况下的最优解，然后GA方法分别10次，以得到平均物流成本和平均计算时间。本实例两种方法的计算结果如表3所示。

计算结果分析：穷举法的计算时间明显比GA方法更长。在不同的工作站单位重构成本条件下，有不同的最优布局。GA方法在各种设置下都能得到最优解。

表1 实例1的初始负载流量表

表2 实例1新的负载流量表

2） 实例 2

本实例的工作站数量为15，系统位置布局为3行5列的格子布局，同样根据不同流量表进行布局求解。由于本实例的工作站数量较多，无法用穷举法求得最优结果，所以只给出GA方法的结果，如表4所示。

表3 实例1两种方法的结果

表 4 实例2 GA方法的结果

计算结果分析：在问题规模较大的情况下，穷举法不能在有限时间内完成，所以只能采用启发式方法。GAL方法的运行效果较好。

通过由以上计算实例说明， GA方法比穷举时间更短，在问题规模较大的情况下，GA方法能在有限时间内完成计算，得到较好结果，这说明GA方法是一种快速高效的求解方法。

4 结论

本文根据基于AGV的RMS布局设计特点，提出了变邻域遗传算法的布局设计方法，设计了两个计算实例进行计算分析。计算结果表明：在问题规模较小时，GA方法都能得到最优结果，在问题规模较大时，GA方法能在有限时间内完成计算，这说明GA方法是一种快速高效的求解方法。

[1] Z.M.Bi, et al., Reconfigurable manufacturing systems:the state of the art.International Journal of Production Research, 2008, 46(4): 967-992.

[2] A.Drira, H.Pierreval, and S.Hajri-Gabouj, Facility layout problems: A survey.Annual Reviews in Control,2007, 31(2): 255-267.

[3] G.Meng, S.S.Heragu, and H.Zijm, Reconfigurable layout problem.International Journal of Production Research, 42:22, 4709-4729.

[4] 周明, 孙树栋, 遗传算法原理及应用[M].北京: 国防工业出版社, 1999.

[5] 管贤平, 戴先中, 李俊, 基于变邻域小生境遗传算法的AGV路径网络设计方法[J].中国机械工程, 2009, 20(21):2581-2586.