酷应用

《常用算法之智能计算(六)》：群智能计算

百家作者：数盟 2018-12-24 15:48:58

群智能计算(Swarm Intelligence Computing)，又称群体智能计算或群集智能计算，是指一类受昆虫、兽群、鸟群和鱼群等的群体行为启发而设计出来的具有分布式智能行为特征的一些智能算法。群智能中的“群”指的是一组相互之间可以进行直接或间接通信的群体；“群智能”指的是无智能的群体通过合作表现出智能行为的特性。智能计算作为一种新兴的计算技术，受到越来越多研究者的关注，并和人工生命、进化策略以及遗传算法等有着极为特殊的联系，已经得到广泛的应用。群智能计算在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。

对一般群智能计算，通常要求满足以下五条基本原则：

邻近原则：群内的个体具有对简单的空间或时间进行计算和评估的能力；

品质原则：群内的个体具有对环境以及群内其他个体的品质作出响应的能力；

多样性原则：群内的不同个体能够对环境中某些变化做出不同的多样反应；

稳定性原则：群内个体的行为模式不会在每次环境发生变化时都发生改变；

适应性原则：群内个体能够在所需代价不高的情况下，适当改变自身的行为模式。

群智能计算现含蚁群算法、蜂群算法、鸡群算法、猫群算法、鱼群算法、象群算法、狼群算法、果蝇算法、飞蛾扑火算法、萤火虫算法、细菌觅食算法、混合蛙跳算法、粒子群算法等诸多智能算法。下面对它们中间常用的一些重要算法进行一些简单介绍。

蚁群算法(Ant Colony Algorithm)，受蚂蚁觅食过程及其通信机制的启发，对蚂蚁群落的食物采集过程进行模拟，可用来解决计算机算法中的经典“货郎担问题”，即求出需要对所有n个城市进行访问且只访问一次的最短路径及其距离。

在解决货郎担问题时，蚁群算法设计的虚拟“蚂蚁”将摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。虚拟的“信息素”会因挥发而减少；每只蚂蚁每次随机选择要走的路径，它们倾向于选择路径比较短的、信息素比较浓的路径。根据“信息素较浓的路线更近”的原则，即可选择出最佳路线。由于这个算法利用了正反馈机制，使得较短的路径能够有较大的机会得到选择，并且由于采用了概率算法，所以它能够不局限于局部最优解。蚁群算法具有很多特点，简单说来，它是一种自组织的并行算法，具有较强的算法的可靠性、稳健性和全局搜索能力。

蚁群基本算法由三个操作过程组成，它们分别是解构建，信息素更新和后台操作。

（1）解构建：一定数目的虚拟蚂蚁在完全连接图中按照某种规则出发，各自独立地根据信息素和启发式信息，采用一个概率规则选择下一步的移动，直到建立优化问题一个完整的解，并对构成的解进行质量评估。

（2）信息素更新：包括信息素的释放过程和蒸发过程。信息素释放往往根据构成解的质量决定释放量的大小，而信息素蒸发通常是以一个固定比例值衰减所有边上的信息素。整个更新过程一般是在解的构建完成后，但有时也会出现在解构建的每一步中。每条边上信息素的量直接影响蚂蚁对这条边的选择概率，因而信息素的分布情况决定了整个蚁群的搜索空间方向。

（3）后台操作：以灵活的机制执行单独蚂蚁不能完成的宏观操作，如搜集全局信息素情况，采取局部搜索措施等，从而对整个算法的行为进行调控。

以上三个操作过程的结合方式是根据算法设计者考虑问题特征时自由指定的，可以并行、独立、交叉以及同步，从某种程度上来说它们之间是相互作用的。

蚁群算法对于解决货郎担问题并不是最好的方法，但它首先提出了一种解决货郎担问题的新思路；其次，由于这种算法特有的解决方案，已成功用于解决其他组合优化问题，如图着色、最短超串等；最后，通过对蚁群算法进行的精心研究和应用开发，现己被大量应用于数据分析、机器人协作问题求解，也在电力、通信、水利、采矿、化工、建筑、交通等领域得到成功的应用。

蜂群算法（Bee Colony Algorithm）根据蜜蜂各自的分工不同，对蜂群信息共享和交流及进行采蜜活动等的观察和研究，对蜂群的采蜜行为进行计算机模拟，以此找到问题的最优解，是一种基于群智能的全局优化算法。

经过对蜜蜂采蜜机制的观察和研究，可将除蜂王外的整个蜂群的蜜蜂分为三类，即采蜜蜂、观察蜂和侦察蜂，整个蜂群的目标是寻找花蜜量最大的蜜源。在蜂群算法中，采蜜蜂利用先前的蜜源信息采蜜，寻找新的蜜源并与观察蜂分享蜜源信息；观察蜂依据与采蜜蜂分享的信息寻找新的蜜源；侦查蜂的任务是寻找一个新的更有价值的蜜源，它们在蜂房附近随机地寻找蜜源。蜂群算法通过对三类蜜蜂功能的模拟，以寻找最短路径、最大蜜源为目标，用于寻求问题的最优解。

狼群算法（Wolf Colony Algorithm）是基于狼群群体智能，模拟狼群捕食行为及其猎物分配方式，抽象出游走、召唤、围攻三种智能行为以及“胜者为王”的头狼产生规则和“强者生存”的狼群更新机制，提出一种新的群智能算法。算法采用基于狼主体的自下而上的设计方法和基于职责分工的协作式搜索路径结构，通过狼群个体对猎物气味、环境信息的探知、人工狼相互间信息的共享和交互以及人工狼基于自身职责的个体行为决策最终实现了狼群捕猎的全过程模拟。

粒子群算法（Particle Swarm Algorithm）源于对鸟群和兽群捕食行为的研究，基本核心是利用群体中的个体对信息的共享从而使得整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得问题的最优解。

可以利用一个有关粒子群算法的经典描述，对粒子群算法进行直观描述和简要介绍。

设想这么一个场景：一群鸟进行觅食，而远处有一片玉米地，所有的鸟都不知道玉米地到底在哪里，但是它们知道自己当前的位置距玉米地不远。找到玉米地的最佳策略，就是搜寻目前距离玉米地最近的周围区域。粒子群算法就是从这种群体觅食的行为中得到了启示，从而构建的一种优化模型。

在粒子群算法中，把搜索空间中的鸟称之为“粒子”，而问题的“最优解”对应为鸟群要寻找的“玉米地”。所有的粒子都具有一个位置向量（粒子在解空间的位置）和速度向量（决定下次飞行的方向和速度），并可以根据目标函数来计算当前的所在位置的适应值，可以将其理解为距离“玉米地”的距离。在每次的迭代中，群中的粒子除了根据自身的“经验”（历史位置）进行学习以外，还可以根据种群中最优粒子的“经验”来学习，从而确定下一次迭代时需要如何调整和改变飞行的方向和速度，进行逐步迭代，最终整个种群的粒子就会逐步趋于最优解。

粒子群算法的计算步骤如下：

步骤1 种群初始化：可以进行随机初始化或者根据被优化的问题设计特定的初始化方法，然后计算个体的适应值，从而选择出个体的局部最优位置向量和种群的全局最优位置向量。

步骤2 迭代设置：设置迭代次数；

步骤3 速度更新：更新每个个体的速度向量；

步骤4 位置更新：更新每个个体的位置向量；

步骤5 局部位置向量和全局位置向量更新；

步骤6 终止条件判断：判断迭代次数是否达到要求，如满足，输出计算结果；否则继续进行迭代，跳转至步骤3。

在粒子群算法的应用中，主要是对速度和位置向量迭代算子的设计。迭代算子是否有效将决定整个粒子群算法算法性能的优劣，所以如何设计粒子群算法的迭代算子是粒子群算法算法应用的研究重点和难点。

通过上面几个群智能算法的介绍，不难看出，它们一般都具有如下一些特点：群体中相互合作的个体是分布式的，这样更能够适应当前网络环境下的工作状态；没有中心的控制与数据，这样的系统更具有稳健性，不会由于某一个或者某几个个体的故障而影响整个问题的求解；可以不通过个体之间直接通信而是通过非直接通信进行合作，这样的系统具有更好的可扩充性；由于系统中个体的增加而随之增加的开销十分小，系统中每个个体的能力十分简单，这样每个个体的执行时间比较短，并且实现起来也比较简单，具有简单性，在计算机上容易实现编程和并行处理。

此外，需要对群智能算法实行进一步研发和改进，经常遇到的问题有：

从上面已经列出的十多种群智能算法来看，类似性似乎比较多，应按照数学的抽象性、理论性、应用性和计算机程序的编程类似性等进行合理整顿，需要合并的就进行合并，能略去的就略去，更应加强算法收敛性、有效性等的基础研究；

智能算法重在应用，要特别加强已有算法的应用研究，不断扩大应用范围和领域；

对现有的群智能算法在加强理论研究的同时，进行必要的算法改进，提高应用的广泛性和有效性，克服诸如精度不高、收敛速度较慢、容易收敛到局部极小值、多样性下降过快、参数敏感等问题；

进一步寻求更好、更快、更新和更高效的群智能算法。

群智能算法和传统优化算法相比，具有简单、并行、适用性强等优点，它不要求问题连续可微，特别适用于具有高度可重入性、高度随机性、大规模、多目标、多约束等特征的各类典型优化问题求解。但是，由于群体智能计算是一种新兴的理论和算法，其理论基础还不够完善，数学基础相对薄弱，因此，如何提高算法在解空间内的搜索效率，算法收敛性分析与证明以及对算法模型框架本身的研究都需要进行更深入的探索，特别是对群体智能归纳出统一的计算模式和框架建模理念。

群体智能来源于对自然界中生物群体行为的模拟，而智能个体在群体中的行为在很多方面类似于生物群体在自然环境中的生态行为，物种乃至整个生态系统的进化都离不开种群之间的协同作用。因此，可以从自然界中获取很多具有参考意义的科学法则以及相关理论，用来指导群体智能计算模式的研究及其算法改进。如借鉴自然界中种群生态学中的竞争、捕食和协同进化等机制以及自然系统中的混沌现象与机理以及运行规律来进行群体智能计算模式的设计与改进研究，将是一个很有意义的研究领域。

群智能计算因为具有以上诸多特点，虽说研究还处于初级阶段，理论上存在不少缺空，并有诸多困难和问题，但是由于其具有的分布式、自组织、协作性、稳健性和实现简单等特点，在诸如优化问题求解、机器人领域、电力系统领域、网络及通讯领域、计算机领域、交通领域和半导体制造领域等取得了较为成功的应用，为寻找复杂问题的解决方案提供了快速可靠的基础，为人工智能、认知科学等领域的基础理论问题的研究开辟了新的途径。因此，可以预见群智能的研究代表了以后各类算法研究发展的一个重要方向，具有重要意义和广阔的不可忽视的应用前景，会逐渐成为一个新的重要研究方向，值得给予更多的重视。

识别下图二维码，加“数盟社区”为好友，回复暗号“入群”，加入数盟社区交流群，群内持续有干货分享~~