王瑞等：基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法 ·1347. 动后的中心位置次于扰动前的位置，计算二者的差， 杂度是O((T。-T)/c).其中，T。是初始退火温 利用式(23)确定P.然后，用随机数rand∈(0,1) 度；T是最低温度：c是降温速率.由于模拟退火算 与P比较，若rand<P,保留次优位置，否则，退回 法只在地标算子寻优中加入，所以扰动模拟退火鸽 扰动前状态，继续执行本步操作，直至迭代次数达到 群优化算法的时间复杂度为O(N+NC,*N*D+ NC2,算法收敛 NC2*N2+N*(D+(T。-T)/c)). 基本鸽群优化算法的时间复杂度为O(N+NC,* 基本鸽群优化(PI0)算法和扰动模拟退火鸽群 N*D+NC,*N2+N*D),模拟退火算法的时间复 优化(MSAPIO)算法的参数选择如表1所示： 表1PIO和MSAPIO参数表 Table 1 Parameters of PIO and MSAPIO 参数 参数定义 数值 应用 NC 地图和指南针算子迭代次数 15 NCz 地标算子迭代次数 5 鸽群优化 N 鸽子总数 50 扰动模拟退火鸽群优化 R 地图和指南针因子 0.3 柯西分布概率密度参数 1 高斯分布率密度函数参数（均值） 0 0 高斯分布概率密度函数参数（方差） K 地图和指南针算子的柯西扰动条件 3 扰动模拟鸽群优化 地标算子的高斯扰动条件 2 地图和指南针算子扰动國值 0.1 地标算子扰动國值 0.01 T 初始退火温度 100 红色“×”是随机产生的目标初始位置，数字“1,2， 4实验结果和分析 3,4,5,6”是中间被包围目标下一时刻可能的运动 首先，使用经典适应度函数验证本文算法相对 位置.图4(b)是随机产生的初始环境不确定度，且 基本鸽群优化算法的优越性.然后从搜索覆盖范围 绿色阴影部分正比于不确定度 和发现目标数目两个方面衡量多无人机协同搜索的 为了验证本文算法的优越性，图5是4架无人 性能. 机在不同仿真步数下的运动轨迹和搜索范围覆盖 4.1算法性能比较 率，便于观察运动情况.图5(a)和图5(b)仅给出无 本文算法采用扰动和模拟退火机制，相对基本 人机和目标1在30步和60步的运动轨迹，图5(c) 鸽群优化算法易跳出局部最优.使用多峰适应度评 是不同算法的搜索范围随着搜索步数的变化情况. 价函数进行测试，图3(a)使用Rastrigrin函数，其在 将20km×20km的搜索区域划分为20×20的栅格， x=(0,0,…,0)处取得极小值0，为了便于观察对函 4架无人机的初始位置用“>”表示：“×”是随机产 数取反，即这里取极大值0：图3(b)使用Schaffer函 生的动态目标，“s:”是第i个目标的起始位置，“e:” 数，其在x=(0,0,…,0)处取得极大值1.每个函数 是经马尔可夫链运动后的终止位置.由图分析可 的前两幅图是基本鸽群优化算法随机一次运行和 知，无人机能够用最小步数，实现尽可能多的目标搜 10次迭代取最大值、最小值和均值的收敛情况：后 索，而且随着搜索步数的增加搜索覆盖范围不断 两幅图是扰动模拟退火鸽群优化算法随机一次运行 扩大 和10次迭代取最大值、最小值和均值的收敛情况. 4.3搜索目标有效性 从图中不难发现，本文算法能够有效避免陷入局部 图6从搜索目标的有效性对基本鸽群优化算 最优 法、蚁群算法以及扰动模拟退火鸽群优化算法这3 4.2搜索范围覆盖率 种算法做仿真分析比较，且图6(a)和图6(b)分别 假设搜索区域L为10×10的栅格.图4(a)中， 表示搜索目标平均数和搜索策略有效性.使用4王 瑞等: 基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法 动后的中心位置次于扰动前的位置,计算二者的差, 利用式(23)确定 Pr . 然后,用随机数 rand沂(0,1) 与 Pr比较,若 rand < Pr,保留次优位置,否则,退回 扰动前状态,继续执行本步操作,直至迭代次数达到 NC2 ,算法收敛. 基本鸽群优化算法的时间复杂度为 O(N + NC1* N*D + NC2*N^2 + N*D),模拟退火算法的时间复 杂度是 O(( T0 - Tmin ) / c). 其中,T0 是初始退火温 度;Tmin是最低温度;c 是降温速率. 由于模拟退火算 法只在地标算子寻优中加入,所以扰动模拟退火鸽 群优化算法的时间复杂度为 O(N + NC1*N*D + NC2*N^2 + N*(D + (T0 - Tmin ) / c)). 基本鸽群优化(PIO)算法和扰动模拟退火鸽群 优化(MSAPIO)算法的参数选择如表 1 所示: 表 1 PIO 和 MSAPIO 参数表 Table 1 Parameters of PIO and MSAPIO 参数 参数定义 数值 应用 NC1 地图和指南针算子迭代次数 15 NC2 地标算子迭代次数 5 N 鸽子总数 50 R 地图和指南针因子 0郾 3 鸽群优化 扰动模拟退火鸽群优化 a 柯西分布概率密度参数 1 滋 高斯分布率密度函数参数(均值) 0 滓 高斯分布概率密度函数参数(方差) 1 K1 地图和指南针算子的柯西扰动条件 3 K2 地标算子的高斯扰动条件 2 e1 地图和指南针算子扰动阈值 0郾 1 e2 地标算子扰动阈值 0郾 01 T0 初始退火温度 100 扰动模拟鸽群优化 4 实验结果和分析 首先,使用经典适应度函数验证本文算法相对 基本鸽群优化算法的优越性. 然后从搜索覆盖范围 和发现目标数目两个方面衡量多无人机协同搜索的 性能. 4郾 1 算法性能比较 本文算法采用扰动和模拟退火机制,相对基本 鸽群优化算法易跳出局部最优. 使用多峰适应度评 价函数进行测试,图 3(a)使用 Rastrigrin 函数,其在 x = (0,0,…,0)处取得极小值 0,为了便于观察对函 数取反,即这里取极大值 0;图 3(b)使用 Schaffer 函 数,其在 x = (0,0,…,0)处取得极大值 1. 每个函数 的前两幅图是基本鸽群优化算法随机一次运行和 10 次迭代取最大值、最小值和均值的收敛情况;后 两幅图是扰动模拟退火鸽群优化算法随机一次运行 和 10 次迭代取最大值、最小值和均值的收敛情况. 从图中不难发现,本文算法能够有效避免陷入局部 最优. 4郾 2 搜索范围覆盖率 假设搜索区域 L 为10 伊 10 的栅格. 图4(a)中, 红色“ 伊 冶是随机产生的目标初始位置,数字“1,2, 3,4,5,6冶是中间被包围目标下一时刻可能的运动 位置. 图 4(b)是随机产生的初始环境不确定度,且 绿色阴影部分正比于不确定度. 为了验证本文算法的优越性,图 5 是 4 架无人 机在不同仿真步数下的运动轨迹和搜索范围覆盖 率,便于观察运动情况. 图5(a)和图5(b)仅给出无 人机和目标 1 在 30 步和 60 步的运动轨迹,图 5(c) 是不同算法的搜索范围随着搜索步数的变化情况. 将 20 km 伊 20 km 的搜索区域划分为20 伊 20 的栅格, 4 架无人机的初始位置用“荥冶表示;“ 伊 冶是随机产 生的动态目标,“si冶是第 i 个目标的起始位置,“ ei冶 是经马尔可夫链运动后的终止位置. 由图分析可 知,无人机能够用最小步数,实现尽可能多的目标搜 索,而且随着搜索步数的增加搜索覆盖范围不断 扩大. 4郾 3 搜索目标有效性 图 6 从搜索目标的有效性对基本鸽群优化算 法、蚁群算法以及扰动模拟退火鸽群优化算法这 3 种算法做仿真分析比较,且图 6( a)和图 6( b)分别 表示搜索目标平均数和搜索策略有效性. 使用 4 ·1347·