什么是鸟群算法 | 集智百科
本词条由集智俱乐部众包生产,难免存在纰漏和问题,欢迎大家留言反馈或者前往对应的百科词条页面进行修改,一经修改,可以获得对应的积分奖励噢!
目录
鸟群算法 Boids是模拟鸟类群集行为的人工生命项目,由克雷格·雷诺兹 Craig Reynolds于1986年开发。该模型常用于计算机动画或计算机辅助设计的计算机三维几何。他关于这个主题的论文发表在1987年的 ACM SIGGRAPH(美国计算机协会计算机图形专业组组织的计算机图形学顶级年度会议)会议记录上。“ boid”是“ bird-oid object”的缩写,指一个类鸟对象。恰巧,“boid”也是纽约都市方言中“bird”的发音。
算法介绍
与大多数人工生命模拟一样,Boids 是涌现行为的一个例子; 也就是说,Boids 的复杂性来自于遵循一系列简单规则个体 agents(这里是 Boids)的相互作用。在最简单的Boids世界中适用的规则如下,其描述了鸟群中的个体如何根据周边同伴的位置和速度移动:
分离 Separation: 移动以避开群体拥挤处
对齐 Alignment: 朝着周围同伴的平均方向前进
靠近 Cohesion: 朝着周围同伴的平均位置(质心)移动
该基本模型自Reynolds提出以来,已用多种方法扩展。例如,Delgado-Mata 等人扩展基本模型以加入恐惧的影响。因为动物之间靠嗅觉来传递情感,所以他利用一种可自由膨胀气体中的粒子来模拟信息素。哈特曼 Hartman和贝内斯 Benes我们为这种结盟引入了互补的力量,称之为领导力更替。这个力决定了这个鸟成为领导者或者试图逃脱群体的概率。
Boids 框架通常用于计算机图形学,提供鸟群和其他生物(如鱼群)的逼真表现。例如,在1998年的电子游戏《半条命 Half-Life》中,游戏结束时Xen中出现的类似鸟类的飞行生物就使用了该框架(游戏文件中命名为“ boid”)。
Boids 模型可用于集群机器人 Swarm Robotics中简单的无人地面车辆(UGV)或微型飞行器 Micro Aerial Vehicles(MAV)群体的直接控制和稳定。为了异质 UAV-UGV 群体的稳定性,Saska 等人将该模型用于板载相对定位。
在当时提出时,Reynolds的方法相比于传统的计算机动画电影技术是一个巨大的进步。第一部利用了此模型的动画片是《史丹利和史黛拉: 破冰 Stanley and Stella in: Breaking The Ice》(1987),之后是蒂姆·伯顿 Tim Burton的故事片《蝙蝠侠归来 Batman Returns》(1992),电脑合成的蝙蝠群和成群的企鹅行进穿过哥谭市 Gotham City的街道。
Boids 模型已经被用于其他有趣应用。该系统已应用于互联网多频道广播电台的自动节目编排,它也被用于可视化信息和优化任务。以及可视化信息和优化任务。
代码实现
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()
编者推荐
透过人工鸟群Boid模型学习List的使用
课程推荐:透过人工鸟群Boid模型学习List的使用
https://campus.swarma.org/course/1104
集智相关文章
其他
动画片《Stanley and Stella in: Breaking the Ice (1987)》
https://v.qq.com/x/page/z13491sn7fy.html
百科项目志愿者招募
作为集智百科项目团队的成员,本文内容由Dorr,木子二月鸟,薄荷参与贡献。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页,更多信息可以访问其集智百科个人主页。
在这里从复杂性知识出发与伙伴同行,同时我们希望有更多志愿者加入这个团队,使百科词条内容得到扩充,并为每位志愿者提供相应奖励与资源,建立个人主页与贡献记录,使其能够继续探索复杂世界。
如果你有意参与更加系统精细的分工,扫描二维码填写报名表,我们期待你的加入!
来源:集智百科
编辑:王建萍
点击“阅读原文”,阅读鸟群算法相关内容与参考文