基于改进人工蜂群进化算法的移动机器人路径规划与仿真分析

2020-05-19张竞丹邵海见

江苏科技大学学报(自然科学版) 2020年2期

邓星,张竞丹,邵海见,张露

(1.江苏科技大学计算机学院,镇江 212003) (2.东南大学自动化学院,南京 210096) (3.东南大学复杂工程系统测量与控制教育部重点实验室,南京 210096)

移动机器人具有自动化和无人化方面优势,其应用前景已经越来越广泛．移动机器人的路径规划是移动机器人研究领域中衡量机器人智能化水平的主要因素之一．目前关于移动机器人路径规划的算法层出不穷,主要有神经网络[1]、A*算法[2]、遗传算法[3]、蚁群优化算法[4]、粒子群优化算法[5]以及人工蜂群(artificial bee colony,ABC)算法等群体智能算法．ABC算法能避免A*算法因遍历所有路径对空间需求太大的问题，防止在路径搜索时陷入死锁,凭借更好的全局搜索能力,在移动机器人路径规划领域应用最广泛．ABC算法[6-7]根据蜜蜂自组织模型，模拟蜜蜂采蜜行为，并结合粒子视觉等方法提出,在多维多模路径寻优[8]、模型参数优化、迭代递归以及最短路径计算等领域应用广泛．

ABC算法比其他类似进化算法的全局搜索能力更佳,但由于其容易陷入寻优过程中的局部极值,导致收敛速度慢．为提高经典ABC算法的路径规划能力,文中利用移动机器人与目标位置距离来构造启发信息,通过在启发信息中加入EP(evolutionary programming)算子增大ABC算法在陷入局部极值搜索时的跳出概率,尤其是提升ABC算法在局部样本特征差异大以及梯度大时的搜索能力,从而能够更有效地得到最优解．文中提出的改进ABC算法能有效提高路径规划初期蜂群搜索随机性，增强EP路径规划时粒子筛选能力,从而提高ABC算法移动机器人的全局最优路径规划能力．文中分析了ABC算法的基本原理,提出了改进思路，阐述了ABC算法改进方法与实施流程，给出了文中方法与经典算法的性能评估结果．

1 人工蜂群算法

ABC算法模拟自然界中蜜蜂的觅食行为进行路径规划．研究表明,蜜蜂通过跳“摇摆舞”向其他蜜蜂传达信息,通过信息传递,整个蜂群将寻找到更加优质的蜜源．经典ABC算法的组成要素包括食物源、被雇佣的蜜蜂和未被雇佣的蜜蜂[6]．其中蜜蜂划分为雇佣蜂、跟随蜂和侦查峰3组.雇佣蜂和非雇佣蜂各占蜂群总数的一半,其路径规划过程分为搜索过程与寻优过程．

1.1 搜索过程

食物点xi(i∈1,2,…,SN)代表可行的解决方案．位置xi(i∈1,2,…,SN)皆具有待优化参数D(xij,j∈1,2,…,D)．于是食物点初始化定义为:

xij=lj+rand(0,1) (uj-lj)

(1)

式中：lj和uj分别为参数j的下限和上限；rand(0,1)为0和1之间的均匀随机数；SN为蜜源数量．

1.2 寻优过程

(1) 雇佣蜂阶段:每个被雇用的蜜蜂与食物位置相对应．被雇用的蜜蜂在其当前的食物位置xi附近进行局部搜索,寻找新的食物位置vi,其计算式为:

vij=xij+φij(xij-xkj)

(2)

式中：k(k≠i,j)为一种随机选择参数,用于表示随机食物位置；φij为区间[-1,1]上的随机数．雇佣蜂计算食物位置vi的花蜜量,然后采用贪心算法进行寻优．如果vi的花蜜量比xi多,食物位置xi被vi代替,此时计数器被重置为零,否则保留xi,计数器增加1．

(2) 观察蜂阶段:观察蜂根据概率pi选择食物位置xi,观察蜂与采蜜蜂进行信息交换,并根据适应度进行蜜源选择,进而引领蜂选择蜜源,根据择优来寻找到局部最优．更新蜜源信息的同时确定蜜源的花蜜量,与第i个蜜源相对应的采蜜蜂寻找新的蜜源,其概率为:

(3)

式中：fiti为可能解xi的适应值．一旦观察蜂选择了食物位置,他们就会利用式(2)产生新的食物位置,评估新的食物位置并应用相同的贪婪选择．

(3) 侦查蜂阶段:通过扩大搜索区域来寻求解空间中更优化的解,如果食物位置经多次实验后没有得到改善，limit=SN×D，limit为维持代数,则引领蜂变为侦查蜂,通过式(1)随机生成新的食物点,进而根据式(3)寻找新的蜜源．

(4) 最优密源确定阶段:初始化蜜源、雇佣蜂阶段、观察蜂阶段和侦查蜂阶段后,通过判断终止条件是否满足来获取最优密源．其中雇佣蜂和侦查蜂分别用于局部和全局搜索,而观察蜂用于两者间的平衡．通过3个阶段的多次迭代与循环更新,最终找出最优解．

2 算法分析与改进

2.1 EP全局规划

与遗传算法相比,EP算法是一种表述能力更好的进化算法．EP算法与遗传算法分别在表型空间和基因型空间中工作,并且EP算法中不存在交叉算子,演化过程仅依靠变异算子进行,因此对该算子突变的改进能更好促进路径选择,对性能提升至关重要．群体中的每条路径通过变异算子产生一条新路径,但该方法仅适用于可行的轨迹空间搜索,适用于改善ABC算法易陷入局部最优、收敛速度慢等情况．

2.2 进化过程

改进算法对现有粒子进行二次筛选,选择相对较优的粒子作为父母,并引入变异算子产生下一代．通过多次迭代实现路径寻优.算法进化机制源于选种和突变.选种主要用于选择优秀的子代.突变在演化过程中有举足轻重的作用．于是,文中基于全局路径规划优化算法EP，结合ABC算法,来改善ABC算法易陷入局部最优的情况，提高ABC算法陷入局部最优时的跳出概率，增加全局规划能力来提高其搜索效率．该路径规划过程涉及到路径长度、平滑度与计算时间等因素,并且方法性能与最终到达目的点的实施效率密切相关．即在路径长度、平滑度与成功率类似的情况下,首先达到目的地的路径规划方法最优．由于搜索方法在可行轨迹搜索空间中工作,因此变异算子只有当其产生一个自由路径碰撞时才予以应用,主要包括删除、平滑、更新和可见性4步．每个变异算子的图形表述如图1．

图1 变异操作符的图形化描述Fig.1 Graphical description of mutation operators

删除操作是指随机选择路径中的一个顶点,然后删除它．平滑操作是指随机选择路径中的一个顶点．计算过去顶点段的随机点A(x,y)选定的顶点，和随机点B(x,y)所选顶点与下一个顶点的距离．根据该距离插入的新顶点将联合位置点B(x,y)在位置更新时使用．更新操作是指随机查找路径的顶点,生成一个新的空闲碰撞顶点并更新信息．可见性是指以随机方式选择两个顶点,然后移除它们之间的顶点．

2.3 改进算法处理流程

改进ABC算法主要通过加强经典算法的选择、重组和变异机制来实现多次优化,进而寻找到最好的蜜源,记录并输出最优解,并通过增加其跳出局部最优的概率,得到更为优化的路径．改进人工蜂群算法流程图如图2．

2.3.1 初始化

食物点xi(i∈1,2,…,SN)为优化问题的可行解决方案．其中每个位置点xi(i∈1,2,…,SN)都有对应的优化参数D(xij,j∈1,2,…，D)．使用以下公式初始化食物点:

xij=lj+rand(0,1)(uj-lj)

(4)

式中：lj和uj分别为参数j的下限和上限；rand(0,1)为0和1之间的均匀随机数．

图2 改进人工蜂群算法流程Fig.2 Flowchart of improved artificial bee colony algorithm

2.3.2 适应度计算

适应度函数的计算公式为:

(5)

通过适应度值比较来判断当前循环是否为最优解,然后针对当前最优解的组合进行邻域搜索;如果邻域内得到的解的适应度优于当前最优解,则进行更新,否则继续搜索直到邻域搜索循环结束．

2.3.3 寻优过程

(1) 雇佣蜂阶段:每个被雇用的蜜蜂与一个食物位置相对应．被雇用的蜜蜂使用其当前的食物位置xi,在其附近进行局部搜索,寻找新的食物位置vi,其计算公式为:

vij=xij+φij(xij-xkj)

(6)

式中：k为随机食物位置，k≠i,j,参数随机选择；φij为区间[-1,1]上的随机数．

雇佣蜂计算食物位置vi的花蜜量,然后利用贪心算法进行筛选:如果vi的花蜜量比xi多,则食物位置xi被vi代替,此时计数器被重置为零,否则保留xi，同时计数器增加1．

(2) 观察蜂阶段:观察蜂根据概率pi选择食物位置xi,观察蜂与采蜜蜂进行信息交换,根据适应度进行蜜源选择,并且根据引领蜂选择的蜜源质量择优实现，寻求到局部最优．更新蜜源信息的同时确定蜜源的花蜜量．与第i个蜜源相对应的采蜜蜂寻找新的蜜源,其概率为:

(7)

式中：fiti为可能解xi的适应值．一旦观察蜂选择了食物位置,就通过式(6)产生新的食物位置,并应用贪婪选择来评估新的食物位置．

(3) 侦查蜂阶段:通过扩大搜索区域来寻求解空间中更加优化的解,当多次实验食物位置仍然没有得到改善时，limit=SN×D，则引领蜂变侦查蜂,通过式(1)随机生成一个新的食物点,进而再根据式(7)寻找新的蜜源．

(4) 判断终止条件是否成立,获得最优蜜源．通过初始化蜜源、雇佣蜂阶段、观察蜂阶段和侦查蜂阶段多次迭代与循环更新,判断终止条件是否满足，获取最优密源,最终找出最优解．

3 实验评估

3.1 实验结果

文中基于图形用户界面对多个场景进行仿真,模拟真实的移动机器人路径规划,进而实现对移动机器人的路径规划测试．为接近真实的障碍物分布,文中采用大方块，避免了因障碍物过小导致机器人从障碍物间隙直接穿过的情况．

文中对改进算法与经典算法进行对比,在路径长度、平滑度与成功率类似的情况下,首先达到目的地的路径规划方法最优．图3～5分别为障碍物设置、粒子初始化以及移动机器人的路径规划．

图3 障碍物设置Fig.3 Setting obstacles

图4 粒子初始化Fig.4 Particle initialization

图5 路径规划Fig.5 Path planning

3.2 算法性能指标

3.2.1 评价参数

控制该算法的主要性能参数有:蜜源数量NP、优化参数iterMax以及维持代数limit3个(表1)：蜜源数量NP为待解决问题的解空间中被选取的点个数,该参数值对算法性能的影响不确定,但并无明显规律；优化参数iterMax为迭代最大次数．当该参数逐渐增大时,迭代次数亦随之增大,此时算法优化性能逐渐增强，但经过测试当大于200时,该算法性能逐渐趋于平缓；维持代数limit提高全局搜索能力,增加算法多样性．

表1 算法参数对性能影响Table 1 Effect of algorithm parameters on performance

用于路径更新的代价函数定义为:

(8)

图6 路径规划解析Fig.6 Path planning parse

3.2.2 性能对比

为比较文中方法性能,与基于遗传算法、A*算法以及经典人工蜂群算法的机器人路径规划实验进行对比．A*算法的机器人路径规划实验中估价函数f′(n)为:

f′(n)=g′(n)+h′(n)

(9)

遗传算法的累计损失函数以及最后的进化位置如图7．由图8得知,在不同交叉概率下进化次数对粒子选择有很大影响,而且并未呈现线性关系,在交叉概率为0.7时状态收敛最快．因此实验设置遗传算法种群大小、最大遗传代数、个体长度和代沟分别为40,50,20和0.95,交叉概率和变异概率分别为0.7，0.01．采用A*算法的路径规划如图9．记录4种方法的路径长度和规划时间,数据如表2．

图7 累计损失函数空间Fig.7 Function space of cumulative loss

图8 不同交叉概率下的遗传算法的进化次数与粒子选择之间的关系Fig.8 Relationship between the number of particles and evolutionary genetic algorithm under the different crossover probability

图9 采用A*算法的路径规划Fig.9 Path planning using A* algorithm

表2 路径规划所用时间和长度Table 2 Time and length for path planning

注：数据为仿真数据,长度无单位．

从表2可以看出,相较于遗传算法、A*算法、经典ABC算法,文中方法在路径长度计算上分别减少了2.83%,0.08%和0.31%,而对应的时间损耗分别减少了26.19%,0.17%和11.13%．由于A*算法是一种典型的启发式搜索算法,该算法理论上可获得最优解,但其对空间需求较大．如果路径寻优中不存在一条通达的路,采用A*算法势必会穷举所有可能的情况．而文中方法仅需要对粒子进行规划,无须像A*算法那样遍历所有可能,因此能减少时间消耗,尤其针对较大场景,文中方法优势更明显．

综上所述,文中方法相较于传统算法能够寻找到更加优化的路径,验证了文中方法在移动机器人路径规划中的可行性．