一种改进的多种群遗传算法在车间布局的应用

摘要：针对基本遗传算法中存在早熟的问题，本文设计出一种新的多种群遗传算法选择与协作方式，合理设计出种群内与种群间的协作关系，采用一种新的选择、交叉与变异方式。实验证明，本算法能够有效地解决早熟问题，而且能够达到快速的收敛。与基本遗传算法相比较，在应用车间设施布局问题方面不但能够快速地收敛，而且减少了物流成本费用。

Abstract： Aiming at the problem of premature maturity in basic genetic algorithm， this paper designs a new multi-group genetic algorithm to select and cooperate， and rationally design the cooperative relationship between population and population， adopting a new way of choice， cross and mutation. Experiments show that the algorithm can effectively solve the premature problem and achieve rapid convergence. Compared with the basic genetic algorithm， it can not only quickly converge on the application floor layout problem， but also reduce the logistics cost.

關键词：多种群遗传算法;设施布局;精英保留

Key words： multi-population genetic algorithm;facility layout;elite retention

中图分类号：TH181                                       文献标识码：A                                  文章编号：1006-4311（2019）17-0206-03

0  引言

遗传算法是模拟生物繁殖生存演化过程，基于自然生存法则淘汰机制的一种搜索算法，能够并行、高效、速地解决各类复杂的工程问题。最先由美国学者Holland教授[1]在1975年提出的优化算法，许多实验都能够证明此算法有着良好地解决全局最优化问题。虽然遗传算法有着很强的全局搜索能力，但是许多学者验证了算法存在着局部搜索能力差和早熟收敛等问题[2]。针对遗传算法中的缺点，涌现了许多种有关遗传算法操作的改进方法，如Srinivas M等人提出的自适应遗传算法[3]、陈辉等人提出的改进的混沌量子遗传算法[4]、李军华等人提出的改进双种群遗传算法[5]、吕卉等人提出的一种多种群遗传算法[6]，也有诸多学者尝试与其它智能优化算法相结合等方法。本文在遗传算法的基础上提出一种新的多种群间协同合作方法与各种群内选择交叉与变异方式，把此改进算法应用到车间设施布局设计之中，提高了遗传算法的性能。

1  模型建立

在设计车间设施布中，厂房的面积大小，选址等工作，车间的布局方式均确定的情况下，已知所有设施的大小尺寸，车间的占地面积，设施之间物流量大小与其搬运费用，建立以最小费用为目标的数学模型。模型如图1所示。

在图1中mk，mi，mj为设施的名称，hj0为设施j到边界最小的间距要求，hki为设施k和i设施之间的最小距离要求，？驻j为设施j到边界或者与设施j-1的净距离，s为设施摆设的行间距，s0为第一行或最后一行设备到边界的距离。车间的多行设施布局目标是设施之间的物料搬运费用最低，建立目标函数为：C

其中：Pij为设施和设施j之间的每单位距离物料的搬运费用，Qij为设施i和设施j之间的搬运物流量，Dij为设施i和设施j之间的搬运距离。

在实际车间设施布局中，不仅要余留设施之间的最小间距，也要存在设施之间的净距离？驻，在模型中净距离值设为[0-1]m之间的随机数。模型的约束条件主要包括以下几点：

①确保同一行设备不重叠，即：

2  算法简介

2.1 多种群遗传算法简介

多种群遗传算法是在遗传算法的基础上经过改进引入多种群概念而产生的：

①把单个种群改变为多个种群，每个种群都有着可控制的参数，例如交叉，变异概率，给予不同的数值能够产生不同的搜索目的。

②通过特定的操作因子来控制各种群之间的联系与协同进化，例如设定移民算子，可以得出所有种群最优的进化结果。

③多种群的收敛条件可以根据每个种群进化的最优个体的数量来测定，各个种群中的最优个体可以增加人工选择算子来进行保留。

多种群遗传算法有以下几种优点：

各个种群不同参数的设定，例如交叉概率与变异概率的设定，可以使各个种群向着不同方向进行进化，这样全面增强搜索能力。

各个种群之间的交流是经过特定的操作因子进行实现了，通过设定移民算子，即种群中最优个体，把最优个体引入到其他种群之中，实现各个种群之间的信息交流。

判断整个遗传操作过程是否收敛，设定精华种群，在精华种群中，每个个体均不参加遗传操作，这样每代的最佳个体均能得到保护，也可以根据精华个体的数量作为终止条件。

多种群遗传算法流程图如图2所示。

2.2 多种群遗传算法改进

本文在多种群遗传算法的改进点是通过对选择、交叉、變异等过程进行改进，各种群之间的协作是根据精华个体之间的遗传操作进行的。针对每个种群中，选择出每个种群中的最优个体，作为本种群的一个基础遗传操作个体，然后选择种群中其他的个体与本群落中最优个体进行遗传操作，且在进行交叉与变异操作过程中，最优个体是不发生改变。遗传操作过程如图3所示。

多种群之间的信息交流方式是通过每个种群的最优个体进行交流，对这些种群内的最优个体与所有群落中最优的一个个体进行遗传交叉与变异操作，只改变种群内的最优个体，全局最优个体不发生基因的改变。整个多种群算法流程如图4所示。

对于多种群遗传算法的参数控制，交叉概率Pc与变异概率Pm采用不同的控制参数，这样能够保持种群的差异化，交叉概率Pc与变异概率Pm的值能够决定算法全局搜索和局部搜索能力的均衡，交叉概率Pc的值一般保持在[0.7，0.9]区间内，变异概率Pm的值一般保持在[0.05，0.1]区间内。交叉概率Pc与变异概率Pm可采用公式（4）进行计算。

其中Pc0为交叉概率，Pm0为变异概率;单个种群的总数目为G;c是交叉概率的变化区间长度，m是变异概率的变化区间长度;frand是产生特定区间的随机函数。

适应度函数设计：由于当占地面积有限，设施布局有可能会走出厂区的面积，在此设计出适应度函数，保证在布局的时候不会超过车间的范围。适应度函数如公式（5）所示。

其中ck为物流成本，T为超过车间范围的惩罚值，此处设为1000。

本文设计的多种群遗传算法终止条件根据最大进化次数进行决定的，设置最大迭代值为gMax=500。

3  算例分析

实验数据来源于文献[7]，各个设施尺寸如表1所示。车间的总面积为10m×8m。各设施之间的搬运费用如表2所示。设施之间最小间距如表3所示。

本文使用matlab2015进行仿真，整个多种群遗传算法的程序参数设置如下：种群的数量设置为10，种群的规模设置为50，交叉概率在区间，变异概率在区间。

本文使用改进的多种群遗传算法与遗传算法相比较，每种算法实验10次，实验结果如表4所示。

本文改进的多种群遗传算法与基本遗传算法收敛性能如图5所示。

由表4与图5可得，本文改进的多种群遗传算法相比遗传算法有以下优势：由于设施布局问题属于NP-hard问题，算法只能得出近似最优解，本文改进的多种群遗传算法最优值为1734，而基本遗传算法得出的最优结果为1825，设施布局成本费用降低了约5%;相比基本遗传算法，本文设计的算法在100代左右达到收敛，而基本遗传算法在260代左右才达到收敛;本文改进的算法实验结果标准差为46.8569，均值为1794，而基本遗传算法标准差为128.8436，均值为1939，两者相比本文改进的算法稳定性较好，得出的近似最优解比基本遗传算法更优。

4  结论

针对基本遗传算法的早熟与局部搜索能力较弱问题，本文提出的一种改进多种群遗传算法，能够很好地解决这类问题，能够达到更快的收敛与更优的结果。本文提出的多种群遗传算法在种群间和种群内均能够达到很好的协调，提出的新的交叉与变异方式，使得本算法有着一定的独特性。本算法应用实例是车间设施布局问题，也可以把本算法应用到其他的领域进行更深地研究。

参考文献：

[1]Holland， John Henry. Adaptation in natural and artificial systems： an introductory analysis with applications to biology， control， and artificial intelligence. MIT press， 1992.

[2]Jong K A D. An Analysis of the Behavior of a Class of Genetic Algorithm Adaptive System[D]. Ann Arbor， USA： University of Michigan， 1975.

[3]Srinivas M， Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transactions on Systems， Man， and Cybernetics， 1994， 24（4）： 656-667.

[4]陈辉，张家树，张超.实数编码混沌量子遗传算法[J].控制與決策，2005，20（11）：1300-1303.

[5]李军华，黎明，袁丽华.一种改进的双种群遗传算法[J].小型微型计算机系统，2008（11）：2099-2102.

[6]吕卉，周聪，邹娟，郑金华.基于多种群进化的遗传算法[J].计算机工程与应用，2010，46（28）：57-60.

[7]汪一筇，米智伟.SLP和遗传算法结合在车间设备布局中的应用[J].计算机工程与应用，2010，46（05）：211-213.

作者简介：陆庆伟（1972-），男，上海人，毕业于上海电机技术高等专科学校，机械制造，工程师。