本文主要是介绍深度学习结合树搜索求解集装箱预翻箱问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

论文阅读笔记，个人理解，如有错误请指正，感激不尽！该文分类到Machine learning alongside optimization algorithms。

01 container pre-marshalling problem (CPMP)

对集装箱进行预翻箱整理,使得集装箱的堆放顺序符合取箱顺序,以尽量减少取箱装船过程中的翻箱次数。如下图所示，出箱顺序为1234……6，灰色的集装箱2、4、5挡住了先要出来的集装箱1、3，因此需要不断移动灰色的集装箱到别处去，直到不挡住别的箱子。这样1可以顺利先出，而后是2，接着是3……目标是最小化移动集装箱的次数。

02 tree search中的DNN

树搜索大家不会陌生，深度优先、广度优先、分支定界等都属于树搜索策略。将Deep learning集成进tree search中，用于求解CPMP。利用深度神经网络(classification DNN)在分支选择上进行预测，给出分支的“好坏”，随后按照分支的“好坏”（好的分支得到最优解的可能性更大）继续搜索。同时，利用深度神经网络(regression DNN)对分支节点的lower bound进行预测，剪掉不必要的分支。

下图解释了搜索过程中的分支选择决策，以c节点为例，通过将c节点表示的问题和解信息输入到DNN中，经过隐藏层，在输出层通过一个softmax函数给出三个child节点e、f、g的概率（搜索该分支最终得到最优解的概率）。

通过DNN预测该节点的lower bound也是类似的，只不过该网络的输出只有一个数值，即当前节点的得到完整solution的cost（有可能overestimate或者underestimate）。

下图展示了预测分支(classification DNN)的具体网络形态。该神经网络依赖于算例的size，假如训练的算例size为n，那么只能预测size为n以及小于n的算例（通过设置虚拟点）。每一个集装箱位都是一个节点，从而构成了DNN的输入层。在输入层之后通过weight sharing，给每一个tier分配一个权重，\(w_i\)。这样就给每一个container分配了权重，比如第3层的container，对应的权重就是\(w_3\)。最终输出层输出每一个movement的概率，比如\(y_{2,1}\)表示的将stack 2上的container移动到stack 3上。

关于模型训练，样本通过精确算法求解获得，无法精确获得的，则是通过启发式算法获得近似解。

03 搜索策略

将上面的DNN应用到tree search中，搜索策略有好几种，作者实现了三种结合DNN的树搜索策略： Depth first search、Limited discrepancy search和Weighted beam search。前两个的框架如下：

DNN在这些搜索框架中起到的作用主要有：

• 预测各个分支得到最优解的概率，令框架优先搜索概率高的支路。
• 预测节点的lower bound，从而进行必要的剪枝。不过预测lower bound是搜索树深度为k的倍数才会执行一次，因为全部执行需要消耗大量的时间。

04 实验结果

通过和目前最好的启发式算法（BRKGA）进行对比，通过数据集G1训练的模型为DLTS-G1，通过数据集G123训练的模型为DLTS-G123。Gap(%)表示和最优解的对比。从下表可以看出，虽然BRKGA有着更快的求解速度，时间大概是DLTS的一半，但是得到的Gap却是DLTS的3到23倍不等。

05 参考文献

[1] Hottung A , Tanaka S , Tierney K . Deep Learning Assisted Heuristic Tree Search for the Container Pre-marshalling Problem[J]. Computers & Operations Research, 2019.

这篇关于深度学习结合树搜索求解集装箱预翻箱问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！