基于改进遗传算法和多目标决策的货位优化策略

陈晓艳，张东洋，苏学斌，代钰贺，赵春东

(1. 天津科技大学电子信息与自动化学院，天津 300222；2. 青海通达油脂加工有限责任公司，西宁 810000)

近年来，仓库管理信息化、自动化程度日趋提高．自动化立体仓库是现代物流技术、仓储技术、自动化技术与计算机技术高度集成化的产物[1]．目前，自动化立体仓库应用广泛，提高仓库空间利用率、优化货物存储方案是降低仓储成本、提高工作效率的关键[2]．

随着人工智能技术的发展，遗传算法成为解决上述问题的有效解决方法之一．Lam等[3]提出货位优化问题是仓储货位管理的核心问题之一；Celebi[4]提出使用遗传算法控制集中分配网络中的库存，并以土耳其汽车制造商作为案例研究；Ene等[5]研究仓库中挑拣操作和适当存储策略，并采用遗传算法解决能耗问题；Dai等[6]依据安全距离规则，建立仓库安全布局的数学模型，通过遗传算法优化存储布局．但上述研究中运用传统遗传算法仍存在一定不足，如收敛速度不够快、易陷入局部最优、出现未成熟收敛等．

为了获得更佳的优化结果，提升算法性能，Ehsan等[7]提出一种改进的交叉、逆、插入、交换变异算子，获得了更高质量的解；Yan等[8]利用自适应遗传算法构建多目标分配模型，实现库存的动态货位分配；Manatkar 等[9]、Homayouni等[10]、Zu 等[11]将遗传算法与其他智能算法(粒子群算法、模糊决策等)结合起来，通过混合遗传算法实现对库存的优化．

综合国内外遗传算法在货位优化问题上的研究及应用现状可以发现，大多研究专注于获得比传统遗传算法更佳的优化结果，而对算法的收敛速度鲜有明确阐述．本文结合青海省通达油脂加工有限责任公司的实际需求，提出一种改进的遗传算法，通过增加二次优化环节，提高算法的收敛速度，同时综合考虑仓库出入库效率、货物分类摆放合理性、货架稳定性三方面需求，通过构建多目标优化模型、改进算法、仿真验证，获得了一个综合、可行的货位优化解决方案，从而实现了随机库存的在线动态货位分配．

1 模型构建

1.1 模型假设

货位位置采用三维坐标(x，y，z)表示，即第 x排y列z层．仓库货位共有n排k列l层．为研究方便，在构建模型之前，本文提出如下假设：

(1)货物出入库方式为单端口出入．

(2)不考虑存取货物的用时与方式，只提出优化存储策略．

(3)货位规格统一，且满足国际化标准托盘存放最低要求．

(4)货物采用标准化托盘存放，单个托盘内货物种类相同．

(5)只考虑货物重量，不计货架重量．

1.2 构建过程

货物存储问题是一个复杂的多维度的优化问题，不仅要考虑到货物的整体出入库效率和分类存放的合理性，还要尽可能的使货架的重心接近地面，保证货架的稳定性．综合考虑这 3方面因素，本文提出基于多目标决策方式构建优化模型．

1.2.1 出入库效率

提高出入库效率的关键在于减少货物的出入库时间，当叉车存取托盘及运输速度不变的情况下，货物移动的距离将成为影响货物出入库时间的关键因素．本文研究货位优化问题的目标之一就是调整货物存放位置，实现货位的自动分配，从而尽可能缩短货物出入库的距离，提升出入库效率．具体模型见式(1)．

式中：s表示当前仓库已存放货物的货位数；(xi, yi, zi)表示第i个已存放货物的货位坐标．

1.2.2 分类存放合理性

如果货物不按照分类随意摆放，会大大增加库存管理和取货的难度，降低工作效率．因此，在货物存放中，将同类货物存放在该类货物的中心货位附近，从而实现货物的合理分类存放．具体模型见式(2)．

式中：(a*, b*, c*)表示当前种类货物的中心货位坐标，模型采用欧几里得度量描述货位之间的距离．

1.2.3 货架稳定性

货架的稳定性取决于其重心的高度，其重心越低，稳定性越高，将较重的货物摆放在货架的低层可以增加货架的整体稳定性，使得货架的重心到地面的距离最短．具体模型见式(3)．

式中：s表示当前仓库已存放货物的货位数；mi为第i个货位中的货物质量．

综上所述，货位优化问题的多目标数学模型为

2 算法原理

遗传算法(genetic algorithm，GA)是一种基于生物进化机制的随机搜索算法，能够有效地进行概率意义下的全局搜索，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则．遗传算法的基本运算过程包含初始化、个体评价、选择运算、交叉运算、变异运算、终止条件判断几个部分．

本文在传统遗传算法基础上，提出了一种改进的二次优化遗传算法(quadratic optimization genetic algorithm，QOGA)．遗传算法鲁棒性高，寻优能力强，结合二次优化环节，加速算法收敛，能够在短时间内计算出最优解．由于各目标函数之间互有影响，单独进行研究无法解决问题，依据多目标决策方案，采用权重系数法赋予各个目标函数不同的权重，将该模型转化为方便计算的单目标函数问题．其模型为

二次优化遗传算法流程如图1所示．

图1 二次优化遗传算法流程图Fig. 1 Flow chart of QOGA

3 算法实现

3.1 初始化

3.1.1 编码

编码是遗传算法的第一步，常用的编码方式有二进制编码、浮点数编码以及格雷码编码等．本文中将货物存储信息作为决策变量，为了适应所研究的问题，采用十进制整数编码，一个染色体个体的编码代表一种可行的货位分配方案．货架上的货位由行数、列数和层数这3个维度确定，每条染色体的基因个数为3N个(N代表存货货位的个数)．

3.1.2 控制参数

控制参数包含种群规模、遗传代数、终止条件、交叉概率、变异概率等．参数初始化是依据算法设计规则，对控制参数赋合理的初值．参数符号及初值见表 1．

表1 算法参数初值及含义Tab. 1 Initial values and meanings of parameters

3.1.3 初始种群

在开始算法迭代过程之前，需要对种群进行初始化．确定种群规模，即确定种群里的个体数量，一般随机生成初始种群，但是如果知道种群的实际分布，也可以按照此分布来生成初始种群．根据表 1确定的种群规模，创建一个psize行、3N列的初始种群矩阵pop．

3.1.4 适应度函数

遗传算法中构建的适应度函数将影响算法的收敛速度以及能否得到最优解．个体的适应度值是对个体优良与否的评价指标，适应度值与被遗传的几率成正比．本文通过目标函数变换得到适应度函数

3.2 选择、交叉、变异操作

3.2.1 选择操作

选择操作即从前代种群中选择个体到下一代种群的过程．一般根据个体适应度的分布来选择个体．适应度值与被遗传的几率成正比，即优秀的个体有更大的几率存活下来，更有机会参与后续的交叉和变异，更有权利繁衍后代．本文选用锦标赛法，每次随机从种群矩阵pop中抽取两个个体比较其适应度，选择适应度高的个体直接保留到下一代，并淘汰适应度低的个体，循环直至个体数达到原种群规模．

3.2.2 交叉操作

交叉操作是对任意两个个体进行的，是遗传算法中个体染色体进行交配的运算规则，目的是保证种群的稳定性，朝着最优解的方向进化．本文采用单点交叉，随机选择两个个体，同时生成一个(0，1)上的随机数，若生成的实数小于预设的交叉概率，则对这两个个体进行交叉，再随机选择交叉位置，将两个体交叉点位置之后的整数串进行对换，如图2所示．

图2 交叉操作示意图Fig. 2 Crossover operation diagram

3.2.3 变异操作

变异操作是对单个个体进行的，是为了保证种群的多样性，避免交叉可能产生的局部收敛．本文选用均匀变异算子进行单点变异(图 3)，规则为用符合约束条件的随机数根据变异概率代替染色体上的原有基因，然后在(0，1)上生成随机数，若随机数小于变异概率则进行变异运算，否则不进行变异运算．

图3 变异操作示意图Fig. 3 Mutation operational diagram

3.3 二次优化环节

为了适应研究的问题，加快算法求解速度，本文在传统遗传算法的基础之上进行了改进——在种群的每一次迭代中增加了二次优化环节，实时追踪全局最优个体，同时将每一代种群中的最差个体用全局最优个体代替，保证每一代种群中的优势个体数量，减少劣势个体数量．用优势个体去进行交叉、变异等进一步的寻优，有更大的概率找寻到更优个体，提升算法求解效率．

在二次优化环节中，首先引入变量 Best追踪全局最优个体及其适应度值，在每一次迭代过程中，比较Best与当前种群最优个体的适应度值，若Best优于当前种群最优个体，Best保持不变，更新当前种群最优个体，用 Best代替．若 Best劣于当前种群最优个体，更新Best，保证Best为整个迭代过程中的最优个体．然后依据个体适应度确定当前种群中的最差个体，用最优个体替代当前种群最差个体．通过“否定”掉当前最不适应环境的个体，并将其替换为当前最适应环境的个体，尽可能的让更适应环境的个体去生存、繁衍，保证优秀父代的规模与质量，能够大大提升算法求解效率．其操作流程如图 4所示．其中：Best为迭代全局最优解；pop_best为每一代种群中的最优解；pop_worst为每一代种群中的最差解．

图4 二次优化环节操作流程Fig. 4 Flow chart of quadratic optimization

二次优化环节有较大概率能够对算法迭代前期的收敛起到加速作用．分析算法原理后发现，在每一次迭代之后用全局最优个体代替当前种群的最差个体就会降低当前种群的多样性，依据玛格列夫物种多样性指数可知，每次当前种群最差个体被替代后，总物种数量S会减少1，总个体数量N不变，故玛格列夫指数D减小，物种多样性下降．玛格列夫物种多样性指数定义为

式中：D为玛格列夫指数；N为总个体数量；S为总物种数量．

依据算法原理，种群物种多样性下降会对遗传算法的收敛效果产生影响，可能产生过早收敛的情况.经多次测试，改进二次优化遗传算法并未出现明显的过早收敛现象．

4 仿真与应用

首先，构建一个仿真的自动化立体仓库，有 15个随机存储的货位，其初始坐标见表 2，该仓库中货架共有4排4列4层，各类型货物的中心货位坐标分别设定为(2，2，2)、(3，2，2)、(2，3，2)．通过MATLAB软件求解，分别得到改进二次优化遗传算法和传统遗传算法求解过程中的最优适应度函数值随种群迭代的变化曲线，如图5所示．

由图 5可知：改进二次优化遗传算法能够有效提升算法在前期的收敛速度；当种群迭代到 150次时，结果趋于稳定，且计算时间与误差均在可接受范围之内，但传统遗传算法大约需要400次迭代才能获得相同结果；改进二次优化遗传算法的收敛速度较传统算法提升了约 2.7倍．按货物编号顺序，优化后的货位坐标依次为(2，2，2)、(2，1，2)、(1，2，1)、(2，2，1)、(1，2，2)、(3，2，1)、(3，2，2)、(4，2，2)、(3，1，2)、(3，1，1)、(2，3，1)、(1，3，1)、(1，3，2)、(3，3，2)、(2，3，2)．

表2 货位优化结果Tab. 2 Location optimization results

图5 最优适应度函数值变化曲线Fig. 5 Optimal fitness function value curve

为了衡量优化效果，分别求解3个目标函数优化前后的函数值，结果见表3．由表3可以看出：3个目标函数值较优化前分别降低了 19.10%、43.26%、67.39%，优化效果各异，其中货物合理分类存放方面的优化效果最好．

依据多目标决策分析整体优化效果时，需要将各方面的优化结果加以综合．为使出入库效率、分类存放合理性、货架稳定性在分析整体优化效率时具有相近的影响力，令

即 89ω1＝15ω2＝223ω3，求得 ω 分别为 0.136、0.809、0.055．依据优化结果，照顾优化效果较差的出入库效率，调整权重，得到最终结果：ω1＝0.155，ω2＝0.800，ω3＝0.045．

表3 优化前后目标函数值对比Tab. 3 Object function values before and after optimization

由表 3可知：依据多目标决策综合分析，总的目标函数下降了 49.91%，优化效果显著．对比优化前后货位分布状态(图 6)可以发现：优化前货位分布杂乱无章，布局混乱；优化后的货位大多集中在出口位置附近，且多数货物位于底层，整体布局合理有序．综合分析仓库的出入库效率、货物分类存放合理性和货架的整体稳定性，较优化之前有了明显的改善.

图6 货位优化前后分布状态Fig. 6 Distribution before and after location optimization

本算法实地应用于青海省通达油脂加工有限责任公司．该公司的粮油仓库占地面积约 8000m2，立体仓库货架分布为 8排 8列 4层．主要存储产品类型有5类：5L海北花经典浓香菜籽油、5L海北花土榨菜籽油、20L雪莲花纯香菜籽油、20L润百香纯香四级菜籽油、22L互助通达纯香菜籽油．采用QOGA算法为仓库中5类共150件商品进行存储货位优化，初始时刻所有商品随机存放，经算法 2000次迭代优化，评价函数指标由 1132.50降低至 957.05，下降约15.5%，优化效果比较明显．

5 结 语

本文对仓库的出入库效率、货架的稳定性和货品的分类摆放方面构建目标函数优化数学模型，采用定量分析方式，实现仓库货物的动态货位分配．同时在传统遗传算法基础之上，提出了一种改进的二次优化遗传算法，利用 MATLAB软件求解，并与传统遗传算法求解曲线对比分析，求解结果清晰，算法收敛速度明显提升，改进方案切实可行．通过算法分析可以看出，优化后的目标函数值较优化之前有明显降低，优化效果显著．结果表明，采用二次优化遗传算法优化自动化立体仓库的货位问题行之有效，为自动化立体库货位分配和优化提供了一个综合、可行的解决方案．同时经仓库实际应用也验证了本文算法具有可行性和实际应用价值．

本算法还具有智能推荐功能，体现在货位优化后，对新入库的货物可智能化推荐合理的存储货位，使其符合出入库效率高、分类存放合理、摆放货架稳定的多目标要求．