Page 21 - 《软件学报》2021年第12期
P. 21

阳名钢  等:求解二维装箱问题的强化学习启发式算法                                                        3685


         的石材,箱子则对应待切割的完整石板,目标是使石材的利用率更高.由于装箱问题广泛地存在于各个领域,高
         效的求解算法有助于公司节省材料和减少资源浪费,提高生产和工作效率,帮助更合理利用有限的资源.多年
         来,二维带形装箱问题(2DSPP)被众多国内外学者研究以获得更快更优的解决方案.与其他组合优化问题一
                                                                          [1]
         样,2DSPP 可通过精确算法、近似算法(启发式和元启发式)或者混合算法等来求解 .
                                                                                        [2]
             精确算法可以找到问题的最佳解决方案,但在较大的问题实例上通常需要花费大量的时间.Hifi 基于分支
         定界过程提出了一种精确算法用于解决带状切割和包装问题,该算法在可接受的执行时间内解决一些中小规
                              [3]
         模问题实例.Martello 等人 提出了一种新的松弛方法,该方法可产生良好的下界,基于此下界构造出较好的启
                                                                                  [5]
                             [4]
         发式算法.Kenmochi 等人 设计了一个基于分支规则和边界操作的分支定界算法.Côté 等人 提出了一种基于
         Bender 分解的精确算法,该方法可以在有限的计算时间内解决中小规模的基准实例.大多数精确算法都是基于
         分支定界策略或者混合整数线性规划,但是因为装箱问题的复杂性,当问题实例增大的时候,不可避免地导致计
         算量的指数级增长,耗时增加.故大部分精确算法仅在小规模的数据集上表现良好,对于解决大规模的问题实
         例,更多的研究重点则倾向于使用近似算法来解决.
             启发式算法虽然无法保证获得的解是最优的,但是它能在合理的时间范围内给出良好的解.启发式被认为
         是解决大规模组合优化问题的有效解决方案,因此在装箱领域中十分流行.大多数启发式算法都包含构造性过
                                                               [6]
         程,即每次将一块添加到现有的部分解决方案中.1980 年,Baker 等人 为了构造合理的装填顺序,就提出了左下
         (bottom-left,简称 BL)启发式算法.该算法每次取出列表中的第 1 个矩形,放入容器最左最低的可用空间.Chazelle
             [7]
         等人 对 BL 算法进行了改进,提出了左下填充算法(BLF).算法首先确定即将被放入的矩形合适的所有位置,然
                                    [8]
                                                                                    [9]
         后选择其中最低位置.Huang 和 Liu 提出了基于欧氏距离的确定性启发式求解算法.Burke 等人 提出了最佳填
         充算法(BF),该算法会动态地在列表中搜索放入可用空间的最佳候选矩形.Leung 等人                         [10] 提出了适合度策略,该
         策略用于决定哪个矩形要填充到指定位置.
             元启发式算法常见的有模拟退火(SA)、遗传算法(GA)、蚁群算法(AC)和禁忌搜索算法(TS)等,大多数研究
         者会结合构造性启发式和元启发式算法来解决二维带形装箱问题.Jakobs                        [11] 在提出的遗传算法中,使用一个特
         定的交叉算子和变异算子来交换某些元素的位置,并使用 BL 算法解码解决方案.Hopper 和 Turton                        [12] 混合 BL 方
         法与 3 种元启发算法(遗传算法(GA)、模拟退火算法(SA)、朴素演化(NE))和局部搜索启发式算法.其他作者                            [13,14]
         也提出了多种结合遗传算法的方法来解决 2DSPP.He 等人                   [15] 提出了动态归约算法求解面积最小的装箱问
         题.Wei 等人  [16] 开发了一种基于配置文件的构造启发式算法的禁忌搜索算法.Alvarez-Valdés                 [17] 提出了一种针对
         带状包装问题的贪婪随机自适应搜索程序(GRASP).Zhang 等人                [18] 提出了基于随机局部搜索的二分搜索启发式
         算法.Leung 等人  [19] 提出了两阶段智能搜索算法(ISA),该算法基于简单的评分规则选择矩形放入,该评分策略中
         设置了 5 个分值(0~4).在简单随机算法(SRA)         [20] 中使用了具有 8 个分值的评分规则,并引入了最小浪费优先策
         略.Chen 等人  [21] 提出了新的算法框架 CIBA,提出了角增量的概念,只包含了 4 个评分值,用于在选择矩形的时候
         评价矩形.Chen 等人     [22] 基于评分规则以及角增量的基础上,再结合分层搜索的思想,提出了一种混合启发式算
         法.这些不同的评分规则设计的大致思路都是想实现更平坦平滑的布局,以此来减少空间的浪费.值得注意的
         是: Chen 等人  [22] 研究了解的不同初始化策略,如贪心策略,最后在 6 种贪心策略中选择最好的初始序列,取得了
         不错的效果.
             深度学习算法在分类、回归任务和图像识别等方面取得了非凡的成功,但是将机器学习用于组合优化问题
         的求解,进展仍然缓慢.1985 年,就有学者在组合优化问题中使用神经网络用于优化决策,该论文使用 Hopfield 网
         络解决小规模的旅行商问题(TSP)          [23] .组合优化问题大部分都是序列的决策问题,例如旅行商问题就是求解访
         问城市顺序的问题.Vinyals 等人         [24] 设计了一种非常适合用于求解组合优化问题的神经网络,指针网络
         (PointerNetwork,Ptr-Net),该模型使用注意力机制   [25] 作为指针来选择输入序列中的某一个元素输出.作者将该模
         型应用在解决旅行商问题上.Bello 等人          [26] 采用了 Actor-Critic 算法来训练 Ptr-Net 并在多达 100 个节点的 TSP
         问题上获得最佳结果.受到 Bello 等人          [26] 工作的启发,Nazari 等人 [27] 提出了一个强化学习解决车辆路径问题的
         端到端框架,该框架中简化了指针网络,采用 Actor-Critic 算法训练模型.Kool 等人                 [28] 提出了基于注意力机制的
   16   17   18   19   20   21   22   23   24   25   26