联系我们

Contact

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

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

* 来源: * 作者: * 发表时间: 2020-06-07 0:04:52 * 浏览: 19
自动化三维仓库是当代物流技术,仓储技术,自动化技术和计算机技术的高度集成产品。它集成了存储,运输,分配,管理等功能。具有存储容量大,占地面积小的优点。这是一家现代化工厂。物流和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优化问题是固定货架拣选操作的优化,这种问题最终可以归结为属于NP-C问题的组合优化问题中的旅行商问题(TSP)。 2混合遗传算法遗传算法是一种基于生物进化机制的随机搜索算法,可以有效地进行概率意义上的全局搜索。人们已经使用传统的遗传算法解决了这些问题,但是当解决中型和大型问题时,算法本身固有的遗传漂移和局部优化的效率都低下。通过旅行的销售,可以得出货运商问题(TSP)的局部最优解的分布适应度分析(FDC):在FDC分析中,局部最优解通常相互聚类,而全局最佳解决方案通常位于其中心。这意味着在次优解和最优解之间存在更多相同的边。由于局部最优解与全局最优解之间的距离在搜索空间中具有更多的边缘,因此,如果我们能够从高质量的局部最优解开始,并有效地控制人口以使其由局部最优解组成子空间可以大大提高全局最优解的搜索效率。为此,本文从两个方面对遗传算法进行了改进:初始种群的构建和遗传算子的设计。该算法实现的几个重要方面描述如下:2.1多起点2近点搜索算法可以从TSP问题中获得以下推断信息:如果城市数为i,则j)代表距城市i的距离。对于城市j,集合W(i,j)| i由W-1个元素组成。一般来说,不选择较大的j,并且相应的路径i也不是全局最优路径的一部分。根据该推理信息,可以设计最近点启发式路径构造方法。如图2(a)所示,以a为起点,并使用此方法获得路径(a,b,c,d,e,f,g,h)。通过最近点法构造的解通常是质量较差的局部最优解。为了改善这一缺陷,从而获得一组高质量的初始组,本文提出了一种多起点2-最近点搜索算法。下面以TSP问题为例来说明算法。多连接初始化,从连接两个或两个城市的边集开始i,j = 1,2,... jV,i边j选择颤动距离最长的i边,并随机选择标尺边(i构造一个队列和两个集合。首先组合2,用于收听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,...)成为个体的变异,否则不会发生变异。 opt变异算子:首先,随机选择连接两个或两个城市的3条边线并将其删除。翻转3条随机路径(或点)后,将获得与3条随机路径(或点)相对应的端点,以构造当前的搜索队列。作为当前搜索点集,使用多起点2最近邻居搜索方法修复成对路径。上述两个突变算子不使用常规的随机BK方法来选择种群中的某些个体进行突变操作,而是对种群中的所有个体进行突变测试。如果改善了个人路径,则可以实施突变。否则,不执行任何突变。根据路径的随机选择部分是否得到改善,以自适应方式执行变异操作。 3优化拣选操作的模拟研究货架和堆垛机的参数设置如下:do = 1m,h = 1m,v = 1m / s,v,= 3m / s。由于拣选台的机械强度有限,单次拣选操作所拣选的货物数量通常少于100。随机产生80个拣选点进行拣选。首先,使用随机生成方法,最近点启发式算法和多起点2最近点搜索算法来生成30条拾取路径。结果如表1所示。其中,多起点2近邻搜索算法的执行参数=3。表1总体初始化方法性能的比较初始化方法最优值拣选成本(T / s)最差值平均标准差随机方法最近点方法多起点2-最近点方法使用最近点通过点启发法生成的初始组所对应的平均拣货成本为随机生成方法所生成的初始组的252%,而本文提出的多起点2-近邻法用于培育对应于平均采摘成本的初始群体,只是随机产生对应于初始采摘群体的成本,成本为238%。从统计数据的角度来看,与最近点方法相比,tb多起点2-最近点方法生成的拣配路径的质量也得到了一定程度的提高,可以得到高质量的初始解获得相对稳定。然后,采用本文设计的混合遗传算法和将稳态复制算子与PMX交叉算子和插件变异算子结合使用的常规遗传算法来优化上述问题。工作参数如表2所示。演化过程和适应性变化曲线如图3所示。表2算法的执行参数混合遗传算法遗传算法种群大小(数目)交叉概率(%)变异概率(%)自适应模式**对所有人进行突变试验如果路径得到改善,则进行mut操作。圄3(a)所示的曲线是本文设计的混合遗传算法的优化过程。在前几代人的基因操作中,人口的平均适应度略有增加。然后,人口的平均适应度迅速下降,人口的素质迅速提高。在随后的遗传操作中,在次优解决方案组成的空间中有效地控制了每一代的种群。使用2-opt变异算子的混合遗传算法在达到第662代时获得了非常接近全局最优解的拣配路径,拣配成本为10433s,使用3-opt变异算子的混合遗传算法正在运行。在第561代中,搜索了全局最优路径,选择成本为104s。在实验中,只使用了10个人的一小组,并且在短的迭代步骤中获得了令人满意的优化效果,并且提高了执行效率。快速搜索全局最佳解决方案。相反,如图3(b)所示,尽管使用了40个人的种群进行了5000次种群迭代,但是传统的遗传算法仍然难以收敛到令人满意的解决方案,并且无法优化这种中等规模的大型算法。规模经营。最后,使用混合遗传算法对数个随机生成的不同大小的作业进行了30次模拟测试,统计结果如表3所示。从测试结果可以看出,该问题提出了种群初始化方法。种群可以降低进化搜索的强度,使用自适应进化算子的混合遗传算法可以快速,稳定地寻找具有小规模种群的全局最优解。同时,可以获得最佳解决方案的质量和稳定性