有意思,让两种“蜂群”去解决一种“蚂蚁”?

   自动化那些事        

人工问题被认为是机器人路径规划的子问题。该研究采用两种不同的方法来解决这个问题:人工蜂群规划和一个新的版本的收缩人工蜂群规划。前者是一种基于人工蜂群算法的基于进化计算的自动规划方法,是前人将其应用于该问题的研究。


但是该研究提供了更全面的分析和比较研究。收缩人工蜂群规划是该研究开发的,其基本思想是周期性地减少食物来源的数量,而不是在人工蜂群规划中使用的常数。


首先,对收缩人工蜂群规划进行了参数整定研究。然后,比较了人工蜂群规划、收缩人工蜂群规划和其他几种基于进化计算的自动规划方法在Santa Fe和Los Altos山地路径上的性能。仿真结果和比较研究表明,两种算法都能有效地解决人工蚂蚁问题。本文以“Solving artificial ant problem using two artificial bee colony programming versions”为题于2020年6月25日发布于《Applied Intelligence》杂志上。


研究背景


机器人被用于许多不同的领域,如机器人制造、无人系统和车辆(陆地、空中、水下),特别是在危险的、小的或无法到达的区域,人们无法进入,它们扮演着重要的角色。因此,在自主机器人(无人系统)领域有广泛的研究。


对于无人系统和机器人来说,路径规划是最基本的问题之一。机器人路径规划和自动驾驶汽车是人工智能的两个热门应用领域,近十年来得到了广泛的研究。机器人路径规划的定义如下:在一个包含一定障碍物的环境中,移动机器人必须避开所有障碍物,找到从起始点到目标的最优路径(至少是可行的)。


当在复杂环境下进行路径规划时,特别是考虑多个目标和动态问题时,基于进化计算的优化算法和机器学习技术为移动机器人和无人驾驶车辆提供了一些重要的优势。人工蚂蚁问题(AAP)可以看作是机器人路径规划的一个子问题,其中人工蚂蚁必须找到一条路径(trail),使其能够在有限的时间内沿着这条路径收集所有的食物。根据问题的轨迹,可以在文献中找到许多版本:Santa Fe trail (SFT)、Los Altos Hills trail (LAHT)、John Muir trail (JMT)、San Mateo trail等。


采用启发式和人工智能优化算法等多种方法求解AAP。


人工蜂群(ABC)是卡拉巴赫于2005年发明的一种群智能算法。它模拟蜜蜂的觅食行为。作业成本法已应用于数值函数优化等多个领域。


此外,还介绍了ABCP的一个新版本,称为收缩ABCP(ShABCP)。如前所述,ABCP基于ABC算法。虽然作业成本法的搜索策略设计精良,控制参数少,但其收敛速度也有一定的缺陷。


该研究采用两种不同的ECBAP方法:ABCP和shABCP解决了机器人路径规划问题,即AAP问题。ABCP是一种新型的机器学习方法,其性能还没有在AAP上得到全面的研究。该研究在文献中引入了shABCP。


实验研究表明,ABCP和shABCP可以有效地解决AAP问题,所提出的收缩机制显着地提高了ABCP在此问题上的性能。实际上,在比较的方法中,shABCP显示出了较好的性能之一。


SFT是由ChristopherLangton设计的,被研究者广泛使用。这是一个不规则的,非直的和不连续的轨迹,在一个由32×32细胞组成的方形环形网格中。


图为SFT


LAHT由100×100个细胞组成,有157粒食物颗粒,以29圈的速度躺在一条小径上。这条小径的长度是221。从起始点到片号105,轨迹类似于smt。然而,在那之后,通过添加更多的新的不规则食品来延长试验范围。


除了前面解释的间隙之外,LAHT还有一个间隙类型,它在同一行中包含四个空细胞。与SFT相比,这条道路更加困难。它含有更多的食物颗粒,有一个更宽和更复杂的网格。由于网格(100×100)是如此之大,仅在图中显示了含有食物颗粒的轨迹的形式。


图为拉赫特


ABCP是一种ECBAP方法,它采用ABC算法的一般结构来搜索空间。ABC算法是一种流行的群体智能算法,它模仿蜜蜂的觅食行为。


在ABCP中,初始化后有三个阶段:使用蜜蜂阶段、旁观者蜜蜂阶段和侦察蜜蜂阶段,它们被重复地、有序地执行。


图为ABCP流程图


在该研究中,提出了一种控制ABCP种群规模(食物来源数量)的新技术。根据这一技术,在开始时,种群规模被设置得足够大,以探索搜索空间,然后周期性地减少个体数量,试图对其余的个体进行更密集的开发。


图为SHABCP的流程图


在这一部分中,给出了ABCP和shABCP求解AAP的实验结果。首先,对该算法的控制参数进行了实验分析,找出了控制参数的适当设置。


除了ABCP的参数外,shABCP还有两个新的参数,即SHP和SHR。而且,CS成为shABCP中的初始CS(InitCS)。


图为不同initcs值的平均原始适配值的平均值


该研究对shabcp、abcp、gp、lgp效率和lgp效率进行了比较研究。为了进行公平的比较,使用了最大的评估数作为停止标准,并对每个配置进行了100次独立运行。


当在比较中包含GP时,其他算法在SFT和LAHT的平均适应度和SR值上的性能都明显优于GP算法。总的来说,ABCP比GP有更好的结果,并且这个基本版本与其他ECBAP方法相比具有竞争性的性能,而shABCP在五种不同的情况中,分别获得了100次运行的平均、最好和最差的结果和我的最佳结果。


图为在SFT上ABCP和shABCP的收敛性能(MaxEval=20000)


图为在SFT上ABCP和shABCP的收敛性能(MaxEval=100000)


图为在SFT上ABCP和shABCP的收敛性能(MaxEval=200000)


图为ABCP和shABCP在LAHT上的收敛性能(MaxEval=50000)


图为ABCP和shABCP在LAHT(MaxEval=500000)上的收敛性能


所提出的ECBAP方法(ShABCP)在比较的方法中表现出了优越的性能。ABCP和shABCP可以有效地解决AAP问题。与shABCP一起提出的收缩机制显着地提高了ABCP在AAP上的性能。如前所述,ABCP是以ABC算法为基础的,这与其收敛速度有关。


GP是一种基于遗传算法的ECBAP方法。同样,ABCP是使用ABC算法的一般搜索策略的ECBAP方法的基本形式。在所有考虑的情况下,ABCP比GP提供了更好的结果,并且与其他ECBAP方法(包括基本GP和基本ABCP的修改和增强版本)相比,它具有竞争性的性能。


结果表明,与其他基于GP的方法相比,ABCP在较难的情况(LAHT)中表现出更好的性能。这可能与算法的全局优化能力或收敛速度有关。


讨论与研究结论


该研究利用两种新的ECBAP方法,即ABCP和shABCP,对机器人路径规划问题进行了求解。该研究提出了一种求解最优解的方法,该方法可以提高最优解的收敛性能。shABCP是在ABCP的基础上,通过周期性地减小FS来更新FS的新技术。参数shP和shR分别用于控制将会有多少个时期以及在每个时期将从种群中消除的不健康个体的数量。


由于控制参数CS也随着FS的减小而减小,因此在shABCP中使用初始控制参数CS代替控制参数CS。定期消除不适合的个体允许算法围绕剩余的个体执行更多的研究(开发)。


对固定MaxEval值的shP、shR以及initCS和minMaxCyc的适当速率进行了一些参数调优实验。同时,对ABCP、shABCP和GP、LGP effmut、、、、、、等ECBAP技术进行了比较研究,考察了这些方法在AAP上的性能。当与其他ECBAP方法进行比较时,虽然它是一个基本的版本,但其性能具有一定的竞争力。


在所有可用的情况下,ABCP比其他基本版本GP获得更好的结果。在实验中,该方法得到了最好的或非常接近最好的结果,显示出了在所比较的方法中较优的性能之一。考虑结果表和收敛图,可以得出ABCP和shABCP是求解AAP的有效方法之一,而在shABCP中所采用的收缩机制显著提高了ABCP对AAP的性能。作为今后的工作,可以对动态种群大小方法进行改进。


在该研究中,只实现了一个收缩行为。在未来,种群规模可以根据动态变化的需要,通过增加或减少来更新。在此基础上,提出了一种包含所有控制参数的实验设计方法,并对该方法进行了复杂性研究。该方法可以在符号回归等其他领域进行测试,并且可以通过更详细的分析来评估该方法在考虑各种自动编程问题时的优化效果。


此外,ABCP和shABCP可用于解决其他机器人路径规划问题,它们的性能可以与一组更广泛的不同方法进行比较,可用于解决机器人路径规划问题。此外,所提出的收缩机制也可应用于其他使用固定种群大小的ABCP版本。


参考文献: Fateh Boudardara & Beyza Gorkemli Solving artificial ant problem using two artificial bee colony programming versions  Applied Intelligence3695–3717(2020)



最新评论(0)条评论
取消

还没有人评论哦,抢沙发吧~

相关新闻推荐