基于双层启发式遗传算法的三维装箱问题

于明正， 徐 斌， 陈 佳

(大连海事大学航运经济与管理学院，大连 116026)

三维装箱问题是一类多模式资源受限项目调度(non-deterministic polynomial, NP-hard)问题[1-2]，它通过研究如何在给定箱容器内建立组合优化方案从而达到优化目标，对于物流货物装载、资源分配、多处理器任务调度等方面的研究具有深远的学术前景和重要的实际应用价值。由于装箱算法的计算结果是不可量化的，所以国内外的学者常采用启发式算法来计算接近于最佳方案的整体最优解[3-5]。

George等[6]最先提出以空间分割为原则的启发式算法，建立了一种标准的装箱秩序，张德富等[7-9]以此为基础，受实际生产活动中砌墙原理的影响提出新的启发式算法，通过调入“参考线”这一概念来引导整个箱容器的装填过程。这种算法可以降低使用以空间分割原则的启发式算法进行装填时，因为没有引导约束而产生的局部装填混乱，从而更加接近真实的最优解。但是这种算法的最终结果依赖于初始装箱顺序，如果初始装箱顺序的质量不高，很容易陷入局部最优的情况。翟钰[10]结合遗传的概念提出了混合遗传算法，这种算法减小了初始解对装箱方案的影响，但算法稳定性极差。由于在遗传演化过程中未能保留优秀的装箱序列，导致对下一代可行解的搜索缺少信息指引，所以每次运算后得到的空间利用率差距明显。

基于以上问题，借鉴二层规划的思想[11]，根据三维装箱问题的特点与遗传算法的规律对混合遗传算法进行改进，提出一种新的遗传演化方法，分别以广度和深度两种不同的搜索方向将整个算法分为两层进行，尽可能综合遗传算法的优势来提高装箱方案的质量。通过两种不同的遗传层解决算法中出现的局部最优和稳定性问题，从而缩小最优解与算法最佳方案的差距，提出双层启发式遗传的思路来解决三维装箱问题。

1 问题描述与数学模型

讨论的三维装箱问题基于以下几个前提条件[12]：

(1)箱容器与箱体均为长方体。

(2)箱体的尺寸不同且均小于箱容器尺寸。

(3)箱体的摆放方向与箱容器边界方向平行，有两种摆放形式。

(4)忽略已放置箱体之间的空隙。

根据以上假设及问题描述，记符号li、wi、hi表示箱体i(i=1, 2, 3, …,n)的长、宽、高；L、W、H表示箱容器的长、宽、高；αi表示箱体i的放置状态，αi=0代表箱体i没有被装入箱容器中，αi=1代表箱体i已被装入箱容器中，同时存在坐标(xi，yi，zi)表示箱体i在箱容器中的放置点位置，建立基于双层启发式遗传算法的三维装箱问题数学模型。

目标函数的建立：

(1)

约束条件：

(2)

(3)

(4)

(5)

2 算法设计

2.1 基于三维装箱的启发式算法

基于三维装箱的启发式算法大体上是以空间分割为原则的装箱思想结合层的概念并加入“参考线”来限制装箱趋势而形成的启发式算法。其中，算法的核心部分是描述箱体的装入及其装入后产生的3个独立空间。

假设箱容器内坐标为(0, 0, 0)处放入第一个箱子，箱子的长宽高分别为a1、b1、c1，如图1所示，根据空间分割原则，下一个箱子的可放置点有3个，分别为(0, 0,c1)、(0,b1， 0)、(a1， 0, 0)。如果第二个箱子被放置在(0, 0,c1)处，且长宽高分别为a2、b2、c2，根据空间分割原则，第三个箱子的可放置点就有5个，分别是(0,b1， 0)、(a1， 0, 0)、(0, 0,c1+c2)、(0,b2，c1)、(a2， 0,c1)。以此类推可知，假设一个长宽高为a、b、c的箱子选取了坐标为(x，y，z)的可放置点，那么实际上就是删掉了可放置点(x，y，z)，增加了(x，y，z+c)、(x，y+b，z)、(x+a，y，z)3个新的可放置点[13-16]。

图1 空间分割示意图Fig.1 The diagram for spatial segmentation

综合上述思路并引入“参考线”，以层的概念对混合启发式算法进行以下伪代码形式的描述，如算法1所示。

算法1：混合启发式装箱算法

Rx← 0，Rz← 0，iGroup← {(0,0,0)}，bGroup←BoxList;

fort← 0 tobGroup.lengthdo

fors← 0 toiGroup.lengthdo

if 箱子bGroup[t]可以放入位置iGroup[s]中 then

pGroup←bGroup[t]，iGroup[s];

对iGroup，Rx，Rz进行一次更新；

break;

end if

end for

ifRx为0或达到极值 then

if 箱子bGroup[t]可放入位置(0, 0,Rz)中 then

pGroup←bGroup[t]，(0, 0,Rz)；

对iGroup，Rx，Rz进行一次更新；

else

Rz取值范围内最大化；

t←t-1；

continue；

end if

else

fors← 0 toiGroup.length且x达到极值y为0 do

if 箱子bGroup[t]可放入位置iGroup[s]中 then

pGroup←bGroup[t]，iGroup[s];

对iGroup，Rx，Rz进行一次更新；

break;

end if

end for

Rx取值范围内最大化；

t←t-1；

continue；

end if

end for

2.2 二层规划与混合遗传算法

2.2.1 混合遗传算法的改进

利用新遗传演化方法设计的混合遗传算法计算出的最佳装箱方案符合装箱问题的最基本需求，但经过多次实验发现，装箱方案的前半部分序列几乎不会改变。这种情况意味着算法的最佳方案很大程度上取决于初始可行解的状态。在此基础上详细地对三维装箱过程进行分析，利用箱体装入后染色体编码所表现的特点可以进一步在遗传算法的结合上提出改进方法，从启发式算法的装填思想和生活常识来看，一个装箱顺序的优劣与否并不是由单独一个箱体的位置来决定的，一段连续的装箱序列或者说一部分箱体编码区间才是决定整个装箱效果是否优秀的关键。所以如果在混合遗传算法的基础上，增加一层可以提高搜索广度的遗传迭代，这样可以缩短得到的最佳装箱方案与最优解之间的差距。这样就用到了二层规划的概念，上层遗传使用搜索范围不受限制的方法找到一个基因良好的可行解，在上层的基础上加入上述混合遗传算法作为下层遗传进行深度搜索，找到更优秀的可行解。

2.2.2 二层规划策略

图2所示为基于双层启发式遗传算法流程。上层遗传使用选择、交叉、变异等不受限的遗传演化形式，这是为了加大可行解的搜索范围，找到一个足够优秀的可行解；下层遗传在上层遗传的基础上对这个可行解进行有目的的多层次变异，经过迭代进化得到最优解。从宏观上对算法进行分析，上层遗传是面向广度的搜索，而下层遗传是面向深度的搜索，结合两层遗传的特点综合使用可以找到最合适的装箱方案。

图2 双层遗传算法流程Fig.2 Flow chart for double-layer genetic algorithm

2.3 下层遗传算法的设计

2.3.1 编码预处理与染色体编码

在染色体编码之前，要对箱体编码进行相关的预处理：将n个箱体按照体积由大到小的顺序依次编码，i=1, 2, 3, …,n。

染色体在编码时主要考虑箱体装入顺序的约束，一个染色体对应一个编码长度为n的基因段S1～n=(S1，S2，S3， …,Sn)，其中Sk表示第k位放置次序上箱体的编号i，一个位置次序k对应一个箱体i并且S1～n内的基因段是不可重复排列的。对于遗传算法而言，一个编码长度n的染色体S=(S1，S2，S3， …,Sn) 表示为三维装箱的一个箱体组合装入过程。

2.3.2 适应度函数

要求在满足条件约束的情况下尽可能多地装入箱体，要求箱容器的空间浪费最少，所以决定装箱方案好坏的因素就是箱容器的空间利用率，空间利用率越大装箱效果越好。如式(6)所示，适应度函数F直接选取目标函数来使用。

(6)

2.3.3 选择算子

遗传过程使用轮盘赌选择法进行选择算子。不同于传统方法利用适应度占比进行概率选择，各个染色体的适应度差值并不明显，因此在计算概率占比之前先对适应度进行处理，已知染色体Si的适应度为f(Si)，其中最大适应度为maxF，最小适应度为minF，设置一个浮动误差值∂，处理后的f(Si)为

(7)

假设遗传算法的种群数量为M，染色体Si的适应度为f(Si)，计算染色体Si的选择概率Pi为

(8)

利用选择概率计算累积概率Qk，即

(9)

轮盘赌选择法详细流程可以描述为随机生成一个0～1的小数r，若r≤Q1，则染色体S1被选中，若Qk-1

2.3.4 变异算子

新的遗传演化方法的特殊性主要体现在变异算子上，如图3所示，在变异前要先确立有效装箱区和无效装箱区，选定一个可行解编码次序按照装箱算法依次放入，直到出现无法放入箱容器内的箱体则停止放入，该箱体之前的次序则为有效装箱区，其余的次序则都是无效装箱区。

图3 有效装箱区示意图Fig.3 Effective packing area

如图4所示，当变异开始时随机选取有效装箱区的一位基因A和无效装箱区的一位基因B，基因A放入无效装箱区基因B的位置，有效装箱区内基因A之后的基因依次向前移动一位，基因B放入有效装箱区的最后一位。此后对新的有效装箱区再运行一遍装箱算法并评估长度，如果与之前的有效装箱区长度一样，则再从无效装箱区中随机选取一位基因放入有效装箱区的尾部，重复上述步骤直至有效装箱区的长度无法再增加，则一次完整的变异过程结束。

图4 变异演示Fig.4 Variation diagram

2.4 上层遗传算法的设计

2.4.1 算法描述

上层遗传迭代的目的是为了增大染色体出现新相性的概率，从算法逻辑上来说，这种策略并没有带有优秀的基因片段，且变异的过程缺乏完备性。下层遗传迭代的目的是为了保留染色体大体组成的同时找到更加优秀的染色体特性并传递到下一代中。这种策略可以保留可行解大部分的基因形式，从算法逻辑上来说，它是在一定基因基础上的进一步深化搜索。本文中的两层遗传编码形式和适应度函数一致，上层遗传与下层遗传的不同主要表现在遗传演化方法上，接下来对上层遗传算法进行描述。

2.4.2 交叉算子

上层遗传迭代将会用到交叉算法，由于染色体编码是利用箱体编号组成的一组装箱顺序集合，对于这样的编码来说，组编码之间的差异主要体现在基因的顺序排列上，要保证组编码内基因的互异性的同时又能达到交叉的目的，因此采用能够最大限度保留父辈基因相对次序的顺序交叉(order crossover, OX)算法进行交叉。根据以往诸多论文和理论的证明，这种交叉算法是可以满足遗传完备性要求的。之所以会在第一层遗传上使用交叉是因为要最大限度地保证可行解的广度，摆脱遗传迭代过程中陷入局部最优的状态。OX交叉算子的原理如图5所示。

图5 OX算法原理Fig.5 OX algorithm

2.4.3 变异算子

上层遗传使用多次对换变异的方法，当变异发生时，对指定染色体内的随机两个不同的基因进行位置交换，并且随机进行多次上述变换变异出新的染色体。每一次变异过程都是随机选取可变异位置且只变异一次。

3 实例计算与结果实现

利用表1所示的测试数据集对上述算法进行验证与分析，其中，在算法计算过程中需要设置的各个参数值如下：箱体数量goodsNum=200，上层遗传运行代数MAX_GEN1=500，下层遗传运行代数MAX_GEN2=500，种群规模scale=30，交叉概率Pc=90%，变异概率Pm=90%，浮动误差值∂=0.005。本次实验选取长、宽、高分别为3、2、1 km的箱容器，要求将表1描述的箱体数据装入箱容器后达到最优的空间利用率。箱体的简易装载方案如表2所示，基于双层启发式遗传算法计算后的结果如表3所示，遗传过程中各代的适应度最优值分布如图6所示，经过上层遗传迭代后，可以计算出的最佳空间利用率为89.579%，继续对这个装箱方案进行下层遗传迭代，空间利用率的数值可达到91.245%，装箱方案达到进一步的优化。

表1 测试数据Table 1 Text data

表2 装载方案Table 2 Loading solution

表3 三维装箱计算结果Table 3 3D loading calculation result

图6 适应度最优值分布Fig.6 Fitness optimal value distribution

如表4所示，利用表1的数据分别计算各个算法下的空间利用率。其中，A1是文献[7]提出的启发式算法，A2是结合本文提出的遗传演化方法设计的混合遗传算法，A3是文献[10]提出的混合遗传算法，A4是本文所提出的算法。A1没有引入机器学习的概念，而且一旦初始装箱顺序固定，最终的装箱方案也就无法改变；A2在此基础上引入了遗传算法，但是与初始装箱顺序相比，装箱方案中装箱序列的前5位没有变化，这说明遗传过程很容易陷入局部最优，而本次实验所用的初始解预先会按照体积和长宽高排序，所以当出现初始解的质量不高的情况时，算法可能会产生隐患；A3算法的遗传演化方法与A2不同，可行解的搜索是偏向广度的，装箱方案不受初始解的影响，但从结果来看，这种算法的稳定性不高，可行解的搜索过程缺少导向性，最终方案的质量依赖遗传代数；A4算法引入二层规划的概念，设计出两种搜索方向不同的遗传演化方法。实验结果表明，利用本文的算法进行三维装箱的效果是最好的。

表4 各类算法对比分析Table 4 Comparative analysis of various algorithms

实验可以使用Three.js架构并结合Java Web等相关技术对实验方案进行对应的三维可视化实现，联系实际的信息管理系统拓展出对某个领域的三维可视化功能，提升整个信息管理系统的综合竞争力。对本次实验结果进行三维可视化结果如图7所示，从图中可以看出，该方案可以满足装箱问题的最基本原则。

图7 可视化结果Fig.7 The result of visualization

4 结论

针对混合遗传算法在装箱过程中因为遗传演化方法的缺陷导致局部最优和算法稳定性差的问题，结合二层规划的思想，通过建立两类遗传层来提高最优解搜索的广度和深度，对局部最优和稳定性的缺陷进行有效规避，进而提升最终装箱方案的质量。实验结果表明，双层启发式遗传算法要优于其余的混合遗传算法。同时可以将算法理论和结果用可视化技术描述出来，这样可以为三维装箱问题结合现代化管理思想实现规范的商业平台模式提供一定的理论基础。