论文部分内容阅读
文章编号：1002-3100（2016）06-0131-06
摘 要：文章将遗传算法应用于仓储管理调度系统的储位分配过程，分析了基本遗传算法应用于储位分配的优缺点。通过采用精英保留策略，保证了基本遗传算法设计的多样性，实现了算法搜索的快速收敛和最优性能保持，克服了基本遗传算法的“返祖”现象。
关键词：改进遗传算法；精英保留策略；储位分配
中图分类号：F252.13 文献标识码：A
Abstract： This thesis applies genetic algorithm into the storage allocation process of warehouse management dispatching system， and analyzes the advantages and disadvantages of applying genetic algorithm into storage allocation. By adopting elitism-reserved strategy， it has ensured the diversity of the basic genetic algorithm design， realized the fast convergence and optimal performance of algorithmic search， and has overcome the“atavism”phenomenon of basic genetic algorithm.
Key words： improved genetic algorithm； elitism-reserved strategy； storage allocation
1 研究背景
随着经济的全球化，给很多跨国公司带来前所未有的发展机遇，也给物流行业带来新的发展契机。在国内，电商企业如雨后春笋般的发展势头一个比一个好，也带动物流业快速发展，与电商发展亦步亦趋，相辅相成。仓储是物流的关键环节之一，只有拥有先进的仓储管理系统，具备完善的仓储调度策略，才能在当前激烈的市场竞争中不断发展壮大。
众多学者认为，当前世界经济处于经济危机后深度调整中，我国经济发展也在转型中跨入新常态。就物流业当前面临的形势来看，物流业的地位正处于快速发展机遇期，也意味着这一时期将是我国物流业发展的完善期和物流发展的拓展期。通过研究该领域的动态，不难发现我国物流业有以下几种发展趋势：
（1）物流平台开始崭露头角，合同物流或将逐渐退出
为了追求利益的最大化，物流业势必面向平台化整合，以替代合同物流。伴随着电子商务的蓬勃发展，新的互联网经济将传统的TOB业务变革成TOC业务，这种散碎的物流服务是促进物流平台建设的有利基础。
（2）在大数据的作用下，物流数据将成为新的价值点
从马云对菜鸟的定位来看，“菜鸟”通过利用和整合获得的数据和信息，找到新的物流成本压缩点。合理分配存储区域，去除物流发展资源利用不充分的大屏障。
从小的方面来看，做好仓储内部调度，合理安排货物储位也是适应物流业发展的需要。因此本文利用遗传算法，研究货物上下架的优化策略，通过改进遗传算法的搜索策略，快速实现货物上下架调度。
2 遗传算法的基本理论
遗传解释了生物能够延续并不断进化的内在机理及其规律，而遗传算法正是诞生于生物科学和计算机科学的交叉点。将遗传进化的某些特质，融合在计算机编程和算法的设计之中，应用于工业控制、管理优化等诸多方面。
2.1 遗传算法的基本原理
遗传算法（Genetic Algorithm，GA）是由美国密歇根（Michigan）大学心理学教授、电子工程和计算机科学教授Holland提出的一种随机自适应全局搜索算法。这种算法模拟的自然界生物遗传进化过程，对优化问题的最优解（近似解）进行不断的迭代搜索。算法在维护一个潜在解的集合（群体），对群体进行优化，在优化过程中，算法引入了选择、交叉、变异等遗传算子。而遗传算法在搜索全局最优解过程中，是一个不断迭代的过程（每次迭代相当于自然界生物遗传的一次进化），直到算法满足终止条件为止。
2.1.1 相关概念
（1）染色体
一个染色体是问题的一个有效解。相对于生物群体中的一个个体。遗传算法的每个染色体，又由多个基因组成。如果将求解问题简化称一个y=fx的函数，那么染色体就可以看作变量x的取值。
（2）基因
可以认为是问题的一个有效解的某一维的值。它的改变会改变一个染色体的适应值，但一般不会引起整个种群发生太大变化。如果x的值由一段编码组成，那么一个编码序列可以看作是一个基因。
（3）适应值
适应值是用来表征一个染色体在群体中的优劣程度。一般来说，一个染色体的值越大，该染色体离最优解就越“近”。适应值就可以看作是这个函数y=fx的应变量y。
（4）评价函数
评价函数是用来计算一个染色体的适应值的大小，判断染色体优劣的一个手段。对应一个函数y=fx的对应法则f。
（5）选择算子
在对群体中若干个染色体进行筛选时，需要依据一定的规则，选出一些适应值较好的染色体进入下一代。那么如何选择，才能让更多、（适应值）更好的染色体从当前过度到下一代，同时保证染色体分布不失均匀，这就取决于选择算子。
（6）交叉算子
在对两个染色体作用时，交换两个染色体的部分基因，希望交换后，能从新的得到的染色体中能产生适应值更好的一个或两个染色体。为此而设计染色体概率性的交换基因片段的一个过程，使得算法能具备良好的全局搜索最优解的能力。 （7）变异算子
对比交叉算子，那么使染色体的某个基因发生变化，可以让算法具备较好的具备搜索最优解的能力。
通常，传统方法在求解某类优化问题采用的都是分析问题的某些特质，简化问题的约束，针对该问题的特质来求解。而Holland教授提出的遗传算法的基本思想，却不是去分析待求解问题的特质，而是采用一种泛化的求解原则。
2.2 遗传算法的基本流程
设计实现遗传算法，通常有以下几个比较重要的步骤：
（1）对群体进行初始化：包括选择适当规模的群体，每个染色体的编码方式，设计准确的适应度评价函数。
（2）群体适应值评价：用评价函数计算染色体适应值，并按照适应值的优劣，对染色体进行排序。
（3）选择种群进入下一代：利用设计好的选择算子，选出适应值较优秀的染色体进入下一代。
（4）交叉操作产生新的染色体：利用交叉算子，产生一些新的染色体。一个染色体通过评价函数的计算，会对应一个适应值。而交叉操作一般设计成不定向的，故交叉操作等可能产生适应值更差的染色体。
（5）变异操作产生新的染色体：利用变异算子，产生一些新的染色体，但是相比较交叉操作，变异后的新染色体，其适应值可能变化不是特别大。
3 遗传算法的应用于仓储优化
现代物流的竞争力在于：如何向客户提供更优质的服务，即服务效率高、物流过程安全。仓储物流是物流的关键环节之一。本文重点研究仓储物流的优化，将智能算法引入仓储物流过程中，实现对现有货位的合理规划。
现假设需将10个货物堆放至一个规格为10×20的空货架中，堆垛机事先通过3D标签获得了各类货物的进出库频次和各个货物的质量。通常来说，我们在货物入库时会考虑一些因素：如质量较大的货物放置在货架的底层，有利于货架重心保持稳定。进出库频次较高的货物放置在靠近出入巷道的位置，同时尽量放置在货架的底层。
货物的质量和出入库频次如表1所示。
3.1 算法实现
（1）种群初始化
初始化产生一个拥有40个个体的种群pop，每个个体的特点就是10个货物随机散落在该10×20的货架中。
5 结 论
对比采用精英保留策略和未采用该策略的10次运行结果，重复10次，计算最佳适应值个体的平均值分别为705.8和765.4，平均减小7.78%。从图5也能直观看出，采用精英保留策略得到的最佳适应值个体的优化值基本优于策略使用前的结果值。因此，通过采用精英保留策略来改进遗传算法，不仅能使得算法在运行过程中绝对收敛（单调趋优），也能改进算法的搜索性能。
参考文献：
[1] 侯景超. 基于改进遗传算法的仓储系统动态货位优化研究[D]. 沈阳：沈阳工业大学（硕士学位论文），2014.
[2] 张飞超. 基于微遗传算法的仓储布局优化方法研究[D]. 锦州：辽宁工业大学（硕士学位论文），2015.
[3] 侯秋琚. 基于遗传算法的中小型仓储配送车辆路径优化策略[J]. 物流技术，2014（11）：210-211，243.
[4] 王健. 基于遗传算法的仓储货位优化研究[D]. 西安：西安建筑科技大学（硕士学位论文），2009.
[5] 赵建文. 遗传算法在仓储物流系统中的应用研究[J]. 信息与电脑（理论版），2014（9）：139-141.
摘 要：文章将遗传算法应用于仓储管理调度系统的储位分配过程，分析了基本遗传算法应用于储位分配的优缺点。通过采用精英保留策略，保证了基本遗传算法设计的多样性，实现了算法搜索的快速收敛和最优性能保持，克服了基本遗传算法的“返祖”现象。
关键词：改进遗传算法；精英保留策略；储位分配
中图分类号：F252.13 文献标识码：A
Abstract： This thesis applies genetic algorithm into the storage allocation process of warehouse management dispatching system， and analyzes the advantages and disadvantages of applying genetic algorithm into storage allocation. By adopting elitism-reserved strategy， it has ensured the diversity of the basic genetic algorithm design， realized the fast convergence and optimal performance of algorithmic search， and has overcome the“atavism”phenomenon of basic genetic algorithm.
Key words： improved genetic algorithm； elitism-reserved strategy； storage allocation
1 研究背景
随着经济的全球化，给很多跨国公司带来前所未有的发展机遇，也给物流行业带来新的发展契机。在国内，电商企业如雨后春笋般的发展势头一个比一个好，也带动物流业快速发展，与电商发展亦步亦趋，相辅相成。仓储是物流的关键环节之一，只有拥有先进的仓储管理系统，具备完善的仓储调度策略，才能在当前激烈的市场竞争中不断发展壮大。
众多学者认为，当前世界经济处于经济危机后深度调整中，我国经济发展也在转型中跨入新常态。就物流业当前面临的形势来看，物流业的地位正处于快速发展机遇期，也意味着这一时期将是我国物流业发展的完善期和物流发展的拓展期。通过研究该领域的动态，不难发现我国物流业有以下几种发展趋势：
（1）物流平台开始崭露头角，合同物流或将逐渐退出
为了追求利益的最大化，物流业势必面向平台化整合，以替代合同物流。伴随着电子商务的蓬勃发展，新的互联网经济将传统的TOB业务变革成TOC业务，这种散碎的物流服务是促进物流平台建设的有利基础。
（2）在大数据的作用下，物流数据将成为新的价值点
从马云对菜鸟的定位来看，“菜鸟”通过利用和整合获得的数据和信息，找到新的物流成本压缩点。合理分配存储区域，去除物流发展资源利用不充分的大屏障。
从小的方面来看，做好仓储内部调度，合理安排货物储位也是适应物流业发展的需要。因此本文利用遗传算法，研究货物上下架的优化策略，通过改进遗传算法的搜索策略，快速实现货物上下架调度。
2 遗传算法的基本理论
遗传解释了生物能够延续并不断进化的内在机理及其规律，而遗传算法正是诞生于生物科学和计算机科学的交叉点。将遗传进化的某些特质，融合在计算机编程和算法的设计之中，应用于工业控制、管理优化等诸多方面。
2.1 遗传算法的基本原理
遗传算法（Genetic Algorithm，GA）是由美国密歇根（Michigan）大学心理学教授、电子工程和计算机科学教授Holland提出的一种随机自适应全局搜索算法。这种算法模拟的自然界生物遗传进化过程，对优化问题的最优解（近似解）进行不断的迭代搜索。算法在维护一个潜在解的集合（群体），对群体进行优化，在优化过程中，算法引入了选择、交叉、变异等遗传算子。而遗传算法在搜索全局最优解过程中，是一个不断迭代的过程（每次迭代相当于自然界生物遗传的一次进化），直到算法满足终止条件为止。
2.1.1 相关概念
（1）染色体
一个染色体是问题的一个有效解。相对于生物群体中的一个个体。遗传算法的每个染色体，又由多个基因组成。如果将求解问题简化称一个y=fx的函数，那么染色体就可以看作变量x的取值。
（2）基因
可以认为是问题的一个有效解的某一维的值。它的改变会改变一个染色体的适应值，但一般不会引起整个种群发生太大变化。如果x的值由一段编码组成，那么一个编码序列可以看作是一个基因。
（3）适应值
适应值是用来表征一个染色体在群体中的优劣程度。一般来说，一个染色体的值越大，该染色体离最优解就越“近”。适应值就可以看作是这个函数y=fx的应变量y。
（4）评价函数
评价函数是用来计算一个染色体的适应值的大小，判断染色体优劣的一个手段。对应一个函数y=fx的对应法则f。
（5）选择算子
在对群体中若干个染色体进行筛选时，需要依据一定的规则，选出一些适应值较好的染色体进入下一代。那么如何选择，才能让更多、（适应值）更好的染色体从当前过度到下一代，同时保证染色体分布不失均匀，这就取决于选择算子。
（6）交叉算子
在对两个染色体作用时，交换两个染色体的部分基因，希望交换后，能从新的得到的染色体中能产生适应值更好的一个或两个染色体。为此而设计染色体概率性的交换基因片段的一个过程，使得算法能具备良好的全局搜索最优解的能力。 （7）变异算子
对比交叉算子，那么使染色体的某个基因发生变化，可以让算法具备较好的具备搜索最优解的能力。
通常，传统方法在求解某类优化问题采用的都是分析问题的某些特质，简化问题的约束，针对该问题的特质来求解。而Holland教授提出的遗传算法的基本思想，却不是去分析待求解问题的特质，而是采用一种泛化的求解原则。
2.2 遗传算法的基本流程
设计实现遗传算法，通常有以下几个比较重要的步骤：
（1）对群体进行初始化：包括选择适当规模的群体，每个染色体的编码方式，设计准确的适应度评价函数。
（2）群体适应值评价：用评价函数计算染色体适应值，并按照适应值的优劣，对染色体进行排序。
（3）选择种群进入下一代：利用设计好的选择算子，选出适应值较优秀的染色体进入下一代。
（4）交叉操作产生新的染色体：利用交叉算子，产生一些新的染色体。一个染色体通过评价函数的计算，会对应一个适应值。而交叉操作一般设计成不定向的，故交叉操作等可能产生适应值更差的染色体。
（5）变异操作产生新的染色体：利用变异算子，产生一些新的染色体，但是相比较交叉操作，变异后的新染色体，其适应值可能变化不是特别大。
3 遗传算法的应用于仓储优化
现代物流的竞争力在于：如何向客户提供更优质的服务，即服务效率高、物流过程安全。仓储物流是物流的关键环节之一。本文重点研究仓储物流的优化，将智能算法引入仓储物流过程中，实现对现有货位的合理规划。
现假设需将10个货物堆放至一个规格为10×20的空货架中，堆垛机事先通过3D标签获得了各类货物的进出库频次和各个货物的质量。通常来说，我们在货物入库时会考虑一些因素：如质量较大的货物放置在货架的底层，有利于货架重心保持稳定。进出库频次较高的货物放置在靠近出入巷道的位置，同时尽量放置在货架的底层。
货物的质量和出入库频次如表1所示。
3.1 算法实现
（1）种群初始化
初始化产生一个拥有40个个体的种群pop，每个个体的特点就是10个货物随机散落在该10×20的货架中。
5 结 论
对比采用精英保留策略和未采用该策略的10次运行结果，重复10次，计算最佳适应值个体的平均值分别为705.8和765.4，平均减小7.78%。从图5也能直观看出，采用精英保留策略得到的最佳适应值个体的优化值基本优于策略使用前的结果值。因此，通过采用精英保留策略来改进遗传算法，不仅能使得算法在运行过程中绝对收敛（单调趋优），也能改进算法的搜索性能。
参考文献：
[1] 侯景超. 基于改进遗传算法的仓储系统动态货位优化研究[D]. 沈阳：沈阳工业大学（硕士学位论文），2014.
[2] 张飞超. 基于微遗传算法的仓储布局优化方法研究[D]. 锦州：辽宁工业大学（硕士学位论文），2015.
[3] 侯秋琚. 基于遗传算法的中小型仓储配送车辆路径优化策略[J]. 物流技术，2014（11）：210-211，243.
[4] 王健. 基于遗传算法的仓储货位优化研究[D]. 西安：西安建筑科技大学（硕士学位论文），2009.
[5] 赵建文. 遗传算法在仓储物流系统中的应用研究[J]. 信息与电脑（理论版），2014（9）：139-141.