基于差分元胞多目标遗传算法的车间布局优化

张 屹，卢 超，张 虎，方子帆

（三峡大学 水电机械设备设计与维护湖北省重点实验室，湖北 宜昌 443002）

0 引言

设备布局优化设计是现代制造业面临的重要且复杂的问题之一。一般来说，设备布局问题（Facility Layout Problem，FLP）指将一组设备合理地布置在特定布局空间内，使设计目标集尽可能地优化，并且满足给定的空间或性能约束条件［1］。车间设备布局是否科学、合理，将直接影响企业的生产效率。随着社会经济的快速发展，越来越多的企业开始意识到合理的车间布局不仅可以降低运输成本，还可以提高设备的使用寿命、厂房的利用率等。因此，科学合理的车间设备布局对企业来说尤为重要。

目前，大多数学者对车间布局的研究主要集中在减少车间设备间物料搬运费用的单目标布局优化方面。然而在实际车间布局设计过程中，当物料传输费用成本下降时，往往会使车间设备的其他性能有所降低，如产品质量降低、占地利用率减少等。因此，不能盲目追求物料传输费用最小，要统筹兼顾车间设备布局的整体规划。实际上，面积利用率这项指标直接影响车间布局的美观和投资成本，应在评估最佳布局方案时予以考虑。因此，应该综合考虑搬运费用成本和车间占地面积利用率这两项指标，建立车间设备布局多目标优化模型，以设计出更科学合理的布局方案。在解决多目标优化问题时，国际上涌现出许多经典的多目标进化算法，如非支配排序遗传算法（Non－dominated Sorting Genetic Algorithm Ⅱ，NSGAⅡ）［2］、强度Pareto进化算法2（Strength Pareto Evolutionary Algorithm Ⅱ，SPEA2）［3］等。近年来，Nebro等又提出了经典元胞多目标遗传算法和 MOCell［4］，总体而言，MOCell在多样性和收敛性方面均表现出比NSGAⅡ和PESAⅡ更为优越的性能，并在工程中得到很好的应用［5－9］。但是对于解决 FLP 这样非线性、高维的NP－hard问题，MOCell的收敛性依然不尽如人意。2005年，Kukkonen S提出的 GDE3［10］在解决高维、非线性的复杂问题时，其收敛性相比其他算法有明显提高。本文针对这些问题，结合MOCell良好的多样性和GDE3良好的收敛性，在MOCell算法中引入差分演化（Differential Evolution，DE）策略［11］，并采用换位变异算子，形成一种混合算法DECell，以达到高效求出FLP的Pareto最优解集的目的。

1 车间设备布局优化模型

1．1 目标函数的建立

因为车间布局问题可分为环型布局、U型布局等问题，所以以多行线性车间设备布局问题为例；又因为该问题较为复杂，所以需要对其模型进行简化。假定各设备为矩形块状结构，长和宽已知，同一行中设备的中心位置处于同一水平线上，两设备之间的物流运输方向只能平行于相应的参考线。多行线性车间布局示意图如图1所示。

图1中，X和Y轴分别表示车间的长度和宽度方向，H和W 分别为车间的长度和宽度。xi和xj为设备i和j与垂直参考线之间的水平距离；yi和yj为设备i和j与水平参考线之间的垂直距离。该模型主要考虑下述两个布局优化设计目标：①车间里总的物料搬运费用最小；②车间占地面积利用率最大，一是充分利用现有给定的空间，二是防止工作时车间之间噪音干扰，因此在指定的范围内占地面积越大越好。这两个目标一方面使物料搬运费用最小，另一方面要使占地面积利用率尽可能的高，因此它是一个典型的多目标问题。由于多目标优化问题一般是求解目标的最小值，可将面积函数转化为A＝Z－f（s）形式。其中：Z为给定的常值；f（s）为车间实际占地面积，即f（s）＝a×b，且Z＞f（s）。综上所述，多行线性车间设备布局问题的目标函数可以表示为

式中：n为布局的设备的数目；C为总物流费用；A为车间的占地转化面积；fij为设备i和j之间的搬运频率；pij为设备i和j之间物料搬运一次单位距离的搬运费用（令pij＝pji）；dij为设备i和j之间的距离

1．2 约束条件的确定

由于各设备在车间中需占一定的面积，设备间还需为操作人员留出一定的活动空间，在多行线性车间布局设计中还需考虑各种约束条件。dxmin为相邻设备i和j的边界在水平方向（X方向）应保证的最小间距，dymin为相邻两行设备i和j的边界在垂直方向（Y方向）应保证的最小间距。Si和Li分别为设备i在X方向和Y方向的尺寸。考虑到多行布局的约束情况，引进决策变量Zik，i＝1，…，n，k＝1，2，…，m，其中m为设备被排布的总行数。

因此，实现多行线性车间设备布局的优化设计的约束条件包括：

（1）一台设备只能被布置在一行，且每一行最多只能布置n台设备。

式中tk表示第k行排布的设备数。

（2）边界约束，即每一台设备都应处于车间之内。

（3）同一行中设备的y坐标相同。

（4）同一行中的设备不能重叠，且设备边界之间的最小间距需要大于水平方向上应保证的最小间距，边界间的最大距离要小于布局车间的长度。

（5）处于不同行的任意两台设备在垂直方向上设备边界之间的最小间距，要大于垂直方向上应保证的最小间距；边界间的最大距离要小于布局车间的宽度。

2 差分元胞遗传算法设计及性能测试

为了对上述FLP多目标优化模型进行优化计算，提出一种差分元胞遗传算法DECell。DECell是在MOCell的基础上引入DE策略的算法，该算法采用换位变异算子。为了对上述FLP多目标优化模型进行优化计算，提出一种差分元胞遗传算法DECell。DECell是在MOCell的基础上改进的一种算法，它引入了DE策略，并采用换位变异算子，从而使获得的Pareto前端的解集能在保持良好均匀性和分布广度的同时，朝着最优前端不断逼近。

2．1 差分演化策略原理

DE策略利用群体中个体之间的距离和方向信息，具有全局并行直接搜索的特点，适于求解高维、非线性的多目标问题，且实施起来相对较容易［12］。具体操作过程是：

对于每个个体xi，D，i∈［0，N－1］，N 为种群大小，定义操作［13］

式中：D 为个体的决策变量个数，xr1，D，xr2，D和xr3，D为选择出来的三个父本向量，r1，r2和r3为三个父本的索引位置，F为缩放因子。式（10）表示随机取出两个父本向量xr2，D和xr3，D，取两者的差值，将其缩放后的结果加到第三个父本向量xr1，D上，最终得到交叉后的个体向量vi，D＝［vi，1，…，vi，j，…，vi，D］。而对于处于第i索引位置的父本向量xi，D＝［xi，1，…，xi，j，…，xi，D］中的每一分量xi，j，随机产生一个数randj∈［0，1］，比较randj与交叉因子CR 或j与K 的大小，判断是否用vi，，j来替换xi，j，随机产生一个数randj∈［0，1］，比较randj与交叉因子CR或j与K（K∈［0，D－1］之间的整数）的大小，从而利用式（11）判断是否用vi，，j来替换xi，j，判断操作完成以后，得到新个体ui，D＝［ui，1，…，ui，j，…，ui，D］，其中

若交叉后的新个体ui，D优于父代个体xi，D，则用新个体替换父代个体，否则保持不变。

2．2 DECell算法原理

DECell算法具体原理如图2所示。首先将种群个体安排在二维的环形网格中，从每个当前个体周围邻居中随机选出两个较优秀的个体，与当前个体共同构成三个父本个体；然后对这三个父本进行DE策略的交叉操作；最后进行变异操作，产生子代。如果子代支配当前个体，或者子代和当前个体都处于非支配地位，且子代的拥挤距离比当前个体的拥挤距离大，则子代个体代替当前个体，同时将该非支配的个体存放到外部文档中，并对这些外部文档存放好的个体按拥挤距离进行排序，若其非支配个体超过了规定的容量，则将其中拥挤距离最小的个体删除。最后，在每代结束时，从外部文档中选一些个体代替相同数量的原始种群中的个体，使种群不断进行更新操作，最终使外部文档中的非支配个体在保持多样性的同时，能朝着Pareto最优前端的方向不断逼近。其主要伪代码如下：

2．3 DECell算法性能测试及结果分析

为验证算法DECell的性能，选用一个多约束、多变量的双目标测试函数Osyczka2［14］和一个高维多 目 标 函 数 DTLZ2［15］。 分 别 利 用 DECell，NSGAⅡ及MOCell对上述测试函数进行计算，并分析相同评价体系下三种算法的性能。

2．3．1 算法性能评价指标

这里采用世代距离［16］、分布指标［3］和超体积［17］三个性能指标进行度量。

（1）世代距离

世代距离是用来评价所得的Pareto前端与最优Pareto前端之间的间隔距离，计算公式为

式中：n为所得Pareto前端个体的数目，di为目标空间中的第i个解与Pareto最优前端中最近解之间的欧氏距离。显然，当GD＝0时，所得的Pareto解集就是Pareto最优解。因此，GD 越小，表明收敛到最优Pareto解的程度越好。

（2）分布指标

Deb提出的分布指标是衡量所得的Pareto前端解集的分布情况，计算公式为

式中：di为所得Pareto前端上每两个连续解点的欧氏距离，为这些欧氏距离的平均距离，df和dl分别为所得Pareto前端的边界点与Pareto最优边界点的欧氏距离，n为所得Pareto前端个体的数目。对于分布均匀的解来说，该指标取0。因此，该指标的值越小表明分布程度越均匀。

（3）超体积

超体积是用来计算获得的Pareto解集个体在目标域所覆盖的体积，计算公式为

式中Q为所获得的Pareto前端的个数。对于该Pareto前端中的每一个体i，vi是由参考点W ＝ （0，…，0）和成员i所形成的超体积，该指标越大表明所得的Pareto解集能越宽广地覆盖在其前端上。

2．3．2 算法性能优化结果及分析

Osyczka2与DTLZ2基准测试函数的定义如表1所示。

表1 基准测试函数

NSGAⅡ，MOCell和DECell算法的参数设置为：均采用实数制进行编码，多项式变异；NSGAⅡ和MOCell采用模拟二进制交叉（Simulation Binary Crossover，SBX）［18］算子，DECell使用DE交叉操作算子；种群规模为100，最大评价次数为25 000，交叉概率为0．8，变异概率为1／len，len为变量维数；在此取CF＝0．6，CR＝0．5。这三种算法分别对测试函数进行10次独立运行计算。图3是三种算法所获得到Pareto前端的对比图之一。

从定性的角度分析图4可知：NSGAⅡ收敛性好，但分布性能较差；MOCell的分布性能较好，但其收敛性和覆盖性能较差；采用DE策略的DECell所求的Pareto前端解集，在分布性、覆盖广度和收敛性方面均比NSGAⅡ和MOCell好。

表2记录了三种算法在Osyczka2和DTLZ2函数上的收敛性、分布性和覆盖范围。每种性能指标的第一列为性能均值，第二列为性能标准差，加粗数据为最优值。分析表2可以发现，在解决DTLZ2和Osycka2时，DECell在收敛性方面和覆盖范围方面要比NSGAⅡ和MOCell更好一些。虽然在解决Osyczka2时DECell的分布性能比MOCell的差，但DECell的稳定性比MOCell好。DECell之所以表现出优良的性能，其原因在于它结合了MOCell和DE两种算法的优点。由实验数据可知，DECell的确提高了解集的收敛性能，有效地保持了种群的多样性，增大了解集的覆盖范围。因此，通过以上算例结果分析可知，在解决多约束、多变量、高维的多目标问题时，DECell比NSGAⅡ和MOCell具有良好的优势。

表2 算法性能结果对比

3 DECell算法在设备布局问题中的应用设计

采用DECell对FLP模型进行计算，基本步骤如下：

（1）随机生成初始种群 采用实数制编码生成初始种群，根据车间布局问题的实际要求，将编码设计为 ［（m1，…，mn），（x1，…，xn），（y1，…，yn）］。其中mn表示第n台设备编号，xn和yn为第n台设备的坐标，（m1，…，mn）是n台设备的一个全排列。

（2）选择操作 采用锦标赛法，该选择方法是基于个体的秩和拥挤距离对种群父本进行选择，因此步骤为：选出当前个体的邻居个体，首先比较邻居个体的秩，秩越小个体的性能越优秀，因此处于较小秩的个体被保留下来。若邻居个体的秩相等，则比较它们的拥挤距离，拥挤距离较大的个体被保留下来。最终选出邻居中较优秀的两个个体。

（3）交叉操作 其作用是产生更多的新个体，增大搜索空间的能力。为保障交叉后的解集可行，只对 （x1，…，xn）区域进行交叉操作，并对 （y1，…，yn）进行重新移动，调整设备的行距。在交叉操作中引入DE策略，其交叉过程如式（10）和式（11）所示。该操作中要使用到交叉系数CR和缩放因子F两个参数，在这里CR＝0．8，F＝0．5，具体参数设置详见参考文献［19］。DECell算法中的交叉代码流程如下：

（4）变异操作 为使个体逃离局部收敛，且尽可能保障产生的子代是可行解，此处对 （m1，…，mn）区域进行换位变异操作。具体步骤如图5所示。

4 实例求解

在一个长×宽，即17m×14m的车间放置9台设备，这些设备分3行放置在车间内，每行3台，设备的尺寸如表3所示，设备之间的搬运频率如表4所示，单位距离的搬运费用如表5所示，设备之间应保证水平方向和垂直方向的安全距离，其最小距离分别为dxmin＝1m，dymin＝1 m，设常数Z＝500。

表3 设备尺寸

表4 设备之间的搬运频率fij

表5 单位距离的搬运费用pij

依然采用DECell，MOCell和NSGAⅡ三种算法分别对车间设备布局进行优化计算。三种算法的参数设置为：种群数量M＝25，文档大小N＝100，反馈数目C＝5，终止评价次数G＝25 000，交叉概率pc＝0．8，变异概率pm＝0．2。求出这三种算法所产生的Pareto前端，如图6所示。

由于问题的复杂性，很难找到最优解集，这里将最后得到的非支配解集当作最优Pareto解集。从图6可以看出，位于左上方的Pareto前端的点具有较大的转换区域面积和较低的物料运输费用，即物料运输费用越低，车间设备占地面积利用率越小。而位于右下方的Pareto前端的点具有较小的转换区域面积和较大的物料运输费用，意味着车间设备占地面积利用率越大，其物料运输费用就越高。在目标空间中，这些算法为决策者提供了各自的Pareto前端解集，以便决策者根据自己的偏好选择出合适的解。由图6可以看出，DECell的Pareto前端的解集的分布性和收敛性比NSGAⅡ和MOCell好。为进一步说明DECell算法在车间布局优化设计上的应用较其他算法具有一定的优势，本文用上述三种算法对车间设备布局各自进行了10次独立运算，计算结果如表6所示。

表6 三种算法准确率比较 %

综上所述，与MOCell和NSGAⅡ相比，DECell表现出了一定的优势，因此选择采用DECell算法求解得到FLP的Pareto前端，并从中选出A和B两点所对应的Pareto解集解，A和B两点如图6所示，结果如表7所示。

表7 DECell算法得到的部分Pareto解集

5 结束语

本文针对车间FLP建立了一个同时考虑物料搬运费用和车间占地面积利用率的多目标优化模型，基于MOCell良好的多样性，以及GDE3良好的收敛性和分布广度的优点，结合这两种算法的特点，互补长短，在MOCell算法中引入DE策略，并采用换位变异算子，形成一种混合算法DECell，以使获得的Pareto前端的解集在保持均匀性和覆盖性能的同时，其解集能朝着最优前端不断逼近。最后将DECell与MOCell和NSGAⅡ进行了性能对比，验证了DECell的有效性和可行性，并将三种算法分别对车间设备布局进行优化设计。通过实例对比分析可知，该算法比其他两种算法的效果有所改善，为解决多行车间布局问题提供了一种新的方法。未来工作将进一步改善该算法的性能，并将此算法推广到其他类型的车间布局实际问题中。

［1］CAGAN J，SHIMADA K，YIN S．A survey of computational approaches to three－dimensional layout problems［J］．Computer－Aided Design，2002，34（8）：597－611．

［2］DEB K，PRATAB A，AGARWAL S，et al．A fast and elitist multiobjective genetic algorithm：NSGA－Ⅱ［J］．IEEE Transactions on Evolutionary Computation，2002，6（2）：182－197．

［3］CORNE D W，JERRAN N R，KNOWLES J D，et al．PESA－Ⅱ：region－based selection in evolutionary multi－objective optimization［EB／OL］．［2011－11－15］．http：／／www．macs．hw．ac．uk／～dwcorne／pesall．pdf．

［4］NEBRO A J，DURILLO J J，LUNA F，et al．MOCell：a cellular genetic algorithm for multiobjective optimization［J］．International Journal of Intelligent Systems，2009，24（7）：726－746．

［5］BRUDARU O，POPOVICI D，COPACEANU C．Cellular genetic algorithm with communicating grids for assembly line balancing problems［J］．Advances in Electrical and Computer Engineering，2010，10（2）：87－93．

［6］ALBA E，MOLINA G．Location discovery in wireless sensor network using metaheuristics［J］．Applied Soft Computing，2011，11（1）：1223－1240．

［7］CANYURT O E，HAJELA P．Cellular genetic algorithm technique for the multicriterion design optimization［J］．Structural and Multidisciplinary Optimization，2010，40（1－6）：201－214．

［8］LI Xunbo，WANG Zhenlin．Cellular genetic algorithms for optimizing the area covering of wireless sensor networks［J］．Chinese Journal of Electronics，2011，20（2）：352－356．

［9］WU Feng，ZHOU Hao，REN Tao，et al．Combining support vector regression and cellular genetic algorithm for multi－objective optimization of coal－fired utility boilers［J］．Fuel，2009，88（10）：1864－1870．

［10］KUKKONEN S，LAMPINEN J．GDE3：the third evolution step of generalized differential evolution［C］／／Proceedings of the 2005IEEE Congress on Evolutionary Computation．Washington，D．C．，USA：IEEE，2005：443－450．

［11］STORN R，PRICE K．Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces［J］．Journal of Global Optimization，1997，11（4）：341－359．

［12］SHI Yanjun．The cooperative co－evolutionary differential evolution and its applications for complex layout optimization［D］．Dalian：Dalian University of Technology，2005（in Chinese）．［史彦军．复杂布局的协同差异演化方法与应用研究［D］．大连：大连理工大学，2005．］

［13］DURILLO J J，NEBRO A J，LUNA F，et al．Solving threeobjective optimization problems using a new hybrid cellular genetic algorithm［J］．Lecture Notes in Computer Science，2008，5199：661－670．

［14］OSYCZKA A，KUNDO S．A new method to solve generalized multicriteria optimization problems using a simple genetic algorithm［J］．Structural and Multidisciplinary Optimization，1995，10（2）：94－99．

［15］DEB K，THIELE L，LAUMANNS M，et al．Scalable test problems for evolutionary multi－objective optimization［C］／／Proceeding of 2002Congress on Evolutionary Computation．Berlin，Germany：Springer－Verlag，2002：852－890．

［16］VAN VELDHUIZEN D A，LAMONT G B．On measuring multiobjective evolutionary algorithm performance［C］／／Proceedings of the 2000Congress on Evolutionary Computation．Washington，D．C．，USA：IEEE，2000：204－211．

［17］ZITZLER E，THIELE L．Multiobjctive evolutionary algorithms：a comparative case study and the strength Pareto approach［J］．IEEE Transactions on Evolutionary Computation，1999，3（4）：257－271．

［18］DEB K，AGRAWAL R B．Simulated binary crossover for continuous search space［J］．Complex Systems，1995，9（2）：115－148．

［19］ZIELINSKI K，WEITKEMPER P，LAUR R，el at．Parameter study for differential evolution using apower allocation problem including interference cancellation［C］／／Proceedings of the IEEE Congress on Evolutionary Computation．Washington，D．C．，USA：IEEE，2006：1857－1864．