一种基于进化多目标多任务优化的路径规划方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN112132312A(43)申请公布日2020.12.25(21)申请号202010818231.9(22)申请日2020.08.14(71)申请人蓝海（福建）信息科技有限公司地址361000福建省厦门市软件园三期诚毅北大街62号109单元0011号(72)发明人蔡奕侨傅顺开曾省明刘弘钊(74)专利代理机构厦门市首创君合专利事务所有限公司35204代理人连耀忠(51)Int.Cl.G06Q10/04(2012.01)G06Q10/08(2012.01)G06N3/12(2006.01)权利要求书2页说明书8页附图1页(54)发明名称一种基于进化多目标多任务优化的路径规划方法(57)摘要本发明提供了一种基于进化多目标多任务优化的车辆路径规划方法，将车辆路径规划的每一个目标函数作为一个单独的任务，并利用多任务优化中的种群构造、信息迁移、子代生成、种群更新等操作对多个任务同时进行求解；采用多任务优化与多目标优化交替进行的两阶段策略，当满足设定的切换条件时，将多任务优化过程切换到多目标优化过程，通过多目标优化的种群构造、子代生成、种群更新、外部存档更新等操作优化非占优解集；采用基于精英保留的种群重构策略，当满足设定的重构条件时，只保留部分精英解，其余规划方案通过基于高斯游走的方式重新生成并加入到种群中。本发明提出的方法，解决了相似问题的优化信息在求解过程中不能有效地进行交流和协作的问题，实现了相似问题的信息共享，提升VRP的求解性能。CN112132312ACN112132312A权利要求书1/2页1.一种基于进化多目标多任务优化的路径规划方法，具体包括如下步骤：S1：种群初始化：采用基于随机排列的编码方式产生初始序列集合，然后对集合中的每一个序列采用构造方法生成规划方案，按照目标函数进行评估，并将所有规划方案加入到初始种群中，用于更新外部存档，其中所述目标函数：f2(s)＝maxk＝1,..,Mc(rk)其中，M表示规划方案s包含的车辆路径数目，rk表示第k条车辆路径，c(rk)表示第k条车辆路径的行驶距离，f1(s)和f2(s)分别表示路径规划方案s的车辆行驶总距离和最长车辆路径长度。S2：进化多任务优化：依次进行多任务种群构造、多任务信息迁移、多任务子代生成和多任务种群更新及外部存档更新；S3：两阶段切换：如果外部存档发生更新，则进入步骤S4，执行多目标优化阶段；否则，返回步骤S2，继续执行多任务优化阶段。S4：进化多目标优化:依次进行多目标种群构造、多目标子代生成和多目标种群更新及外部存档更新；S5：判断是否执行重构：外部存档不发生变化的代数大于设置的阀值，则进入步骤S6，执行种群重构操作；否则，进入步骤S7。S6：种群重构：根据非支配排序方法和拥挤距离的方法，得到最优种群，并采用基于高斯游走的方式组成新的种群。S7：判断算法是否结束：迭代的次数达到设定的迭代次数最大值，输出外部存档中所有的规划方案，算法结束；否则，返回步骤S2。2.根据权利要求1所述的一种基于进化多目标多任务优化的路径规划方法，所述步骤S2中进化多任务优化：依次进行多任务种群构造、多任务信息迁移、多任务子代生成和多任务种群更新及外部存档更新，具体包括：S21：多任务种群构造：对于初始种群所有规划方案，计算该规划方案的标量适应值，然后选择标量适应值最大的规划方案，构造对应任务的种群。S22：多任务信息迁移：初始化对应任务的临时种群，将步骤2中构造的对应任务的种群中标量适应值最大的规划方案加入到临时种群中，并从另一任务中选择适应值最大的规划方案加入到临时种群中。S23：多任务子代生成：将对应任务的临时种群中每一个规划方案对应的序列，执行差分进化算法的变异和交叉操作，再利用最大顺序值规则，产生子代序列，并利用构造方法得到相应的规划方案及其在相应任务上的目标函数值，对于每一个规划方案，对其进行局部搜索操作，并将所得到的新的规划方案替换临时种群中原有的规划方案。S24：多任务种群更新及外部存档更新：将步骤2中得到种群和步骤3中得到的临时种群中的所有规划方案，按照目标函数值，计算其标量适应值，并选择标量适应值最大的规划方案构成新的种群，将新的种群中的每个规划方案，根据非支配排序和拥挤距离方法更新外部存档。3.根据权利要求1所述的一种基于进化多目标多任务优化的路径规划方法，所述步骤2CN112132312A权利要求书2/2页S4中进化多目标优化:依次进行多目标种群构造、多目标子代生成和多目标种群更新及外部存档更新，具体包括：S41：多目标种群构造：利用非支配排序和拥挤距离的选择方法，构造新的多目标种群。S42：多目标子代生成：对多目标种群执行顺序交叉操作和交换变异操作，生成新的序列，对这些序列分