《基于烟花算法的仓储物流机器人任务调度优化设计实例》24000字

PAGE2基于烟花算法的仓储物流机器人任务调度优化设计实例目录TOC\o"1-2"\h\u14815第1章绪论 1155711.1研究背景和意义 154271.2国内外研究现状 3252961.3论文研究内容及技术路线 618035第2章仓储物流系统研究 1010322.1路径模型概述 10266182.2任务调度原理 1190902.4任务调度算法 14170232.5本章小结 196583第3章仓储物流机器人任务调度实例 20155383.1引言 20190223.2仓库实例建模分析 20113973.3智能算法对仓储物流调度实例模型的求解分析 2322700第4章烟花算法及其改进策略 25163894.1烟花算法工作原理分析 2523039算法4.1烟花算法伪代码 3086234.2烟花算法性能分析 31145164.3改进烟花算法对实例模型的求解 32237084.4遗传算法对实例模型求解 33236624.5关于仓储物流机器人调度的烟花算法改进策略 3426375第5章实验方案与结果分析 397695.1实验方案设计 39117605.2实验参数设定 3948425.3实验结果对比分析 419679第六章总结与展望 4554696.1总结 45272466.2展望 46第1章绪论1.1研究背景和意义随着我国电商行业近年来的蓬勃发展，国内物流行业的总体规模和物流总需求逐渐在这种发展的促进下日益增多。仅2019年我国社会物流总额就高达298.0万亿元，2019年全年的社会物流总额与2018年全年的社会物流总额相比增长近6%[1]。日益增长的物流需求意味着在货物运输过程中需要更快且更准确的将货物送达目的地。传统的仓库管理系统是以人工规划调度，人工分拣，机器辅助搬运为主，货物通过入库登记、入库预检、收货检验、上架最终完成入库操作，而后实行货物保管，在接到订单请求后又通过预分配、拣货、集货最终完成发货。这其中涉及大量劳动力参与，由于是人力分拣搬运，通常还存在人为失误的情况，这也最终导致传统的仓库管理系统容易发生安全事故，容易出现误拿、错放等失误，且综合效率不高。这些劣势会很直接的影响客户消费体验，也极大的增加了企业的物流成本，成本增加而收益不变，企业的利润也就相对减少。由此可见，传统的仓储模式在当前的物流行业发展环境下已经很难适应当今社会，于是仓储物流智能化[2]应运而生。图1.12011-2019年我国社会物流总额仓储物流智能化是指仓库管理者运用计算机软件和机器人代替传统的人力，使货物管理信息化，货物搬运无人化，提高货物流通效率，增加货物搬运过程中的准确率，降低企业物流成本，提高盈利。仓储物流机器人是这类机器人的总称，根据不同场景，仓储物流机器人又可以分为搬运机器人，即：AGV(AutomatedGuidedVehicle,自动引导小车)和AMR(AutonomousMobileRobot,自主移动机器人)；分拣机器人、货架机器人，即：机械臂、码垛机器人和穿梭车RGV（RailGuidedVehicle）。本文研究中涉及的仓储物流机器人是AGV和AMR这类用于移动搬运货物的搬运机器人。与传统仓库管理系统中的搬运辅助工具相比，AGV和AMR这类用于移动搬运的机器人在仓管系统中有着无可比拟的优势：一是自动化。它们在搬运物料时可以实现全自动化运行，任务分配，响应，调度都可以由控制系统统一管理，使得各个机器人之间可以共享信息。针对机器人集群中的信息共享及时调整任务分配并更改后续的任务调度策略选择，以达到动态优化的目的，节省系统资源开销；二是使用成本低。在人力成本日渐增长的今天，机器人取代人力可大大减少仓库运营管理的开支；三是效率高。机器人受控制系统统一调配，可以24小时不间断进行作业；四是可靠性较高。控制系统对于所有的机器人实时监控，货物运输状况一目了然，能很大程度上保证仓库管理系统的稳定性。五是适用性强。在一些潮湿，低温，空间有限或其他极端情况下，人类长期工作很容易损害健康，而机器人却可以通过改装适应各种环境。从二十世纪五十年代至今，各类功能不尽相同的仓储物流机器人经过长足的发展在智能仓储中得到很好的应用，在以亚马逊，京东为代表的国内外大型物流企业中都可以看见它们的身影，也有越来越多的生产车间采用仓储物流机器人进行物料运输。随着这些普及，一些问题慢慢出现在人们眼前:（1）协同作业问题；当多个机器人同时工作时，系统如何实时调配任务，使得机器人之间不产生冲突，并且效率最大化。（2）路径规划问题；路径规划问题更多的是针对AMR,机械臂这类自由度较高的机器人，它们在运行过程中可能存在遇到障碍物的情况，而路径规划则是选择一条避开障碍且路径最短的路线，使机器人以最短的时间送达货物。（3）调度问题；当系统接到多个任务时，怎样把接到的任务按照一定的规则分配给多个机器人，使这些机器人在执行任务过程中达到一定的优化目标，如:消耗最少的时间，完成最多的任务等，并且在运行过程中不发生任务遗漏，锁死等情况。在这些问题中，仓储物流机器人的调度策略选择对于机器人在运行中是否可以高效运行起着至关重要的作用。仓储物流机器人调度问题，特别是AGV调度问题正逐渐成为生产调度领域的重要热点研究之一[3]。本课题着重研究的就是仓储物流机器人的调度问题，通过对仓储物流机器人的任务调度过程进行分析，建立适当的模型，探索求解算法，最终在实例模型中解决仓储物流机器人的调度问题。1.2国内外研究现状1.2.1国外研究现状国外的仓储物流机器人调度研究从20世纪80年代开始兴起[4-7]，最初对于任务调度问题的求解，学者们认为可以将调度问题抽象成数学模型，通过数学模型对其进行描述，而后采用分支定界整数规划及混合整数规划来求解。Toshiyuki等[8]将无冲突路径规划和仓储物流机器人分派问题描述为整数规划问题通过精确求解的方式进行求解。Meersmans等[9]采用分支界定法与定向搜索算法求解自动化集装箱码头不同类型物料处理设备的集成调度问题。Bilge等[10]将柔性制造系统(FlexibleManufacturingSystem,FMS)中制造系统中的机器调度问题和物料搬运中涉及到的AGV调度问题结合起来考虑，而后将这个混合问题表述成一个混合整数规划问题，对于这个非线性的混合整数规划问题，通过数学精确求解的方式求解。以上两位学者都使用了数学精确求解的方式求解整数规划问题，这种求解方法虽然一定可以获得全局最优解，但只限于解决小规模调度问题，随着问题规模的增大，数学精确求解的计算量成指数倍增长，求解问题也就变得毫无可能。相比精确求解法，启发式算法则有其独特的优势。启发式规则的建立是运用启发式算法的基础，Egbelu等[13]整理了在作业车间中产生的调度问题中涉及到的启发式规则，这些规则包括运行时间最长/短、运送距离最长/短、队列中剩余输出空间最小/大、AGV闲置时间最短/长和最近/远AGV等，最终得出这些规则对系统作业性能的影响。Jawahar等[14]则提出一种启发式算法，他们研究生产过程中AGV调度系统运行和生产过程结合起来的问题，该启发式算法采用操作时间、运输时间等AGV分派的相关因素来解决指派冲突。Sabuncuoglu等[15]研究了柔性制造系统在交货期不同时AGV调度规则的变化对机床工件调度会产生何种影响。Singh等[16]探究使用仿真模拟的方式解决调度问题，他们的研究采用自定义的调度规则，评估了进行物料分配的AGV调度问题中物料分配效率和均匀性的仿真性能。Kim等[17]对启发式规则提出了他们的观点——一种多属性指标加权法，这种方法在解决考虑AGV空载路程和工件等待时间这两项因素为主要因素时，被证明为有效的。Ulusoy等[18]则认为柔性制造系统包含AGV调度问题，也就是将柔性制造系统看作机床调度和AGV调度2个子问题，采用迭代启发式方法结合滑动时间窗进行处理。还有一些学者则是采用建模与仿真方法进行求解。Cenk等[19]同样认为柔性制造系统包含AGV调度问题和柔性机床，通过建立智能柔性制造系统对柔性机床和AGV进行同时在线调度。Nishi等[20]采用时间Petri网分解方法进行AGV调度与无冲突路径规划。而Giglio等[21]则将AGV的管理权分派给一个新的混合系统，这个系统由Petri网和多Agent系统共同组成，其中Petri网主要描述路径，AGV行为和车间中的其他资源相互之间的关系，行为决策则由Agent系统负责。Yim等[22]针对柔性制造系统结合Petri网建立模型，将AGV的分派系统联合Petri网共同控制AGV指派。采用模拟方法研究不同AGV分派规则对FMS运行的影响。Olatunde等[23]采用时间有色Petri网(TimedColouredPetriNet，TCPN)和混合启发式搜索方法求解机床和AGV同时调度问题。Mousavi等[24-25]针对多目标AGV调度问题，对求解结果采用Flexsim仿真软件进行验证。Viharos等[26]采用离散事件仿真方法对机器人装配系统中每台工作站的装配工序和AGV进行调度控制，使总的制造时间最短。1.2.2国内研究现状国内关于仓储物流机器人调度问题相关研究比国外要晚近30年[3]。国内学者对于精确求解法，排队论法等传统分析方法研究较少，马越汇等[27]采用混合整数规划模型研究自动化集装箱码头在考虑交通拥堵等不确定情况下的AGV调度与配置问题。霍凯歌等[28-29]将自动化集装箱码头多载AGV调度问题描述为混合整数规划模型，并使用数学精确求解的方法求解。管贤平等[30]研究提出一种多属性任务调度方法，这种任务调度方法能动态调整权值，且可以避免调度目标发生锁死现象。肖海宁等[31]在管贤平等人研究的基础上增加在线实时调度的要素，提出柔性制造系统中AGV在线实时多属性任务调度的方法，此方法通过启发式调度规则有效防止系统锁死的发生。黄一钧[32]建立排队论模型，以最小总成本为目标，求解AGV的最佳数量配置问题。金芳等[33]采用逗留时间和平均等待长度为指标，建立基于启发式规则的调度算法，用于解决AGV调度中出现的N/M/1排队模型。对于建模与仿真方法，国内学者则有大量的研究，桑泽磊[34]运用合同网协议下的协商机制，建立以Agent系统为基础的信息平台，用以车间内的AGV调度，该平台的鲁棒性和柔性较好，且能对环境扰动及时做出响应，调度效率较高。经建峰[35]则提出多AGV调度中，AGV相互之间自主交流的协商机制，给出各个AGV之间出现冲突时，解决冲突的途径，进而建立一种分布式的AGV调度系统。李晓萌等[36]基于Agent系统结合协作学习、多级决策理论提出一套独特的动态分布式调度策略，用以解决任务调度中多AGV的调度问题。任小龙[37]针对FMS中工件加工和AGV运送物料同步调度问题，以Petri网为基础建立相关模型，用以研究任务调度，寻求更优的AGV分派、规划策略。李国飞[38]则以Petri网为基础提出二次变迁Petri网分解方法，这种方法等价于将Petri网模型拆分成多个子网，每个子网对应不同的AGV，同时为多个AGV求解不同时刻下Petri网变迁激活的顺序，以获得整体最优路径问题。柯冉绚等[39]基于Netlog软件针对自动化集装箱码头建模并进行仿真模拟获得车道数、岸桥与AGV的最佳配比。李军涛等[40]通过比较交叉环单向循环搬运系统在制定不同的调度规则时AGV的搬运效率，运用仿真模拟手段，找出更为优质的调度规则。杨武平[41]对工件派工规则和AGV调度这两个问题形成的类组合策略优化问题进行了研究，在模具智能车间背景下，通过Plant-Simulation求解了该问题。韩晓龙[42]采用em-plant建立仿真模型对自动化集装箱港口中AGV数量配置及任务调度策略进行分析，提出了有效的解决方案。对于仓储物流机器人调度问题而言，往往只用一类方法是很难解决实际问题的，虽然我们可以从仿真模拟实验中建立的实际情况模型模拟现实中的情况，方便求解，但却很难从仿真实验中寻找到一般性规律；而传统分析法容易发现规律，但却难以求解。因此，对实际调度问题的研究，通常是先用传统分析法寻求一般规律，再根据规律进行仿真模拟，最终得出优化策略。总之，通过对国内外研究现状的了解，在仓储物流机器人任务调度问题的研究上，国内外学者都已经取得了一定的进展，但随着物流行业的飞速发展，物流需求的不断提高，对仓储物流机器人的调度效率要求也在渐渐提高。因此，在仓储物流机器人调度问题上，提出一种可行且高效的调度算法十分必要。1.3论文研究内容及技术路线论文通过搜集整理仓储物流机器人调度问题的研究现状，详细分析并阐述仓储物流中搬运机器人的主要任务，并根据其调度过程通过建立数学模型对实际的仓储物流机器人任务调度问题加以描述。论文对烟花算法和其他各类智能算法的实现原理，算法步骤和算法优缺点进行整理，结合仓储物流机器人任务调度问题，提出一种基于烟花算法且适用于仓储物流机器人任务调度的任务调度算法。该算法结合仓储物流机器人任务调度特点，对烟花算法的算子进行改进，并验证改进后的算法在解决一般性问题是否具备有效性。最后对实例问题进行实验设计，通过实验得出的实验结果对得到的结果进行分析，分析得出改进后的烟花算法在解决仓储物流机器人任务调度问题上具备一定优势，其算法收敛速度较快，得到的任务调度序列所耗费的总时间与其他算法、基本烟花算法相比更短一些，这意味着该算法在求解精度上同样具备优势。论文的主要内容包括:（1）研究仓储物流机器人调度问题的类型及特点，对仓储物流机器人调度任务基本流程，步骤进行介绍和分析。（2）通过研究烟花算法基本原理，算法步骤，实现过程，分析烟花算法在解决调度问题上具备的优势和不足，对于算法容易陷入局部最优的缺陷，提出熄灭算子对烟花爆炸中产生的相对劣质的烟花进行处理，筛选劣质烟花产生火花中距离较近的火花，将其熄灭并重新爆炸产生新的火花。对于收敛速度方面，为提升其效率，优化选择算子的选择策略，加快收敛速度。（3）结合烟花算法提出一种仓储物流机器人调度算法。仓储物流机器人任务调度问题是离散型问题，而烟花算法面向的是解空间连续的优化问题，所以针对仓储物流机器人任务调度问题的特点，对烟花算法中爆炸算子的爆炸范围，子代数目等参数参与计算的方式进行重设计，同时为了有效增加种群的多样性，将高斯变异火花用遗传算法中的基因变异法替代。（4）通过对各种智能算法的了解、分析，结合仓储物流机器人任务调度问题的背景设计仿真模拟实验，仿真实验选用矩阵计算更加高效的Matlab进行，将改进后的算法与遗传算法相比较，验证改进烟花算法对解决该问题具备优势，将改进后的烟花算法和改进前的相比较，验证改进后算法的有效性，最终得出该算法拥有更快的收敛速度，在求解精度上也更具优势。1.3.1论文组织结构第一章是全文的绪论，这部分主要是对论文的选题背景、论文研究的目的和选择仓储物流机器人任务调度研究作为选题的意义进行详细介绍，通过研究国内外专家学者在和仓储物流机器人任务调度相类似的问题上的已有研究，提出研究仓储物流机器人调度算法的必要性，最后对本文的组织结构进行简要的介绍，明确本文的研究内容。第二章则聚焦仓储物流系统，首先通过路径模型概述，了解仓储物流系统的类别，接着通过对任务调度原理的分析，得出仓储物流机器人调度问题的特点，并探索任务调度的步骤。通过对仓储物流调度问题的基本描述，建立仓储物流机器人调度的基本模型，为后文中对仓储物流机器人任务调度实例的相关研究打下坚实基础。最后对专家学者们研究任务调度问题常用的一些智能算法进行简单的介绍。第三章从仓储物流机器人调度任务实例出发，对实例仓库进行建模分析，将仓库环境以节点网络的形式展现出来，并对实例调度问题的优化目标做出定义，而后又结合改进烟花算法和遗传算法特点，提出两种算法在仓储物流机器人调度任务中需要进行哪些步骤，明确实例仓库情形下任务调度各步骤中的工作内容。第四章是对烟花算法的研究及改进，通过对烟花算法的原理，算法组成，算法步骤，算法优缺点的介绍，分析出基本烟花算法在解决优化问题中的不足，并提出改进方法，用增加熄灭算子的方式对劣质烟花产生的近距离火花实施熄灭处理，增加劣质火花对远距离空间的探索范围，提高烟花种群的多样性，避免算法陷入局部最优，增加算法的求解精度。最后通过测试函数对改进后的烟花算法有效性进行验证。证明改进烟花算法确实有解决一般优化目标问题的可行性。第五章主要以第三章所提出的实例模型为基础，对烟花算法和遗传算法两种算法的对比实验进行设计，确定仿真模拟实验运行的各项参数，通过实验得出仿真模拟数据，并对得出的数据进行简要的分析和探讨，最终得出改进烟花算法在仓储物流机器人调度问题上有着收敛速度较快求解，精度较高的优势。

1.3.2技术路线图1.2技术路线图

第2章仓储物流系统研究2.1路径模型概述随着导航定位技术的不断更新换代以及信息通讯技术的飞速发展，仓储物流机器人的导引方式越来越多样化。如前所述，目前为止在实际应用环境中主流的仓储物流机器人按照引导方式可分为地磁导引，通过在物流机器人运行路径上设置磁体引导机器人移动；导轨导引，通过在物流机器人运行路径上设置导轨引导机器人移动；激光导引，通过在物流机器人运行路径上设置激光制导装置引导机器人移动；惯性导引，利用惯性引导机器人移动；地图导引，在物流机器人管理系统中预先设置匹配的地图引导机器人移动。引导方式还可以从路径是否固定大体分为固定路径与非固定路径。根据现有的仓储物流机器人通行规则和应用环境等刚性需求，智能仓储物流系统中路径模型主要可分为四种情形[43]:（1）在一个智能仓储物流系统中，任意时间段内的任意一条通路只能允许一台仓储物流机器人通过，在这条通路上，机器人也只能沿着一个固定的方向前进，不能反向行驶，这种路径模式被称为单通路单向路径模型。在这种路径模型下，所有的通路都不存在对向冲突，是一种较为简单的通路模型，但由于通路只能单项同行，前面的机器人在装卸货物时，后面的机器人只能等待，而路径选择方面也会受到非常大的限制，运输效率相对其他路径模式而言非常低下。（2）单通路双向模型；顾名思义，这种路径模型与单通路单向路径模型相似，同样对于任意的通路只让一台仓储物流机器人通过，不同的是这种模型允许机器人反向行驶。这意味着可能出现两台机器人对向行驶的情况，这也是此类路径模型下调度系统需要考虑的问题。由于机器人可以双向行驶，在路径选择上更加自由，较单向通行的模型提升了运输效率，相对的也使得运输环境更加复杂，对调度系统的调度策略要求更高。（3）双通路单向模型；现实生活中的道路交通基本使用的都是这种路径模式，在该路径模型中，每条道路都可以让两台机器人同时通行，且通行的方向互为反向，如道路左侧只允许向东，右侧只允许向西。这样的路径模型较前两种更加灵活，避免大部分的对向行驶冲突，运输效率也因此提升不少。需要考虑的是在路口处，由于双通道且单向允许通行的规则，组合情况较多，对调度能力的要求也更高。（4）双通路双向模型；双通路双向模型是四种通路模型中最为灵活的一种。灵活性的提升主要原因在于每条通路的两条路径都允许两种方向的机器人通行，这极大的提升了道路的通行效率，而代价则是对调度能力的要求也大幅度提升。这里的调度能力涉及到的关键部分是动态调度部分，在处理多个执行任务的机器人在同一通路发生对向冲突或是路口处的路径选择问题上，需要考虑多种情况，这对采用该路径模型的调度系统运行效率来说是巨大的考验。本文所使用的模型在通行方向上是双向的，通路方向上则是单向的。2.2任务调度原理2.2.1任务调度问题分类根据仓储物流机器人在执行任务期间获取信息的情况，可将仓储物流机器人调度问题分为仓储物流机器人静态调度,仓储物流机器人动态调度和仓储物流机器人资源联合调度:图2.1三种任务调度过程示意图（1）仓储物流机器人静态调度仓储物流机器人静态调度是指在某一静态时刻，通过对仓储物流机器人指派任务序列，解决仓储物流机器人调度问题。静态调度问题常见于基础算法或基本模型的研究，为了体现算法有效性，模型的准确性，静态调度可以直观的反应算法或模型变化带来的性能指标变化。其常见的优化目标包括:任务时间最短，仓储物流机器人利用率最高，仓储物流机器人数量最少，拖期延迟最小，物流成本最低等。其常见的约束则包括:仓储物流机器人容量约束，仓储物流机器人充电约束，任务顺序约束，路径方向约束等。（2）仓储物流机器人动态调度仓储物流机器人动态调度是指在考虑动态扰动，如任务变更、设备故障、冲突死锁等问题下，通过对仓储物流机器人进行实时任务指派，解决仓储物流机器人调度问题。动态调度更接近实际生产中的情形，多适用于解决实际的问题。其常见的优化目标包括:任务时间最短，仓储物流机器人数量最少，搬运时间最短，仓储物流机器人利用率最大，仓储物流机器人负荷均衡，仓储物流机器人最小行走时间等。其常见约束则包括:仓储物流机器人容量约束，仓储物流机器人充电约束，任务顺序约束，路径方向约束等。（3）仓储物流机器人资源联合调度仓储物流机器人资源联合调度多出现于生产制造系统当中一般为多目标优化问题，资源联合调度主要是指在仓储物流机器人调度过程中需要考虑其他生产工序的资源产出或使用情况，然后根据这些情况对仓储物流机器人实施任务指派，以达到任务调度期望达到的优化目标。调度问题中最常见的几类优化目标包括：完成任务时间最短，消耗资源最少，资源利用率最大，惩罚成本最低，仓储物流机器人负荷均衡，每个工件在队列中等待时间最少等。而常见的优化目标约束则包括:工件队列中的缓冲量，工件工序约束，仓储物流机器人容量约束，仓储物流机器人充电约束，任务顺序约束，路径方向约束等。本文研究的仓储物流机器人任务调度问题属于仓储物流机器人静态调度问题，静态调度问题可以通过仿真模拟对比实验更准确的反应本文提出算法的有效性。2.2.2任务调度步骤仓储物流机器人任务调度系统主要工作步骤可分为三层:生成任务，分配任务，完成任务。其中，分配任务和完成任务称为资源分配，在系统生成的任务全部完成之前，智能仓储物流系统将会不间断的进行任务的分配并指导仓储物流机器人完成任务，直至系统不再生成新的任务。（1）生成任务。本文系统中由于不包含上位机系统，因此本文中所有实验的任务均为人工生成。（2）分配任务。系统在分配任务时需要对未完成任务的目标地点和空闲的仓储物流机器人情况进行实时的监测，在系统生成新的任务后能够立即根据目标地点将任务分配给空闲且状态正常的仓储物流机器人。分配任务的主要约束就是均衡性，在保证所有任务完成时间最短的前提下，实现任务的均衡分配。（3）完成任务。完成任务的过程为仓储物流机器人从起始地点到达任务的目的地，即为路径规划过程。为了高效有序的完成任务，需要对仓储物流机器人进行路径规划，而路径规划的合理性也影响着任务的分配。系统需要根据任务的具体分配情况来对仓储物流机器人进行路径规划，保证仓储物流机器人在无死锁、无冲突的情况下完成任务，并也要根据任务的完成情况来对任务的分配进行调整，力求仓储物流机器人完成任务时间最短。2.2.3基础问题描述普通的仓储物流布局由仓储物流机器人，货物存放区，货物装卸区组成，整个环境布局图如图2.2所示，蓝色胶囊为仓储物流机器人以及其起始区域，黄色方块表示货架，最下面是完成任务的卸货区，两个货架之间的通道允许两台仓储物流机器人并排通过，中间通道可允许两台仓储物流机器人并排通过。图2.2仓储物流布局图为了方便求解，本文将整个环境转化为节点图形式，仓储物流机器人起始节点为一个节点。货架每个货物位置为一个节点，货物装卸区为一个节点，并且将仓储物流机器人起始位置设为1号节点，货物按顺序编号2到n节点，装卸区为最后一个节点。为了保证仓储物流机器人调度系统的顺畅运行，本文对调度过程做如下合理假设:（1）仓储物流机器人装卸货时间忽略不计；（2）仓储物流机器人匀速行驶，不考虑转弯或其他情况造成的减速；（3）每台仓储物流机器人可以搬运多个货物，但不能超出最大载重量；2.4任务调度算法智能优化算法能解决其他方法难以求解的复杂组合优化问题，因而广泛应用于调度优化方面，仓储物流机器人调度中用到的智能优化方法包括粒子群算法(ParticleSwarmOptimization,PSO)、遗传算法(GeneticAlgorithm,GA)、差分进化算法(DifferentialEvolution,DE)、蚁群算法(AntColonyOptimization,ACO)等。（1）遗传算法遗传算法（GeneticAlgorithm，GA）的起源最早可以追溯到20世纪60年代初期，当时由Holland教授的学生在其博士论文中首次提出，论文主要探讨该算法在博弈中如何应用，但这类早期研究缺少指导性理论，也没有计算工具作为支撑。直到1975年JohnHolland教授出版《自然系统和人工系统的适配》，于该书中对遗传算法的算法原理，算法的基本方法及步骤进行系统阐述，推动遗传算法的发展。遗传算法本质上是模仿生物的进化过程而得出的计算模型[44]，达尔文在生物进化论中提出自然选择，而现代进化论中提出基因突变的概念，这两大概念促成了遗传算法的诞生，遗传算法也因此成为一种探索最优化问题的常用算法。遗传算法流程如图2.2所示。图2.2遗传算法流程图通过流程图可以看出，遗传算法在求解问题时先将问题的解空间进行染色体编码，使解和求解用的染色体成一一对应关系，然后随机产生初始种群，在对当前种群进行交叉、变异操作后，就可以得到新一代的染色体，而后通过计算每条染色体的适应度值（目标函数的最优值）来对新一代染色体做出评价，选出最优质的一部分子代成为下一代的父基因。为了防止以获得的最优解因为处在父代基因中被舍弃，我们会将父代基因中最优的解和子代中所有基因相比较，取出其中最优的一个基因，让其必定可以遗传到子代。这样就得到历史最优解和子代基因的集合，只要对这个集合再进行上述操作，重复足够的次数后，就能将解无限接近全局最优解。遗传算法在解决任务调度问题上具有一定优势，特别是对指派问题的求解上，由于指派问题的解空间一般是不连续的解空间，遗传算法的基因序列可以很好的模拟指派任务的组别和序列，而通过遗传算法与其他算法的结合，混合后的算法在扩展性上有着明显的优势，鲁棒性也较好。遗传算法求解任务调度问题的不足主要在于遗传算法的两种算子较为复杂，交叉操作通过交换一对基因中部分基因实现，交换后的两个解和交换前的两个解相比，在目标函数上很难体现其迭代规律，因此遗传算法在收敛速度上并不具备很大的优势。变异操作本质是为了增加解的范围，防止陷入局部最优，但在遗传算法中变异基因受变异概率影响，其作用效果有限。总而言之，遗传算法在求解中，初始参数对算法求解情况影响较大，较好的参数设定可能提升算法效率，反之亦然。（2）粒子群算法粒子群算法是对自然界中鸟群觅食的过程进行模拟得出的智能算法，这种算法最早由J．Kennedy和R．C．Eberhart等人提出[45][47]。粒子群算法原理与大部分智能算法类似，首先产生初始解集合，然后通过适应度值对粒子群中粒子的位置、速度进行改变，引导粒子向更优区域飞行得到全局最优解[46]。其算法流程图如图2.3所示。图2.3粒子群算法流程图在粒子群算法的迭代过程中，根据粒子群体中的不同个体得出的适应度值，驱使粒子在解空间内运动，所有的粒子都在朝极值位置移动，直到得出全局最优解。该算法的步骤与参数设计都较为简单，算法本身容易实现，能适用于大部分优化求解问题，且在求解过程中算法收敛速度较快。但缺点也很明显，由于算法全局搜索性不强的特点，容易陷入局部最优，在求解离散问题时收敛速度过慢。（3）差分进化算法差分进化算法(DifferentialEvolution，DE)由Storn和Price于1995年首次提出[48-49]。主要用于求解实数优化问题。该算法是一类基于群体的自适应全局优化算法，属于演化算法的一种。该算法通过群体内个体之间的相互合作与竞争产生的群体智能来指导优化搜索的方向。该算法的基本思想是:从一个随机产生的初始种群开始，通过把种群中任意两个个体的向量差与另外的个体求和，若得到的新个体适应度更优，就用新个体代替旧个体，否则依然使用旧个体继续执行进化操作。以此方式不断迭代，最终趋近全局最优。图2.4展示了差分进化算法的流程。图2.4差分进化算法流程图在基本的差分进化算法中，参数设置对算法本身的影响非常大，特别是变异算子中的变异率，该值设置过小会导致种群的多样性降低，以至于陷入局部最优，该值设置过大算法就很难收敛。在特定情况下，差分进化算法还可能出现算法停滞。（4）蚁群算法蚁群算法作为放生智能算法的一种，在20世纪90年代被提出。意大利学者Marco．Dorigo等人发现自然界中蚁群觅食的方式可以作为启发式规则用于算法的求解[50-51]。蚁群觅食主要通过每一只蚂蚁在寻找食物过程中在路径下留下的信息素来传递信号，告诉其他蚂蚁这条道路上的信息。根据每条路上的信息素浓度，后面经过的蚂蚁就会知道如何找到食物。信息素浓度越高，表示该路径越优质，反之亦然。图2.5展示了蚁群算法的算法流程。图2.5蚁群算法流程图蚁群算法在求解优化问题具备一定的有效性，使用的概率搜索方式使算法更容易寻找到全局最优解。由于使用的使正反馈机制作为信息传递方式，在算法初期收敛速度相比其他算法更慢，并且在初始时刻，信息素浓度相同的情况下蚂蚁选择路径使完全随机的，如果开始得到的为局部最优解，在信息素反馈机制下，信息素浓度不断增加，使算法陷入局部最优。2.5本章小结首先通过路径模型概述了解仓储物流系统的类别，接着对任务调度原理的分析，得出仓储物流机器人调度问题的特点，并探索任务调度的步骤。通过对仓储物流调度问题的基本描述，建立仓储物流机器人调度的基本模型，最后对调度问题常用的智能算法进行简单的介绍，研究各个算法的算法原理及不足之处，为后面烟花算法的研究打下基础，也为最终求解仓储物流机器人任务调度问题做好铺垫。

第3章仓储物流机器人任务调度实例3.1引言上一章本文对仓储物流系统的路径模型，任务调度原理，任务描述和基本的任务调度模型及算法进行详细的描述，本章节主要针对仓储物流机器人任务调度实例进行实例问题描述，建立实例模型并将其转化为数学模型，最后结合该问题的优化目标对模型的输入输出给出清晰定义。3.2仓库实例建模分析3.2.1实例仓库现状任务调度实例中的仓库是某物流公司的成品仓库，该仓库于2013年建成，年出库量约为3万余件，最大静态库存量5000件，业务范围主要涉及该公司的三类产品，通过该仓库外发或储存。本文主要探讨该仓库的成品存放区，对于该区域内的成品货物出入库过程中，仓储物流机器人的任务调度问题。仓库左边为仓储物流机器人调度区，中间货物存放区共计拥有100个货架，沿横向中轴线两侧摆放，每侧共计5排货架，货架两边都可以摆放货物，每排货架共有五个货位。在仓储物流机器人需要搬运货物时，首先从仓储物流机器人调度区行驶前往目标货架，通过机械臂将货架上的货物取出放在仓储物流机器人上，仓储物流机器人取到货物则继续前往下个目标货架，直至载满系统分配的任务，最终驶向装卸区。仓库平面图如图3.1所示。

图3.1实例仓库平面布局图

对于本章的实验模型，我们可以参照第二章的方法，将仓库环境转化为节点模型，整体模型由仓储物流机器人，货架，装卸区组成，所有的通道都支持仓储物流机器人双向通过。在节点地图中每个仓储物流机器人的路径都只存在三种情况:起点到任务地点，任务地点到下一个任务地点，任务地点到终点。而如果将其中的任务地点到下一任务地点提取出来，所有的仓储物流机器人任务——任务路径的总和就是所有的任务地点的串联。这样就把一个多车辆调度问题转化成为一个TSP问题，而通过建立节点与节点之间的距离表可以将此问题进一步简化。3.2.2数学模型构建通过对实例仓库现状的分析，得出解决仓储物流机器人任务调度问题目标在于如何缩短任务完成的总时间，对完成任务总时间的求解涉及到的参数，变量如下：（1）集合N=1,2,…,n:所 M:货物节点集合 P:仓储物流机器人的集合（2）参数 p:仓储物流机器人编号 k:第k台机器人为完成任务时长最长的机器人 Aij:节点i到节点j之间的路段 tij:机器人通过A W：仓储物流机器人的最大载重量 wi（3）决策变量X仓储物流机器人在完成任务的同时要保证路径最短，即完成任务时间最短，且在完成任务过程中不得超过最大载重量。通过以上分析及调度问题模型建立，可得出目标函数为:minT=i∈Nj∈Ntijxkij s.t.i∈Nj∈Np∈Ptijp∈Pxpij=1j∈M p∈Pxpijwi≤Wi∈M 式（3-1）为目标函数，第k台仓储物流机器人完成任务的时间最短,式（3-2）表示第k台仓储物流机器人是所有仓储物流机器人中任务时长最长的一台，式（3-3）表示所有的任务都对应一个仓储物流机器人，即所有的任务都被完成了，式（3-4）表示所有的仓储物流机器人都不超过其最大载重量。3.3智能算法对仓储物流调度实例模型的求解分析智能优化算法要解决的一般是最优化问题。最优化问题可以分为（1）求解一个函数中，使得函数值最小的自变量取值的函数优化问题和（2）在一个解空间里面，寻找最优解，使目标函数值最小的组合优化问题。典型的组合优化问题有：旅行商问题（TravelingSalesmanProblem，TSP），加工调度问题（SchedulingProblem），0－1背包问题（KnapsackProblem），以及装箱问题（BinPackingProblem）等。经典的优化算法有很多，按照搜索域的大小可分为：局部搜索算法，全局搜索算法；按照规划问题的静动态可分为：静态规划，动态规划；按照优化目标是否线性可分为：线性规划，非线性规划；按照求解规则可分为：智能算法，数学精确求解法。而智能算法又包括遗传算法，粒子群算法等仿生算法。求解特定的最优化问题，并不是所有的优化算法都能起到很好的效果，而是需要具体问题具体分析。本文提到的算法都是从局部搜索算法中发展而来，所谓局部搜索算法是指利用贪婪思想在函数的领域进行求解搜索，当算法找到一个更优值时，就放弃前一个值。这种搜索方法在没有其他极值干扰的情况下效率很高，但出现其他极值时就容易陷入局部最优。而现有的智能算法对算法的策略进行改进，使其通过多个算子同时进行局部搜索，强制移动解的位置等类似的方法使搜索域扩大，提高算法发现全局最优值的概率。智能算法在求解过程中使用的解空间一般为连续解空间，而仓储物流机器人调度问题的解空间则是离散解空间，针对这个问题一般有两种解决途径，一是通过映射将离散解空间编码，使其成为相对连续的解空间，然后直接用算法进行求解，二是对算法进行调整，使其能够对离散解空间进行求解。在调度问题中，解空间可以看作一个任务节点矩阵，需要注意的是由于所有的任务必须完成，所以解空间不能有重复的或者遗漏的任务，也就是说，仓储物流调度问题的解空间实质上是一个任务列表的MTSP问题，而不同解之间的距离可以看成任务列表的差异程度。根据求解过程分析，结合算法特点，提出算法基础步骤如下:步骤1:初始化解空间；步骤2:计算当前解集中各个解的适应度值。步骤3:筛选出优秀的子代解；步骤4:增加变异解；步骤5:保留优秀子代；步骤6:判断是否满足终止条件，满足则终止不满足则转至步骤2；步骤7:通过累计概率值进行轮盘赌操作，对适应度好的个体提供更大的被选中概率；步骤8:输出最优序列，算法终止；

第4章烟花算法及其改进策略4.1烟花算法工作原理分析烟花算法最初是由谭营教授在2010年提出的一种非生物种群群体智能优化算法[52-54]。该算法是一种并行式寻优算法，模拟烟花爆炸的过程，这种组合优化算法在求解复杂的优化问题上性能良好[55]。烟花算法的基本步骤与其他的智能算法，包括仿生算法的步骤大致一样，先根据初始解确定初始种群，接着对初始种群进行爆炸操作，产生下一代烟花的候选者，经过变异筛选，选出适应度值较优的一部分火花作为下一代烟花，多次迭代最终得出最优解。4.1.1烟花算法的组成烟花算法主要由爆炸算子，变异算子以及选择策略三部分组成，在爆炸算子和变异算子中通过映射规则将产生的越界火花映射回解空间。烟花算法的变异算子属于高斯变异算子，变异过程如图4.1所示。图4.1高斯变异流程图高斯变异操作实际上是利用高斯分布概率函数产生一个随机数，用产生的随机数对原本的火花进行一定程度的位移，以达到增加种群多样性的目的。通过爆炸算子和变异算子的操作，特别是变异算子，产生的火花可能会出现超出解空间的情况，这是因为变异根据高斯分布概率产生的随机数进行，这就有可能产生非常大或非常小的数字。对于这类火花，因为其携带一定的信息，不能将其直接舍去。所以需要对其进行映射操作，将保存下的信息利用起来。随后，运用筛选策略在新的烟花种群中选出下一代烟花。筛选操作包含两个步骤，首先根据精英选择策略将质量最好的烟花保留到下一代，再根据基于距离的选择策略选择剩余的烟花。烟花算法的框架如图4.2所示。图4.2烟花算法框架图4.1.2烟花算法实现原理烟花算法是将烟花在空中爆炸的过程应用于解空间的探索模式，在此基础上增加特定的选择策略而形成的智能算法[54]，烟花算法在爆炸后产生大量火花，对这些火花进行变异后，选择一部分适合的火花作为下一代烟花保存下来，这就完成了一次迭代，当迭代次数达到设定值，或是求得的解达到求解精度要求时，烟花算法就输出当前最优解并终止算法。这个过程主要包括以下基本的步骤[55]:(1)初始化参数并产生初始解，根据初始解生成初始烟花种群。(2)对当前的种群中所有个体计算其适应度值(3)对每个烟花个体进行爆炸算子操作，爆炸的参数根据初始设定的参数和适应度值计算得到。爆炸后产生的火花和爆炸前适应度最优的烟花共同组成新的种群。(4)将新的种群根据变异概率选择少量火花进行变异操作，用以增加种群的多样性(5)根据选择策略对当前种群进行筛选，并计算出所选的种群中最优的适应度值，若该值满足求解精度要求或达到迭代的最大值，则算法终止，否则返回第二步。烟花算法的爆炸算子设计中，为了避免算法过早收敛于局部最优值，进行爆炸的烟花遵循着一定的规律，即优质的烟花在爆炸过程中能产生更多的火花，且火花较为集中，而劣质的烟花在爆炸过程中产生的火花则非常稀疏，并且分布的范围更广。从图4.3可以看出，两种质量的烟花在自然界中爆炸也基本遵循这个规律。图4.3爆炸火花质量示意图产生爆炸火花的数量如公式（4-1）所示。QUOTESi=M∙ymax−f(Xi)+εi=1N(y式中 ymax M ——限制火花产生数量的常数 ε ——为避免出现除零操作，增加的机器最小量在爆炸算子产生火花时，为了避免产生的火花太多或太少而影响算法的性能，需要对计算得出的烟花数目Si加上一定的限制条件，如公式（4-2）所示。QUOTESi=roundα∙M,Si<α∙Mroundβ∙M,式中 α ——用于确定最少火花数的常数 β ——用于确定最大火花数的常数 round() ——对括号中的数进行四舍五入取整烟花算法在求解过程中为了保证能有效收敛到最优值，适应度越好的烟花应当更加注重局部搜索，即优质烟花的爆炸半径应当适当缩小，而对于适应度差的烟花，只有扩大其搜索半径，才更有可能找到局部最优值所在的位置，即需要扩大劣质烟花的爆炸半径，以达到全局搜索的目的。因此，每个烟花的爆炸半径可由公式（4-3）表示。QUOTEAi=A∙f(Xi)−ymin+εi=1N(f(式中 A ——控制烟花爆炸半径的参数 ymin 爆炸产生的烟花可以随机出现在母代烟花的Ai范围内，通过调整M和A，即可实现对子代搜索范围的调整，高效的求解算法取决对搜索范围的控制，不同情形下，使用不同的搜索策略，能有效提高对该问题的求解速度和精度。为了避免算法陷入局部最优，就要使烟花种群增加多样性，不能只在初始种群附近搜索。烟花算法采用的是高斯变异，变异算子主要将一个服从高斯分布的随机数与烟花的位置坐标相乘，得到的新坐标即为高斯变异后的烟花位置坐标。其方法如公式（4-4）（4-5）所示。QUOTExik=xik∙e xik=xLB,k+x式中 xik ——烟花i e ——高斯分布函数的值 xLB,k xUB,k 公式（4-4）表示若烟花i被选为变异个体，则需要对其随机k个维度进行变异，即将k个维度的值分别乘以一个服从高斯分布函数的值，而这个值可能非常大，也可能非常小，所以变异后的k个维度可能出现越界情况，于是（4-5）提供了将越界数据映射到该维度中可行域中的方式。烟花算法中每一代种群进过爆炸算子、变异算子的操作后，得到的新一代火花个体，计算所有的个体适应度值，将适应度最优的个体保留作为下一次迭代的母本之一，其余的个体保留的规则按照轮盘赌的方式进行，概率由该个体的适应度值和最优个体的适应度值的比值决定，即适应度越好的个体越由概率被选中，但不是必定选中轮盘赌概率如公式（4-6）所示。QUOTEPi=fifmax 其中fi表示轮盘赌决定是否保留火花个体的适应度值，fmax表示这一代火花个体中适应度最好，即已经被确定保留的火花个体的适应度值。烟花算法的流程如图4.4所示。图4.4烟花算法流程图算法4.1烟花算法伪代码算法4.1烟花算法伪代码1：初始化相关参数2：生成M个初始解，即初始烟花集合Parent_X3：计算Parent_X的适应度值集合Parent_X_Fitness4：if最大迭代次数T>迭代次数ido5：for母代烟花个体PiinParent_Xdo6：计算母代烟花个体Pi的爆炸产生的子代火花数量S7：计算母代烟花个体Pi的爆炸范围A8：while产生子代火花个数j<Sido9：子代火花集合Candidate_X[j]=rand(0,Ai)10：j=j+111：endwhile12：endfor13：for子代火花中高斯变异火花Xido14：产生变异维度随机数k15：xik16：endfor17：for子代火花集合Candidate_Xido18：计算Candidate_Xi的适应度值保存至集合Candidate_X_Fitness中19：endfor20：保留最优适应度值对应的子代火花21：for除最优适应度值外的火花do22：ifPi23：保留该烟花24：endif25：endfor26：i=i+127：endif4.2烟花算法性能分析烟花算法在求解各类复杂问题中都表现优异，如CPU性能优化，电网电力配送，垃圾邮件检测算法，施肥问题等。烟花算法适用于组合优化问题，特别是在复杂问题处理上具有良好的性能，该算法不但具备现有智能算法的种种优点，还有以下特色[54]：瞬时性。烟花算法在初始解集合的基础上生成初代烟花，通过爆炸算子和变异算子产生新一代火花，火花根据一定的规则选择出适合的火花作为下一代烟花，未被选择的火花就此消失，这便是烟花算法所具备的瞬时性。分布并行性。在算法迭代时，母烟花在可行域内爆炸，同时在解空间中的不同区域进行搜索，这个过程时多个烟花并行的，且每一代烟花都是如此迭代，因此算法具有分布并行性。爆发性。烟花算法在爆炸算子的操作下，会产生多个火花，而初始烟花一般选择多个，每个烟花所产生的火花在下一代迭代时又会产生更多的火花，在火花数目限制范围内，火花是呈指数倍增长的，这也体现出烟花算法的爆发性。简单性。烟花算法在迭代中逐渐接近全局最优值，这个过程比较简单，每个烟花通过设定好的参数在周围产生火花，选择小部分火花变异后，留下一部分，就完成了一次迭代。可扩充性。烟花算法中每个烟花表示一个解，解的维度可根据问题的需要求解的变量个数确定，也就是说烟花算法不仅可以求解二维解空间问题，这种求解能力可以扩展到任意维度的解空间对应的问题中。多样性。种群的多样性决定一个智能算法是否容易在优化问题中陷入局部最优解，当种群的多样性越大，个体的分布越广，找到最优解的可能性越大，同时不会对算法效率造成太大影响。烟花算法在多样性方面具备一定的优势，主要体现在：a．爆炸算子设计。在爆炸算子设计中，烟花会根据其适应度值对爆炸后产生的火花范围，火花数量进行初步的限制。适应度较差的烟花产生的火花相比适应度好的更少，范围更大，这也是除了变异算子外，烟花算法拥有多样性，具备全局搜索能力的关键原因。b．高斯变异是烟花算法中第二个增加种群多样性的操作，高斯变异将爆炸算子中产生的火花通过高斯分布函数产生的随机数进行位置的移动，这种移动通过高斯分布概率控制，移动后的火花不仅可以覆盖整个解空间，甚至可能超出解空间，于是在变异后，烟花算法采用一定规则将超出解空间的火花映射回解空间内。这种覆盖全域的操作是主要增加种群多样性的原因。(7)适应性。烟花算法通过计算烟花们的适应度值来衡量求出的解的优劣，这种特性决定烟花算法不需要被求解问题必须为显示表达问题，因此烟花算法可以适用于多数优化问题的求解。由烟花算法的特性可见，烟花算法在求解仓储物流机器人任务调度问题上是非常适用的。4.3改进烟花算法对实例模型的求解烟花算法在求解过程中使用的解空间一般为连续解空间，而仓储物流机器人调度问题的解空间则是离散解空间，针对这个问题一般有两种解决途径，一是通过映射将离散解空间编码，使其成为相对连续的解空间，然后直接用算法进行求解，二是对算法进行调整，使其能够对离散解空间进行求解。本文采用的是第二种方法，要将烟花算法改造成求解离散解空间的算法，最主要的是调整爆炸算子和变异算子，根据爆炸算子的概念我们知道，爆炸算子是为了将每一代的信息通过距离这一数值传递到下一代烟花中，这样通过多代信息的启发，最终可以慢慢接近全局最优解。在调度问题中，解空间可以看作一个任务节点矩阵，需要注意的是由于所有的任务必须完成，所以解空间不能有重复的或者遗漏的任务，也就是说，仓储物流调度问题的解空间实质上是一个任务列表的MTSP问题，而不同解之间的距离可以看成任务列表的差异程度，因此，本文将烟花算法的爆炸算子计算出的爆炸后的位移半径做了取整处理，将其映射为任务列表中交换位置的任务数量，变异算子相比爆炸算子就简单很多，将高斯分布函数得出的函数值进行边界检验，然后取整，将取整后的数看作任务列表中交换位置的任务数量。通过对烟花算法的求解过程分析，结合烟花算法的改进策略，得出改进烟花算法的步骤包括以下10步:步骤1:参数初始化，设置最大迭代次数T，筛选参数F，烟花初始种群个数N，爆炸数量限制参数a和b，爆炸火花数量控制参数M，爆炸范围控制参数A，；步骤2:根据4.1对仓库调度模型解空间的可行域分析，随机初始化N个烟花位置。步骤3:运用爆炸算子计算初代烟花生成的新个体及新个体的适应值；步骤4:通过熄灭算子熄灭部分火花，并再次生成等量与熄灭个数的新火花；步骤5:按照变异概率随机选择需要变异的火花，进行变异操作，得到高斯变异火花，将其加入子代集合中；步骤6:对所有子代集合中个体的适应度值进行计算并排序；步骤7:通过累计概率值进行轮盘赌操作，对适应度好的个体提供更大的被选中概率；步骤8:将当前适应度最好烟花的和其他轮盘赌得出的子代烟花保存至下一代；步骤9:判断算法终止条件是否达成，达成则转至步骤10，没有达成转至步骤3；步骤10:终止算法并输出最优任务调度序列。4.4遗传算法对实例模型求解遗传算法在求解调度问题有着一定的优势，一般优化问题在使用遗传算法进行求解时都需要先将优化目标的解先进行编码，得到编码后的基因才能开始算法。而调度问题本质上就是一串不重复的数字代码，所以在使用遗传算法求解调度问题时可以直接将调度的任务序列作为基因使用，这样既方便计算，也不用在得到最优值后还要进行解码。对于仓储物流机器人任务调度问题，遗传算法的求解步骤分为以下九个步骤:步骤1:参数初始化，设定迭代次数T、种群规模N、交叉概率c以及变异概率m；步骤2:生成N个初代基因，并计算每个基因的适应度值；步骤3:利用交叉概率局决定参与交叉的初代基因；步骤4:通过累计概率进行轮盘赌，从步骤3得出的初代基因种群中选择出两个初代基因进行交叉；步骤5:判断子代是否达到种群规模，没达到则转至步骤3，达到规模则转至步骤6；步骤6:通过变异概率判子代变异的数量，并随机挑选出合适数量的子代进行变异操作；步骤7:对子代基因种群计算其适应度值，将适应度最好的个体直接加入下一代，剩下的N-1个子代由轮盘赌概率选择出；步骤8:判断算法终止条件达成与否，若条件达成，转至步骤9，若没有达成则转至步骤3；步骤9:终止算法并将最优任务调度序列输出。遗传算法的交叉规则一般分为两种，一种是部分匹配交叉法，一种是顺序交叉法，部分匹配交叉法是从两个父代基因中取位置长度都相同的一段基因，将他们位置交换，剩下的根据匹配关系进行逐一替换，替换过后需要对两段基因都进行冲突检测，防止一段基因中有两个相同的基因位。而顺序交叉法就简单很多，即从一个父代基因随机选择一段编码放到子代的对应位置，剩下的由另一个父基因按顺序将不重复的基因放入子代的空位中。这种方法操作容易，且不需要进行基因冲突检测。因此在最终的实验里，本文所编写的遗传算法代码中采用的是顺序交叉法进行交叉操作。4.5关于仓储物流机器人调度的烟花算法改进策略由于烟花算法在爆炸过程中产生的火花会受到爆炸数量和爆炸幅度的限制，质量较差的火花爆炸范围大，爆炸数量少，在随机产生位移的阶段，可能会出现火花都集中在上一代劣质烟花附近，从而难以达到劣质烟花的探索目的，降低整个种群的多样性。因此，可以在爆炸过程中，引入熄灭算子，针对适应度较差的个体，限制其在近距离范围内产生的火花数量，这样不但可以提高劣质烟花的搜索效率，也可以减少整个迭代过程中的无效计算量。4.5.1引入熄灭算子基本烟花算法在求解一般优化问题和各类组合优化问题时，其收敛速度和寻优能力都表现良好，但在烟花算法的爆炸算子中，爆炸得出的劣质烟花因为其爆炸数量和范围受烟花本身的适应度影响，只会产生少量火花，而这些火花时该算法提升寻优能力的关键，一旦生成的火花太过接近烟花本身，劣质烟花提升寻优能力的功能就无法发挥。最终导致算法陷入局部最优。为了避免劣质烟花有可能不产生远距离烟花的问题，本文引入熄灭算子，针对劣质烟花的产生的火花进行筛选，将距离过近的火花熄灭，并重新产生火花。筛选的距离标准使用欧氏距离来衡量。劣质烟花的评价标准按照种群适应度平均值来设定，而熄灭火花的范围则通过母代烟花的爆炸半径和子代火花适应度与最优火花适应度差值的比值来确定，这样既能保证优质火花不被熄灭，也可以提供更好的探索能力。筛选操作如公式（4-7）所示。QUOTEri=Ai∙F∙ymax−f(xi)f(x 式中 ri—— f(i)——i烟花的适应度值 ymax Ai F——熄灭算子参数算法4.2熄灭算子伪代码算法4.2熄灭算子伪代码1：初始化相关参数，载入母代烟花Parent_X2：筛选出适应度低于F的较差烟花Xi3：计算X的适应度值集合X_Fitness，记最优适应度值为X_Fitness_max4：for所有较差烟花do5：ifri=6：移除子代火花Xi7：重新由母代烟花Parent_X生成一个子代火花8：endif9：endfor4.5.2改进算法有效性验证对于改进后的烟花算法，是否能在求解优化问题中快速收敛，得到精度较高的解，是算法是否具有有效性的关键。为了验证改进后的烟花算法的有效性，本文选取了常见的CEC测试函数，通过对这些函数的求解，验证有效性的问题。实验环境为MatlabR2014b,处理器为InternetCoreI7,内存4G，操作系统为Windows10的计算机。表4.1为改进烟花算法的参数。表4.1改进烟花算法参数设定参数名参数值烟花数8最大迭代次数1*10^3最大计算次数5*10^4解空间维度16（1）ACKLEY函数Ackley函数是常用于测试优化算法求解性能的测试函数，其函数图形如图4.5所示，可以看到该函数的全局最小值处于中心位置，在周围有大量的局部极值，对于爬山算法而言，大量的局部极值提高算法陷入局部最优的概率，这也是此函数成为测试函数的主要原因。它的函数表达式为:QUOTEfx=−a∙exp−b1di=1图4.5Ackley函数改进烟花算法对Ackley函数求解情况如图4.6所示。图4.6改进烟花算法对Ackley函数求解情况（2）GRIEWANK函数Griewank函数也是测试优化算法性能的常用测试函数之一，其特点是局部极小值分布广泛，而这种分布是具有一定规律的，规律分布的极小值会引导算法陷入局部最优，以检验算法的完备性。函数表达式如（4-9）所示。QUOTEfx=i=1dxi24000−i=1图4.6Griewank函数改进烟花算法对Griewank函数求解情况如图4.7所示。图4.7改进烟花算法对Griewank函数求解情况从以上两个测试函数的实验结果可以看出，改进烟花算法在求解最优化问题时能快速收敛，且最终能得到精度较高的最优值。证明了改进烟花算法用于解决仓储物流机器人任务调度问题的可行性。

第5章实验方案与结果分析5.1实验方案设计本章节实验方案设计主要基于前文第三章中给出的仓储物流机器人任务调度实例模型进行，为了验证改进烟花算法的性能，在Matlab平台设计实验对比改进烟花算法和遗传算法的性能。实验首先将仓库实例平面地图通过距离比例和货架所在相对位置转化成节点地图，转化后的节点地图中包含货架节点100个，通过对所有节点相对位置的计算，形成节点距离表，该表包括所有节点两两的距离关系，仓储物流机器人出发点、卸货地点和所有节点的距离关系。这样可以减少Matlab在计算适应度值时所耗费的时间，由于适应度值的计算在算法的比较中不是决定性的差异指标，所以减少这部分的计算时间可以让对比更加明显，结果更加清晰。任务目标确定则采用随机生成的任务节点，分别在不同规模下设计多组实验验证改进烟花算法的高效性。（1）第一组对比实验考察改进烟花算法、遗传算法在不同任务规模下的收敛情况和算法得到的最优的调度策略。由于货架节点总量为100个，实验将任务规模从10个到100个每间隔20做一次对比实验。（2）第二组对比试验考察改进烟花算法、基本烟花算法在相同任务规模下的收敛情况和和算法得到的最优的调度策略。为了控制变量，设置任务规模为50个任务时，进行多次对比试验。5.2实验参数设定第一组对比试验中，通过对任务规模的调整，考察改进烟花算法和遗传算法的运算情况。表5.1是第一组实验中两种算法的初始参数设定。其中N表示种群规模，在烟花算法中表示初始烟花的数量，在遗传算法中表示初始染色体的数量。T表示迭代次数，即最大循环的次数。变异概率M由迭代次数T决定，迭代次数越多，变异概率越低。遗传算法中的参数包括交叉概率C，表示基因在每次交叉操作中，有C的概率发生。改进烟花算法中的参数包括爆炸数量系数S，爆炸半径系数A和火花数量系数a，b。爆炸数量系数S表示控制爆炸产生的子代火花数量的参数，通过调整此参数可以控制烟花产生的子代火花的大致数量。爆炸半径系数A，表示控制爆炸产生的子代火花范围的参数，通过调整此参数可以控制烟花产生的子代火花的大致范围。火花数量系数a，b表示火花的数量最少不少于a个，最多不超过b个。表5.1第一组实验参数设定算法参数名参数值-迭代次数T1000-种群规模N-改进烟花算法爆炸数量系数S10爆炸半径系数A15火花数目系数a0.3火花数目系数b0.6遗传算法交叉概率C0.8变异概率M(T-t)/T第二组对比试验中通过对相同参数设定下的仿真模拟，考察基础烟花算法和改进烟花算法的求解情况，表5.2是第二组实验中两种算法的初始参数设定。其中N表示种群规模，在烟花算法中表示初始烟花的数量，在第二组实验中将其固定为50。T表示迭代次数，即最大循环的次数。变异概率M由迭代次数T决定，迭代次数越多，变异概率越低。爆炸数量系数S表示控制爆炸产生的子代火花数量的参数，通过调整此参数可以控制烟花产生的子代火花的大致数量。爆炸半径系数A，表示控制爆炸产生的子代火花范围的参数，通过调整此参数可以控制烟花产生的子代火花的大致范围。火花数量系数a，b表示火花的数量最少不少于a个，最多不超过b个。表5.2第二组实验参数设定参数名参数值迭代次数T1000种群规模N50爆炸数量系数S10爆炸