引自：《群体智能》（作者：张国辉、文笑雨）

【资料图】

「 1. 群体智能的含义与特点 」

群体智能（swarm intelligence，SI）是人工智能领域中重要的概念，最早由Gerardo Beni和Jing Wang于1989年提出[1]，用以研究细胞机器人系统，如兰顿的蚂蚁和康韦的生命游戏。群体智能在有的文献中也称为集群智能（collective intelligence，CI）[2]。在动物社会里，有些个体微不足道，然而群体能够解决单个个体难以解决或不可能解决的复杂问题。例如，蚂蚁、蜜蜂、鱼以及其他群居动物，它们的群体协调能力都令人难以置信。群体中的个体可以更容易地捕捉到更大的猎物，或者更好地保护自己免受捕食者的攻击[3]。对群体行为的研究促使人们认识到，群体生活也可以帮助解决超出单个动物能力范围的认知问题[4,5]，虽然个体动物在认知上相对简单，在其能达到的目标上受到限制，然而，群体的能力则能做出惊人的成就[6]。

群体智能并不是简单的多个体的集合，而是超越个体行为的一种更高级表现，这种从个体行为到群体行为的演变过程往往极其复杂，是群体中各个个体随时间相互作用的模式和结果，以至于很难由个体的简单行为来预测和推演。这称为涌现（emergence），指推演一个复杂系统中某些新的、相关的结构、模式和性质（或行为）的过程。

可以用图1来说明群体中的个体比个体或小群体中的个体做出更好决策的过程[7]。个体用黑色圆圈表示，从源头到接收者的信息流用箭头表示。（a）当个体认知能力水平提高时，个体之间就没有信息流动。相反，在一个群体中可以减少对捕食风险的感知，允许个体将更多的认知资源分配到其他任务中，或者在风险不受（或更少）被捕食群体规模影响的情况下对捕食者保持警惕。（b）信息可以从所有或部分成员集中，在那里进行处理，并作出总体决策，或将信息提供给群内成员使用。（c）在领导力方面，信息从一个（或几个）具有相关知识的个体流向其他群体成员。（d）在群体智能中，只有信息交流，没有明显的集中者领导关键个体。

图1 群体智能信息交流

对于一个由众多简单个体组成的群体，若其个体具有能通过彼此间的简单合作来完成一个整体任务的能力，则称该群体具有“群体智能”。群体智能中的“群体”指的是一组相互之间通过改变局部环境信息可以进行直接或间接通信的个体，这些个体能够合作进行分布式问题的求解。群体智能中的“个体”是指仅具有较为简单的能力，这种能力可用某一简单的功能函数来表示。个体间的相互作用、间接通信也称为外激励（stigmergy）。

在自然界中，通过群体中个体间的相互协作完成任务的例子有：

（1）白蚁建造的大巢穴结构的复杂度是单个白蚁凭借自己的能力所无法实现的。

（2）在一个蚂蚁群中，在没有任何中心管理者和任务协调员的情况下，其任务都是动态分配的。

（3）在蜜蜂类中通过摆动跳舞实现了最佳的觅食行为。觅食行为作为简单的轨迹跟踪行为也在蚁群中涌现。

（4）鸟群中的鸟和鱼群中的鱼会自组织成最佳的空间模式。鸟群或鱼群通过声音和视觉感知的通信基于少量的邻近个体来确定它们的行为（例如调整自己的方向和速度）。

（5）猎食者（例如一个狮群）表现出的猎食策略比被猎食者更精明。

（6）细菌利用分子（类似信息素）通信，共同保持对环境变化的跟踪。

（7）粘菌由非常简单的且能力有限的分子有机体组成。然而，在缺少食物的时代，它们聚集形成一个移动的块，以便将聚集在一起的个体运送到新的食物区域。

关于群体智能的定义在已发表和出版的文献中都不尽相同。如有的定义为，两个或更多个独立收集信息的个体通过社交互动进行信息交流，并为单个个体无法解决的认知问题提供群体的含义。也有定义为：是指在某群体中，若存在众多无智能的个体，它们通过相互之间的简单合作所表现出来的智能行为。在蚁群算法提出者Dorigo[8]的文献中对群体智能如此描述：指具有简单智能的个体通过相互协作和组织表现出群体智能行为的特性，具有天然的分布式和自组织特征。

总之，群体智能的核心是由众多简单个体组成的群体能够通过相互之间的简单合作来实现某一较复杂的功能，完成某一较复杂的任务。群体智能可以在没有集中控制并且缺少全局信息和模型的前提下，为解决复杂的分布式问题提供了可能。

群体智能的特点主要包括[9]：

（1）灵活性（flexibilty），群体可以适应随时变化的系统或网络环境；

（2）鲁棒性（robustness），没有中心或者统一的控制，即使单个个体失败，整个群体仍然具有完成任务的能力，不会出现由于某一个或者某几个个体的故障或失败而影响整个问题的求解；

（3）自组织（self-organization），活动既不受中央控制，也不受局部监管。

群体智能的优点主要体现在[9]：

（1）分布性（distribution），群体中相互合作的个体是分布的，这样更能够适应当前网络环境下的工作状态；

（2）简单性（simplicity），系统中每个个体的能力十分简单，个体的执行时间比较短，并且实现也比较简单；

（3）可扩充性（extensibility），可以仅仅通过个体之间的间接通信进行合作，系统具有很好的可扩充性，因为系统个体的增加而引起的通信开销的增加很小。

Millonas提出了群体智能遵循的五条基本原则[10]：

（1）邻近原则（proximity principle），群体能够进行简单的空间和时间计算；

（2）品质原则（quality principle），群体能够响应环境中的品质因子；

（3）多样性反应原则（principleof diverse response），群体的行动范围不应该太窄；

（4）稳定性原则（stability principle），群体不应在每次环境变化时都改变自身的行为；

（5）适应性原则（adaptability principle），在所需代价不太高的情况下，群体能够在适当的时候改变自身的行为。

「 2. 群体智能算法的分类 」

群体智能算法是早期学者基于群体智能，针对群体行为特征规律上的研究，受社会昆虫（如蚂蚁、蜜蜂）、群居脊椎动物（如鸟群、鱼群和兽群）或其他群居生物的启发，提出一系列具备群体智能特征的算法用来解决复杂问题。自1992年意大利学者Dorigo[8]从蚁群寻找最短路径的现象中受到启发在他的博士论文中提出蚁群优化（ant colony optimization，ACO）理论开始，群体智能算法作为一个理论被正式提出，并逐渐吸引了大批学者的关注，应用于不同的领域，从而掀起了研究高潮。1995年，Kennedy等学者[11]模拟鸟群觅食行为提出了粒子群优化算法（particle swarm optimization，PSO），由于PSO模型简单、参数少得到了广泛的研究与应用，进一步推进了群体智能算法的研究。近年来，众多研究学者模拟不同的群体特征陆续提出了不同的群体智能算法。

如图2所示，按照启发式方法的发展进行分类。对于优化问题的求解，最早通过数学方法寻求最优解。而启发式算法是受大自然的运行规律或面向具体问题的经验、规则启发出来的方法，在可接受的计算时间或空间范围内给出待解决优化问题的可行解，该可行解与最优解的偏离程度一般不能被预计。由于早期启发式方法在求解大规模问题时容易陷入局部最优，求解效果并不理想，研究学者根据自然界现象提出了自然启发式方法。在自然启发式方法中包括一类是基于生物行为的算法，即生物启发式方法，另外一类模拟物理现象等自然现象的，如模拟退火算法。而在生物启发式方法中，最主要的一类是模拟动物群体行为的群体智能算法，也是本书后续章节中主要讲的内容，另一类是模拟生物进化的进化计算，还有一类是模拟其他生物群体的算法，如文化算法、免疫算法等。

图2 启发式方法分类

由于群体智能算法的灵感主要来自于模拟不同生物群体，按照不同群体的方式进行分类，可以分为昆虫类、细菌类、鸟群类、水生类以及陆生类等，如图3所示。由于新的模拟生物群体的算法仍在不断被学者提出，图3中无法包括所有提出的算法。

图3 群体智能算法分类

目前，由于每种算法经过改进后可以衍生出较多算法，为了能够对常用算法的提出思想有所了解，如表1所示，给出了常用算法的名称、提出作者、基本思想以及提出的年份[12,13]。

表1 部分群体智能算法基本信息

群体智能算法具有以下特点[31-34]：

（1）智能性。群体智能算法通过向大自然界中的某些生命现象或自然现象学习，实现对于问题的求解，这一类算法中包含了自然界生命现象所具有的自组织、自学习和自适应性等特性。在运算过程中，通过获得的计算信息自行组织种群对解空间进行搜索。由于群体智能算法具有的这种优点，应用群体智能算法求解问题时，不需要已知待优化问题的梯度信息，也不需要事先对待求解问题进行详细数学建模。对于某些复杂性高的问题，高效求解成为可能。

（2）隐含本质并行性。群体智能算法通过设定相应的种群进化机制完成计算，而种群内的个体则具有一定的独立性，个体之间完全是一种本质上的并行机制。如果使用分布式多处理机来完成群体智能算法，可以将算法设置为多个种群并分别放置于不同的处理机实现进化，迭代期间完成一定的信息交流即可（注：信息交流并不是必要的），迭代完成之后，根据适应度值进行优胜劣汰。所以，群体智能算法这种隐含的本质并行性，能够更充分利用多处理器机制，实现并行编程，提高算法的求解能力。更加适合目前云计算等分布式计算技术迅速发展的背景。

（3）解的近似性。群体智能算法通常来自于对大自然中某种生命或其他事物的智能协作进化现象的模拟，利用某种进化机制指导种群对解空间进行搜索。由于该类算法缺乏严格的数学理论支持，对于问题的解空间采用反复迭代的概率性搜索，所以群体智能算法会存在早熟或求解精度较低等问题，而这也是所有群体智能算法几乎都存在的弱点。所以，很多时候对求解的问题来说，群体智能算法仅仅得到的是一种近似最优解。但是，这种近似最优解可以一次提供多个，为决策者提供更多选择。

参考文献

[1] Beni, G. and Wang, J. (1989) Swarm Intelligence in Cellular Robotic Systems, Proceed. NATO Advanced Workshop on Robots and Biological Systems, Tuscany, Italy, Jun. 26–30.

[2] Kennedy J, Eberhart R C. Swarm Intelligence[M]. San Francisco, CA: Morgan Kaufmann, 2001.

[3] Krause, J. and Ruxton, G.D. (2002) Living in Groups, Oxford University Press.

[4] Bonabeau, E. et al. (1999) Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press

[5] Camazine, S. et al. (2001) Self-Organization in Biological Systems, Princeton University Press.

[6] Krause J, Ruxton G D, Krause S. Swarm intelligence in animals and humans[J]. Trends in Ecology & Evolution, 2010, 25(1):28-34.

[7] Ioannou, Christos C. Swarm intelligence in fish? The difficulty in demonstrating distributed and self-organised collective intelligence in (some) animal groups[J]. Behavioural Processes, 2016, 141:141-151.

[8] Dorigo M. Optimization, learning and natural algorithms. Ph. D. Thesis, Politecnico di Milano, Italy, 1992.

[9] 余建平, 周新民, 陈明. 群体智能典型算法研究综述[J].计算机工程与应用, 2010, 46(25): 1-4+74.

[10]K E Parsopoulos, M N Vrahatis. Recent approaches to global optimization problems throug h particle swarm opti- mization[J]. Natural Computing, 2002, 1(2): 235-306.

[11]Kennedy J, Eberhart R. Particle swarm optimization[C]. Proceedings of IEEE International Conference on Neural Networks, Perth, 27 November-01 December 1995, pp. 1942-1948.

[12]Ouarda Z, Antonio G, Nicolas J, et al. Swarm intelligence-based algorithms within IoT-based systems: A review[J]. Journal of Parallel & Distributed Computing, 2018, 177: 173-187.

[13]Slowik A, Kwasnicka H. Nature inspired methods and their industry applications—swarm intelligence algorithms[J]. IEEE Transactions on Industrial Informatics, 2018, 14(3): 1004-1015.

[14]Passino K. M. Biomimicry of bacterial foraging for distributed optimization and control[J]. Control Systems Magazine, 2002, 22(3): 52-67.

[15]Li X L , Shao Z J , Qian J X . An optimizing method based on autonomous animate: Fish swarm algorithm[J]. Systems Engineering-theory & Practice, 2002, 22(11): 32-38.

[16]Li W W, Wang H, Zou Z J, et al. Function optimization method based on bacterial colony chemotaxis[J]. Journal of Circuits and Systems, 2005, 10(1): 58-63.

[17]Teodorovic D, DellOrco M. Bee colony optimizationa cooperative learning approach to complex transportation problems[C]. In Proc. 16th MiniEURO Conference and 10th meeting of EWGT, 2005, pp. 51-60.

[18]Chu S C , Tsai P W , Pan J S . Cat Swarm Optimization[C]. International Conference on Artificial Intelligence. LNCS, 2006, 4099: 854-858.

[19]Karaboga D , Basturk B . A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm[J]. 2007, 39(3):459-471.

[20]Yang X S, & Deb, S. Cuckoo Search via Lévy flights. 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), 2009, 210-214.

[21]Yang X S. Firefly algorithms for multimodal optimization[C]. In Proc International Symposium on Stochastic Algorithms, LNCS, 2009, 5792: 169-178.

[22]Krishnanand K N , Ghose D . Glowworm swarm optimisation: a new method for optimising multi-modal functions[J]. International Journal of Computational I, 2009, 1(1):93-119.

[23]Yang X S. A new metaheuristic bat-inspired algorithm[C]. In Proc. Nature Inspired Cooperative Strategies for Optimization (NICSO), 2010, pp. 65-74.

[24]Chen Z H, Tang H Y. Cockroach swarm optimization[C]. In Proc. 2nd International Conference on Computer Engineering and Technology, 2010, pp. 652-655.

[25]Rajakumar B R . The Lion"s Algorithm: A new nature-inspired search algorithm[J]. Procedia Technology, 2012, 6: 126-135.

[26]Tang R, Fong S, Yang X S, Deb S. Wolf search algorithm with ephemeral memory[C]. In Proc. Seventh International Conference on Digital Information Management (ICDIM), 2012, pp. 165-172.

[27]Xing B, Gao W J. Fruit fly optimization algorithm[C]. In Innovative Computational Intelligence: A Rough Guide to 134 Clever Algorithms, pp. 167-170, 2013.

[28]Cuevas E, Cienfuegos M, Zaldivar D, Perez-Cisneros M. A swarm optimization algorithm inspired in the behaviour of the social-spider[J]. Expert Systems with Applications, 2013, 40(16): 6374-6384.

[29]Wu T Q, Yao M, Yang J H. Dolphin swarm algorithm[J]. Frontiers of Information Technology and Electronic Engineering, 2016, 17(8): 717-729.

[30]Mirjalili S, Lewis A. The whale optimization algorithm[J] Advances in Engineering Software, 2016, 95: 51-67.

[31]孙嘉泽, 王曙燕. 群体智能优化算法及其应用[M]. 科学出版社, 2017.

[32]Andries P. Engelbrecht著, 谭营译. 计算智能基础[M]. 清华大学出版社, 2009.

[33]王培崇. 群体智能算法及其应用. 电子工业出版社[M], 2015.

[34]程适, 王锐, 伍国华, 郭一楠, 马连博, 史玉回. 群体智能优化算法[J].郑州大学学报(工学版), 2018, 39(06): 1-2.

关键词： 康威生命游戏 知识改变生活 人工智能 BENI