群体智能算法从生物现象中获得哪些启示

群体智能算法从生物现象中获得哪些启示
2019年01月07日 09:43 科工力量

还记得电影《蚁人》中的神队友吗?如果没有那些成群蚂蚁机器人,蚁人要对付坏人的话,可是没有那么容易的。如同现实中的蚂蚁,一个简单的个体只是有几个神经关节组成,但形成的一个蚁群却能够完成各种复杂的任务。在生物圈中,除了蚂蚁还有很多类似的生物,他们个体活动仅仅遵循简单的活动准则,但是形成的群体行为却表现出高超的智能。其实在人工智能领域这种现象被称为“群体智能”。

受到这种生物群体行为研究的启发,专家学者发明创建群体计算模型,它们表现出了与单个个体完全不同的非凡计算能力,可以用于求解大量复杂的科学工程问题,受到广泛的关注和研究,并发展成为群智能优化计算的新型研究方向。群智能优化算法为计算智能和人工智能研究领域的一个研究热点以及交叉学科中一个非常活跃的前沿研究课题,其应用已经渗透到各个领域。

集群是生物中一种非常常见的生物现象,像蚂蚁,蜜蜂,鱼类集群等,这些生物在不同环境中的生存方式给人类解决问题的思路带来了很多灵感。其实人类从动物进化、免疫、神经元系统、DNA信息、生物协作中得到启发,使得许多人类看起来高度复杂的的优化问题可以从这些生物智能现象得到完美的解决。

群体智能中,群体指的是一群相互之间可以进行直接或间接通信的个体,这组个体可以通过相互协作进行分布问题求解。简单的说,群体智能就是低智能的个体通过相互通信和协作完成高智能的行为,许多简单的个体组成群体,它们相互合作完成较为复杂的功能。为了便于认识群智能优化算法所处的层次,我们给出一张关系图,关系图中展示生物学上现象与对应的仿生计算方法。图中我们可以看到从各种独特的生物学现象提炼出其对应的仿生计算方法。

(仿生计算方法)

而这里面大多数算法都是基于梯度的应用优化算法,举个简单例子来说,求抛物线的极值点时,我们一般先要对函数求导,得到梯度变化最小的点,这个点就是极值点。但是群智能依靠的是概率搜索算法,虽然概率搜索算法通常采用较多的评价函数,但是与梯度方法及传统的演化算法相比,优点明显:

1、算法思想简单容易实现,只需遵循几个简单的规则。

2、以非直接的信息交流方式确保系统的扩张性,也就是说,每个点的行为是自主的,只会根据局部的变化改变自己的行为,不是由中心控制的。

3、具有并行性和分布式特点,可以利用多处理器予以实现。

4、对问题定义的连续性无特许要求,可以处理离散域问题。

5、没有集中控制的约束,不会因个别的故障影响整个问题的求解,确保了系统具备更强的鲁棒性(也就是说抗干扰能力强)。

群智能算法仅仅涉及基本的数学操作,数据处理过程对CPU和内存的要求不高。这种方法只需要计算目标函数的函数值,不用计算梯度信息。群智能理论已经完成的研究和应用证明这种方法是有效解决大多数全局优化问题的新方法。

群智能优化算法主要包括:粒子群优化算法、蚁群优化算法、人工蜂群优化算法、人工鱼群优化算法。

粒子群优化(PSO)算法

粒子群优化算法初期只是设想模拟鸟群觅食行为过程,但是后来发现PSO算法是一种很好用的优化工具。其基本思想源于对鸟类觅食过程中迁移和聚集行为的模拟,通过鸟之间的集体协作和竞争达到目的。设想这样一个场景:一群鸟随机搜索食物,在这个区域里只有一块食物,所有的鸟都不知道食物在哪里,但是他们知道当前位置离食物多远,那么找到食物最优的策略是什么?那就是搜寻离食物最近的鸟周围区域。我们将每只鸟看成一个“粒子”,每个粒子的初始速度和位置都是随机的,而后粒子速度就朝着全局最优和个体最优的方面靠近,所有粒子都有一个由被最优函数决定的适应度值,粒子们追随当前最优粒子在解空间中搜索。初始粒子随机分布,随着迭代进行,粒子们逐渐向最优解逼近。

(图a、b、c、d中粒子逐渐向最优区间逼近)

但是该方法也有缺点,对于有多个极值点的函数,该方法容易陷入局部极值点。就如鸟群都集中在食物量很少的区域内,没找到那块食物量最多的区域。

采用粒子群优化算法可以求解交通信号配时问题,航班进场、离场调度问题,机器人全局路径规划问题。该算法还有另外一个重要应用领域是图像处理,因为图像信息多样性和复杂性特征,目前在图像处理领域,建模困难、处理不完整等问题普遍存在。而粒子优化算法在图形处理领域中取得了一定的成功。(《通讯世界》:图像去燥处理中粒子群优化算法研究)

蚁群优化(ACO)算法

蚂蚁优化算法是对自然界蚂蚁的寻径方式进行模拟而得到的一种仿生算法。在蚂蚁寻找食物过程中,蚁群总能找到一条从食物到巢穴之间的左右路径,这是因为蚂蚁在寻找路径时,会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时,就随机挑选一条路径前行,与此同时释放出与路径长度有关的信息素,路径越长,信息素越低。当后来的蚂蚁碰到这个路口时,就选择信息素浓度高的路径,这就形成了一个正反馈,最优路径上信息素浓度越来越大,其他路径上信息素越来越低,最终蚁群会找到最优路径。蚂蚁算法有较强的自学能力,可以根据环境的改变和过去的行为结果对自身的知识库或自身的组织结构进行调整,从而实现算法求解能力的进化。

(从A到D点,ACD的路径是ABD的两倍,在ABD路径上的蚂蚁返回A时,ACD上蚂蚁刚到D,所以ABD路径上信息素浓度是ACD的两倍)

这个算法应用于其他组合优化问题,如旅行商问题、指派问题、车辆路由问题、网络路由问题等。最近几年,该算法在网络路由中的应用受到越来越多的学者关注,并提出一些新的基于蚂蚁算法的路由算法。同传统的路由算法相比,该算法在网络路由中具有信息分布式性、动态性、随机性和异步性等特点,而这些特点正好满足网络路由的特点。

人工蜂群(ABC)算法

人工蜂群算法是模仿蜜蜂行为提出的一种优化方法,是群智能思想的一个具体应用。在寻找食物源(花朵)过程中,引领蜂通过摇摆舞的持续时间来表现食物源的收益率,其他跟随蜂可以观察这种舞蹈并依据收益率来选择哪个食物源。收益率与食物源被选择的可能性成正比。所以,蜜蜂被吸引到某一个食物源的概率与食物源的收益率成正比。基于上述思想的蜜蜂算法的主要特点是不需要了解问题的特殊信息,只需要对问题进行优劣比价,通过各人工蜂的局部寻优行为,最终在群体中使全局最优值凸显出来,有着较快的收敛速度。为了解决多变量函数优化问题,Karaboga提出人工蜂群算法模型。

(蜂群寻蜜源过程)

专家提出基于人工蜂群算法的煤矿救灾机器人全局路径规划算法。该算法首先进行环境建模,然后根据环境信息特点,巧妙结合人工蜂群算法获得机器人全局优化路径。该路径规划方法具有建模方便、算法简单以及不局限于障碍物的形状等特点。实验证明,本算法可以快速有效地规划出一条全局较优化路径,是解决全局环境已知情况下机器人路径规划的一种有效方法。(《煤炭技术》:基于蜂群算法的煤矿救灾机器人全局路径规划)

针对不相关并行机混合流水线调度问题的特点,专家设计了一种基于排列的编码和解码方法,提出了一种有效的人工蜂群算法。在引领蜂和跟随蜂搜索阶段采用3种有效的邻域搜索方法,以丰富搜索行为。在侦察蜂搜索阶段通过随机搜索对种群进行更新,以增强种群多样性。同时,通过试验设计方法对算法的参数设置进行了分析,给出指导性参数组合。通过基于典型实例的数值仿真以及与已有代表性算法的比较,验证了所提算法的有效性和鲁棒性。(《控制理论与应用》:求解不相关并行机混合流水线调度问题的人工蜂群算法)

人工鱼群(AF)算法

人工鱼群算法是国内李晓磊博士等人在动物群体智能行为研究基础上提出的一种新型仿生群智能优化算法。该算法根据水域鱼生存数目最多的地方就是该水域中富含营养物质最多的地方这一特点来模拟鱼群的觅食行为而实现寻优。算法主要利用鱼的三个基本行为:觅食、聚群和追尾行为,人工鱼是真实鱼的抽象化、虚拟化的一个实体,其中封装了自身的数据和一系列行为,可以接受环境的刺激信息,做出相应的活动。它的下一刻状态取决于自身状态和环境状态,并通过自身活动影响环境,进而影响其他人工鱼的活动。该算法收敛速度快,可用于解决实时性要求高的问题。对于精度要求不高的场合,可以快速得到可行解;

(人工鱼及其环境)

针对车联网环境下若干典型车辆轨迹规划方法存在车速与轨迹波动性较大的问题,专家提出了一种基于改进人工鱼群算法的车辆轨迹规划方法。该方法以DSRC通信的车联网应用场景为设计平台,车辆的最优行车速度为核心计算基础,分析得到车辆的最佳轨迹。(《计算机应用》:基于改进人工鱼群算法的车辆轨迹规划方法)

针对基于BP神经网络室内定位算法收敛速度慢和定位精度低的问题,专家提出了改进的人工鱼群算法(AFSA)和距离加权质心法。通过改进人工鱼觅食和寻优方式来提高人工鱼全局寻优的能力和速度,并用该算法来选取室内定位神经网络参数。通过改进的加权质心法计算距离,以减小室内复杂环境干扰造成的定位的误差。实验证明该改进方法使室内定位的平均精度比BP神经网络模型提高8%左右,并提高了室内定位的可靠性。(《计算机应用》:基于人工鱼群算法的无线室内定位优化)

参考资料:

《群智能优化算法及其应用》

《通讯世界》

《煤炭技术》

《控制理论与应用》

《计算机应用》

财经自媒体联盟更多自媒体作者

新浪首页 语音播报 相关新闻 返回顶部