面向无人机三维航迹规划的改进粒子群优化算法

宋 宇， 王志明

(长春工业大学 计算机科学与工程学院，吉林 长春 130012)

0 引 言

无人机的自主化需要无人机各个模块的协同工作，无人机的研究方向有路径规划、飞行控制、空间定位、图像识别、飞行器设计[1]。其中，无人机的路径规划中当环境已知时，路径规划算法一般有：群智能算法，A*算法，D*算法，可视图法，元胞自动机算法；其中常见的群智能算法有蚁群算法，粒子群算法等[2～6]。

引入粒子浓度机制,将当前代中适应度低且浓度大的粒子的交叉变异概率提高,使得这些粒子在下一次迭代中交叉变异的可能性变大，这种方法改进了基本粒子群算法在无人机三维航迹规划后期收敛速度慢的问题[7]；通过自然选择机制，对所有粒子按适应度值排序后，用适应度较好的前一半的粒子取代适应度差的后一半粒子，同时在粒子速度更新公式中保留所有粒子所记忆的最优位置，有效地增加了粒子的全局寻优能力，改善了基本粒子群算法在路径规划中易陷入局部最优解的问题[8]；用适应度值加权后的所有粒子经历的最优位置，代替单个粒子的所记忆的最优位置的，充分利用全部粒子的个体最优位置信息，有效地加强了粒子群算法在路径规划中的寻优能力[9]；在灰狼算法中，利用第一优个体与第三优个体的差值所带来的当前寻优状态信息,当最优个体位置与第三优个体位置的差值大于给定阈值时采用适应度值加权的速度更新策略，增强了算法的全局寻优能力[10]；无免费午餐定理指出不存一个群启发式算法对解决所有的优化问题都表现最佳[11]。

本文提出了结合模糊C均值(fuzzy C means,FCM)算法的改进粒子群算法，在路径规划仿真实验中有效地避开了障碍物(局部最优)。

1 粒子群算法

在基本粒子群算法的迭代过程中，每个待选解(粒子的位置)都具有向全局最优解与每个粒子当前发现的最优解的速度之和移动的趋势。每个待选解(粒子的位置)位置变化为

(1)

(2)

2 FCM算法

FCM算法将所有待分类中每个点的隶属度取值为0～1之间的数。模糊C均值算法的步骤如下：

1)给定待分类的数据矩阵A,A的大小为m×n，m为待分类点的个数,n为每个点的维数,准备将给定数据分为c类，随机初始化隶属度矩阵W,W为一个c行m列，满足每列之和都等于1，其中的Wij指代第j个待选解(粒子位置)对第i个类的隶属度值。

2)分别计算c个类的类中心P，P为一个c行n列的矩阵，每行代表一个类中心点

(3)

式中k为一个加权指数，一般取2。

3)计算距离矩阵D,D为一个大小为c×m的矩阵，其中Dij为第i个类中心到第j个数据点的距离

4)更新隶属度矩阵中wij的值

(4)

3 改进粒子群算法

1)随机初始化粒子位置(可能解)矩阵，随机初始化粒子速度(可能解在一次迭代中的变化量)矩阵，设定粒子位置与速度的最大最小值。

2)调用FCM算法，准备将所有粒子分为g类，得到停止分类后的隶属度矩阵，再根据得到的隶属度矩阵用轮盘赌算法最终确定每个粒子分别属于哪类。

3)分别计算每个粒子的适应度函数值，得到本次迭代中每个类内适应度值最优粒子位置goal(i,:)与全部粒子到目前为止所经历的全局最优粒子位置globle，为了防止算法陷入局部最优，此处的goal(i,:)不具有记忆性，goal(i,:)的值仅取决于当前代第i类内的最优粒子位置，而此处的globle为具有记忆性的目前为止所有迭代次数中最优粒子的位置，算法按照式(5)更新待选解的改变量(粒子速度)，按照式(6)更新待选解的值(粒子位置)

(5)

(6)

4)将待选解(粒子位置)的速度与位置的越界值赋值为规定的边界值。

5)判断当前迭代次数是否为g的倍数：若否，跳到步骤(6)；若是，再次调用FCM算法，根据FCM算法得到的隶属度矩阵，按轮盘赌算法确定每个粒子属于哪类。

6)迭代次数加1，若未达到最大迭代次数，跳到步骤(3)，若达到最大迭代次数，算法结束。

为了增加粒子群算法在全局最优解附近的搜索精度，可将式(5)替换为

(7)

式中 增加的最后一项为每个粒子趋向类内其他粒子的速度分量，p为从1到本类最大粒子数目的随机数，classi(p)为一个本类内部随机选定的粒子的位置，w1取为0.1。

4 仿真实验

实验结果如图1。由图可知，经改进算法优化迭代后得到的解更优。

图1 算法改进前后对比

5 结 论

仿真实验的结果表明：改进算法成功得到了落在障碍物以外的中间路径点，且利用改进算法找到的最优路径的距离的精度也大为改善。