基于改进遗传算法求解堆垛机路径优化问题

陈 博，冯无恙

CHEN Bo1,2,FENG Wu-yang2

（1. 兰州理工大学 数字制造技术与应用省部共建教育部重点实验室， 兰州 730050；2. 兰州理工大学 机电工程学院，兰州 730050）

0 引言

现代化自动化立体仓库要求作业迅速、准确、稳定等特点。其作业周期由出入库台的时间、货物登记时间和堆垛机在仓库存取货物时间等组成。由于现代化立体仓库的规模越来越大，其高度达50多米，长度也达150米，所以在整个物流周期中堆垛机的行驶时间占到整个仓库作业周期的50%。如果堆垛机的调度不当或选用效率较低的调度模式，会严重影响堆垛机的工作效率，进而影响整个仓库的作业效率。所以选择一种较为合理的拣选路径是提高堆垛机作业效率的方法。

自动化立体仓库堆垛机在进行工作时，要求根据某一原则，如行走路线总长度最短、能量消耗最少等，堆垛机在立体仓库中沿着一条最优的路径行走。可以这样说堆垛机的路径规划问题可建模为一个有约束的优化问题。在以前的论文中，主要是对堆垛机在立体仓库中执行多项存取货物进行研究，但通过在实际中的一系列考察，一方面现在企业中的堆垛机还是执行单项任务的情况较多，即堆垛机从仓库入口处取出货物，然后运行到仓库中的某一存放地点，之后再沿原路线返回。另一方面堆垛机在执行一次任务时，并不是可以经过立体仓库中的任何一个地点，不同性质（包括重量、体积、化学属性）的货物要按类分放，这就要求堆垛机在执行存取任务时要避免经过一些货物存放点。综上所述，就引出了本文所要解决的问题，堆垛机在以上两个方面的约束下，怎样实现路径最短。

1 自动化立体仓库模型的建立

假设堆垛机的工作空间(立体仓库)用二维平面图形来表示。堆垛机执行一次任务时所不能通过的货格的位置已知。用尺寸相同的栅格对立体仓库进行划分。若某一栅格内不含任何障碍物，则称此栅格为自由栅格；反之，称之为障碍栅格[2]。如图1所示。

图1 立体仓库货格表示图

2 改进的自适应遗传算法

遗传算法是一种借鉴生物界自然选择和自然选择机制的随机化搜索算法，对于用传统搜索方法难以解决的复杂和非线性问题具有良好的适应性。但还有很多不足，如早熟收敛、易陷入局部最优和收敛速度慢等。为此，本文将采用改进的自适应遗传算法对堆垛机的工作环境进行建模，找到堆垛机路径优化的最佳路径。

当今改进遗传算法的主要措施主要集中于对交叉概率和遗传概率的选择与确定，因为它们会影响遗传算法的收敛性和搜索速度。针对不同的优化目标需要反复试验来确定交叉概率和遗传概率，而传统的遗传算法采用的是固定数值来代替交叉概率和遗传概率，这是很难找到最佳优化目标。

自适应遗传算法(AGA)[2]是由Srinivas提出来的，它的基本思想是交叉概率Pc和变异概率Pm能够随着适应度的变化而变化。当种群各个体适应度处于趋于一致或者局部最优时，使Pc和Pm增加，从而避免陷入局部最优，继而引发早熟现象；当群体各个体适应度比较分散时，使Pc和Pm减少，从而不易破坏优良个体，以利于优良个体保存下来。同时，对适应度高于群体平均适应度的个体选择较小的Pc和Pm，使得个体保存下来；那些低于群体平均适应度的个体，选择较大的Pc和Pm，一方面将一部分差的个体淘汰，另一方面增加新个体[3]。在自适应遗传算法中，交叉概率和变异概率按如下公式进行调整：

fmax表示种群的最大适应度，favg表示种群的平均适应度，f'表示参与交叉的两个个体中较大的个体的适应度，f表示变异个体的适应度。

AGA算法是有缺陷的，从公式中可以看出，当个体适应度越接近于最大适应度（fmaxf'≈0）时，交叉概率和变异概率越小，到接近为零，这种 调整方法在群体优化后期较为合适，因为在后期，要将优良个体保存下来，即为全局最优解。但是在进化初期不利，因为在进化初期群体中的较优个体几乎处于一种不发生变化的状态，而此时的优良个体不一定是全局最优解，增加了进化走向局部最优解的可能性，就是所谓的早熟现象。

任子武等人在AGA的基础上，提出了一种改进的自适应遗传算法(IAGA)。它除了有AGA的一系列优点之外，还弥补了AGA的缺陷。为了保证每一代的优良个体不被破坏，采取了精英保留策略：如果下一代的最佳个体适应度小于当前种群的最佳个体适应度，那么将当前种群的最佳个体或者多个个体直接复制到下一代，从而不会被当代种群的交叉和变异等遗传操作破坏[4]。IAGA公式如下：

以上公式中，pc1，pc2分别表示交叉概率的最大值和最小值，pm1，pm2分别表示变异概率的最大值和最小值。

在IAGA算法中，根据公式，个体的交叉概率和变异概率应根据个体的适应度在平均适应度和最大适应度之间进行线性变换。如果种群中存在较大规模的适应度接近平均适应度的个体，它的交叉概率最大，几乎为Pc1和Pm1，若个体适应度接近于最大适应度，那么它的Pc和Pm很小，为Pc2和Pm2，即IAGA的自适应交叉概率和变异概率曲线非常陡峭，导致一部分个体只能拥有较低的Pc和Pm，使进化停滞不前，造成局部收敛[5]。

本文所要提出的新的改进自适应遗传算法是根据种群的大小，适应值的分布情况，自适应变化整个种群的Pc和Pm，使它们的变化曲线为一个从振荡而逐渐稳定的形势。设计进化前期具有较大的Pc和Pm，以增强搜索能力，在进化后期采取相对较低的Pc和Pm，以确定最佳个体。本文将采用正弦形式的自适应遗传算法(SAGA)，其公式如下：

如图2和图3所示，两个公式的图像均为正弦式图像，从而保证了交叉概率和变异概率呈一种稳定式变化，而不会出现过度陡峭曲线，因为-1〈sina〈1,它可以弱化由于适应度接近平均适应度或者接近最大适应度而造成的Pc和Pm的过大或者过小，也克服了由于种群停滞不前而陷入局部最优的现象。

图2 自适应交叉概率正弦曲线

图3 自适应变异概率正弦曲线

3 路径规划方法

3.1 编码

采用序号法。基本顺序是从左到右，从下到上。将立体仓库分为若干个空格，从立体仓库的左下角的第一个格开始，给每一个空格一个序号N，依次延续，这样序号N与立体仓库的每一个空格一一对应。

采用序号法来表示堆垛机行走的路径，主要是因为序号法与坐标法作比较可节省内存，表达简洁清楚，更为重要的是便于以后的遗传算子（选择算子、交叉算子、变异算子）的操作。

我们将堆垛机在立体仓库的一条运动路径称之为一个个体，在这里假设堆垛机由起始位置A经过这一条路径最终到达终点位置B，那么这条路径可以表示为一个个体。采用序号法，则表示为（0,1,11,13,22,32,34,45,56,66,77,87,88,99）。我们从中可以看出，每条路径采用序号法具有编码长度短、简明、直观的优点。

3.2 初始种群

初始群体是遗传算法迭代运算的起点，它是由一定数目的个体所组成。一般情况下，在仓库空格数目较大的情况下产生初始群体采用计算机随机生成法，但是我们要求初始群体的所有路径具有目的性、无障碍性。从起点出发，利用局部搜索技术随机选取与前一个点相邻的非障碍物点作为下一路径点，以此类推，直至找到终点。如路径 S={x1，x2xn}。

3.3 个体适应度函数

3.4 遗传算子设计

3.4.1 选择算子

采用轮盘赌选择法和精英保留法相结合的方法，是个体按照与适应度成正比例的概率向下一代群体繁殖。

3.4.2 交叉算子

采用部分匹配交叉法：先随机产生两个 ，定义这两点间的区域为匹配区域，并用位置操作交换两个父代的匹配区域。如：交叉点为3、6父代A 8721309546 父代B 9835671420，先交换130与567，得出来的两个过渡代为A’ 8725679546父代B’9831301420.对于A’、B’中的匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行交换。

5—1,6—3,7—0。子代A 8025679143 子代B 9861305427。

3.4.3 变异算子

在堆垛机优化路径上属于典型的TSP问题，其变异算子采用逆转变异算子，方法如下：在个体中随机挑选两个逆转点，再将两个逆转点间的基因反序插入原位置。如个体A：987654321 ，在第3号位于第6号位采用逆转变异算子。新生成的个体为987456321。

4 仿真分析

采用Matlab遗传算法工具箱对此进行仿真测试。设种群规模为40，每个种群的长度为20，交叉概率Pc=0.9，变异概率为Pm=0.01,然后利用SAGA对每一代的交叉概率和变异概率进行计算。在Matlab窗口中输入Gatool,打开、进入遗传算法工具箱。之前必须将适应度函数写成M文件。输入遗传算法工具出启时的界面。图为遗传算法过程中群体中每一代个体最佳适应度随进化代数的变化情况。如图4所示上图中较为密集的点为每一代的最佳适应度值，而其上的点表示平均适应度值。可以看出，算法收敛较快，进化到约34代就已经搜索到了最优解。在早期个代中，当个体离理想值较远时，最佳值会迅速得到改进；在后来各代中，种群越接近最佳点，最佳值改进的越慢，以上这些顺应了SAGA的要求。图5为代与代平均个体之间的平均距离。

通过图5所示我们可以清晰的看到自适应算法在算完100代之后，这其中的每一代的具体情况，可以看出各代之间的差异性。

5 结论

本文提出了改进的自适应遗传算法(SAGA)，不仅克服了传统遗传算法的早熟和收敛速度慢问题，而且大幅度提高遗传算法的工作效率。此方法应用于堆垛机的路径规划，可以提高堆垛机的路径规划质量和工作效率。通过Matlab遗传算法工具箱的仿真，进一步验证了此方法的有效性和可行性。

图4 仿真结果

图5 各代差异性

[1] 孙树栋,曲彦宾. 遗传算法在机器人路径规划中的应用研究[J]. 西北工业大学学报,1998. 16(1)：79-83.

[2] Srinvas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Trans on Systems,Man and Cybernetics.1992.24(6)： 656-667.

[3] 张京钊,江涛. 改进的自适应遗传算法[J]. 计算机工程与应用,2010,46(11)： 53-55.

[4] 任子武,伞冶. 自适应遗传算法的改进及在系统辨识中应用研究[J]. 系统仿真学报,2006,18(1)： 41-66.

[5] 张国强,彭晓明. 自适应遗传算法的改进与应用[J]. 舰船电子工程. 2010.1： 83-84.