当前位置:   article > 正文

基于智能算法(遗传算法、蚁群算法)的路径规划_基于遗传算法的路径规划

基于遗传算法的路径规划

思路

模拟生物进化过程,物竞天择,适者生存

首先就是要产生一些种群,进行种群的初始化主要有以下三步:

  1. 选择
  2. 交叉
  3. 变异

实例

假设现在为栅格图形进行编码,与使用A*与Dijkstra算法操作一致。
在这里插入图片描述

现在要从起点0到达终点24这个栅格,可以看到这样一条路径。

在这里插入图片描述

就可以用这样一种方法来表示一个个体(指这条路径)。所以说,首先我们就是要产生很多条这种个体(路径),之后再从众多个体当中,选取最优的那一个个体。

种群初始化

与A*等算法一致,其只能在相邻的栅格或者对角栅格当中进行走。以这种方式进行行走的话,每一行都至少会经过一个栅格,所以先把每行必走的一个栅格确认出来。

种群初始化

  1. 每行选择一个栅格
  2. 判断相邻栅格是否连续
  3. 不连续时进行插入栅格操作,直到连续

在这里插入图片描述

Q:选择完每行的栅格后,怎么判断相邻栅格之间是否连续呢?
A:为地图建立一个坐标系,为每一个栅格分配一个X,Y上的坐标,若两个相邻的栅格,其X的坐标或者Y的坐标最大值只相差1的话,即: D = max ⁡ { abs ⁡ ( x i + 1 − x i ) , abs ⁡ ( y i + 1 − y i ) } D=\max \left\{\operatorname{abs}\left(x^{i+1}-x^{i}\right), \operatorname{abs}\left(y^{i+1}-y^{i}\right)\right\} D=max{abs(xi+1xi),abs(yi+1yi)},就可以直接走过去,就表示两个栅格是相邻的或者对角的。

转换过程
y = int ⁡ ( N / G size  ) + 1 y=\operatorname{int}\left(N / G_{\text {size }}\right)+1 y=int(N/Gsize )+1
x = N % ( G size  ) x=N \%\left(G_{\text {size }}\right) x=N%(Gsize )+1
直接除取整就知道在第几行,取余数就说明在第几列。+1操作就是想在编程环境中选择从1开始而不是从0开始,从0开始去掉+1就行。

不连续时采取的操作
做法就是插入新的栅格,插入中间新的栅格,比如说6号点的坐标与13号点的坐标,其距离相差2,所以是不连续的,所以插入中间栅格,就是上面两个坐标加一起取平均值,再向下取整,(2+3)/2直接算的话是2.5,进行向下取整的话,那就是2。所以产生的坐标是(3,2),这样对应的就是7这个栅格,将7加进来,发现6、7就连续了,往后走,发现7和13也是连续的。
在这里插入图片描述

然后就产生了这个路径。
若相邻的两个栅格之间的距离比较远,那我们就可以反复执行这个过程,再判断,直到整个路径都连续。
在经过上方的初始化以后,就要进入遗传算法的循环了。

选择

在这里插入图片描述

为了看哪个个体的路径更好,就要对每一个个体进行打分。采取了一个适应度的概念(即距离的倒数)。
d = ∑ i = 1 e n d − 1 ( x i + 1 − x i ) 2 + ( y i + 1 − y i ) 2 d=\sum_{i=1}^{e n d-1} \sqrt{\left(x_{i+1}-x_{i}\right)^{2}+\left(y_{i+1}-y_{i}\right)^{2}} d=i=1end1(xi+1xi)2+(yi+1yi)2

对越短的路径而言,其适应度越大。
f i t 1 = 1 / d f i t_{1}=1 / d fit1=1/d

还有一个就是路径的顺滑性。
在这里插入图片描述
以这三点为例,组成了一个三角形,要想路径越顺滑,则这个角更大即可满足。可以用余弦定理进行计算,加入到这个适应度函数。角度越大的话越好。

f i t 2 = arccos ⁡ ( ( b 2 + c 2 − a 2 ) / 2 b c ) fit _{2}=\arccos \left(\left(b^{2}+c^{2}-a^{2}\right) / 2 b c\right) fit2=arccos((b2+c2a2)/2bc)

然后分别对两个适应度函数求权重,这个权重可以通过实验来获得。
f i t = a f i t 1 + b f i t 2 fit =a f i t_{1}+b f i t_{2} fit=afit1+bfit2

有了适应度的值,就可以为每个个体计算一个概率。相当于保留这条路径的概率。所以一些好的个体被保留下来的概率越大,但也会有较差的个体,后面可以通过交叉和变异来“发育”的更好。

p i = f i t i / ∑ i = 1 e n d f i t i p_{i}=f i t_{i} / \sum_{i=1}^{e n d} f i t_{i} pi=fiti/i=1endfiti

交叉

发现两条路径在13这个点上进行交叉。可以通过交换交叉点前后的路径形成新路径。这样就丰富了个体。
在这里插入图片描述

变异

  1. 随机选择路径中的两个栅格,此例当中是1和13
  2. 采取种群初始化的方式在两个栅格之间产生新的路径,此例当中是1-7-13,产生了新路径
  3. 循环一直进行的话,整个种群都会向比较好的方向发展(对应于路径规划的话,就是路径越来越优越来越短)
    在这里插入图片描述

总结

关于完备性,起点和终点之间有路径解存在的话,一定可以得到解,但遗传算法并不能保证得到的是最优的一个路径,代码讲解在下一篇Blog,争取早日肝出来。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/443671
推荐阅读
相关标签
  

闽ICP备14008679号