联系我们

Contact

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

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

* 来源: * 作者: * 发表时间: 2019-11-22 0:33:15 * 浏览: 0
自动化仓库是现代物流技术,仓储技术,自动化技术和计算机技术的高度集成产品。它集成了存储,运输,分配,管理等功能。具有存储容量大,占地面积小的优点。这是一家现代化工厂。物流和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)表示距城市的距离。从i到城市j,集合W(i,j)| i是W-1元素。通常,不选择较大的j,并且相应的路径i不属于全局最优路径的一部分。根据该推理信息,可以设计最近点启发式路径构造方法。如果以圄2(a)为起点,则通过该方法获得路径(a,b,c,d,e,f,g,h)。使用最近点方法构造的解决方案通常是局部性较差的最佳解决方案。为了改善该缺陷并获得一组高质量的初始组,本文提出了一种多起点2-最近点搜索算法。以下是TSP问题的示例,如下所示。多点初始化,从连接两个城市的一侧| i,j = 1,2,... jV,和i侧开始,j选择最长的i侧,在其中随机选择了标尺边缘(i构造一个队列和两个集合。首先,第二个访问的城市集合侦听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变异算子的混合遗传算法运行到561th代,搜索全局最优路径,选择成本为104s。在实验中,仅使用了10个单独的小规模小组,并在较短的迭代步骤中获得了令人满意的优化结果,并且提高了执行效率。快速查询了全局最优解。相反,从圄3(b)中可以看出,尽管使用40个个体进行了5000次种群迭代,但是传统的遗传算法仍然难以收敛到令人满意的解决方案,并且无法针对这种中等和复杂的算法进行优化。大规模行动。 。最后,使用混合遗传算法对几个随机生成的不同规模的作业进行了30次仿真实验。统计结果如表3所示。根据测试结果,该问题中提出的总体初始化方法可以产生良好的初始性能。种群降低了进化搜索的强度,使用自适应进化算子的混合遗传算法可以快速,稳定地搜索具有小规模种群的全局最优解。同时,从质量和稳定性的最佳解决方案