基于超启发式算法的自动化码头出口箱箱位分配优化方法

摘要

一种基于超启发式算法的自动化码头出口箱箱位分配优化方法，通过高级控制策略进行参数初始化、问题确认、强化学习状态计算、通过强化学习状态计算动作概率和根据动作概率选择合适的算法，然后通过计算强化学习状态及适应度后判断是否达到迭代次数并输出箱位分配方案及新的指标。本发明从实际出口箱箱位分配的堆场接力、多箱区协同特性出发，将强化学习和深度学习用作高级选择策略，将启发式算子、智能算法用作低级启发式方法，以自适应地生成高质量的箱位分配方案，提高自动化集装箱码头出口箱作业效率。

说明书

技术领域

本发明涉及的是一种自动化控制领域的技术，具体是一种基于超启发式算法的自动化码头出口箱箱位分配优化方法。

背景技术

在堆场作业中，出口箱的箱位分配方案的优劣将会对堆场吞吐能力有直接影响，在出口箱作业中，集装箱由外集卡运输进入堆场，经过陆侧入场作业、堆场存储、海侧出场作业三个阶段，将于海侧由AGV运输离开堆场进行装船作业。由于自动化集装箱码头中堆场的长度较长，且场桥之间无法相互跨越，为避免两台场桥单独执行入场及出场作业导致作业区间较长，降低整体效率的情况，采用两台场桥接力的作业方式，即在堆场中部设立中转区，先由路侧场桥将出口箱运输至中转区，再由海侧场桥运输至目标箱位。该接力操作较为复杂，同时需要考虑箱位选择平衡，从而减少阻塞情况。

若将同一批出口箱集中堆放在同一箱区，该箱区难以完成短时间内密集的出口箱运输任务，将导致总作业时间大大增加。为最小化总作业时间并最大化工作效率，自动化集装箱堆场采用多箱区协同的方式，与传统堆场按类别堆放集装箱的规则不同，自动化码头堆场将该批集装箱分散于多个箱区中，尽可能平衡每个箱区的任务数目，以发挥箱区数量大的优势，满足出口箱要求。

现有箱位分配技术中，一部分关注的是具体箱位的选取，并采用精确求解、调度规则或智能算法加以解决。另一部分则关注箱区或倍位的选择，通过和其他问题的集成形成全局中最优方案。但是由于自动化集装箱码头出口箱箱位分配问题的规模较大且复杂，提升问题的难度，当前的解决方案并不能完全满足集装箱码头整体高效作业的需求。另外，在考虑上述提到的堆场接力以及多箱区协同特性的情况下，出口箱箱位分配问题将会变得更加复杂。

发明内容

本发明针对现有箱位分配方法存在的上述不足，提出一种基于超启发式算法的自动化码头出口箱箱位分配优化方法，从实际出口箱箱位分配的堆场接力、多箱区协同特性出发，将强化学习和深度学习用作高级选择策略，将启发式算子、智能算法用作低级启发式方法，以自适应地生成高质量的箱位分配方案，提高自动化集装箱码头出口箱作业效率。

本发明是通过以下技术方案实现的：

本发明涉及一种基于超启发式算法的自动化码头出口箱箱位分配优化方法，通过高级控制策略进行参数初始化、问题确认、强化学习状态计算、通过强化学习状态计算动作概率和根据动作概率选择合适的算法，然后通过计算强化学习状态及适应度后判断是否达到迭代次数并输出箱位分配方案及新的指标。

所述的高级控制策略，采用基于策略的强化学习算法DPPO，根据迭代以及场景状态智能选取合适的启发式算法进行问题求解。

所述的参数初始化，即初始化超启发式算法的更新前后的演员网络、评论家网络、不同的启发式算法、最大回合数、回合中的最大步数、批尺寸、中心线程、多个工人线程、线程同步变量参数。

所述的问题确认是指：随机生成新的出口箱箱位分配问题，具体包括：箱区数量、箱区倍位数量、出口箱任务数量。

所述的强化学习状态是指：低层启发式算法所模拟生物种群中的个体得分差异，计算操作为：

所述的动作概率是指：强化学习过程的每个决策中所计算用于判断采用何种低级启发式算法的随机数，该操作采用ε-贪婪的方法来平衡动作选取的探索和利用，于每个决策时刻生成一个随机数。

所述的选择合适的算法是指：根据生成的动作概率大于固定概率ε时，则以贪婪原则选择动作，否则随机选择以下任一算法：局部搜索算子：破坏算子、累加算子、交换算子、翻转算子，全局搜索算子：破坏算子、翻转算子、移位算子以及智能算法：布谷鸟算法、遗传算法、粒子群算法、人工蜂群算法。

所述的适应度，即目标函数值，具体指出口箱箱位分配问题的翻箱率，通过计算翻箱的操作数/出口箱任务总数得到。

所述的迭代次数，采用但不限于最大计算时间或一般根据算例大小有不同修改，如3个箱区、15个倍位的堆场、60个出口箱任务的时间可设置为180s，主要用于限制算法的求解时间。

所述的箱位分配方案包括：出口箱所在堆场箱区的具体位置。

所述的新的指标是指：超启发式算法在上述迭代最大时间内所能达到的最优秀的指标值，即

技术效果

与现有技术相比，本发明考虑码头场桥接力、多箱区协同等特性，短时间内给出能够有效提高堆场作业效率的箱位分配方案，为自动化集装箱堆场提供决策支持。

附图说明

图1为自动化码头出口箱箱位分配优化方法流程图；

图2为高层强化学习控制策略流程图(对应图1中的步骤3至步骤8)；

图3为算法迭代过程；

图4为出口想任务增加下算法性能对比；

图5为倍位数量增加下算法性能对比；

图6为箱区数量增加下算法性能对比；

具体实施方式

如图1所示，为本实施例涉及的一种基于超启发式算法的自动化码头出口箱箱位分配优化方法，通过高级控制策略进行参数初始化、问题确认、强化学习状态计算、通过强化学习状态计算动作概率和根据动作概率选择合适的算法，然后通过计算强化学习状态及适应度后判断是否达到迭代次数并输出箱位分配方案及新的指标。

本实施例中基于强化学习的超启发式算法步骤对应图1中的步骤1至步骤8，的具体步骤为：

I)对当前问题的输入进行处理，得到问题的矩阵化表征；

II)对不同启发式算法以及相应的种群进行初始化；

III)根据种群及当前问题特点计算强化学习的状态参数；

IV)应用DPPO算法计算当前的动作概率；

V)根据动作概率确定采取的启发式算法；

VI)应用选定的启发式算法开展迭代，优化解决方案，并生成优化后的种群；

VII)重复上述两步，直到满足终止条件，即达到最大迭代次数，后输出有效的箱位分配方案。

本实施例涉及的一种基于超启发式算法的自动化码头出口箱箱位分配优化方法，包括：问题映射、低层启发式算法、高层强化学习控制策略。

问题映射层面对应图1中步骤1与步骤2，解决低层启发式算法与高层强化学习算法之间的环境定义与计算以及箱位分配问题与启发式算法之间的编码与解码流程

低层启发式算法为图1中步骤6中的若干算法或算法组合，主要包含了用于求解箱位分配问题的多种局部搜索算子、全局搜索算子、智能算法，组成备选的启发式算法库，所使用的启发式算法以及具体描述如表2所示。

表2低层启发式算法

如图2所示，为本实施例中基于强化学习的超启发式算法中的高层强化学习控制策略流程，包含针对箱位分配问题特点设计的强化学习算法，包括：状态、动作、回报三个操作。

本实施例高层强化学习中的状态操作对应图2中的步骤1，该操作中计算个体得分差异，该状态将在每一步迭代过程中启发式算法对种群进行更新后被计算，用于下一步迭代的指导，种群中个体ind

本实施例高层强化学习中的动作操作对应图2中的步骤2至步骤4，该操作用于在强化学习过程的每个决策时计算动作概率，并选择下一步进行迭代的启发式算法。其中a＝{a

本实施例高层强化学习中的回报操作对应图2中的步骤5，该操作用于定义强化学习策略的目标，被定义为最终状态于初始状态之间的评价方案差值，以评价策略的优劣。

本实施例高层强化学习中所用神经网络以演员-评论家网络为基础。在演员-评论家网络中，演员网络在决策时可计算策略梯度，评论家网络预测状态价值以教导演员网络得到更优的策略梯度。本实施例以相似的建神经网络结构来搭建演员-评论家网络，形成神经网络结构模块。

本实施例高层强化学习中用于训练神经网络的训练方式不同于传统的演员-评论家网络训练方式，本实施例中的训练方式引入A3C方法，系统中包含一个负责更新和训练网络并为工人线程提供网络参数的中心线程以及多个使用来自中心线程的网络参数运行算法的工人线程，该方法有效加快训练过程，减少运行时间。在工人线程收集足够的训练数据后，算法对神经网络进行训练，从每个工人线程的状态、行动及奖励中学习。

为验证本实施例中超启发式算法的有效性及性能，基于洋山四期自动化集装箱堆场的实际场景设计了一系列不同规模的问题，并开展实验，下表2为超参数的选择。后为直观表现本实施例的性能，将引入不同问题中常用的性能较高的一系列智能算法进行算法比较。

表2超参数选择

如图3所示为以3个箱区、15个倍位的堆场和60个出口箱任务为算例的算法迭代过程。迭代过程中，目标函数值不断下降，并且算法能够选择不同的启发式算法尽可能减小该目标函数，证明该实施例中基于强化学习的超启发式算法的有效性，并能在有限的迭代过程中给出较好的箱位分配方案。

为验证超启发式算法的必要性与优越性，建立了一系列箱位分配为题算例，引入常见的智能算法，包括：人工蚁群算法(ABC)、布谷鸟算法(CS)、遗传算法(GA)、粒子群算法(PSO)、模拟退火算法(SA)、改进遗传算法(IGA)、改进模拟退火算法(ISA)来进行实验。

经过具体实际实验，在TensorFlow 1.4，Python 3.5、16GB RAM和i7-8700 CPU的环境下，选取3个箱区，15个倍位的堆场，60/120/180个出口箱任务的设置下，以表2中选择的超参数运行本方法，能够得到的实验对比数据如下表3所示，其中“X-Y-Z”表示X个箱区，Y个倍位的堆场，Z个出口箱任务。

表3实际实验对比数据

为更直观的体现本实施例中超启发式算法的优越性能，通过计算

实验表明，在自动化集装箱码头出口箱箱位分配问题中，本实施例中的基于强化学习的超启发式算法能够在有限的时间内得到较好的可接受的箱位分配方案，能够在全部3个算例中获得最佳箱位分配方案，并且在全部箱位分配方案的平均结果中获得最好的评价，较其他常见算法有18.8％以上的提升，较近期研究中的改进算法有15.2％的提升。

如图4、5、6所示分别为出口想任务数量增加时、贝位数量增加时、箱区数量增加时的算法性能对比，可见本实施例中的超启发式算法的INC值在大多情况下达到最低，并在随着问题规模扩大的情况下有着下降的趋势，证明本实施例能够有效解决箱位分配问题，并且能够提供优于多种智能算法的高水平的箱位分配问题解决方案。

与现有技术相比，本方法在规定时间内所给出的箱位分配方案优于单个启发式算法给出的方案。

上述具体实施可由本领域技术人员在不背离本发明原理和宗旨的前提下以不同的方式对其进行局部调整，本发明的保护范围以权利要求书为准且不由上述具体实施所限，在其范围内的各个实现方案均受本发明之约束。