联系我们

Contact

安徽智浩钢结构工程有限公司
电话:15209809766 
联系人:卢经理
地址:安徽省六安市裕安区城南镇汪家行村
网址:laxygs.com
当前位置:首页> 行业资讯

一类仓库作业优化问题的混合遗传算法研究

* 来源: * 作者: * 发表时间: 2019-07-27 13:56:15 * 浏览: 34
自动化仓库是现代物流技术,仓储技术,自动化技术和计算机技术的高度集成产品。它集成了存储,运输,分配,管理等功能。它具有存储容量大,占地面积小的优点。这是一个现代化的工厂。物流和CIMS的重要组成部分。本文以自动化仓库为对​​象,研究其固定货架子系统拣选操作的优化调度问题。合理解决固定机架系统中拣选操作的最优调度问题,将有效提高仓库的整体运营效率。本文针对优化问题分析并设计了一种快速有效的新型混合遗传算法。提出了一种多起点2最近点搜索算法作为种群初始化方法。将局部搜索算法集成到变异算子中,以自适应方式实现变异操作。同时,结合稳态复制算子有效地控制搜索种群。在由最优解决方案组成的空间中搜索全局最优解。仿真结果表明,混合遗传算法能够从执行效率和优化效果两方面很好地满足操作要求。 1固定式货架拣选操作优化问题自动化三维仓库固定货架子系统包含13排三维货物基金项目:国家自然科学基金(60104009)和山东省自然科学基金(Z2000 /混合动力系统,生产工艺)优化调度,智能机器人等,张攀(1977-),男,辽宁锦州,博士。学生,生产过程优化调度的研究方向,智能控制等。每个排除框架分为10层,72列和720个位置。在相邻的货架行之间存在道路,并且每个堆垛机可以运行堆垛机用于货物进入。当执行单车道固定货架拣选操作时,堆垛机从车道开始拣货。每个货物空间中的货物通过多个货物空间同时进入,然后返回到入口,货物集装箱被转移到交货仓库,从而形成分拣操作。固定货架和堆垛机操作参数设置如下:如图1所示,圄形节点是堆垛机需要在单个车道中访问的货物点,坐标为(x,j标记,货点(0) ,0)同时,它被视为巷道,并用作整个分拣作业的附加货点。单个货物宽度为b,高度为h:堆垛机在进入货物时始终是水平和垂直的。对于高速运行,忽略启动和制动过程,堆垛机的水平运行速度h与垂直运行速度之间的关系为t = 3v,并且堆垛机在运行期间可以在水平和垂直方向上同时移动。在访问货物时,操作员对任何货物的访问速度是恒定的,并且不会因访问顺序的变化而在大会等中发生变化:用于优化一类仓库操作的混合遗传算法,研究和计算拣选操作在时间成本中,货物访问时间被忽略。根据上述模型参数,堆垛机从货物空间/运行到货物空间y的时间成本为:其中:(x,。,y,。),(x,。,y ,.)分为位置的坐标。因此,具有w数1,2,3,...,w的候选位置的拣选操作的总拣选时间成本是:t(0,1)是堆从巷道停机的时间成本(附加货物点)到编号为1的货物处所,t(w,0)是堆垛机返回编号为w的巷道(附加货点)时间成本合理。合理地确定拣选路径,并且一次批量访问批次商品,并且在执行拣选操作之后最小化拣选时间成本T.该离散优化问题是固定架挑选操作的优化问题。这些问题可归因于T.在组合优化问题中抛出推销员问题(TSP),属于NP-C问题。 2混合遗传算法遗传算法是一种基于生物进化机制的随机搜索算法,能够有效地实现概率的含义。全球搜索。人们已经使用传统的遗传算法来解决这类问题,但在解决大规模问题时,算法本身固有的遗传漂移和局部优化的低效率都暴露出来。 (TSP)局部最优解的适应度 - 距离相关分析(FDC)可归纳如下:FDC分析的局部最优解经常相互聚集,全局最优解一般在其中心位置,即之间具有更多侧面的相同解决方案的最佳和次优解决方案。由于局部最优解和全局最优解在搜索空间中具有更多相同的边,因此如果可以使用高质量的局部最优解,则通过局部最优解有效地控制总体。在子空间中搜索可以极大地提高全局最优解的搜索效率。为此,遗传算法已经从初始种群的构建和遗传算子的设计得到改进。算法实现的几个重要步骤如下:2.1多起点2 - 最近点搜索算法以下推理信息可以从TSP问题中获得:如果城市数量是i,j)表示距离城市的距离我对城市j,集合W(i,j)| i是W-1元素。通常,不选择较大的j),并且相应的路径(i,j)不属于全局最优路径的一部分。根据该推理信息,可以设计出最近点启发式路径构造方法。如果a取自圄2(a)的起点,则通过该方法获得路径(a,b,c,d,e,f,g,h)。使用最近点法构造的解决方案通常是不良局部化的最优解。为了改善这一缺陷并获得一组高质量的初始群,本文提出了一种多起点2近点搜索算法。以下是TSP问题的示例如下。多连接初始化,从连接两个城市的一组边,| i,j = 1,2,... jV和i边j选择最长的i侧,其中随机选择标尺边(i Construct)一个队列和两个集合。首先,第二次访问的城市集合侦听a,h和当前访问城市结合C = b,c,d,e,f,g。 (3)采取团队领导b,在C中选择距离最短的城市c,d,并选择d以获得扩展分割路径为(d,b,a,c)。当前搜索点集是C = c,d,e,f,g。 (4)判断没有路径合并后,调整队列为(5)返回步骤(2),重复循环直到满足步骤(5)的搜索结束条件,并获得路径(a,b, d,e,h,f,g),c)。使用多启动2 - 最近邻搜索算法改进最近点算法如下:多城市并行搜索城市之间距离最长或第二长的城市,有效抑制单点搜索路径长度的缺点该过程的最后阶段,如圄2(a)中的路径(h,a),使用2最近邻搜索在某种程度上,它改善了最近点搜索带来的盲目性并增强了初始种群的多样性。系统模拟期刊2.2遗传操作传统遗传算法中的交叉和变异操作是在没有指导的情况下盲目地进行的,并且它是最多的。在由所有可行解决方案组成的空间中执行最优解的搜索。为了提高算法的局部搜索效率,设计了稳态复制,部分映射交叉算子与自适应局部搜索变异算子相结合的演化结构。在变异算子中,个体可以适应生活环境,以引导的方式进行变异操作,优化相应邻域的路径,提高群体的局部优化能力。同时,组合局部搜索变异算子和稳态拷贝选择算子控制部分地图交叉算子的种群质量的损害,使群体在由局部最优或次优解组成的子空间中维持遗传操作。 。实现优化全局优化的过程,同时不失去人口的多样性。本地搜索变异算子基于传统的2-opt和3-opt推理方法,实现如下:opt变异算子:假设要变异的个体是(...,a,b,... ,c,d,......)。首先,随机选择两个不顺序的边(a,b)(c,d),并删除两边以获得两个分段路径(bc)(da),然后在禁止自我的原则下修复路径循环,从搜索点a,b,c,d可以是(a,b)+ d(c,d)然后选择路径(...,a,c ... b,d,...)到个体的变异,否则不会发生变异。选项变异算子:首先随机选择两个城市的三个边并删除它们。在3个路径遵循期望的路径(或点)之后,将构造对应于3个路径(或点)的端点以构造当前搜索队列。作为当前搜索点集,多开始2 - 最近邻搜索方法用于修复配对路径。上述两个变异算子在随机BK选择群体中的某些个体中不使用常规的变异操作方法,而是对群体中的所有个体进行突变测试,并且如果个体路径得到改善,则执行变异。否则不会发生突变。根据随机选择的部分路径是否得到改善,自适应地形成变异操作。 3拣选操作优化问题模拟研究架和堆垛机参数设置为:do = 1m,h = 1m,v = 1m / s,v,= 3m / s。由于拣货站的机械强度,单个第二次拣货操作的货物数量一般小于100.随机选择80个货点进行拣货一,随机生成方法,最近点启发式算法和多-start 2最近点搜索算法用于生成30个拾取路径。结果如表1所示。其中,多个起点2 - 最近邻居搜索算法的执行参数= 3。表1种群初始化方法的性能比较初始化方法最优值选取成本(T / s)平均值均值标准差随机方法最近点法多起点2最近点法采用最近点初始组对应的平均拣选成本启发式方法是随机生成方法生成的初始种群的252%,本文提出的多起始2近邻方法只是为了初始组对应的平均拣选成本,随机生成初始组对应的拣选成本为238%。根据统计数据,还改进了由tb多起点2最近点法生成的拣选路径的质量,并且可以相对稳定地获得高质量的初始解。然后,本文设计的混合遗传算法和使用稳态复制算子的传统遗传算法结合PMX交叉算子和插件变异算子来优化上述问题。操作参数如表2所示,演变过程和适应度。变化曲线显示在圄3中。表2算法执行参数混合遗传算法遗传算法种群大小(数量)交叉概率(%)突变概率(%)自适应模式**对所有个体进行突变检验。如果路径得到改善,则执行变异操作。圄3(a)中的曲线是本文设计的混合遗传算法的优化过程。在第一代遗传操作中,人口的平均适应度有一个小的增加过程。然后,人口的平均适应度迅速下降,人口质量迅速增加。在随后的遗传操作过程中,在次优解形成的空间中有效地控制每一代群体。使用2-opt变异算子的混合遗传算法获得非常接近全局优化的拾取路径运行到第662代的解决方案。采摘成本为10433s,使用3-opt变异算子的混合遗传算法运行到第561代,搜索全局最优路径,选择成本为104s。在实验中,仅使用了10个单独的小规模组,并且在短的迭代步骤中获得了令人满意的优化结果,并且提高了执行效率。实现了全局最优解的快速查找。相反,从圄3(b)可以看出,虽然使用40个人口进行了5000次群体迭代,但传统的遗传算法仍然难以收敛到一个令人满意的解决方案,并且无法针对此类媒介进行优化。大规模的业务。 。最后,使用混合遗传算法对几个随机生成的不同尺度的作业进行30次模拟实验。统计结果如表3所示。从测试结果来看,该问题中提出的种群初始化方法可以产生良好的初始性能。种群减少了进化搜索的强度,使用自适应进化算子的混合遗传算法可以快速,稳定地搜索小规模种群的全局最优解。同时,从最优解的质量和稳定性可以看出,具有自适应3-opt变异算子的混合遗传算法比具有自适应2-opt变异算子的混合遗传算法具有稍好的优化能力。 。 8001000010002000300040005000群体迭代代数群体迭代代数(a)混合遗传算法(b)遗传算法圄3每代群体的平均适应度变化曲线表3混合遗传篝方法性能分析货物大小种群大小初始化自适应3-opt变异算子自适应2 opt变异算子演化代数总体平均拣选成本(T / s)最优拣选成本(T / s)最佳个体发生频率平均拣选成本(T / s)拣选成本标准差最优拣选成本(T / s)最平均个体具有频率平均拣选成本(T / s)拣选成本大学硕士论文,1995年。田大会等:一类仓库操作优化问题的混合遗传算法4结论实验结果表明本文提出了多起点2 - 最近邻法是培养高质量的有效方法在初始解决方案中,所设计的混合遗传算法可以通过控制局部最优解形成的子空间中的种群来有效地实现搜索,从而加快搜索效率并提高解决方案质量,同时满足执行效率和优化的要求。影响。