基于改进粒子群算法的多类型点位智能导航方法及系统

1.本发明涉及智能导航技术领域，具体涉及一种基于改进粒子群算法的多类型点位智能导航方法及系统。


背景技术：

2.随着智能技术、导航技术的高速发展和人们生活水平的提高，人们在生活中对于时间和空间位置信息的需求量越来越大，因此智能导航对各类功能的拓展性和路线规划的快速性提出了更高的要求。无论是在移动机器人领域，还是在日常生活出行领域，智能导航技术都占据着一席之地。智能导航的核心在于任务分配与路径规划。例如：农药机器人需要规划农药喷洒区域的作业路径以完成任务；人们出行需要规划从某一地点前往另一地点的最省时路径；物流机器人需要规划厂区的各个搬运地点的工作路径以完成任务。
3.如今，在科技的飞速发展下，智能导航在家庭服务、智能农业、工业转型、军事支援、抢险救援等方面都得到广泛的应用，例如生活中未知地点的导航，复杂环境中的紧急救援，无人驾驶汽车的导航、定位与任务规划等等。因此，智能导航功能的重要性是有目共睹的。
4.人们在生活中如果没有手机导航的帮助几乎是寸步难行。导航的核心任务是在地图上找到一条从起点到终点的路径，称为路径规划。现在的地图应用中仍只有两点导航的简单功能，如果想要依次前往不同类型的地点，每种类型的地点又有多种同类，则需要多次导航。在多次选取目标点位进行路径规划后，自行合并路线，而且由于多类型点位可能在区域内存在多个，因此自己想要找出一条整体最短、最优的路径并不容易，既费时又费力。
5.因此，如何在现有导航中解决存在多个需求点位的路径规划导航方法成为亟待解决的技术问题。


技术实现要素：

6.针对上述存在的问题，本发明旨在提供一种基于改进粒子群算法的多类型点位智能导航方法及系统，以克服现有导航局限于两点导航的缺陷。此方法可以在较短时间内规划出最短的多类型点位路径轨迹，合理分配各类需求点，寻找有效最佳路径轨迹，提升了出行的舒适感和便利性。
7.为了实现上述目的，本发明所采用的技术方案如下：
8.基于改进粒子群算法的多类型点位智能导航方法，包括以下步骤：
9.s1、获取地图的环境信息，并对地图的环境信息进行划分与建模，得到地图不同类型任务点位置信息；
10.s2、根据地图不同类型任务点位置信息建立多任务点位模型；
11.s3、将地图中的不同类型任务点进行分类，并将分类后的不同类型任务点储存在不同的集合中；
12.s4、根据导航需求和导航需求对应的任务点集合得到多任务分配约束式；
13.s5、计算多任务分配约束式中所有点位之间的距离并储存；
14.s6、根据多任务分配约束式，随机选取一个点位，生成一系列初始的可行序列，采用改进的粒子群算法对生成的一系列初始的可行序列优化输出最优序列；
15.s7、对输出的最优序列进行解码，并将解码后的最优序列进行拼接得到最短路径轨迹。
16.优选的，步骤s1中通过栅格法对地图的环境信息进行划分与建模，得到地图不同类型任务点位置信息。
17.优选的，所述步骤s2中根据地图不同类型任务点位置信息建立多任务点位模型，包括以下步骤：
18.s21,定义导航的起点位置集合为
19.s22，定义导航中途经的任务点的位置集合为其中ta表示在导航规划中必须途经的同一类地点位置集合，a表示导航需要规划途经的任务点的数量；
20.s23,定义导航的终点位置集合为
21.s24,多任务点位模型描述为:
22.优选的，步骤s5中通过dijkstra方法计算多任务分配约束式中所有点位之间的距离并储存。
23.优选的，所述步骤s5中所述计算多任务分配约束式中所有点位之间的距离，包括以下步骤：
24.s51、创建两个集合r、v和一个1
×
m的全0矩阵p，其中r是已经找到最短路径的顶点，v是还待计算的顶点，令r＝ci，v＝v/ci；
25.s52、将集合v中具有最小距离的顶点ck加入到集合r中并将ck从集合v中取出，即r＝r∪ck，v＝v/ck；
26.s53、更新集合v中顶点的距离，若从源点ci到顶点ch的距离大于源点ci到顶点ck的距离加上顶点ck到顶点ch的距离，即d
i,h
》d
i,k
+d
k,h
，则更新d
i,h
＝d
i,k
+d
k,h
，并记录顶点ch的上一顶点ck，即p(h)＝k；
27.s54、若目标点cj∈v，则回到步骤s52中继续，若目标点cj∈r，输出从源点ci到目标点cj最短移动距离d
i,j
；
28.s55、通过回溯矩阵p求解路径l
i,j
；
29.s56、重复以上步骤，直到每两个点之间都计算完成。
30.优选的，步骤s5中多任务分配约束式中所有点位之间的距离存储形式为两栅格点角标与最短距离对应的表格d和两栅格点角标与最短路径对应的表格l，具体表示为如下：角标与最短距离对应的表格d和两栅格点角标与最短路径对应的表格l，具体表示为如下：角标与最短距离对应的表格d和两栅格点角标与最短路径对应的表格l，具体表示为如下：
31.优选的，所述步骤s6具体包括以下步骤：
32.s61、根据多任务分配约束式，在所有需要途经的点位集合中随机选取一个点位，生成一系列初始的可行序列；
33.s62、将生成一系列初始的可行序列采用改进的粒子群算法进行优化输出最优序列。
34.优选的，所述改进的粒子群算法，包括以下步骤：
35.s621、初始化粒子群，并计算每个粒子的适应度；
36.s622、根据每个粒子的适应度更新pbesti、gbest和best；
37.s623、遍历每个粒子，将每个粒子与pbesti、gbest和best进行交叉操作，计算交叉后引起的适应度变化量δe；
38.s624、若交叉后引起的适应度变化量δe《0或δe《e，则接受粒子，更新粒子位置；
39.s625、再次遍历每个粒子，对每个粒子依次进行自我变异操作，计算变异后引起的适应度变化量δe；
40.s626、变异后引起的适应度变化量δe《0或δe《e
′
，则接受粒子，更新粒子位置；
41.s627、判断是否达到了最大迭代次数或群体最优位置是否满足要求，如果是的话，跳出循环，输出最优路径序列i
gbest
与适应度fit
gbest
，否则，继续进入s622进行循环。
42.优选的，对每个粒子依次进行自我变异操作包括三种策略：单点替换、两点交换和片段逆序。
43.基于改进粒子群算法的多类型点位智能导航系统，其特征在于，包括：
44.信息获取模块，所述信息获取模块用于获取地图的环境信息，并对地图的环境信息进行划分与建模，得到地图不同类型任务点位置信息；
45.模型建立模块，所述模型建立模块用于根据地图不同类型任务点位置信息建立多任务点位模型；
46.信息存储模块，所述信息存储模块用于将地图中的不同类型任务点进行分类，并将分类后的不同类型任务点储存在不同的集合中；所述信息存储模块还用于计算多任务分配约束式中所有点位之间的距离并储存；
47.数据运算模块，数据运算模块用于根据多任务分配约束式，随机选取一个点位，生成一系列初始的可行序列，采用改进的粒子群算法对生成的一系列初始的可行序列优化输出最优序列；数据运算模块用于对输出的最优序列进行解码，并将解码后的最优序列进行拼接得到最短路径轨迹。
48.与现有技术相比，本发明至少具有如下的有益效果：
49.本发明一种基于改进粒子群算法的多类型点位智能导航方法，通过在全局环境栅格地图法建模的基础上，建立多任务点位模型，并将地图中的多类型点位进行分类储存在不同集合中并根据任务需求描述出多任务分配约束式，接着计算用户需求涉及到的所有点位之间的距离和路径并储存。最后通过改进的粒子群算法对满足任务约束的解序列迭代寻优，求得行进路程最小的解，对得出的最优任务分配序列进行拼接获得最终路径轨迹。本发明在两点导航的基础上实现多点位导航，可以在较短时间内规划出最短的多类型点位路径轨迹，合理分配各类需求点，寻找有效最佳路径轨迹，提高了用户体验，降低了路径成本和时间成本，具有良好的应用前景。
附图说明
50.图1是本发明实施例中一种基于改进粒子群算法的多类型点位智能导航方法流程示意图。
51.图2是本发明实施例中改进粒子群算法的流程图。
52.图3是本发明实施例中栅格地图示意图。
53.图4是本发明实施例中路径导航结果示意图。
具体实施方式
54.为了使本领域的普通技术人员能更好的理解本发明的技术方案，下面结合附图和实施例对本发明的技术方案做进一步的描述。
55.如图1所示，本发明一种基于改进粒子群算法的多类型点位智能导航方法，包括以下步骤：
56.s1、获取地图环境的信息并对环境进行划分与建模得到地图不同类型任务点位置信息；
57.s2、根据地图不同类型任务点位置信息建立多任务点位模型；
58.s3、将地图中的多类型点位进行分类并储存在不同的集合中；
59.s4、根据任务需求描述出多任务分配约束式；
60.s5、计算多任务分配约束式中所有点位之间的距离并储存；
61.s6、根据多任务分配约束式，随机选取一个点位，生成一系列满足要求的初始序列，并对初始任务序列群进行改进的粒子群算法优化输出最优序列；
62.s7、对输出的最优序列进行解码并通过拼接得到最短路径轨迹。
63.本发明能够在两点导航的基础上实现多点位导航，可以在较短时间内规划出最短的多类型点位路径轨迹，合理分配各类需求点，寻找有效最佳路径轨迹，提高了用户体验，降低路径成本和时间成本，具有良好的应用前景。
64.以下结合附图对本发明进行详细说明。
65.实施例1
66.本实施例一种基于改进粒子算法的多类型点位智能导航方法，包括以下步骤：
67.s1、获取地图环境的信息并对全局环境进行划分与建模。
68.步骤s1中具体通过栅格法对全局环境进行划分与建模。
69.具体地，通过栅格法将全局环境划分为一个n
×
n大小的栅格空间，并为地图加入一圈墙壁。然后对栅格地图的可行区域依次进行位置编号操作，编号后得到一个坐标与编号对应的编号表，即{(0，0)：0，(0，1)：1，...，(n-1，n-1)：n
2-1}，表示为
70.如图3所示，在本发明的一种实施方式中通过栅格法将地图的全局环境划分为一个10
×
10大小的栅格空间，然后对栅格地图依次进行位置编号操作。编号后得到一个坐标与编号对应的编号表，即{(0，0)：0，(0，1)：1，...，(9，9)：99}，表示为c＝{c0，c1，...，c
99
}。
71.s2、建立多任务点位模型。
72.在步骤s2中，由于地图中导航起点固定且唯一，因此，定义起点位置集合为多类型任务点位置集合定义为其中，
表示在导航规划中必须途经的同一类地点位置集合，称为必要途径地点，a表示导航需要规划途经的任务点的数量，在导航途中，存在a个任务点需要途经，每个任务点都包含一系列同类任务点，每一个类型的途经任务点仅需要从对应t集合中任选其一途经即可。终点位置集合单独定义为表示在导航规划中最终必须到达的同一类终点位置集合，称为必要最终地点，在导航结束时，必须以此集合中的任意一点作为导航结束点。
73.因此，多任务点位模型描述为
74.s3，将地图中的多类型点位进行分类并储存在不同的集合中。
75.创建y＝{y1，y2，...，yq}，将地图中的所有已知任务点位进行归类，将同类的点位分别存入集合y1，y2，...，yq，其中同类点位数必须大于等于所需任务数和终点数的和，即q≥a+1。y是区域内同类任务点位的集合(t是用户需求的同类点位集合，在未确定需求时等待被y替换)。
76.具体地，在本发明的一种实施例中，已知从地图信息中获取的多类型同类点位如下，超市点位y1＝{c
81
，c9，c
62
，c
37
，c
14
}，药店点位y2＝{c
48
，c2，c5，c
24
}，加油站点位y3＝{c
89
，c
54
}，a小区点位y4＝{c
21
}等等其他点位集合。
77.s4，根据任务需求描述出多任务分配约束式。
78.在步骤s4中，首先，根据用户需求确定起点，任务点，终点，然后用当前起点替换式中的起点s，并用相应的同类型任务点位y替换式中的f或f，得到用户需求的任务数为ua个，起点1个，终点1个。某个可行解
79.具体地，在本发明的一种实施例中，已知用户需求为：从家出发，路上需要途径区域内的超市、加油站、药店以及a小区，然后回到公司。用户所在起始点位cs＝c0，终点公司点位f＝{c3}，因此多任务分配约束式为：其中y1＝{c
81
，c9，c
62
，c
37
，c
14
}，y2＝{c
48
，c
24
，c2，c5}，y3＝{c
89
，c
54
}，y4＝{c
21
}，任务数4个(y1～y4)，起点1个(c0)，终点1个(c3)。
80.s5，通过dijkstra算法计算各感兴趣点位之间的距离和路径并储存。
81.令i表示用户需求中涉及到的所有区域的集合。依次计算i中所有点位两两之间的最短距离和最短路径，具体的，从源点ci到目标点cj最短移动距离和路径的流程如下：
82.1)创建两个集合r、v和一个1
×
m的全0矩阵p，其中r是已经找到最短路径的顶点，v是还待计算的顶点，令r＝ci，v＝v/ci；
83.2)将集合v中具有最小距离的顶点ck加入到集合r中并将ck从集合v中取出，即r＝r∪ck，v＝v/ck；
84.3)更新集合v中顶点的距离，若从源点ci到顶点ch的距离大于源点ci到顶点ck的距离加上顶点ck到顶点ch的距离，即d
i，h
》d
i，k
+d
k，h
，则更新d
i，h
＝d
i，k
+d
k，h
，并记录顶点ch的上一顶点ck，即p(h)＝k；
85.4)若目标点cj∈v，则回到步骤2)继续，若目标点cj∈r，输出从源点ci到目标点cj最短移动距离d
i，j
；
86.5)通过回溯矩阵p求解路径l
i，j
。
87.6)重复以上步骤，直到每两个点之间都计算完成。
88.由于从点位ci到目标点位cj和点位cj到目标点位ci的最短距离相同，且路径可以逆序，所以都只需要储存一次。所有用户涉及到的需求点位集合如下所示：
[0089][0090]
存储形式为两栅格点角标与最短距离和最短路径对应，表示为如下：
[0091][0092]
在本发明的一种实施例中，已知从源点ci到目标点cj最短移动距离和路径的流程如下：
[0093]
1)创建两个集合r、v和一个1
×
m的全0矩阵p，其中r是已经找到最短路径的顶点，v是还待计算的顶点，令r＝ci，v＝v/ci；
[0094]
2)将集合v中具有最小距离的顶点ck加入到集合r中并将ck从集合v中取出，即r＝r∪ck，v＝v/ck；
[0095]
3)更新集合v中顶点的距离，若从源点ci到顶点ch的距离大于源点ci到顶点ck的距离加上顶点ck到顶点ch的距离，即d
i，h
》d
i，k
+d
k，h
，则更新d
i，h
＝d
i，k
+d
k，h
，并记录顶点ch的上一顶点ck，即p(h)＝k；
[0096]
4)若目标点cj∈v，则回到步骤2)继续，若目标点cj∈r，输出从源点ci到目标点cj最短移动距离d
i，j
；
[0097]
5)通过回溯矩阵p求解路径l
i,j
。
[0098]
6)重复以上步骤，直到每两个点之间都计算完成。
[0099]
用于叠加适应度的距离表示如下：{(89，89)：0，(89，54)：8，(89，81)：8，(89，9)：8，(89，62)：9，(89，37)：7，(89，14)：12，(89，48)：5，(89，2)：15，(89，5)：12，(89，24)：11，(89，21)：14，(89，3)：14，(54，89)：8，(54，54)：0，(54，81)：6，(54，9)：10，(54，62)：3，(54，37)：5，(54，14)：4，(54，48)：5，(54，2)：7，(54，5)：6，(54，24)：3，(54，21)：6，(54，3)：6，(81，89)：8，(81，54)：6，(81，81)：0，(81，9)：16，(81，62)：3，(81，37)：11，(81，14)：10，(81，48)：11，(81，2)：9，(81，5)：12，(81，24)：9，(81，21)：6，(81，3)：10，(9，89)：8，(9，54)：10，(9，81)：16，(9，9)：0，(9，62)：13，(9，37)：5，(9，14)：6，(9，48)：5，(9，2)：7，(9，5)：4，(9，24)：7，(9，21)：10，(9，3)：6，(62，89)：9，(62，54)：3，(62，81)：3，(62，9)：13，(62，62)：0，(62，37)：8，(62,14):7,(62,48):8,(62,2):6,(62,5):9,(62,24):6,(62,21):5,(62,3):7,(37,89):7,(37,54):5,(37,81):11,(37,9):5,(37,62):8,(37,37):0,(37,14):5,(37,48):2,(37,2):8,(37,
5):5,(37,24):4,(37,21):7,(37,3):7,(14,89):12,(14,54):4,(14,81):10,(14,9):6,(14,62):7,(14,37):5,(14,14):0,(14,48):7,(14,2):3,(14,5):2,(14,24):1,(14,21):4,(14,3):2,(48,89):5,(48,54):5,(48,81):11,(48,9):5,(48,62):8,(48,37):2,(48,14):7,(48,48):0,(48,2):10,(48,5):7,(48,24):6,(48,21):9,(48,3):9,(2,89):15,(2,54):7,(2,81):9,(2,9):7,(2,62):6,(2,37):8,(2,14):3,(2,48):10,(2,2):0,(2,5):3,(2,24):4,(2,21):3,(2,3):1,(5,89):12,(5,54):6,(5,81):12,(5,9):4,(5,62):9,(5,37):5,(5,14):2,(5,48):7,(5,2):3,(5,5):0,(5,24):3,(5,21):6,(5,3):2,(24,89):11,(24,54):3,(24,81):9,(24,9):7,(24,62):6,(24,37):4,(24,14):1,(24,48):6,(24,2):4,(24,5):3,(24,24):0,(24,21):3,(24,3):3,(21,89):14,(21,54):6,(21,81):6,(21,9):10,(21,62):5,(21,37):7,(21,14):4,(21,48):9,(21,2):3,(21,5):6,(21,24):3,(21,21):0,(21,3):4,(3,89):14,(3,54):6,(3,81):10,(3,9):6,(3,62):7,(3,37):7,(3,14):2,(3,48):9,(3,2):1,(3,5):2,(3,24):3,(3,21):4,(3,3):0,(0,89):17,(0,54):9,(0,81):9,(0,9):9,(0,62):8,(0,37):10,(0,14):5,(0,48):12,(0,2):2,(0,5):5,(0,24):6,(0,21):3,(0,3):3}。
[0100]
s6，随机生成一群初始的可行任务序列并对初始任务序列群进行改进的粒子群算法优化。
[0101]
具体地，首先，对经典粒子群算法进行改进。由于经典粒子群算法速度与位置均为连续量，因此需要对经典粒子群算法进行改进。此处采用遗传算法中对dna序列交叉、重组和变异的思想替换粒子群算法中的速度更新。交叉与变异后的新解有可能比原来的解要坏，所以采用模拟退火算法思想改进接受准则，为了简化计算不采取metropolis准则的概率接受，而是采取可调节的变坏参数，按照δe《e和δe《e
′
(e和e
′
为允许目标函数变差的范围)，在保证粒子群陷入局部最优时有概率跳出的同时使得解的多样性增加。同时，普通粒子群算法在每一次迭代，会跟随两个极值更新自己，一个是自身所找到的最优解pbesti，另一个是整个种群所找到的最优解gbest。我们在改进时加入了每一代粒子的当前全局最优项best，通过概率性选取这三项最优位置与当前粒子位置进行交叉，可以在加快寻优速度的同时使粒子群陷入局部最优时有概率跳出。通过以上步骤将经典粒子群算法改进为混合粒子群算法(mixed-particle swarm optimization，mpso)。
[0102]
参照图2，本发明中改进的粒子群算法的具体算法流程如下：
[0103]
1)算法初始化，确定了迭代次数max、粒子数num和相关参数后，随机生成一系列粒子，初始序列粒子群为：然后依次遍历距离集d，选取序列从起始点到终点中间所有对应的两点距离d并叠加，得到适应度fit，对应每个序列所代表的路线总距离，适应度越小，得到的路线总距离就越短。然后将得到的所有粒子的适应度存入fit
last
。最后将fit
last
赋值给fit
pbest
，找出fit
pbest
中最小适应度的值，并记录它的位数为index，将fit
pbest
[index]赋值给fit
gbest
，完成初始化。
[0104]
2)进入迭代过程。每次算法开始，都会更新粒子群中的个体、群体、当前最优信息。若fit
last
[i]《fit
pbest
[i]，将fit
last
[i]赋值给fit
pbest
[i]。然后，若pbesti中的最小值fit
pbesti
[index]《fit
gbest
，将fit
pbesti
[index]赋值给fit
gbest
。最后，将fit
las
t[index]赋值给fit
best
，通过以上步骤更新pbesti、gbest和best。
[0105]
3)遍历每个粒子，依次与优秀粒子进行交叉组合操作，首先是必要途径序列的处理。随机选取两个的整数x1，x2∈{0，1，...，a-1}且x1≠x2，以此随机截取必要途径地点部分的pbesti、gbest和best其中的一项的min(x1，x2)位至max(x1，x2)位片段作为优秀交叉片段。需要注意的是，由于。需要注意的是，由于意味着存在多种同类型点位，因此需要保证即将被替换的途经序列ia中不存在组合片段中已含有的同类型点位，需要进行判断，然后在ia中删除这些点位，最后将原序列ia整体左移，将组合片段拼接至ia尾部。由于终点序列ie仅有一位，直接用优秀粒子的ie′
替换原粒子的ie。
[0106]
4)对交叉重组后得到的iz′
＝{ia′
；ie′
}计算其适应度fit
′
，令δe
′
＝fit
′‑
fit
last
，若δe
′
＜0或δe
′
《e，则更新解(将fit
′
赋值给fit
last
，iz′
替换原来的iz)，否则维持原解。
[0107]
5)再次遍历每个粒子，对每个粒子依次进行概率变异操作。变异操作分为三类：单点替换、两点交换、片段逆序，在变异时随机选取其中一种策略。假设此时某个粒子为
[0108]
第一种策略，单点替换：原粒子中存在点位在多类型任务点位置集合中随机选取一个tr，r∈[1，a]。然后从tr中随机选取一个途径点位保证然后将替换为同类型点位同样地，对终点部分也采取同样的操作，从f中随机选取一个最终点位将替换为操作完成表示为
[0109]
第二种策略，两点交换：在原粒子中任意选择两个途径点位和将两个点位互换位置。原粒子操作完成表示为此时终点不进行处理。
[0110]
第三种策略，片段逆序：在原粒子中任意选择两个途径点位和将两个点位之间且包括两个点位的所有点位进行逆序操作。原粒子操作完成后表示为此时终点不进行处理。
[0111]
6)经过变异操作得到的iz″
＝{ia″
；ie″
}计算其适应度fit
″
，令δe
″
＝fit
″‑
fit
last
，若δe
″
《0或δe
″
《e
′
，则更新解(将fit
″
赋值给fit
last
，iz″
替换原来的iz)，否则维持原解。
[0112]
7)最后判断是否达到了最大迭代次数或群体最优位置是否满足要求，如果是的话，跳出循环，输出最优路径序列i
gbest
与适应度fit
gbest
。否则，继续进入循环(返回2)继续迭代)。
[0113]
本实施例中根据多任务分配约束式，在所有需要途经的点位集合中随机选取一个点位，生成一系列初始的可行序列。本实施例中，共需途经4个点位，抵达1个最终点位。因此对选择的途径点位进行随机排序后(例如[c
81
，c
48
，c
89
，c
21
])，并在尾部插入最终点位生成初
始任务序列i1＝{[c
81
，c
48
，c
89
，c
21
]；[c3]}，通过读取储存的数据可以得到当前序列i1的最短移动距离移动距离并将fitness[i]赋值给fit
pbest
[i]，重复以上步骤，直至生成num＝40个粒子。找出fit
pbest
中最小适应度的值，并记录它的位数为index，将fit
pbest
[index]赋值给fit
gbest
。
[0114]
然后进入迭代，首先判断若fit
last
[i]《fit
pbest
[i]，令fit
last
[i]＝fit
pbest
[i]。然后，若fit
pbest
[index]《fit
gbest
，令fit
pbest
[index]＝fit
gbest
。最后，令fit
last
[index]＝fit
best
，通过以上步骤更新pbesti、gbest和best。
[0115]
接下来，对每个粒子进行交叉组合操作，操作对象随机为pbesti、gbest和best其中之一。假设此时选取gbest，已知gbest＝{[c
89
，c
62
，c
24
，c
21
]；[c3]}，此时随机选取x1＝1，x2＝3，即选取第1位至3位片段作为优秀交叉片段。此时ia＝[c
81
，c
48
，c
89
，c
21
]，已知c
62
和c
81
、c
24
和c
48
、c
21
和c
21
同类型，所以删除ia中的同类点位得到[c
89
，0，0，0]，然后将拼接至上式中，得到iz*＝{[c
89
，c
62
，c
24
，c
21
]；[c3]}。由于本实施例终点只有一位，此处ie不变。然后计算得到的iz*的fit
′
，δe＝fit
′‑
fit
last
，若δe《0或δe《e(此时取e＝2)，则更新解(令fit
′
赋值给fit
last
，用iz*替换iz)，否则维持原解。
[0116]
接下来，对每个粒子进行变异操作，随机选取以下一种策略：
[0117]
第一种策略，单点替换：已知iz*＝{[c
89
，c
62
，c
24
，c
21
]；[c3]}，则选取某一个点位进行同类任务替换，ia*部分随机选取了c
89
，在同类点位y3＝{c
89
，c
54
}中随机选取了c
54
进行替换。ie*部分选取了c3，在同类点位中随机选取了c3进行替换。得到的iz**＝{[c
54
，c
62
，c
24
，c
21
]；[c3]}
[0118]
第二种策略，两点交换：已知iz*＝{[c
89
，c
62
，c
24
，c
21
]；[c3]}，则选取某两个个点位进行两点交换，ia*部分随机选取了c
89
和c
21
，得到的iz**＝{[c
21
，c
62
，c
24
，c
89
]；[c3]}。
[0119]
第三种策略，片段逆序：已知iz*＝{[c
89
，c
62
，c
24
，c
21
]；[c3]}，则选取某两个个点位进行片段逆序，ia*部分随机选取了c
89
和c
21
，得到的iz**＝{[c
21
，c
24
，c
62
，c
89
]；[c3]}。
[0120]
然后计算得到的iz**的fit
″
，δe＝fit
″‑
fit
last
，若δe《0或δe＜e
′
(此时取e
′
＝2)，则更新解(令fit
″
赋值给fit
last
，用iz**替换iz)，否则维持原解。
[0121]
最终，达到最大迭代次数终止循环，输出最优序列i
gbest
＝{[c
21
，c
54
，c
24
，c
14
]；[c3]}和对应距离15。
[0122]
s7，对最优序列进行解码并拼接输出最短路径轨迹。
[0123]
已知通过解码分别得到路径为由cs为起点，前往然后前往依次前往，直到抵达最终抵达终点将以上各部分通过遍历l两两路径集，依次拼接数组得到最优路径。
[0124]
具体地，在本发明实施例中，通过对i
gbest
＝{[c
21
，c
54
，c
24
，c
14
]；[c3]}解码并拼接得到的路径为c0，c
10
，c
20
，c
21
+c
21
，c
31
，c
41
，c
51
，c
52
，c
53
，c
54
+c
54
，c
44
，c
34
，c
24
+c
24
，c
14
+c
14
，c3，最优路径c0，c
10
，c
20
，c
21
，c
31
，c
41
，c
51
，c
52
，c
53
，c
54
，c
44
，c
34
，c
24
，c
14
，c3，对应最短距离为15。
[0125]
在本实施例中，对于用户的需求点位组合排列，一共有种可能的情况。如果区域内同类点位和用户的需求点位增多，可能的解会非常多，因此采用一般
方法(例如枚举法)解决该类组合优化问题需要极长的运行时间与超大的内存空间，因此如何采用智能算法求解优秀路径十分有必要。本实施例利用改进的粒子群算法和dijkstra算法，首先通过地图信息和栅格建模确定需求，随机选择满足约束式的初始任务序列并对初始任务序列进行粒子群算法优化操作，最终找到最优的任务序列、最短移动距离及其对应的路径。本实施例仅用不到0.1秒左右的时间就能够找到最优路径及其对应的最短距离，降低了时间成本，提高了出行效率，保证了便捷性。针对大规模的该类组合优化问题，本发明所提出的方法依然能够快速地求解，具有较好的通用性。
[0126]
本发明还提供一种基于改进粒子群算法的多类型点位智能导航系统，该基于改进粒子群算法的多类型点位智能导航系统，包括：
[0127]
信息获取模块，所述信息获取模块用于获取地图的环境信息，并对地图的环境信息进行划分与建模，得到地图不同类型任务点位置信息；
[0128]
模型建立模块，所述模型建立模块用于根据地图不同类型任务点位置信息建立多任务点位模型；
[0129]
信息存储模块，所述信息存储模块用于将地图中的不同类型任务点进行分类，并将分类后的不同类型任务点储存在不同的集合中；所述信息存储模块还用于计算多任务分配约束式中所有点位之间的距离并储存；
[0130]
数据运算模块，数据运算模块用于根据多任务分配约束式，随机选取一个点位，生成一系列初始的可行序列，采用改进的粒子群算法对生成的一系列初始的可行序列优化输出最优序列；数据运算模块用于对输出的最优序列进行解码，并将解码后的最优序列进行拼接得到最短路径轨迹。

技术特征：
1.基于改进粒子群算法的多类型点位智能导航方法，其特征在于，包括以下步骤：s1、获取地图的环境信息，并对地图的环境信息进行划分与建模，得到地图不同类型任务点位置信息；s2、根据地图不同类型任务点位置信息建立多任务点位模型；s3、将地图中的不同类型任务点进行分类，并将分类后的不同类型任务点储存在不同的集合中；s4、根据导航需求和导航需求对应的任务点集合得到多任务分配约束式；s5、计算多任务分配约束式中所有点位之间的距离并储存；s6、根据多任务分配约束式，随机选取一个点位，生成一系列初始的可行序列，采用改进的粒子群算法对生成的一系列初始的可行序列优化输出最优序列；s7、对输出的最优序列进行解码，并将解码后的最优序列进行拼接得到最短路径轨迹。2.根据权利要求1所述的基于改进粒子群算法的多类型点位智能导航方法，其特征在于，步骤s1中通过栅格法对地图的环境信息进行划分与建模，得到地图不同类型任务点位置信息。3.根据权利要求1所述的基于改进粒子群算法的多类型点位智能导航方法，其特征在于，所述步骤s2中根据地图不同类型任务点位置信息建立多任务点位模型，包括以下步骤：s21,定义导航的起点位置集合为s22，定义导航中途经的任务点的位置集合为其中t
a
表示在导航规划中必须途经的同一类地点位置集合，a表示导航需要规划途经的任务点的数量；s23,定义导航的终点位置集合为s24,多任务点位模型描述为:4.根据权利要求1所述的基于改进粒子群算法的多类型点位智能导航方法，其特征在于，步骤s5中通过dijkstra方法计算多任务分配约束式中所有点位之间的距离并储存。5.根据权利要求1所述的基于改进粒子群算法的多类型点位智能导航方法，其特征在于，所述步骤s5中所述计算多任务分配约束式中所有点位之间的距离，包括以下步骤：s51、创建两个集合r、v和一个1
×
m的全0矩阵p，其中r是已经找到最短路径的顶点，v是还待计算的顶点，令r＝c
i
，v＝v/c
i
；s52、将集合v中具有最小距离的顶点c
k
加入到集合r中并将c
k
从集合v中取出，即r＝r∪c
k
，v＝v/c
k
；s53、更新集合v中顶点的距离，若从源点c
i
到顶点c
h
的距离大于源点c
i
到顶点c
k
的距离加上顶点c
k
到顶点c
h
的距离，即d
i，h
>d
i，k
+d
k，h
，则更新d
i，h
＝d
i，k
+d
k，h
，并记录顶点c
h
的上一顶点c
k
，即p(h)＝k；s54、若目标点c
j
∈v，则回到步骤s52中继续，若目标点c
j
∈r，输出从源点c
i
到目标点c
j
最短移动距离d
i，j
；s55、通过回溯矩阵p求解路径l
i，j
；s56、重复以上步骤，直到每两个点之间都计算完成。6.根据权利要求1所述的基于改进粒子群算法的多类型点位智能导航方法，其特征在于，步骤s5中多任务分配约束式中所有点位之间的距离存储形式为两栅格点角标与最短距
离对应的表格d和两栅格点角标与最短路径对应的表格l，具体表示为如下：离对应的表格d和两栅格点角标与最短路径对应的表格l，具体表示为如下：离对应的表格d和两栅格点角标与最短路径对应的表格l，具体表示为如下：7.根据权利要求1所述的基于改进粒子群算法的多类型点位智能导航方法，其特征在于，所述步骤s6具体包括以下步骤：s61、根据多任务分配约束式，在所有需要途经的点位集合中随机选取一个点位，生成一系列初始的可行序列；s62、将生成一系列初始的可行序列采用改进的粒子群算法进行优化输出最优序列。8.根据权利要求1所述的基于改进粒子群算法的多类型点位智能导航方法，其特征在于，所述改进的粒子群算法，包括以下步骤：s621、初始化粒子群，并计算每个粒子的适应度；s622、根据每个粒子的适应度更新pbest
i
、gbest和best；s623、遍历每个粒子，将每个粒子与pbest
i
、gbest和best进行交叉操作，计算交叉后引起的适应度变化量δe；s624、若交叉后引起的适应度变化量δe＜0或δe＜e，则接受粒子，更新粒子位置；s625、再次遍历每个粒子，对每个粒子依次进行自我变异操作，计算变异后引起的适应度变化量δe；s626、变异后引起的适应度变化量δe＜0或δe＜e
′
，则接受粒子，更新粒子位置；s627、判断是否达到了最大迭代次数或群体最优位置是否满足要求，如果是的话，跳出循环，输出最优路径序列i
gbest
与适应度fit
gbest
，否则，继续进入s622进行循环。9.根据权利要求8所述的基于改进粒子群算法的多类型点位智能导航方法，其特征在于，对每个粒子依次进行自我变异操作包括三种策略：单点替换、两点交换和片段逆序。10.基于改进粒子群算法的多类型点位智能导航系统，其特征在于，包括：信息获取模块，所述信息获取模块用于获取地图的环境信息，并对地图的环境信息进行划分与建模，得到地图不同类型任务点位置信息；模型建立模块，所述模型建立模块用于根据地图不同类型任务点位置信息建立多任务点位模型；信息存储模块，所述信息存储模块用于将地图中的不同类型任务点进行分类，并将分类后的不同类型任务点储存在不同的集合中；所述信息存储模块还用于计算多任务分配约束式中所有点位之间的距离并储存；数据运算模块，数据运算模块用于根据多任务分配约束式，随机选取一个点位，生成一系列初始的可行序列，采用改进的粒子群算法对生成的一系列初始的可行序列优化输出最优序列；数据运算模块用于对输出的最优序列进行解码，并将解码后的最优序列进行拼接得到最短路径轨迹。

技术总结
本发明公开了基于改进粒子群算法的多类型点位智能导航方法及系统，在全局环境栅格地图法建模的基础上，建立多任务点位模型，并将地图中的多类型点位进行分类储存在不同集合中并根据任务需求描述出多任务分配约束式，通过计算用户需求涉及到的所有点位之间的距离和路径并储存。最后通过改进的粒子群算法对满足任务约束的解序列迭代寻优，求得行进路程最小的解，对得出的最优任务分配序列进行拼接获得最终路径轨迹。本发明在两点导航的基础上实现多点位导航，可以在较短时间内规划出最短的多类型点位路径轨迹，合理分配各类需求点，寻找有效最佳路径轨迹，提高了用户体验，降低了路径成本和时间成本，具有良好的应用前景。具有良好的应用前景。具有良好的应用前景。


技术研发人员：王心昊 何舟 施威杰
受保护的技术使用者：陕西科技大学
技术研发日：2023.07.17
技术公布日：2023/10/15