866
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
已移除至鸟群算法的重定向
#重定向 [[鸟群算法]]
{{#seo:
|keywords=鸟群算法,Craig Reynolds,计算机图形
|description=涌现,分离,对齐,靠近
}}
'''<font color="#ff8000">鸟群算法（ Boids）</font>'''是模拟鸟类群集行为的人工生命项目，由'''克雷格·雷诺兹 Craig Reynolds'''于1986年开发。该模型常用于计算机动画或计算机辅助设计的计算机三维几何。他关于这个主题的论文发表在1987年的 ACM SIGGRAPH（美国计算机协会计算机图形专业组组织的计算机图形学顶级年度会议）会议记录上。<ref>{{Cite book | last1=Reynolds| first1=Craig| title=Flocks, herds and schools: A distributed behavioral model.| year=1987 |journal=SIGGRAPH '87: Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques| publisher=Association for Computing Machinery | pages=25–34| isbn=978-0-89791-227-3| doi=10.1145/37401.37406| citeseerx=10.1.1.103.7187}}</ref>“ boid”是“ bird-oid object”的缩写，指一个类鸟对象。<ref>{{Cite journal| last1=Banks| first1=Alec| last2=Vincent| first2=Jonathan| last3=Anyakoha| first3=Chukwudi | title=A review of particle swarm optimization. Part I: background and development|date=July 2007| journal=Natural Computing| volume=6| issue=4| pages=467–484| doi=10.1007/s11047-007-9049-5| citeseerx=10.1.1.605.5879}}</ref>恰巧，“boid”也是纽约都市方言中“bird”的发音。
==算法介绍==
[[File:Rule_separation.gif|thumb|200px|分离]]
[[File:Rule_cohesion.gif|thumb|200px|对齐]]
[[File:Rule_alignment.gif|thumb|200px|靠近]]
与大多数人工生命模拟一样，Boids 是[[涌现]]行为的一个例子; 也就是说，Boids 的复杂性来自于遵循一系列简单规则'''个体 agents'''（这里是 Boids）的相互作用。在最简单的Boids世界中适用的规则如下，其描述了鸟群中的个体如何根据周边同伴的位置和速度移动:
* '''<font color="#ff8000">分离 Separation</font>''': 移动以避开群体拥挤处
* '''<font color="#ff8000">对齐 Alignment</font>''': 朝着周围同伴的平均方向前进
* '''<font color="#ff8000">靠近 Cohesion</font>''': 朝着周围同伴的平均位置（质心）移动
每个 boid 个体都可以得知整体的几何参数，但群体要求其只对其周围某个小邻近范围作出反应。该邻近范围由一个距离（从该个体的中心算起）和一个角度（从其飞行方向算起）决定。此范围外的同伴不予考虑。该临近范围可以认为是一个有限知觉的模型（就像浑水中的鱼一样）；但更恰当的想法可能是，其定义了鸟群影响了个体转向的区域范围。
当然也可以添加更复杂的规则，如避障和寻找目标。
该基本模型自Reynolds提出以来，已用多种方法扩展。例如，Delgado-Mata <ref>{{cite journal|first1= Carlos | last1= Delgado-Mata|first2= Jesus Ibanez | last2= Martinez|first3= Simon | last3= Bee|first4= Rocio | last4= Ruiz-Rodarte|first5= Ruth | last5= Aylett|title= On the use of Virtual Animals with Artificial Fear in Virtual Environments
|journal= New Generation Computing|volume=25 |issue=2 |pages= 145–169|date=2007|doi= 10.1007/s00354-007-0009-5}}</ref>等人扩展基本模型以加入恐惧的影响。因为动物之间靠嗅觉来传递情感，所以他利用一种可自由膨胀气体中的粒子来模拟信息素。'''哈特曼 Hartman'''和'''贝内斯 Benes'''<ref>{{cite journal|first1= Christopher | last1= Hartman|first1= Christopher | last1= Hartman|first2= Bedr̆ich |last2= Benes̆|title= Autonomous boids|journal= Computer Animation and Virtual Worlds|volume=17 |issue=3–4 |pages= 199–206|date=July 2006|doi= 10.1002/cav.123}}</ref>我们为这种结盟引入了互补的力量，称之为领导力更替。这个力决定了这个鸟成为领导者或者试图逃脱群体的概率。
Boids 的运动可以表现为混乱（分裂的群体和狂野的行为）或有序。意想不到的行为比如群体分散和避开障碍后的集聚，可以被认为是涌现的。
Boids 框架通常用于计算机图形学，提供鸟群和其他生物（如鱼群）的逼真表现。例如，在1998年的电子游戏《'''半条命 Half-Life'''》中，游戏结束时Xen中出现的类似鸟类的飞行生物就使用了该框架（游戏文件中命名为“ boid”）。
Boids 模型可用于'''<font color="#ff8000">[[集群机器人]] Swarm Robotics</font>'''中简单的无人地面车辆（UGV）<ref>{{cite conference |title= Design and analysis of Group Escape Behavior for distributed autonomous mobile robots |first1= Hongkyu |last1= Min |first2= Zhidong |last2= Wang |year= 2011 |conference= IEEE International Conference on Robotics and Automation (ICRA)|doi= 10.1109/ICRA.2011.5980123 }}</ref> 或'''<font color="#ff8000">微型飞行器 Micro Aerial Vehicles</font>'''（MAV）<ref>{{cite conference |title= Swarms of micro aerial vehicles stabilized under a visual relative localization |first1= Martin |last1= Saska |first2= Vakula |last2= Jan |first3= Preucil |last3= Libor |year= 2014 |conference= IEEE International Conference on Robotics and Automation (ICRA)|doi= 10.1109/ICRA.2014.6907374 }}</ref>群体的直接控制和稳定。为了异质 UAV-UGV 群体的稳定性，Saska 等人将该模型用于板载相对定位。<ref>{{cite conference |title= Coordination and Navigation of Heterogeneous UAVs-UGVs Teams Localized by a Hawk-Eye Approach |first1= Martin |last1= Saska |first2= Vonasek |last2= Vojtech |first3= Krajnik |last3= Tomas |first4= Preucil |last4= Libor |year= 2012 |conference= IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)|url=http://labe.felk.cvut.cz/~tkrajnik/ardrone/articles/formace.pdf}}</ref>
在当时提出时，Reynolds的方法相比于传统的计算机动画电影技术是一个巨大的进步。第一部利用了此模型的动画片是《'''史丹利和史黛拉: 破冰 Stanley and Stella in: Breaking The Ice'''》（1987），之后是'''蒂姆·伯顿 Tim Burton'''的故事片《'''蝙蝠侠归来 Batman Returns'''》（1992），电脑合成的蝙蝠群和成群的企鹅行进穿过'''哥谭市 Gotham City'''的街道。<ref>{{cite journal | url=http://lrss.fri.uni-lj.si/people/ilbajec/papers/ilb_ab09.pdf | last1=Lebar Bajec |first1= Iztok |first2= Frank H. |last2= Heppner | date=2009 | title=Organized flight in birds | journal=Animal Behaviour | volume = 78 | issue = 4 | pages = 777–789 | doi = 10.1016/j.anbehav.2009.07.007 }}</ref>
Boids 模型已经被用于其他有趣应用。该系统已应用于互联网多频道广播电台的自动节目编排，它也被用于可视化信息和优化任务。<ref>{{cite conference| title= DJ-boids: emergent collective behavior as multichannel radio station programming| first1 = Jesús | last1 = Ibáñez| first2 = Antonio F. | last2 = Gómez-Skarmeta| first3 = Josep | last3 = Blat| date = 2003| booktitle = Proceedings of the 8th international conference on Intelligent User Interfaces| pages = 248–250| doi= 10.1145/604045.604089}}</ref>以及可视化信息<ref>{{cite conference| title= Time-Varying Data Visualization Using Information Flocking Boids| last = Moere | first = A V| date= 2004| booktitle = Proceedings of the IEEE Symposium on Information Visualization| pages= 97–104| doi= 10.1109/INFVIS.2004.65}}</ref>和优化任务。<ref>{{cite journal|first1 = Zhihua | last1 = Cui|first2 = Zhongzhi | last2 = Shi|title= Boid particle swarm optimisation|journal= International Journal of Innovative Computing and Applications|volume=2 |issue=2 |pages= 77–85|date=2009|doi= 10.1504/IJICA.2009.031778}}</ref>
==代码实现==
以下内容是使用BOIDS三层模型对鸟群运动进行了模拟，可以通过调节不同的参数获取到不同的实验现象，可以在这个基础上修改模型规则，以更好的模拟集群运动，本文提供一个模板。代码来源是[https://www.cnblogs.com/zhangqifire/p/6621441.html 沐雨橙风fire]所写的博客。
<source lang="python">
# -*- coding:utf-8 -*-
import argparse
import math
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from scipy.spatial.distance import squareform, pdist
from numpy.linalg import norm
width, height = 1920, 1080
N = 100 # number of birds
minDist = 100.0 # min dist of approach
maxRuleVel = 0.3 # max magnitude of velocities calculated by "rules"
maxVel = 3.0 # max magnitude of final velocity
class Birds:
"""
Simulates flock behaviour of birds, using the realistic-looking Boids model (1986)
"""
def __init__(self):
self.N = N
self.minDist = minDist
self.maxRuleVel = maxRuleVel
self.maxVel = maxVel
# Computing initial position and velocity
self.pos = [width / 2.0, height / 2.0] + 10 * np.random.rand(2 * N).reshape(N, 2)
# Create an array of N random variable angles in the range [0. 2pi]
angles = 2 * math.pi * np.random.rand(N)
# Random velocity vector [x,y] coordinates zip grouped
self.vel = np.array(list(zip(np.sin(angles), np.cos(angles))))
def savef(self):
with open("douban.txt", "a") as f:
f.write(str(self.pos.reshape(1, N*2)))
print str(self.pos.reshape(1, N*2))
f.close()
def tick(self, frameNum, pts, beak):
"""
Update the simulation by one time step
"""
# get pairwise distances
self.distMatrix = squareform(pdist(self.pos))
# apply rules:
self.vel += self.apply_rules()
self.limit(self.vel, self.maxVel)
self.pos += self.vel
self.apply_bc()
# update data
pts.set_data(self.pos.reshape(2 * self.N)[::2],
self.pos.reshape(2 * self.N)[1::2])
vec = self.pos + 10 * self.vel / self.maxVel
beak.set_data(vec.reshape(2 * self.N)[::2],
vec.reshape(2 * self.N)[1::2])
self.savef()
#print self.pos.reshape(2 * self.N)
#np.savetxt("x.txt", self.pos.reshape(1, 2*N))
def limit_vec(self, vec, max_val):
""" Limit magnitude of 2D vector """
mag = norm(vec)
if mag > max_val:
vec[0], vec[1] = vec[0] * max_val / mag, vec[1] * max_val / mag
def limit(self, x, max_val):
""" Limit magnitide of 2D vectors in array X to maxValue """
for vec in x:
self.limit_vec(vec, max_val)
def apply_bc(self):
""" Apply boundary conditions """
deltaR = 2.0
for coord in self.pos:
if coord[0] > width + deltaR:
coord[0] = - deltaR
if coord[0] < - deltaR:
coord[0] = width + deltaR
if coord[1] > height + deltaR:
coord[1] = - deltaR
if coord[1] < - deltaR:
coord[1] = height + deltaR
def apply_rules(self):
# apply rule #1 - Separation
D = self.distMatrix < 20.0
vel = self.pos * D.sum(axis=1).reshape(self.N, 1) - D.dot(self.pos)
self.limit(vel, self.maxRuleVel)
# different distance threshold
D = self.distMatrix < 50.0
# apply rule #2 - Alignment
vel2 = D.dot(self.vel)
self.limit(vel2, self.maxRuleVel)
vel += vel2
# apply rule #1 - Cohesion
vel3 = D.dot(self.pos) - self.pos
self.limit(vel3, self.maxRuleVel)
vel += vel3
return vel
def tick(frameNum, pts, beak, birds):
""" Update function for animation """
birds.tick(frameNum, pts, beak)
return pts, beak
def main():
print('Starting flock simulation...')
# Create birds
birds = Birds()
# Setup plot
fig = plt.figure()
ax = plt.axes(xlim=(0, width), ylim=(0, height))
pts, = ax.plot([], [], markersize=10, c='k', marker='o', ls='None')
beak, = ax.plot([], [], markersize=4, c='r', marker='o', ls='None')
anim = animation.FuncAnimation(fig, tick, fargs=(pts, beak, birds), interval=20)
# TODO: add a "button press" event handler to scatter birds
#anim.save('basic_animation.mp4', fps=30, extra_args=['-vcodec', 'libx264'])
plt.show(anim)
if __name__ == '__main__':
main()
</source>
==参见==
*[[群体智能]] Swarm intelligence
*[[粒子群优化算法]]
*[[集群机器人]]
==参考文献==
{{Reflist}}
==外部链接==
* [http://www.red3d.com/cwr/boids/ Craig Reynolds' Boids page]
* [http://www.vergenet.net/~conrad/boids/pseudocode.html Explanation of algorithm in pseudocode]
* [https://gpolo.github.com/birdflocking JavaScript implementation]
* [https://lufemas.github.io/boid-ai-implementation/ JavaScript implementation with Phaser Framework]
* [https://web.archive.org/web/20080205014305/http://www.navgen.com/3d_boids/ 3D Boids Simulation using OpenGL, used by the BBC's Natural History Unit]
* [https://black-square.github.io/BirdFlock/ Live In-Browser 3D Simulation of Bird Flocking Behavior in Unity3D] – Open Source implementation for Windows, Linux and Mac
* [https://github.com/piskvorky/PredatorPrey UNIX+Windows open source implementation in C++, using OpenGL and simulation controls]
* [https://github.com/tofti/javafx-boids A java implementation using the javafx API]
==编者推荐==
===集智相关课程===
[[File:Auklet_flock_Shumagins_1986.jpg|300px|thumb|[https://swarma.org/?p=16504 张江：乌合之众还是群智涌现？鸟群知道答案]]]
====[https://campus.swarma.org/course/1104 透过人工鸟群Boid模型学习List的使用]====
讲师：[[张江]](北师大系统科学学院教授、博士生导师，集智俱乐部、集智学园创始人。)
本课程通过数个案例教会大家如何去动手搭建一个多主体仿真模型，以及如何利用NetLogo去实现。从生命游戏到人工鸟群，从模拟经济系统到病毒沿网络的传播，通过循序渐进的案例，该课程带你逐步走入NetLogo多主体建模的神奇世界。
===集智相关文章===
====[https://swarma.org/?p=16504 张江：乌合之众还是群智涌现？鸟群知道答案]====
生命如何起源，智能如何涌现，因果如何反转，复杂谜题，引人深思。2019年7月13日，集智俱乐部创始人[[张江]]教授在混沌大学授课，详细解读了复杂系统中的混沌、涌现与进化，此文整理自课堂内容。
===其他===
====[https://v.qq.com/x/page/z13491sn7fy.html 动画片《Stanley and Stella in: Breaking the Ice (1987)》]====
Craig Reynolds 与 Symbolics Graphics 和 Whitney / Demos Production 的同事合作制作的利用 boids 模型的小短片，讲述了飞鸟与鱼相爱，鸟儿冲破冰面与鱼相见的故事。影片最早于87年在 SIGGRAPH 电子剧院展出。
----
本中文词条由[[用户:Dorr|Dorr]]参与编译，[[用户:木子二月鸟|木子二月鸟]]审校，[[用户:薄荷|薄荷]]编辑，欢迎在讨论页面留言。
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
[[Category:人工生命]]
[[Category:1986软件]]