第5期 莫宏伟，等：一种生物地理学移动机器人路径规划算法 ·709. 根据仿真统计结果及下降趋势图显示，降维机 为了能更好的评价4个算法的性能，现将算法 制对算法寻找最小路径效果上有作用。由图5可以 参数设置如下： 看出降维机制加快了算法的收敛速度。由图6可以 BB0:岛屿数M=30,最大变异率mm=0.3,采用上 得到，降维机制呈现了较好的稳定性，30次结果的 面提到的降维机制和精英策略，以及双向搜索机制： 标准差为0.9419，而无降维机制为1.2974：也呈现 PS0:粒子个数M=30,惯性常数ωms=0.8, 了较好的搜索能力，30次结果的误差率为2.59%， min=0.4,C1=0.5,c2=0.5,采用线性动态w调整策 而无降维机制为3.35%。在规划时间消耗上图7显 略、降维机制和双向搜索机制； 而易见的表明了其降维机制的优势 AFSA:人工鱼个数M=30,拥挤度因子设为2， 感知距离为0.1，最大移动步长0.08，最大试探次数 ■ ■ 10,同样采用双向搜索机制和降维机制： ■ ■ ABC:人工蜂个数M=30,最大尝试次数Limit= 15,同样采用双向搜索机制和降维机制。 ■ 每个算法统一迭代次数为2000次。 为移动机器人在图8环境下进行路径规划，路 (a)20x20 (b)30×30 径起始点为栅格图的左上角(0,0)点，目的地为栅 格图的右下角(N-1,N-1)。 算法运行在不同的环境模型下的复杂度及 ◆ ” 理论最小路径统计如表1所示。 t ◆ ◆ 每个算法在每种栅格环境下重复运行30次得 到的规划结果和时间消耗结果统计如下表2所示。 ■ ■ 表1仿真环境参数指标 (c)40x40 Table 1 The performance of parameters in simulation en- (d)50x50 vironment 栅格地图 有效顶点数 理论最小值 20×20 141 28.8122 30×30 321 43.9030 40×40 575 58.9938 ■ 50x50 903 73.9526 (e)60x60 (f)70×70 60X60 1305 88.8205 图8仿真环境模型 70×70 1781 103.6884 Fig.8 Simulation environment models 表24种算法路径规划统计结果 Table 2 Statistical results of four path planning algorithms 栅格规模 算法 最小值 最大值 均值 中间值 标准差 误差率/% BBO 29.3487 29.3762 29.3498 29.3487 0.0051 1.87 20×20 PSO 29.3487 35.6218 30.7914 30.3988 1.5300 6.87 (141) AFSA 29.3487 29.3487 29.3487 29.3487 0 1.86 ABC 29.3487 29.4045 29.3506 29.3487 0.0102 1.87 BBO 44.2166 45.5596 44.5585 44.5552 0.2939 2.58 30×30 PSO 47.0589 58.5309 51.7983 51.4951 3.4188 17.98 (321) AFSA 44.3882 48.0344 46.1360 45.8763 1.0564 5.09 ABC 44.5828 52.0776 49.1158 49.3841 2.0587 11.87根据仿真统计结果及下降趋势图显示，降维机 制对算法寻找最小路径效果上有作用。 由图 ５ 可以 看出降维机制加快了算法的收敛速度。 由图 ６ 可以 得到，降维机制呈现了较好的稳定性，３０ 次结果的 标准差为０．９４１ ９，而无降维机制为１．２９７ ４；也呈现 了较好的搜索能力，３０ 次结果的误差率为 ２．５９％， 而无降维机制为 ３．３５％。 在规划时间消耗上图 ７ 显 而易见的表明了其降维机制的优势。 （ａ）２０×２０ （ｂ）３０×３０ （ｃ）４０×４０ （ｄ）５０×５０ （ｅ）６０×６０ （ｆ）７０×７０ 图 ８ 仿真环境模型 Ｆｉｇ．８ Ｓｉｍｕｌａｔｉｏｎ ｅｎｖｉｒｏｎｍｅｎｔ ｍｏｄｅｌｓ 为了能更好的评价 ４ 个算法的性能，现将算法 参数设置如下： ＢＢＯ：岛屿数 Ｍ＝３０，最大变异率 ｍｍａｘ ＝０．３，采用上 面提到的降维机制和精英策略，以及双向搜索机制； ＰＳＯ：粒子个数 Ｍ ＝ ３０，惯性常数 ωｍａｘ ＝ ０． ８， ωｍｍｉｎ ＝ ０．４，ｃ１ ＝ ０．５，ｃ２ ＝ ０．５，采用线性动态 ω 调整策 略、降维机制和双向搜索机制； ＡＦＳＡ：人工鱼个数 Ｍ ＝ ３０，拥挤度因子设为 ２， 感知距离为 ０．１，最大移动步长 ０．０８，最大试探次数 １０，同样采用双向搜索机制和降维机制； ＡＢＣ：人工蜂个数 Ｍ＝ ３０，最大尝试次数 Ｌｉｍｉｔ ＝ １５，同样采用双向搜索机制和降维机制。 每个算法统一迭代次数为 ２ ０００ 次。 为移动机器人在图 ８ 环境下进行路径规划，路 径起始点为栅格图的左上角（０，０）点，目的地为栅 格图的右下角（Ｎ－１，Ｎ－１）。 算法运行在不同的环境模型下的复杂度及 理论最小路径统计如表 １ 所示。 每个算法在每种栅格环境下重复运行 ３０ 次得 到的规划结果和时间消耗结果统计如下表 ２ 所示。 表 １ 仿真环境参数指标 Ｔａｂｌｅ １ Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｐａｒａｍｅｔｅｒｓ ｉｎ ｓｉｍｕｌａｔｉｏｎ ｅｎ⁃ ｖｉｒｏｎｍｅｎｔ 栅格地图 有效顶点数 理论最小值 ２０×２０ １４１ ２８．８１２ ２ ３０×３０ ３２１ ４３．９０３ ０ ４０×４０ ５７５ ５８．９９３ ８ ５０×５０ ９０３ ７３．９５２ ６ ６０×６０ １ ３０５ ８８．８２０ ５ ７０×７０ １ ７８１ １０３．６８８ ４ 表 ２ ４ 种算法路径规划统计结果 Ｔａｂｌｅ ２ Ｓｔａｔｉｓｔｉｃａｌ ｒｅｓｕｌｔｓ ｏｆ ｆｏｕｒ ｐａｔｈ ｐｌａｎｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ 栅格规模 算法 最小值 最大值 均值 中间值 标准差 误差率／ ％ ２０×２０ （１４１） ＢＢＯ ２９．３４８ ７ ２９．３７６ ２ ２９．３４９ ８ ２９．３４８ ７ ０．００５ １ １．８７ ＰＳＯ ２９．３４８ ７ ３５．６２１ ８ ３０．７９１ ４ ３０．３９８ ８ １．５３０ ０ ６．８７ ＡＦＳＡ ２９．３４８ ７ ２９．３４８ ７ ２９．３４８ ７ ２９．３４８ ７ ０ １．８６ ＡＢＣ ２９．３４８ ７ ２９．４０４ ５ ２９．３５０ ６ ２９．３４８ ７ ０．０１０ ２ １．８７ ３０×３０ （３２１） ＢＢＯ ４４．２１６ ６ ４５．５５９ ６ ４４．５５８ ５ ４４．５５５ ２ ０．２９３ ９ ２．５８ ＰＳＯ ４７．０５８ ９ ５８．５３０ ９ ５１．７９８ ３ ５１．４９５ １ ３．４１８ ８ １７．９８ ＡＦＳＡ ４４．３８８ ２ ４８．０３４ ４ ４６．１３６ ０ ４５．８７６ ３ １．０５６ ４ ５．０９ ＡＢＣ ４４．５８２ ８ ５２．０７７ ６ ４９．１１５ ８ ４９．３８４ １ ２．０５８ ７ １１．８７ 第 ５ 期 莫宏伟，等：一种生物地理学移动机器人路径规划算法 ·７０９·