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年，雷諾茲因「對電影製作中3D電腦動畫的發展作出的開創性貢獻」獲得奧斯卡科技成果獎^[3][16]。

除電影製作外，類似Boids的算法也被應用於電子遊戲製作^[17]、人群模擬^[18]、集群機器人（英語：Swarm robotics）^[19]和無人機（UAV）^[20]等領域。

參見

• 群體智能
• 人工生命
• 粒子群優化
• 進化算法
• 蟻群算法
• 蜂群算法（英語：Bees algorithm）