一种基于蜜蜂进化选择算子的布局遗传算法

王金敏， 朱丽苹， 甄士刚

(1. 天津市高速切削与精密加工重点实验室，天津 300222；2. 天津职业技术师范大学机械工程学院，天津 300222)

一种基于蜜蜂进化选择算子的布局遗传算法

王金敏1,2， 朱丽苹2， 甄士刚2

(1. 天津市高速切削与精密加工重点实验室，天津 300222；2. 天津职业技术师范大学机械工程学院，天津 300222)

三维矩形布局问题属于NP难问题，对于三维矩形布局问题的求解大多依赖于各种启发式算法。该文以布局物体体积递减为定序规则，结合布局物体在布局空间中的几何可行域，以吸引子法为定位规则，利用蜜蜂进化型遗传算法优化吸引子函数中的参数来求解三维矩形布局问题(BEGA)，得到新型布局遗传算法。最后对不同的算例进行了计算，并与以标准比例选择作为选择算子的传统布局遗传算法(SPGA)等对比证明了该算法的有效性。

布局问题；启发式算法；吸引子；蜜蜂进化

布局问题[1-2]广泛存在于生产生活实际中，如运输、下料、剪裁、排版等。解决好布局问题无疑具有巨大的现实意义。布局问题可以定义为给定布局空间和若干布局物体，将布局物体合理地布置到布局空间中并满足某种最优指标。这些指标通常是使布局空间利用率最大、布局成本最小等。学术界已经证明布局问题属于非确定多项式(non-deterministic polynomial，NP)难问题。对于NP难问题，普通的精确性求解算法难以建立合适的数学模型及找到问题的全局最优解，因此长期以来大多布局问题的求解依赖于各种启发式算法。如Zhang等[3]提出了一种分层算法，分别利用深度和广度优先搜索方法来解决布局问题。Leung等[4]提出一种混合模拟退火启发式算法，其应用适应函数评价准则动态地确定一个布局序列，再利用贪心算法确定布局物体的最佳放置位置。Burke等[5]提出了一种基于遗传算法的超启发式算法，它强调通过搜索空间的办法来构建布局方案而不是直接的寻找一个解决方案，所以它的程序输出是一种启发式算法而不是布局块的布置信息。Cintra和Miyazawa[6]使用纵列码遗传算法和动态编程方法解决了二维装填问题。杨林等[7]提出了一种分布式评估算法，该算法是基于概率模型的遗传算法，它没有遗传算法中的交叉、变异运算，后代个体是根据评估父代种群中个体的概率分布情况而产生的。Bischoff和Ratcliff[8]针对当时算法应用面狭窄这一事实，提出两种分别针对均匀和非均匀布局块的方案，当二者结合使用为解决三维装载问题提供了强大的通用性工具。Gehring和Bortfeldt[9]通过将三维待布局块组成互不相连的塔状，然后结合遗传算法来解决三维布局问题。Bortfeldt和Gehring[10]通过将一种改进之后的禁忌搜索算法应用在三维布局问题上，来解决此类问题。Lim等[11]通过将三维装载问题分割为箱体选择、空间选择、箱体旋转和新空间的产生四部分，利用设计好的基础启发式算法和两种增强启发式算法来解决布局问题。Moura和 Oliveira[12]等为了解决容器装载问题，提出一种砌墙构造启发式算法，并应用智能启发式算法(greedy randomized adaptive search procedure，GRASP)优化。本文通过蜜蜂进化选择算子的遗传算法与吸引子定位函数相结合的方法对三维矩形布局问题进行了研究，提出一种新的启发式算法，并通过与传统布局遗传算法(search packing genetic algorithm，SPGA)等算法对比验证了它的有效性。

1 三维矩形布局问题

1.1 问题描述

本文对三维矩形布局问题进行研究，布局容器及物体均为长方体(三维矩形)。令布局容器的体积为V，第i个布入的布局物体的长、宽和高分别为li、 wi和 hi，布局空间的体积利用率设为 f，则其中，n为布入的布局物体块数，布局结果的优劣由体积利用率f值的大小来衡量，f值越大说明布局结果越好。

三维矩形布局问题的数学模型描述如下式：

式中，L、W、H分别表示布局容器的长度、宽度和高度；（ xi,yi,zi） 和（ xj,yj,zj）分别为第i个和第j个已布入的布局物体的中心点坐标，且i ≠ j。这里布局容器的左下前角为坐标原点(0，0，0)；li、wi、 hi和 lj、 wj、 hj分别为第i个和第j个布入的三维矩形块的长度、宽度和高度。式①~③保证布局物体完全布入到布局空间中，式④~⑥保证两布入布局物体之间不能发生干涉。

1.2 基于吸引子法的布局过程

基于吸引子法的布局是布局构造启发式算法的一种。布局构造启发式算法主要从定序规则和定位规则两方面来进行考虑。

(1) 定序规则，即通过比较布局块的某一项或某几项属性来决定布局物体放入的顺序。常见的定序规则主要有按布局物体最长边递减、按布局物体体积递减、按布局物体可行域递减等顺序来对布局物体进行排列。本文采用体积递减的定序原则，来确定布局物体放入容器的顺序。

(2) 定位规则，即确定布局物体的摆放位置，本文采用吸引子定位函数结合布局块的几何可行域[13]计算出的数值来对布局物体进行定位。吸引子法可描述为在空间中设置一些吸引子，使布局物体由于其“吸引作用”而向吸引子移动，从而对布局物体进行定位。吸引子法具体见文献[14]。

待布长方体i的定位函数的具体形式为：

f(xi,yi,zi)为总的定位函数， ft(xi,yi,zi)为关于各个吸引子的定位函数，m为吸引子的个数，这里t=1、2、3、4表示吸引子分别位于布局空间 4个角点。

定位函数的参数有许多可供选择的参数值。对于不同的参数值，定位函数所得到的结果会不同，布局物体的布入结果更会完全不一样，故参数值的选择是布局求解的关键，也是本文的研究重点。显然，三维矩形布局问题的求解可化为一个 16维函数的优化问题。

2 布局遗传算法(BEGA)

2.1 算法流程

本文提出了基于蜜蜂进化选择算子的吸引子布局遗传算法(BEGA)。算法首先对优化的参数进行相应编码，并随机产生初始种群，然后计算个体适应度。算法以容器利用率达 100%和最大进化代数作为停止条件，若满足停止条件，则停止计算；否则，对个体进行选择、交叉、变异操作，每一过程都要计算适应度值，在整个过程中运用精英保留策略，直到满足终止条件，输出优化参数值和布局方案。

具体步骤如下：

Step 1.随机生成初始种群A(0)。

Step 2.实现布局过程。

Step 3.计算种群中所有个体的适应度，将最优个体(即第0代蜂王)保存到best中。

Step 4.如果满足停止准则，算法输出结果并停止运行；否则，继续。

Step 5.t = t+1。

Step 6.利用蜜蜂进化选择算子，从A(t−1)中选出父代个体。

Step 7.父代个体进行交叉运算产生种群B(t)。

Step 8.对B(t)执行变异操作，得到种群C(t)。

Step 9.实现布局过程。

Step 10. 计算种群C(t)中所有个体的适应度，将适应度最大的个体记为newbest。

Step 11.如果newbest的适应度值大于best的适应值，用 newbest代替 best；否则，用 newbest代替C(t)中最差的个体。得到第t代种群。

Step 12.转Step5。

2.2 算法参数选择

遗传算法由Holland于1975年首次提出，这种求解策略和方法通过选择、交叉、变异等操作模拟了自然界的生物演化过程。传统遗传算法在解决布局问题方面虽然有着较大的优势。但是也存在着一些不足，比如所采用选择算子产生新解种类较少，容易过早收敛。本文采用蜜蜂进化选择算子，是对传统遗传算法的改进。(本文所讲的传统遗传算法，是指采用传统轮盘赌选择算子的遗传算法)。

2.2.1 编码策略

采用实数编码的方式，每个染色体是变量为16维的解向量，并且每一个分量都是在有限的区间上进行定义，编码向量表示为：Vk(t)=(ω1，ω2，ω3，ω4，α1，α2，α3，α4，β1，β2，β3，β4，γ1，γ2，γ3，γ4)。式中：t为进化代数，k∈[1,m]且为整数，m为种群数。

2.2.2 适应度函数及初始化

算法的适应度函数取为布局容器的体积利用率f。显然，适应度值越大，布局容器的体积利用率就越大，个体的性能也就越好。

本文在产生初始种群时，采用如下方式进行：

(1) 人为指定部分个体的某些参数。例如，可假设其中一个个体的 ω1=1，ω2=0，ω3=0，ω4=0，此时相当于该个体当中就只有一个吸引子在起作用；或者可假设其中一个个体的α1=1，β1=0，γ1=0，此时相当于在第一个吸引子当中只有在X轴方向的吸引作用。

(2) 其余的个体由计算机随机产生。

2.2.3 选择算子

在进行选择配对个体时采用蜜蜂进化选择法[15]，其主要步骤如下：

(1) 选取种群中 A(t)的最优个体，与上一代蜂王比较，优胜者作为第t代蜂王，记为Queen。

与传统遗传算法相比，蜜蜂进化型遗传算法的主要特征有两个：

(1) 每对父本均包含蜂王(种群中的最优个体)。

(2) 在代进化过程中引入了随机外来种群，这个随机外来种群的规模由参数λ决定。

第一个特征加强了遗传算法的开采能力，后代主要依赖与最优个体的交叉操作产生。这同时降低了算法过早收敛的可能性；第二个特征帮助遗传算法搜索新的空间，引入随机种群提高了遗传算法的勘探能力。这两个特征使遗传算法的进化过程加快，并保持了优良的解。

2.2.4 交叉算子

交叉操作的具体过程如下：

对于两父代个体中第i个分量 Xi(k)， Xi(k+1)，通过交叉得到的个体分量为 Xi′(k)， Xi′(k+1)，那么：

其中，α有两种取值方法：

(1) α为(0,1)之间随机产生的数(此为后面算例及分析中所使用交叉方式)。

(2) /tTα= (t)为现在的进化代数，T为最大进化代数。

2.2.5 变异算子

对当前种群中的个体进行变异操作，是产生新解和维持种群多样性的有效手段。本算法采用非均匀变异，提供了两种变异策略。设新的个体中的分向量为()ikX′，则：

(1) 随机产生一个变异位，用新产生的(0,1)的数代替这个基因。

(2) 随机产生一个变异位，再在[0.5,1)上随机产生一个数β。设变异位处的基因为()ikX ，令用()ikX′代替()ikX (此为后面算例及分析中所使用变异方式)。

2.3 扰动策略

通过算例证明本文所提出算法更适合强异构问题。针对弱异构问题，本文通过对布局物体布入顺序的干扰，来改善算法对弱异构问题的解决能力。具体做法如下：

(1) 统计原算法结果当中体积较大布局物体的个数m；

(2) 将体积较大的布局物体个数控制在某个范围内，例如m/2；

(3) 当体积较大的布局物体的数目达到 m/2时，进行下一类型布局物体的布置。

3 算例及分析

算例1.此算例来自文献[9,16]，算例中所有箱子总体积小于容器体积，但最优解并不知道，即不确定是否能把所有箱子装入容器中。测试数据总共有15个类型，每个类型有100个算例，共1500个算例，分别对应不同的箱子种类。BR1-BR7是弱异构问题，BR8-BR15是强异构问题。每个类型当中的算例布局物体的种类是相同的。布局物体种类数3～100不等。BR1当中的算例异构性最弱，每个算例中只有3个类型布局物体，而BR15当中的算例异构性最强，每个算例有100个类型的布局物体。

对于这 1500个算例，很多学者进行了研究测试。这些算法有的只计算了BR1-BR7，有的只计算了BR8-BR15。图1 所示为BEGA和SPGA对BR算例的最大体积利用率变化图。(注：本文所有计算过程均在2 GB内存，2.79 GHz计算机上进行)

从图1可以看出，BEGA与SPGA相比变化走势大体一致。计算结果中有6组BEGA高于SPGA，6组持平，只有3组低于SPGA，表明BEGA相对SPGA有了改善。

表1给出了各算法对算例BR1-BR7的计算结果。表2给出了各算法对算例BR8-BR15的计算结果。表3给出了BEGA的计算结果(注：表1~2中数字指每类算例中100个算例的平均利用率)。

表1 各算法对弱异构问题的计算结果

表2 各算法对强异构问题的计算结果

表3 BEGA的计算结果

通过对表 1~3的数据观察、分析可以看出，BEGA相对其他算法有了提高。BEGA在BR14和BR15这两类算例中的表现比较出色，得到了最大值。计算可得BR1-BR7最大值项和最小值项方差分别为34.79、127.92，BR8～BR15相应方差为6.94和9.8。由此可得，BEGA随着算例异构性的增强，不仅计算结果越来越好，而且计算结果的稳定性也不断增加。也就是说本文的BEGA更适合解决强异构问题。

考虑到BEGA不太适合解决弱异构问题，本文尝试应用扰动策略对其进行改善。BEGA与扰动策略对BR1～BR7算例体积利用率的平均值、最大值及最小值的对比如表4所示。

从表4中可以看出，扰动策略对于弱异构问题有了不同程度的改善，证实扰动策略可以提高算法对弱异构问题的解决能力。

算例2.本算例是由二维C类算例改进而来，在原有算例的基础上，对布局空间和布局物体都增加了同样的高。并与文献[17]提出的粒子群算法进行了比较，比较结果如表5所示。

表4 BEGA与扰动策略的对比

表5 C类算例布局利用率的对比(%)

由表5中的数据可以看出，BEGA对C类算例的计算结果有9个算例优于文献[13]、[17]的结果，有5个算例与文献[17]中的结果持平。本文的平均利用率较文献[17]提高了1.51%。

4 结 束 语

本文按照体积递减对布局物体进行定序，然后利用吸引子定位函数结合布局块的几何可行域对布局物体进行定位，最后用蜜蜂进化型遗传算法对基于吸引子法的定位函数参数进行优化。论文对一些算例进行了计算，通过算例结果可以看出BEGA更适合于强异构布局问题，并且其相对于传统布局遗传算法(SPGA)等有了改进。另外，本文提出的一种扰动策略对解决弱异构问题有了改善。本文布局物体的定序规则固定，若改变定序规则，则可能提高布局利用率空间。因此如何确定合理的定序规则将是我们今后的研究工作内容之一。

[1] Sweeny P E, Paternoster E R. Cutting and packing problems: a categorized, application -orientated research [J]. Journal of Operation Research Society, 1992, 43(7): 691-706.

[2] Dowsland K A, Dowsland W B. Packing problems [J]. European Journal of Operational Research, 1992, 56(1): 2-14.

[3] Zhang Defu, Peng Yu, Leung S C H. A heuristic block-loading algorithm based on multi-layer search for the container loading problem [J]. Computers & Operations Research, 2012, 39(10): 2267-2276.

[4] Leung S C H, Zhang Defu, Zhou Changle, Wu Tao. A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem [J]. Computers & Operations Research, 2012, 39(1): 64-73.

[5] Burke E K, Hyde M, Woodward J. A genetic programming hyper-heuristic approach for evolving two dimensional strip packing heuristics [J]. IEEE Transactions on Evolutionary Computation, 2010, 14(6): 942-958.

[6] Cintra C F, Miyazawa F K. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation [J]. European Journal of Operational Research, 2008, 191(1): 61-85.

[7] 杨 林, 陶庆云, 全惠云. 求解矩形物体布局问题的分布评估算法[J]. 湖南师范大学自然科学学报, 2007, 30(3): 42-45.

[8] Bischoff E E, Ratcliff M S W. Issues in the development of approaches to container loading [J]. Omega, 1995, 23(3): 377-390.

[9] Gehring H, Bortfeldt A. A genetic algorithm for solving the container loading problem [J]. International Transactions in Operational Research, 1997, 4(5-6): 401-418.

[10] Bortfeldt A, Gehring H. A tabu search algorithm for weakly heterogeneous container loading problems [J]. OR Spectrum, 1998, 20(4): 237-250.

[11] Lim A, Rodrigues B, Yang Y. 3-D container packing heuristics [J]. Applied Intelligence, 2005, 22(2): 125-134.

[12] Moura A, Oliveira J F. A GRASP approach to the container loading problem [J]. IEEE Intelligent Systems, 2005, 20(4): 50-57.

[13] 朱丽苹, 王金敏. 基于空间分割的求解布局几何可行域的算法[J]. 天津职业技术师范大学学报, 2012, 22(2): 30-33.

[14] 王金敏, 杨维嘉. 动态吸引子在布局求解中的应用[J].计算机辅助设计与图形学学报, 2005, 17(8): 1725-1730.

[15] 孟 伟, 韩学东, 洪炳熔. 蜜蜂进化型遗传算法[J].电子学报, 2006, 34(7): 1294-1300.

[16] Davies A P, Bisschoff E E. Weight distribution considerations in container loading [J]. European Journal of Operational Research, 1999, 114(3): 509-527.

[17] Qi Yang, Wang Jinmin. The particle swarm optimization algorithm for solving rectangular packing problem [J]. Advanced Materials Research, 2011, 186: 479-483.

A Genetic Algorithm for Packing Problems Based on Bee Evolutionary Selection Operator

Wang Jinmin1,2, Zhu Liping2, Zhen Shigang2
(1. Tianjin Key Laboratory of High Speed Cutting & Precision Machining, Tianjin 300222, China; 2. School of Mechanical Engineering, Tianjin University of Technology and Education, Tianjin 300222, China)

Three dimensional rectangular packing is a NP-hard problem, which is often solved by heuristic algorithms. In this paper the sequencing rules is determined by the volume of packing items, the positioning rules are determined by attractor function with the geometry feasible region of packing items in packing space. Then the parameters in the attractor function are optimized by bee evolution genetic algorithm (BEGA), the new packing genetic algorithm is formed. Finally, different benchmarks are carried out, and the paper proves the validity of the algorithm by comparing with the traditional packing genetic algorithm (SPGA) which chooses the standard proportional selection as its operator, etc.

packing problem; heuristic algorithm; attractive factor; bee evolutionary

TP 391

A

2095-302X(2014)05-0690-07

2013-11-21；定稿日期：2013-12-13

国家自然科学基金资助项目(60975046)

王金敏(1963–)，男，河南舞阳人，教授，博士。主要研究方向为智能布局、计算机图形学。E-mail：wang_jin_min@163.com