基于遗传算法的堆场自动化设备调度策略

孙 斐，沈安江

（上海振华重工集团股份有限公司，上海 200125）

0 简介

随着人力成本的增加，全球物流需求的增长，国内外越来越多的港口开始启用自动化设备进行堆场作业。由于堆场在码头运输中的重要地位，堆场的作业效率很大程度上影响了装卸船的整体速度，是决定码头服务能力的关键因素之一。在堆场建造设计和设备机械性能一定的前提下，优化作业任务的调度可以有效的提升堆场的作业效率。因此，本文提出一种利用遗传算法为数学模型从而解决复杂的堆场任务调度问题的策略，适用于在TOS一次性发送多条同一个堆垛的任务给ASC-MS的情况下，ASC-MS如何使用遗传算法解决同一个堆垛内2台ASC的选车问题、调度问题、避让问题等问题。本文提出的自动化堆场调度策略继承了遗传算法的优点与特性，不需要知道研究目标的内在性质也能进行求解。

1 调度策略各模块构成

本策略采用遗传算法（Genetic Algorithm）作为系统框架来进行问题求解。遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的策略。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体（individual）组成。每个个体实际上是染色体（chromosome）带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

系统各模块及其功能如下：

1.1 初始化

设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。

1.2 个体评价

计算群体P(t)中各个个体的适应度。

1.3 选择运算

将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

1.4 交叉运算

将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。

1.5 变异运算

将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。

群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。

1.6 终止条件判断

若t=T，则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

1.7 计算过程

计算过程如图1所示。

图1 遗传算法计算流程图

2 算法的实现

2.1 概述

本章节阐述如何将遗传算法应用于堆场设备解决ASC-MS（智能堆场管理系统）的选车问题、调度问题、避让问题等问题。

2.2 ASC-MS的编码规则

本算法将TOS发送给自动化堆场的N条任务定义为长度为N位的二进制数值。

将海侧ASC作业一条任务定义为数值0。将陆侧ASC作业一条任务定义为数值1。

例：TOS发送10条任务给自动化堆场，经过遗传算法计算后可能得到完成五条任务时间最快的排列为10101。

这代表第一条任务使用陆侧ASC，第二条任务使用海侧设备，第三条任务使用陆侧设备，第四条任务使用海侧ASC，第五条任务使用陆侧ASC。

2.3 ASC-MS的适应度函数

ASC-MS的适应度函数的目的是将遗传算法生成的二进制数值进行计算，适应度函数的输入是代表设备选择、运行方案的二进制数值，任务的具体信息以及设备的运行参数等数据，适应度函数的输出是代表设备选择、运行方案的完成总时间。经过计算获得该数值代表的ASC运行的总体时间，时间越短，则适应度越高，解越优。

由于ASC大车运动是非匀速的甚至是非线性的，为了获得更接近实际情况的任务完成时间，本算法快速模拟了设备的机构动作从而得到任务完成所需的时间值。

对于两台设备在作业过程中可能发生的避让需求，具体方法如下：

根据两车当前任务状态得到目标位置（任务暂停状态下设备的目标位置为任务目标位置加/减安全距离，左侧设备为减，右侧为加）。如果两车目标位置（大车）没有冲突，即左侧设备的目标位置+安全距离<右侧设备的目标位置，则按照目标位置移动或抓放箱。如果存在冲突，处于空闲状态或任务暂停状态下的设备要进行避让，两车都正常作业的情况下任务优先级低的要避让优先级高的，如果优先级也相同，采用生成随机数比较大小的方式来决定哪台做要避让。避让位置为另一台的目标位置加/减安全距离，左侧设备为减，右侧为加。最后得出两车决策目标位置。如果一辆车已有指令，则另一辆没有新指令的车若存在位置冲突需要 避让。

两台ASC各自生成随机数，初始范围为0到3，比较两个整数大小，若相等则再进行一次随机，直到不等为止。随机数大的那台设备获得“胜利”，另一台需要进行避让。“失败”的设备将随机数生成范围翻倍，以提高下次避让决策时的获胜概率，减小连续失败的可能性，获胜后，生成范围恢复为初始状态。

通过对同一基因的多次计算，选取用时最短的结果作为适应度并记录它所对应的避让策略。

2.4 ASC-MS的选择运算

选择运算（或称为复制运算）把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体中。

在本算法中，每一个得到的个体都会被保存，而遗传到下一代的个体将不会重复计算其适应度，以避免时间的浪费。

优秀的个体只在遗传时进行使用，用更大几率去产生更优秀的个体。

2.5 ASC-MS的交叉运算

交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某两个个体之间的部分染色体。

在本算法中，以10条任务为例。

0000000000代表10条任务全部由海侧ASC完成，1111111111代表10条任务全部有陆侧ASC完成。

经过交叉运算后得到新的两个解：0000011111和1111100000。

0000011111代表前5条任务由海侧ASC完成，后5条任务由陆侧ASC完成。

1111100000代表前5条任务由陆侧ASC完成，后5条任务由海侧ASC完成。

2.6 ASC-MS的变异运算

变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法。

还是以10条任务为例。

0000000000代表10条任务全部由海侧ASC完成。经过变异后得到新的解0000000001。

0000000001代表前9条任务由海侧ASC完成，最后1条任务由陆侧ASC完成。

2.7 ASC-MS使用遗传算法的流程图

流程图如图2所示。

图2 ASC-MS使用遗传算法的流程图

2.8 ASC-MS使用遗传算法的流程说明

当ASC-MS获取到TOS任务时，ASC-MS开始调用遗传算法模块。

ASC-MS将TOS任务传给遗传算法模块。

遗传算法模块根据传入的TOS信息进行二进制编码，并产生第一组初始解。类似于1010111001（10条任务），有几条任务，二进制数值就一共会有几位。

遗传算法模块调用适应度函数，在本方案中，适应度函数通过任务信息，计算完成这些任务所需要花费的总时间，时间越短，代表解越好，适应度越高。

遗传算法模块获得这些解及其适应度（时间），保存在内存中。

遗传算法模块查看是否有必要进行下一次迭代，本方案中，按照设定的迭代次数，到达迭代次数上限则停止迭代。

未到达迭代次数上限则继续迭代。

遗传算法模块继续迭代，根据选择、交叉、变异规则产生下一代新的解。

遗传算法模块查看这些新的解之前是否已经出现过。

剔除已经出现过的解，把没有出现过的解交给适应度函数进行计算。

遗传算法模块获得这些解及其适应度（时间），保存在内存中，然后进行下次迭代，直到达到迭代次数上限。

遗传算法提供ASC-MS框架一个最优化的解。

3 不足和改进

当前的遗传算法编码规则为二进制，0代表海侧ASC，1代表陆侧ASC，因此当一个堆垛的ASC数量大于2台时，无法适用当前编码规则和遗传规则，因此需要改进。

当前算法尚无调整任务执行的先后顺序的能力。

当前算法还没有计算接力的情况。

当前算法尚未试验得出一组交叉和变异的参数值使得迭代能更好地趋向于种群进化，即得到更优的解，并跳出局部最优解陷阱。

4 结束语

本文提出的策略通过使用遗传算法模型建立堆场调度的解决方案并在计算适应度的同时得出了基于一定任务分配条件下两车避让的决策优化。相较于基于就近原则的任务调度策略及其它基于固定逻辑的调度算法，此策略对于各种复杂工况有着更好的自适应能力，能整体地提高堆场作业效率。实现了自动化堆场管理和执行批任务的工作模式。

参考文献：

[1]Taejin Park · Ri Choe · Seung Min Ok ·Kwang Ryel Ryu.Realtime scheduling for twin RMGs in an automated container yard[J]. Springer-Verlag 2010,Published online:4 April 2010.

[2]陈国良,王熙法,庄镇泉,王东生.遗传算法及其应用[M].人民邮电出版社,1999,11(7):59-62.

[3]周明,孙树栋.遗传算法原理及应用[M].国防工业出版社,1999.