| 标题 | 基于改进自适应遗传算法的入库货位优化研究 |
| 范文 | 刘玮玮 摘 要： 探讨了基于Srinivas M提出的线性自适应遗传算法，在此基础上，从种群多样性的表示上，对算法进行了改进，得出了一种新型自适应遗传算法。根据基本入库原则和库存现状，将入库时库位选择归纳为一个多目标优化问题，建立对应的数学模型。将改进的算法用于入库货位模型求解，结果表明，该算法能够较好的解决入库问题，选择出最佳货位，从而证明了算法的有效性。 关键词： 仓储效率； 货位优化； 改进的自适应遗传算法； 多目标优化 中图分类号：TP393.09 文献标志码：A 文章编号：1006-8228（2018）08-57-04 Study on the warehousing slotting optimization based on improved adaptive genetic algorithm Liu Weiwei （Faculty of Informatics， Fujian Vocational College of Agriculture， Fuzhou， Fujian 350001， China） Abstract： This paper discusses the linear adaptive genetic algorithm which is presented by Srinivas M， on this basis， improves the algorithm from the representation of population diversity， and proposes a new adaptive genetic algorithm. According to the basic principle of warehousing and the status of inventory， the storage location selection is summarized as a multi-objective optimization problem， and a corresponding mathematical model is established. Using the improved algorithm to solve the storage location model， the result indicates that the algorithm can better work out the problem of warehousing and choose the best location， and then the validity of the algorithm is proved. Key words： storage efficiency； slotting optimization； the improved adaptive genetic algorithm； multi objective optimization 0 引言 貨位优化的目的是将仓库黄金区域分给高频捡取的货物，从而实现最大化拣选效率以及最小化拣选成本， 还可方便补货及平衡各工作区的工作量，这些能为仓储管理提供有效的支撑并提高拣选的准确性。当前世界各物流管理公司推出了许多货位优化软件，大致分为两种，一种是与WMS绑定，另一种是适合中小规模仓库使用并与WMS分离的。在货位分配时考虑的原则一般包括[1]：货架承载均匀，上轻下重；加快周转，先入先出；提高可靠性，分巷道存放；提高效率，就近出入库及产品相关性等。存储位置的分配和实现策略[2]有分类存储策略；改进的先进先出策略；随机存储策略；货物相关性策略；共享存储策略等。 1 入库货位分配模型的建立 入库货位优化问题可描述如下。 已知：参见表1数据和拟入库货物的相关数据。 约束：⑴ 货位分配原则； ⑵ 当前仓库货位存储状况。 目标：优化货位，提高货位利用率及仓储运作效率。 本文的入库分配模型由五个子模型组成，在货物入库对库位进行选择时，需要综合考虑这五个模型的值来选择最优货位，根据商允伟等[3]、郑凌莺等[4]、邰世文[5]等人的研究成果，将货位分配归结为多目标优化问题，建立入库货位分配模型见式⑴，相关变量说明见表1。 2 改进的自适应遗传算法 遗传算法（Genetic Algorithm，GA）是一种基于生物进化机制的随机搜索算法，能够有效地进行概率意义下的全局搜索[6]。目前常见的自适应遗传算法有：线性自适应遗传算法、余弦自适应遗传算法、指数自适应遗传算法，本文改进算法基于Srinivas M的线性自适应遗传算法[7]，见公式⑵： 当个体适应度较大而接近种群适应度最大值时，Pc和Pm都会变的很小。在种群中个体适应值为最优值时，其变异概率为零，对最优个体不进行交叉和变异操作。Srinivas M以fmax-favg为标准来衡量种群多样性，在整个种群适应值水平较为平均时是可行的，但在种群最优个体的适应值是一个离群值，即其值是远离序列的一般水平极大值和极小值的情况下，再使用fmax-favg衡量种群多样性就会失去意义。为防止此情况出现，使用种群个体适应度的标准差代替fmax-favg，得出改进的自适应遗传算法，即自适应变异交叉概率公式[8]，即见式⑶，其中Pc1=0.7， Pc2=0.1，Pm1=0.1，Pm2=0.001： ⑶ 为验证该改进遗传算法的性能，本文选取一个含有四个局部最优解的函数作为测试函数， 因全局最优解常被最差解包围，如果遗传算法的种群收敛性不好，则极易陷入局部最优[9]。同时引用线性自适应遗传算法（LAGA）[7]、余弦自适应遗传算法（CAGA）[10]、幂指数自适应遗传算法（IAGA）[11]与本文算法进行性能上的比较，本文改进算法因使用了反三角函数故简称为AAGA[8]。测试函数f说明见表2所示。 可以看到在平均适应度方面，本文算法的种群比其他自适应遗传算法的种群拥有更多的优良个体和相对较强的自适应能力，无论求解最大值还是最小值，该算法都有一定的优势。在最优适应度方面，本文算法也能更快地达到最优解，且有较强的自适应能力，从局部最优走向全局最优；且在收敛次数、平均收敛代数和平均收敛值三个方面，本文算法也具有一定优势。 3 入库货位分配模型求解 货位优化问题实际上是一个多目标求解问题，多目标优化问题没有绝对意义上的最优，而只能平衡、协调多个目标达到Pareto最优解[12]。目前有许多使用遗传算法对多目标求解的方法，其中常用的有权重系数法、并列选择法、排列选择法等， 本文使用并列选择法对前文所建立货位分配模型求解。求解过程主要由四个部分组成：编码机制、控制参数、适应度函数和遗传算子[6]，流程图如图3所示。 ⑴ 编码使用二进制。假设仓库有16*32个货位，每个货位可以使用横纵坐标（i，j）（i=1，2，3…16；j=1，2，3…32）进行标定，因使用二进制编码方式，横坐标使用四位二进制编码1111表示，纵坐标使用五位二进制编码11111表示，标识货位的坐标形式为（iiii，iiiii）（i=0，l）形式。为更好提高效率，将横纵坐标组合成为一体（iiii， iiiii）→iiiiiiii进行编码。 ⑵ 解码：根据编码中规定的横纵坐标二进制串的长度，将整个染色体划分为两部分，将横纵坐标当中的二进制子串转换为对应的十进制，再根据十进制数字得到具体货位。 ⑶ 初始化种群：交叉和变异概率分别为Pc1=0.8，Pc2=0.5，Pm1=0.04，Pm2=0.001，种群规模100，最大演化代数3000。 ⑷ 适应度函数设计：适应度值的计算需要用到表1中的数据和入库货物的相关数据，包括货位订单号、货物ID号、货物数量和每件货物的高度等。确定以上数据后，可使用建立的入库货位分配模型的五个数学模型计算仓库當中所有货位的适应度值，得到五个16*32的适应度值矩阵，在遗传算法的遗传操作当中，查表即可知某个货位在某个函数下的适应度值。 ⑸ 遗传操作：使用改进自适应遗传算法计算个体发生交叉和变异的概率。算法的选择算子采用无放回式随机余数算法获得，交叉算子采用单点交叉算法获得，变异算子采用离散变异算法获得，货位高度参考企业提供限高信息，应用时根据实际情况修改货位限定高度即可。 表5列出了入库时一些关键未知数据，其中仓库入库口坐标和仓库中最大坐标为常量值，据每个仓库的实际规划获得。 为1时表示以（i，j）为坐标的货位上有同一订单的货物；为0时表示该货位上没有同一订单的货物 决策变量。为1时表示以（i，j）为坐标的货位上有同一种货物； 为0时表示该货位上没有同一种货物 ] 图4和图5是本文算法AAGA求解入库货位分配模型最优解的仿真过程，图4为初始状态的仓库，其中方块表示高度已经高于250厘米不能再放置的货位；菱形表示其高度在[100，250）之间的货位；下三角表示其高度在[50，100）之间的货位；上三角表示其高度在[0，50）之间的货位，图5为经过本文算法标记过的仓库，其中用五角星标记的坐标（8，18）货位是推荐的最优货位。 在具体的仓储系统中，参照入库货位分配模型，本文算法可用Java等高级编程语言实现。进行入库操作时，仓库管理员通过Android客户端扫描贴在货物上的二维码，获得货物信息，输入入库数量， 信息提交给服务器端后， 服务器端根据传递的参数和算法进行运算，得出推荐入库货位后返回给客户端显示。 4 结论 本文首先根据基本的入库原则和库存现状分析了影响仓储运营效率的入库操作，将入库时库位选择问题归纳为一个多目标优化问题，建立货位分配数学模型；接下来阐述一种在自适应函数对种群多样性的表示上进行改进的遗传算法，其在平均适应度和最优适应度等方面，较之其他自适应遗传算法有一定优势；最后采用遗传算法的并列选择法对该货位分配模型进行求解，解决多目标优化问题。结果表明，这种改进的自适应遗传算法用于所建立的货位分配模型，能够较好的解决入库问题，选择出最佳货位。 参考文献（References）： [1] 左生龙，刘军.现代仓储作业管理[M].中国物资出版社，2006. [2] 马永杰，蒋兆远，杨志民.基于遗传算法的自动化仓库的动态 货位分配[J].西南交通大学学报，2008，3（43）：415-420. [3] 商允伟，裘聿皇，刘长有.自动化仓库货位分配优化问题研究[J]. 计算机工程与应用，2004.26：16-17 [4] 郑凌莺，张欣，言勇华.物流中心仓库货位优化系统的设计研 究[J].物流技术，2006.6：33-34 [5] 邰世文.汽车零部件物流中心设施布局优化研究[D].大连理 工大学，2013. [6] 王雄志.配送中心配货作业方法研究[M].中国经济出版社， 2008. [7] Srinivas M，Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. Systems， Man and Cybernetics， IEEE Transactions on，1994.24（4）：656-667 [8] 杨志龙.基于遗传算法的仓库管理系统的研究与实现[D].中 国海洋大学，2014. [9] 韩瑞锋.遗传算法原理与应用实例[M].兵器工业出版社， 2010. [10] 石山，励庆孕，王兴华.基于自适应遗传算法的无刷直流电 机的优化设计[J].西安交通大学学报，2002.12：1215-1218 [11] 金晶，苏勇.一种改进的自适应遗传算法[J].计算机工程与应 用，2005.18：64-69 [12] Carlos F M， Peter F J. An overview of evolutionary algorithms in multiobjective optimization[J]. Evolutionary Computation，1995.3（1）：1-16 |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。