Boids

Boids是模拟鸟群和其他生物群行行为的一种人工生命算法，由克雷格·雷诺兹（Craig Reynolds）于1986年开发，他介绍该算法的论文最初发表于1987年计算机协会（ACM）的SIGGRAPH会议上^[1]。Boids算法中个体行为遵循“分离、对齐、聚集”三条原则，其中“boids”一词为“bird-oid objects”（类鸟群对象）的缩写。该算法在面世后出现多种变体，并启发了之后的一系列群体智能算法，被广泛应用于计算机图形领域和电影特效等的制作中^[2][3]。

基于OpenGL的Boids算法模拟，其中红色箭头可以看作其他黑色个体的天敌

Boids算法三原则

分离

对齐

聚集

原理

和其他群行行为模拟一样，Boids算法也体现了涌现现象和去中心化，即群体的复杂性是单个个体简单相互作用的结果^[4][5]。克雷格·雷诺兹认为通过给单个个体不断施加条件，就能用个体的运动模拟出鸟群的整体运动，并针对个体的行为总结出三条原则：

• 分离（Separation）：个体会避开群体拥挤处，以免与其他个体发生碰撞。
• 对齐（Alignment）：个体会朝着周围个体的平均速度矢量方向前进。
• 聚集（Cohesion）：个体会尽量相互靠近，朝着周围个体的中心位置移动。^[1][6][7]

雷诺兹还指出，真实的群行行为依赖于个体局部的世界观，所以在模拟中应当仅给个体提供有限而非全面的信息^[1][2]。

变体

Boids算法在以上三条原则的基础上还可以补充更为复杂的规则，进而产生不同的变体模型，比如使个体自动避开障碍物^[1]，引入使个体产生恐惧的天敌对象^[8]或使个体跟随的领导者对象等^[9]。作为群体智能领域的开创性研究，Boids算法也启发了后续一系列算法研究，包括粒子群优化（PSO）^[10]、蚁群算法（ACO）^[11]等。

需要注意的是，Boids并非最早的群行行为模拟算法，日本研究者青木一郎于1982年对鱼群行为进行了模拟研究，并提出类似模型^[12]。

应用

克雷格·雷诺兹于1986年使用自己和同事在Symbolics开发的一款图形软件工具编写了Boids算法的初代版本，之后该算法被广泛应用于计算机图形领域和电影特效等的制作中^[3][13]。1987年Symbolics制作的动画《Stanley and Stella in: Breaking the Ice（英语：Stanley and Stella in: Breaking the Ice）》中首次使用了该算法，这部动画旨在宣传公司的产品和Boids算法。首次应用该算法的商业电影是蒂姆·伯顿的《蝙蝠侠归来》（1992年），电影中蝙蝠群和企鹅群场景是使用雷诺兹开发的Boids软件的修改版本制作的^[3][14]。类似Boids的算法也被用于《狮子王》（1994年）、《星球大战》系列、《指环王》三部曲、《泰坦尼克号》（1997年）等电影中^[15]。1998年，雷诺兹因“对电影制作中三维计算机动画的发展作出的开创性贡献”获得奥斯卡科技成果奖^[3][16]。

除电影制作外，类似Boids的算法也被应用于电子游戏制作^[17]、人群模拟^[18]、集群机器人（英语：Swarm robotics）^[19]和无人机（UAV）^[20]等领域。

参见

• 群体智能
• 人工生命
• 粒子群优化
• 进化算法
• 蚁群算法
• 蜂群算法（英语：Bees algorithm）