一种基于自组织多模态多目标量子粒子群优化算法的路径规划方法

摘要

一种基于自组织多模态多目标量子粒子群优化算法的路径规划方法，包括：一种自组织网络模型被用来获取每一个粒子的最佳邻居位置，该邻居位置参与量子粒子群算法中粒子位置的更新；将决策空间划分为多个相等区域，在更新粒子位置过程中，种群的中心位置和全局最佳位置是根据决策空间子分区中帕累托最优解数量最少区域确定，进而引导粒子位置进化更新；为了维持帕累托解档案集在决策空间和目标空间的多样性和收敛性，一种档案选择更新策略被用于维持档案集的多样性和收敛性。本发明不仅能够在决策空间找到多样和等价的帕累托解，而且能够维持解集合在目标空间的收敛性。同时，更好地解决路径规划问题，为用户在路径规划时提供多种等效路径以供选择。

说明书

技术领域

本发明涉及一种路径规划问题。

背景技术

在日常生活中，航线规划、物流车辆调度、铁路调度等都需要根据需求规划一条符合经济利益最大化等需求的最佳路径。从某种程度上说，这类人类从事的社会活动都可以看作一个最优化问题。这类问题可能存在多个路径存在相同的社会效益及其他目标。因此，这类问题是一个多模态多目标路径优化问题。

多模态多目标优化问题涉及在决策空间存在多个等效的解对应目标空间同一个目标值。一般来说，多目标优化算法的重点在目标空间搜索更逼近真实帕累托前沿的解，这样会导致大部分多目标优化算法搜索到的解在决策空间的多样性表现较差。因此，现在已有的多目标优化算法并不能有效地解决多模态多目标问题，特别是应用多目标优化算法求解多路径规划问题。最近，一些修改的多目标优化算法被用来处理多模态多目标问题。可是，这些算法的表现却很难达到满意的效果，主要是因为这些修改的算法本质上还是一个多目标算法，重点在于处理多目标问题；其次，这些修改的多目标算法在处理多模态多目标优化问题时很难把所有等效的解全部找到。

小生境技术已经被广泛地用于处理多模态优化问题并取得了非常优异的效果。鉴于多模态多目标优化问题涉及多模态问题，小生境技术被引入多目标问题中处理多模态多目标问题。例如，DN-NSGAII、MO_Ring_PSO_SCD、MMO-CLRPSO、SSMOPSO。这些算法使用不同的小生境技术都可以有效地处理多模态多目标问题。可是，这些小生境在使用时都需要预定义一个参数，并不能自适应参数，因此，自适应小生境参数或者小生境不带参数在解决多模态多目标问题是一种挑战。

发明内容

针对目前存在的问题，本发明提供了一种基于自组织多模态多目标量子粒子群优化方法，同时使用无参数的自组织小生境方法，能够在决策空间搜索到所有等效的解并保持解在决策空间和目标空间的多样性和收敛性，并成功适用于求解路径规划规划问题。

为达到上述目的，本发明采用的技术方案为，一种基于自组织多模态多目标量子粒子群优化算法的路径规划方法，包括以下步骤：

S1.在决策空间内初始化一个种群POP带有NP个粒子，并计算目标函数值；

S2.对每一个粒子POP

S3.计算所有粒子最佳历史位置pbest

S4.对种群POP进行非支配排序并获得非支配解PSPF，非支配解PSPF中第一个解即为种群POP的最优个体位置gbest；

S5.初始化自组织模型SOM；

S6.初始化一个冗余档案RA为空；

S7.算法进入主循环，如果迭代结束条件不满足进入S8；

S8.更新自组织网络SOM并获取最好的邻居粒子，具体步骤如下：

S81.初始化种群POP中新产生的非支配解为自组织网络的训练集trainingset；

S82.根据种群中每一个个体POP

S83.自组织模型训练T次；

S84.在每一次训练过程中，对训练集中每一个样本trainingset

S85.更新权重向量

其中，T是总训练次数，t是当前训练次数，η

S86.更新神经元

其中，σ(t)是第t次训练的学习半径，σ

S87.自组织模型训练结束。对于每一个粒子POP

S88.获得最佳神经元u

S89.获得所有邻居的个体最好历史个体集合

S810.获得所有个体的最佳邻居nbest。

S9.种群更新迭代。具体步骤如下：

S91.更新每一个粒子的p

其中，λ和r是0到1的随机数，ξ是一个随机整数，g和G是当前迭代次数和最大迭代次数，pbest

S92.更新每一个粒子的位置根据公式6；

其中μ是一个0至1之间的随机数，β是一个逐渐递减的参数，其定义如下：

其中，β

S93.计算每一个更新后POP

S94.更新每一个粒子POP

S95.合并所有粒子的PBset

S96.将决策空间等分为k＝2

S97.根据区域划分结果，找到非支配解数量最少的区域和该区域的非支配解

S98.更新种群的平均位置mbest。计算

S99.根据

S10.当PSPF档案集的数量大于NP时进行外部档案集PSPF维护，其主要步骤如下：

S10-1.初始化一个临时的解集tempPSPF，对于决策空间，找到PSPF的每一个决策向量中每一维的最大值与最小值放入临时解集tempPSPF，并将他们从PSPF中移除；

S10-2.分别计算tempPSPF和PSPF中解与解之间的距离，找到PSPF与tempPSPF中每一个解之间最小的距离的所有解，并在这些最小距离解中找出一个最大距离的解从PSPF中移动到tempPSPF，直至tempPSPF中解的数量等于NP；

S10-3.将PSPF中剩余的非支配解放入冗余矩阵RA中，并重新将tempPSPF赋值给PSPF；

S10-4.返回PSPF和tempPSPF。

S11.种群迭代结束。合并PSPF和RA并进行非支配排序获得非支配解PSPF；

S12.进行步骤S10选择多样的非支配解，输出最终的解PSPF。

与现有技术相比，本发明具有以下优点：

1.相比较基本粒子群算法，本发明采用量子粒子群算法处理多模态多目标路径规划问题具有更好的全局搜索能力。一个基于邻居领导者的小生境技术被引入到量子粒子群位置更新公式中更有利于搜索等效的最优解。在获得邻居领导者的方法中，本发明使用自组织网络训练得到邻居领导者是一种新颖的方法。

2.为了防止粒子向粒子中心位置mbest收敛，本发明使用了一种分区确定种群的mbest和gbest。在该方法中，决策空间被分为多个相同的子空间，子空间中包含最少非支配解的区域内的非支配解用于更新种群的mbest和gbest。

3.一个基于距离的外部档案集在该方法中用于维护解的多样性，该方法可以在进化过程中不断地维持档案解集的多样性，并能同时维持档案解集的多样性和收敛性。

附图说明

图1为本发明方法整体流程图。

图2为路径规划实例。

具体实施方式

为了更好的理解本发明，下面结合附图2和实例对本发明进行详细描述。

在附图2中，该图为50*50的城市网格，白色区域为建筑物，不可穿行，黑色区域为城市道路，道路交叉区域为路口。地图红色区域为道路拥堵区域(1*1),地图蓝色点为出发位置(START),绿色点为目的地(GOAL)。所求解问题有三个目标函数，分别为:1)F

本发明的流程图如图一所示，其具体实现步骤如下：

Step1.根据每一个路口的坐标初始化种群POP,种群规模为100.每一个粒子的基因编码方式为POP

Step2.根据编码方式初始化每一个粒子的最佳位置Pbest和最佳位置集合Pbestset。

Step3.根据所有粒子的Pbest计算种群的中心位置mbest。

Step4.初始化自组织网络模型SOM。

Step5.迭代进化过程

Step5.1.根据粒子位置训练自组织网络模型SOM获取每一个粒子的最佳邻居位置。

Step5.2.更新每一个粒子的位置。

Step5.3.获取种群中的非支配解PSPF和冗余解RA

Step5.4.确定更新后的种群的mbest和gbest。

Step6.迭代结束。合并所有的PSPF和RA。

Step7.根据多样性选择机制MAXMINdiversity选取最终的解集PSPF。

Step8.输出PSPF并解码。对于PSPF解集的一个解PSPF

本发明旨在解决多路径规划问题，为大众出行提供多种可靠路径以供其选择，其难点在于如何搜索到相同目标函数下的多种路径。针对该问题，本发明提出一种基于自组织网络的量子粒子群算法求解路径规划问题的方法，该方法采用自组织模型训练能力得到粒子的最佳邻居参与粒子进化，能够搜索到更多等效的路径。

本发明包括：一种自组织网络模型被用来获取每一个粒子的最佳邻居位置，该邻居位置参与量子粒子群算法中粒子位置的更新；将决策空间划分为多个相等区域，在更新粒子位置过程中，种群的中心位置和全局最佳位置是根据决策空间子分区中帕累托最优解数量最少区域确定，进而引导粒子位置进化更新；为了维持帕累托解档案集在决策空间和目标空间的多样性和收敛性，一种档案选择更新策略被用于维持档案集的多样性和收敛性。本发明不仅能够在决策空间找到多样和等价的帕累托解，而且能够维持解集合在目标空间的收敛性。同时，更好地解决路径规划问题，为用户在路径规划时提供多种等效路径以供选择。

尽管以上结合附图对本发明的具体实施过程进行了描述，但本发明并不局限于上述的具体实施方案，上述实施例和说明书中描述的只是说明本发明的原理，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其等效物界定。