自适应双边界约束遗传算法的储位分配研究
钱同惠+赖重远+张仕臻+王波
摘 要： 在采用精英保留策略改进遗传算法的基础上，创新性地提出一种自适应双边界约束策略来改进遗传算法，使改进后的算法在提升搜索效率上效果显著，收敛性增强。实验数据表明，自适应双边界约束遗传算法应用于仓储管理的储位分配算法的寻优平均效率提升77.8%，寻优平均速度提升62.5%。
关键词： 自适应； 双边界约束； 遗传算法； 储位分配
中图分类号： TN911.1?34； F251 文献标识码： A 文章编号： 1004?373X（2017）17?0127?04
Research on storage distribution based on adaptive dual?boundary
constraints improving genetic algorithm
QIAN Tonghui， LAI Zhongyuan， ZHANG Shizhen， WANG Bo
（Institute for Interdisciplinary Research， Jianghan University， Wuhan 430056， China）
Abstract： On the basis of genetic algorithm improved with elitism?reserved strategy， an adaptive dual?boundary constraint strategy to improve genetic algorithm is put forward innovatively， which can improve search efficiency， and enhance its convergence. Experimental data shows that the adaptive dual?boundary constraint improving genetic algorithm is applied to storage distribution of warehouse management， whose average optimization efficiency is increased by 77.8%， and average optimization speed is increased by 62.5%.
Keywords： self?adaption； dual?boundary constraint； genetic algorithm； storage distribution
1 研究背景
仓储管理是整个供应链管理的一个重要环节，近年来仓储管理的合理化和人性化受到越来越多企业和管理者的重视，包括管理的系统化、信息化、现代化。其中，仓储管理的核心之一是仓储物流技术，包括采用更加柔性的智能制造系统，高度逼真的仿真技术，集成更加智能的仓储管理软件以及采用一些人工智能优化控制算法等。在仓储管理方面，储位分配任务是一个高度复杂的调度任务，它直接决定了仓储设备进出库作业的效率，也是充分利用现有货架资源的重要保证。在货物资源快速流转的现代物流现状下，在保证货物流通安全的同时不断提高物流和仓储效率是企业生存的重要竞争力。
2 自适应双边界约束遗传算法应用于储位分配
2.1 遗传算法参数设置
现假设需将10个货物堆放至一个规格为10×20的空货架中，堆垛机事先通过3D标签获得各类货物的进出库频次和各个货物的质量。通常来说，在货物入库时会考虑一些因素：如质量较大的货物放置在货架的底层，有利于货架重心保持稳定，进出库频次较高的货物放置在靠近出入巷道的列，同时尽量放置在货架的底层。
货物的质量和出入库频次见表1。设置遗传算法参数，见表2。
设计评价函数：
（1）
式中：分别代表货架的行、列以及待入库货物的序号；为待入库货物的质量和出入库频次；分别为出入库规划质量的权重以及出入库频次在货架行列上的权重。
2.2 自适应双边界约束原理
遗传算法执行到一定阶段，在变异算子设计过程中试着改变算法搜索的两个边界，并且随着算法运行不断将优化结果的最优个体值反馈到算法之中，这个反馈值作为一个动态约束边界，从而实现算法的自适应双边界约束。
2.3 算法实现流程图
自适应双边界约束改进策略遗传算法运行的主要步骤包括：种群的初始化、适应值评价、个体排序（保存最优个体——精英保留策略，为增强算法收敛性的可选策略）、选择下一代个体、交叉操作、变异操作（需要自适应调整变异搜索范围），迭代直到滿足结束条件。如图1所示。
2.4 实验运行结果
重复运行模型10次得到的结果见表3。
选取最早收敛个体适应值结果和最佳收敛个体适应值结果对比，见表4。
通过采用自适应双边界约束策略得到的最早收敛与最佳收敛曲线对比图如图2，图3所示。
从图2，图3结果来看，货物入库状态基本呈现出如下特点：
（1） 由于货架初始状态为空，所以算法基本能够搜索到距离进出口位置最近的货位。
（2） 货物是成批（10个一批）入库货架，改进算法能够实现货物之间不留空货位，尽可能搜索到离真实最优解更近的近似最优解。
（3） 货物在货架上的排布基本实现质量和进出库频次加权值较大的被优先安排在货架底层和进出口外层；货物进出库频次被作为安排货位的优先因素。出现这种现象的原因是：货物进出库频次数和货物质量值计量单位不同且未均一化，进出库频次数这个动态值和货物质量静态值在动态调度规划中不协调。
自适应双边界约束遗传算法（带精英保留策略）与精英保留策略改进遗传算法运行结果对比见表5。
图4的运行结果直观展示出通过自适应双边界约束改进遗传算法不仅使种群中个体最佳适应值均值从705.8直接降到397.0，大幅逼近真实最优解。同时最佳适应值出现所需迭代次数（均值）从3 498.1降到了2 151.6；从表5中数据来看，采用双边界约束遗传算法的迭代时间会有所延长，原因是双边界约束遗传算法在后期能够防止算法进入全局无目的搜索，通过自适应调节边界范围，逐步将搜索局域约束在某个动态边界值以内，使得算法在自适应调整边界的同时，加强算法的局部搜索能力。通过控制自适应调节的时机和步伐，能够保证了算法优化结果的全局最优和快速局部搜索。
3 结 论
本文提出一种自适应双边界约束策略，算法运行过程中能够自动调整搜索边界，在保证算法前期全局搜索的同时，能够增强算法后期的局部搜索能力和快速收敛性能。从图2～图4可以直观看出，采用该策略前后，算法的寻优平均效率提升77.8%，寻优平均速度提升62.5%。由此可以看出，自适应双边界约束策略改进遗传算法非常适合解决储位分配管理优化问题。
参考文献
[1] 龙锋.基于自适应遗传算法的W公司仓库货位分配与优化研究[D].广州：华南理工大学，2015.
[2] 马永杰.大型仓储系统的调度算法研究[D].兰州：兰州交通大学，2011.
[3] 党培.医药冷链物流仓储管理系统关键问题研究[D].西安：陕西科技大学，2015.
[4] 孙晓琳.基于云模式的智能仓储管理系统研究[D].武汉：武汉理工大学，2014.
[5] 黄刚.物流发展呈现多重新趋势[J].经理人，2014（5）：24?25.
[6] 王健.基于遗传算法的仓储货位优化研究[D].西安：西安建筑科技大学，2009.
摘 要： 在采用精英保留策略改进遗传算法的基础上，创新性地提出一种自适应双边界约束策略来改进遗传算法，使改进后的算法在提升搜索效率上效果显著，收敛性增强。实验数据表明，自适应双边界约束遗传算法应用于仓储管理的储位分配算法的寻优平均效率提升77.8%，寻优平均速度提升62.5%。
关键词： 自适应； 双边界约束； 遗传算法； 储位分配
中图分类号： TN911.1?34； F251 文献标识码： A 文章编号： 1004?373X（2017）17?0127?04
Research on storage distribution based on adaptive dual?boundary
constraints improving genetic algorithm
QIAN Tonghui， LAI Zhongyuan， ZHANG Shizhen， WANG Bo
（Institute for Interdisciplinary Research， Jianghan University， Wuhan 430056， China）
Abstract： On the basis of genetic algorithm improved with elitism?reserved strategy， an adaptive dual?boundary constraint strategy to improve genetic algorithm is put forward innovatively， which can improve search efficiency， and enhance its convergence. Experimental data shows that the adaptive dual?boundary constraint improving genetic algorithm is applied to storage distribution of warehouse management， whose average optimization efficiency is increased by 77.8%， and average optimization speed is increased by 62.5%.
Keywords： self?adaption； dual?boundary constraint； genetic algorithm； storage distribution
1 研究背景
仓储管理是整个供应链管理的一个重要环节，近年来仓储管理的合理化和人性化受到越来越多企业和管理者的重视，包括管理的系统化、信息化、现代化。其中，仓储管理的核心之一是仓储物流技术，包括采用更加柔性的智能制造系统，高度逼真的仿真技术，集成更加智能的仓储管理软件以及采用一些人工智能优化控制算法等。在仓储管理方面，储位分配任务是一个高度复杂的调度任务，它直接决定了仓储设备进出库作业的效率，也是充分利用现有货架资源的重要保证。在货物资源快速流转的现代物流现状下，在保证货物流通安全的同时不断提高物流和仓储效率是企业生存的重要竞争力。
2 自适应双边界约束遗传算法应用于储位分配
2.1 遗传算法参数设置
现假设需将10个货物堆放至一个规格为10×20的空货架中，堆垛机事先通过3D标签获得各类货物的进出库频次和各个货物的质量。通常来说，在货物入库时会考虑一些因素：如质量较大的货物放置在货架的底层，有利于货架重心保持稳定，进出库频次较高的货物放置在靠近出入巷道的列，同时尽量放置在货架的底层。
货物的质量和出入库频次见表1。设置遗传算法参数，见表2。
设计评价函数：
（1）
式中：分别代表货架的行、列以及待入库货物的序号；为待入库货物的质量和出入库频次；分别为出入库规划质量的权重以及出入库频次在货架行列上的权重。
2.2 自适应双边界约束原理
遗传算法执行到一定阶段，在变异算子设计过程中试着改变算法搜索的两个边界，并且随着算法运行不断将优化结果的最优个体值反馈到算法之中，这个反馈值作为一个动态约束边界，从而实现算法的自适应双边界约束。
2.3 算法实现流程图
自适应双边界约束改进策略遗传算法运行的主要步骤包括：种群的初始化、适应值评价、个体排序（保存最优个体——精英保留策略，为增强算法收敛性的可选策略）、选择下一代个体、交叉操作、变异操作（需要自适应调整变异搜索范围），迭代直到滿足结束条件。如图1所示。
2.4 实验运行结果
重复运行模型10次得到的结果见表3。
选取最早收敛个体适应值结果和最佳收敛个体适应值结果对比，见表4。
通过采用自适应双边界约束策略得到的最早收敛与最佳收敛曲线对比图如图2，图3所示。
从图2，图3结果来看，货物入库状态基本呈现出如下特点：
（1） 由于货架初始状态为空，所以算法基本能够搜索到距离进出口位置最近的货位。
（2） 货物是成批（10个一批）入库货架，改进算法能够实现货物之间不留空货位，尽可能搜索到离真实最优解更近的近似最优解。
（3） 货物在货架上的排布基本实现质量和进出库频次加权值较大的被优先安排在货架底层和进出口外层；货物进出库频次被作为安排货位的优先因素。出现这种现象的原因是：货物进出库频次数和货物质量值计量单位不同且未均一化，进出库频次数这个动态值和货物质量静态值在动态调度规划中不协调。
自适应双边界约束遗传算法（带精英保留策略）与精英保留策略改进遗传算法运行结果对比见表5。
图4的运行结果直观展示出通过自适应双边界约束改进遗传算法不仅使种群中个体最佳适应值均值从705.8直接降到397.0，大幅逼近真实最优解。同时最佳适应值出现所需迭代次数（均值）从3 498.1降到了2 151.6；从表5中数据来看，采用双边界约束遗传算法的迭代时间会有所延长，原因是双边界约束遗传算法在后期能够防止算法进入全局无目的搜索，通过自适应调节边界范围，逐步将搜索局域约束在某个动态边界值以内，使得算法在自适应调整边界的同时，加强算法的局部搜索能力。通过控制自适应调节的时机和步伐，能够保证了算法优化结果的全局最优和快速局部搜索。
3 结 论
本文提出一种自适应双边界约束策略，算法运行过程中能够自动调整搜索边界，在保证算法前期全局搜索的同时，能够增强算法后期的局部搜索能力和快速收敛性能。从图2～图4可以直观看出，采用该策略前后，算法的寻优平均效率提升77.8%，寻优平均速度提升62.5%。由此可以看出，自适应双边界约束策略改进遗传算法非常适合解决储位分配管理优化问题。
参考文献
[1] 龙锋.基于自适应遗传算法的W公司仓库货位分配与优化研究[D].广州：华南理工大学，2015.
[2] 马永杰.大型仓储系统的调度算法研究[D].兰州：兰州交通大学，2011.
[3] 党培.医药冷链物流仓储管理系统关键问题研究[D].西安：陕西科技大学，2015.
[4] 孙晓琳.基于云模式的智能仓储管理系统研究[D].武汉：武汉理工大学，2014.
[5] 黄刚.物流发展呈现多重新趋势[J].经理人，2014（5）：24?25.
[6] 王健.基于遗传算法的仓储货位优化研究[D].西安：西安建筑科技大学，2009.
