基于改进花授粉算法的共融AGV作业车间调度

  • 基于改进花授粉算法的共融AGV作业车间调度已关闭评论
  • 140 views
  • A+
所属分类:AGV设计资料
摘要

提出一种用于求解AGV与机器集成的车间调度问题的改进花授粉算法,其中,基于主成分分析法提出新的变异算子以增强算法对解空间的感知能力和跳出局部极值的能力;引入交叉算子以提高花授粉算法的全局搜索能力;基于染色体相似度矩阵提出一种自适应个体初始化生成策略以提高初始种群的多样性。而面向这种集成调度问题需求,首先建立机器与AGV集成的调度数学模型,然后采用新的解码算法和新解接受机制对模型进行求解,最后通过搭建集成调度实验平台来验证所提出的改进算法有效性。

0 引言

随着德国工业 4.0 高科技战略计划的提出,以及互联网、物联网、云计算、雾计算/边缘计算和大数据等新一代信息技术的快速发展,新一轮工业革命已拉开了帷幕,制造模式正从以前的大规模标准化生产,向大规模个性化定制生产模式转变,生产制造模式的改变意味着车间需要更具柔性以适应复杂多变的产品[1-3]。而个性化定制生产模式下,产品种类不仅繁多,而且加工作业流程不同,此时不仅依赖 AGV 在不同工位之间进行物料的运输,更重要的是 AGV 与加工作业机器协同工作。因此近几年越来越多的学者关注智能 AGV 小车设计、AGV 与作业车间的集成调度等问题[4],旨在提高信息获取的实时性和系统的鲁棒性,进而构建一个高度灵活的智能化生产系统,以适应复杂多变的个性化生产需求,同时有助于降低单位产品所需能耗。但是,传统的车间调度算法仅适用于工件(半成品)运输时间与工件加工时间相比可忽略的情形,而在面向多品种小批量的个性化定制模式的复杂生产环境中,AGV 作为个性化智能生产高效运行的关键设备,不能简单地忽略处理,为此本文着重研究多 AGV 与机器的集成调度问题。车间调度可分为静态调度(离线调度)和动态调度(实时或在线调度),静态调度一般是根据订单按一定的周期制定生产计划,而动态调度考虑实时的紧急订单插入、工件工序调整等,本文着重研究共融 AGV 的作业车间离线调度问题。

传统车间调度和 AGV 与机器的集成车间调度都是典型的 NPHard 型问题。虽然对于小规模调度优化问题,采用诸如动态规划法和分支定界法等传统算法可获得较好的求解速度和精度,但随着问题规模的增加,解空间结构复杂且规模庞大,传统算法难以在可接受的计算时间内求解出近似最优解,因此在可接受计算时间内求解出待解决的车间调度智能优化算法应运而生。比如,文[5]综述了教-学优化算法(Teaching-Learning-Based Optimization,TLBO)在流水线车间、作业车间调度问题及其他组合优化领域中的应用,并采用 TLBO 求解多种流水线车间和作业车间调度问题;文[6]综述了进化算法求解集成制造系统中的车间布局、柔性车间调度、多级工艺规划和先进规划与调度四类组合优化问题的研究现状;文[7]同时考虑最大完工时间和机器负载建立焊接调度问题(WeldingScheduling Problem,WSP)的混合整数规划模型,并提出求解该问题的多目标离散灰狼优化算法(Multi-Objective Discrete Grey Wolf Optimization,MODGWO);文[8]研究了考虑两阶段装配流水线车间调度中工件到达时间的问题,并应用灰狼优化算法(Grey Wolf Optimization,GWO)求解该调度问题;文[9]采用 TLBO 求解多种车间调度问题,与其他算法对比证明 TLBO 能有效求解小规模和大规模车间调度优化问题;文[10]研究了遗传算法(Genetic Algorithm,GA)和 PSO 等智能算法在车间调度领域的应用。

传统的机器人只能在封闭空间作业不能与人融洽地完成复杂的任务,随着高精度传感器、物联网、深度学习、大数据处理、云计算和雾计算等新兴技术的快速发展,及其在机器人控制系统中的应用,使机器人不仅能自主地感知周围环境,而且能与人交互和协作,使机器人向智慧化方向发展[11]。这种具备自主感知环境且能与人交互和协作的 AGV 称为共融 AGV[12]。共融 AGV 的作业车间调度无疑会成为未来智能制造系统和智能物流系统的关键技术,与传统调度模型相比,由于约束条件和解码复杂度增加导致目标函数与解空间之间的映射关系更加复杂,同时对算法设计提出了更高的要求。综合上述文献分析看出,由于 GA、PSO、TLBO、GWO 等智能优化算法在传统车间调度领域取得了大量成功的应用案例,从而也导致越来越多学者开始开展 AGV 与机器的集成调度问题研究:比如,文[13]基于非定向析取图建立 AGV 与作业车间集成调度模型,并采用改进文化基因算法(Memetic algorithm,MA)求解该集成调度问题,但文中假设 AGV 沿预定路线运动降低了系统的柔性,使其不能适应复杂的生产系统;文[14]同时考虑 AGV 无冲突的路径选择和车间调度建立混合整数规划模型(Mixed Integer Linear Programming,MILP),并提出求解该问题的两阶段蚁群算法(Ant ColonyOptimization,ACO),其中第一阶段解决 AGV 任务分配,第二阶段解决 AGV 无冲突路径选择,并以 AGV 台数为自变量研究了 AGV 数量对最大完工时间的影响,并从初期投资成本、AGV 路径冲突、系统维护、投资回报率等多方面分析了一个生产系统如何确定合适的 AGV 数量,缺点是 AGV只能沿预定轨迹行驶,导致 AGV 之间路径冲突可能性增加,也降低了系统的柔性和鲁棒性;另外模型缺少考虑 AGV 利用率的因素,导致优化出的调度方案 AGV 能耗较高。文[15]对于包含一个 AGV的中小型柔性制造系统,考虑系统运行最大作业数、有限的缓冲区、AGV 空行程等约束条件建立线性规划模型,并研究了各个因素对目标函数的影响,但只考虑一台 AGV 的情形,缺少 AGV 数量对最大完工时间影响的研究,同样缺少 AGV 利用率的优化;文[16]研究了 AGV 的指派、无冲突路径选择以及 AGV 与作业车间集成调度问题,并考虑最大完工时间、AGV 运行时间、因冲突导致加工作业延迟三种因素,利用模糊专家系统根据种群目标函数均值和前两代种群的标准差自适应调节变异和交叉概率,提出应用于求解该问题的混合遗传算法(Hybrid Genetic Algorithm,HGA),但文中未给出 AGV 与机器的集成调度数学模型;文[17]建立 AGV 与机器集成的作业车间调度的 MILP 模型,采用操作序列固定和 AGV 分配固定的邻域结构以提高算法的局部搜索能力,提出改进的下界计算方法以提高求解大规模调度问题的效率,但缺少对解空间有感知能力的变异算子研究;文[18]考虑 AGV运行、停止和转弯时间的影响,采用时间窗方法基于 GA 提出两阶段集成调度策略,第一阶段主要是利用 Dijkstra 算法选择最优路线,第二阶段考虑多台 AGV 在一个系统运行的约束条件基于 GA 对AGV 调度进行进一步优化,虽然结果表明该策略可有效提高 AGV 系统的运行效率,但如果进一步考虑同一时刻一条轨迹上的 AGV 双向运行的话,系统运行效率还可提高。

No free lunch 理论[19]证明每种智能算法都有自身的局限性,因此近些年来不同学者根据不同需求从不同角度提出一些新型智能优化算法,如 TLBO[20]、花授粉优化算法(Flower Pollination Algorithm,FPA)[21]、GWO[22, 23]、鲸鱼优化算法(Whale Optimization Algorithm,WOA)[24]、蝗虫优化算法(Grasshopper Optimisation Algorithm,GOA)[25]、蜻蜓优化算法(Dragonfly Algorithm,DA)[26]等,同时各种优势互补的混合智能算法应运而生,以克服单种算法寻优机制单一的局限性。TLBO 模拟实际的教学过程,GWO 模拟灰狼群围捕猎物的行为,而 FPA 模拟植物的花授粉过程,从生物进化的角度来看,花授粉使环境适应性更好的植物的花粉得以更广泛的传播,从而繁殖更多子代。FPA 主要包括全局授粉(全局搜索)和局部授粉(局部搜索)两个阶段。同 PSO 和人工蜂群算法(Artificial BeeColony,ABC)一样,FPA 也是一种基于种群的智能优化算法,有很强的鲁棒性、全局搜索和局部开发能力,FPA 及其改进的混合算法已在不同领域获得应用,如文[27]采用精英反向学习策略来增加种群多样性,进而增强算法对解空间的探索能力,并基于 ABC 提出抛弃算子,以克服了算法陷入局部极小值的缺点,再引入逐维进化思想,以消除不同维度之间相互冲突的现象,但缺少种群初始化方法的研究;文[28]基于 PSO 提出改进 FPA 的局部搜索算子,利用概率动态切换策略改进 PFA 的恒定概率策略,使 FPA 更好地平衡全局搜索和局部开发能力,应用于求解无人潜航器(Unmanned UnderseaVehicle,UUV)的 2 维和 3 维路径规划问题,但针对特定问题的变异算子研究较少;文[29]采用克隆选择算法(Clonal Selection Algorithm,CSA)来改进 FPA,这种改进继承了 FPA 全局搜索能力和 CSA 局部信息开采能力,与蝙蝠算法(Bat Algorithm,BAT)、CSA 和萤火虫算法(Firefly Algorithm,FF)等相比,改进 FPA 求解复杂高维优化问题效率更高;文[30]针对 FPA 求解高维多峰函数优化问题寻优能力差的缺陷,采用精英对立学习策略(Elite Opposition-Based Learning Strategy,EOLS)和局部自适应贪婪策略(Local Self-adaptive Greedy Strategy,LSGS)来改进 FPA,并应用于求解多种标准多峰优化算例、焊接梁设计和压缩弹簧设计等优化问题,但缺少提高初始种群多样性的种群初始化算法研究。

从现有文献来看,尽管 FPA 在求解复杂组合优化问题具有较好的潜力,但很少应用于车间调度研究报道,应用于 AGV 与机器集成的作业车间调度研究更稀少,此外,AGV 与机器集成的作业车间调度现有的研究缺少考虑 AGV 的利用率因素,本文考虑 AGV 的利用率和工件最大完工时间两个因素建立多目标优化数学模型,并基于 FPA 设计了求解该问题的算法。传统的 GA、ACO 等智能优化算法求解车间调度问题时,初始种群一般采用随机方法生成,导致初始种群不能有效地感知解空间,进而导致算法对解空间的探索能力不足,为此本研究设计染色体相似度矩阵用于评价染色体相似度,进而基于此方法设计改进的初始解生成算法;传统的变异算子变异时对解空间的信息缺少感知,为此基于主成分分析法(Principal Component Analysis,PCA)提出带有启发式规则的变异算子;而通过 GA 的交叉算子与 FPA 的优化流程融合来提高其全局搜索能力;最后采用模拟退火算法中的“按概率接受较差解”思想改进 FPA 新解的接受机制,来增强算法跳出局部极小值的能力。为了验证所提出的改进 FPA 求解 AGV 与机器集成的作业车间调度的有效性,首先应用于求解 FT06、FT10等传统车间调度问题证明其求解较大规模车间调度问题的可行性;再通过建立 AGV 与机器集成的作业车间调度数学模型,并搭建了集成调度的实验原型平台,从实验角度验证所提改进算法的有效性。

基于改进花授粉算法的共融AGV作业车间调度

图 1 全局授粉示意图

恭喜,此资源为免费资源,请先
注意:本站资源多为网络收集,如涉及版权问题请及时与站长联系QQ:2766242327,我们会在第一时间内与您协商解决。如非特殊说明,本站所有资源解压密码均为:agvba.com。
weinxin
微信公众号
agvba是一个分享AGV知识和agv案例视频的网站。