十、兽群、鸟群和交通堵塞
原文：Chapter 10 Herds, Flocks, and Traffic Jams 译者：飞龙 协议：CC BY-NC-SA 4.0 自豪地采用谷歌翻译
本章的代码位于chap10.ipynb中，它是本书仓库中的 Jupyter 笔记本。使用此代码的更多信息，请参见第？节。
10.1 交通堵塞
是什么导致交通堵塞？在某些情况下，有明显的原因，如事故，车速监视或其他干扰交通的事情。 但其他时候，交通堵塞似乎没有明显的原因。
基于智能体的模型有助于解释自发性交通拥堵。 例如，我根据 Resnick，海龟，白蚁和交通堵塞模型实现了一个简单的高速路模拟。
这是代表“高速路”的类：
代码语言：javascript复制class Highway:
def __init__(self, n=10, length=1000, eps=0):
self.length = length
self.eps = eps
# create the drivers
locs = np.linspace(0, length, n, endpoint=False)
self.drivers = [Driver(loc) for loc in locs]
# and link them up
for i in range(n):
j = (i 1) % n
self.drivers[i].next = self.drivers[j]n是汽车的数量。
length是高速路的长度，默认为 1000（以任意单位）。
eps是我们将添加到系统中的随机噪声。
loc包含驾驶员的位置；最初它们沿着高速公路等距分布。
驾驶员由Driver对象表示。 每个驾驶员都包含前方驾驶员的引用。 高速公路是圆形的，所以最后的驾驶员可以引用第一个。
step方法简单；它只是移动每个驾驶员：
def step(self):
for driver in self.drivers:
self.move(driver)这里是move方法：
def move(self, driver):
d = self.distance(driver)
# let the driver choose acceleration
acc = driver.choose_acceleration(d)
acc = min(acc, self.max_acc)
acc = max(acc, self.min_acc)
speed = driver.speed acc
# add random noise to speed
speed *= np.random.uniform(1-self.eps, 1 self.eps)
# keep it nonnegative and under the speed limit
speed = max(speed, 0)
speed = min(speed, self.speed_limit)
# if current speed would collide, stop
if speed > d:
speed = 0
# update speed and loc
driver.speed = speed
driver.loc = speedd是驾驶员与前方驾驶员之间的距离。 这个距离被传递给choose_acceleration，它规定了驾驶员的行为。 这是司机做出的唯一决定; 其他一切都由模拟的“物理”决定。
acc是加速度，它受min_acc和max_acc限制。 在我的实现中，汽车可以在max_acc = 1时加速，在min_acc = -10时加速。speed是旧的速度加上请求的加速度，但是我们做了一些调整。 首先，我们向速度添加了随机噪音，因为这个世界并不完美。eps决定了噪音的幅度，这是适用于速度的百分比; 例如，如果eps为 0.02，则速度乘以 98% 到 102% 之间的随机数。- 然后速度限制在 0 到
speed_limit之间，在我的实现中为 40，所以汽车不允许后退或加速。 - 如果请求的速度会引起与下一辆车的碰撞，则速度设置为 0。
- 最后，我们更新驾驶员的速度和
loc属性。
以下是Driver类的定义：
class Driver:
def __init__(self, loc, speed=0):
self.loc = loc
self.speed = speed
def choose_acceleration(self, d):
return 1loc和speed属性是驾驶员的位置和速度。
choose_acceleration的这个实现非常简单：它总是以最大速率加速。
由于汽车起步距离相等，因此我们预计它们都会加速，直到达到限速，或者直到它们的速度超过它们之间的距离。 此时，至少会发生一次“碰撞”，导致一些汽车停下来。
图 10.1：三个时间点中，环形公路上的驾驶员的模拟。 点表示驾驶员的位置；十字表示驾驶员必须刹车来避开另一个驾驶员。
图？展示了该过程中的几个步骤，从 30 辆汽车和eps = 0.02开始。 左边是 16 个时间步后的状态，汽车排列成一圈。 由于随机噪音，有些汽车比其他汽车要快，并且间距变得不均匀。
在下一个时间步骤（中），两辆车相撞，用x标记表示。
在下一个时间步骤（右），两辆汽车会与已停车的汽车碰撞，我们可以看到最初形成的交通堵塞。 一旦堵塞形成，它就会持续下去，其它汽车从后面靠近并碰撞，而前面的汽车加速离开。
在某些情况下，堵塞本身会向后传播，如果你观看本章的笔记本中的动画，你可以看到它。
10.2 随机噪声
图 10.2：平均速度和汽车数量的函数，带有三个大小的附加随机噪声
随着汽车数量的增加，交通堵塞变得更加严重。 图？显示了汽车能够达到的平均速度，相对于汽车数量的函数。
最上面那行显示eps = 0的结果；也就是说，速度没有随机变化。 如果汽车数量少于 25 辆，则汽车之间的间隔大于 40，这样汽车可以达到并保持 40 的最大速度。超过 25 辆汽车形成交通堵塞，平均速度迅速下降。
这种效果是仿真物理学的直接结果，所以它不应该令人惊讶。 如果道路的长度为 1000，则n个车辆之间的间距为1000 / n。 而且由于汽车的行驶速度不超过前面的空间，所以我们预计，最高平均车速为1000 / n或 40，取最小者。
但这是最好的情况。只有少量的随机性，情况会变得更糟。
图？也显示了eps = 0.001和eps = 0.01的结果，其对应于 0.1% 和 1% 的速度误差。
即使有少量噪音，高速路的容量也会从 25 降至 20（“容量”是指可以达到并保持速度限制的最大车辆数量。 如果有 1% 的误差，容量会下降到 10。
作为本章结尾的练习之一，你将有机会设计出更好的驾驶员; 也就是说，你将在choose_acceleration中尝试不同的策略，并查看你是否可以找到可提高平均速度的驾驶行为。
10.3 Boids
1987 年，Craig Reynolds 发表了《兽群，鸟群和鱼群：分布式行为模型》（Flocks, herds and schools: A distributed behavioral model），描述了一个基于智能体的兽群行为模型。 你可以从 http://www.red3d.com/cwr/papers/1987/boids.html 下载他的论文。
这种模型中的智能体被称为“boids”，既是“bird-oid”的缩写，又是“bird”的口音发音（虽然 boids 也用于模拟鱼类和集中的陆生动物）。
每个智能体模拟了三种行为：
避免碰撞：
避开障碍物，包括其他鸟类。
鸟群集中：
移向鸟群的中心。
速度匹配：
将速度（速率和方向）与邻近的鸟类对齐。
Boid 只根据局部信息做出决定；每个 boid 只能看到（或注意）其视野范围内的其他 boid。
在本书的仓库中，你会发现Boids7.py，它包含我的 boids 实现，部分基于《Flake, The Computational Beauty of Nature》（雪花：自然的计算之美）中的描述。
该程序定义了两个类：Boid，实现了 boid 算法，和World，包含Boid列表和吸引Boid的“胡萝卜”列表。
boid 算法使用get_neighbors在视野中查找其他 boid：
def get_neighbors(self, others, radius, angle):
boids = []
for other in others:
if other is self:
continue
offset = other.pos - self.pos
# if not in range, skip it
if offset.mag > radius:
continue
# if not within viewing angle, skip it
if self.vel.diff_angle(offset) > angle:
continue
# otherwise add it to the list
boids.append(other)
return boidsget_neighbors使用向量减法来计算从self到other的向量。 这个向量的们是到另一个 boid 的距离。 diff_angle计算self的速度（也是视线）与另一个 boid 之间的角度。
center寻找视野中 boid 的质心，并返回一个指向它的向量：
def center(self, others):
close = self.get_neighbors(others, r_center, a_center)
t = [other.pos for other in close]
if t:
center = sum(t)/len(t)
toward = vector(center - self.pos)
return limit_vector(toward)
else:
return null_vector同样，avoid寻找范围内任何障碍物的质心，并返回一个指向它的向量，copy将返回当前朝向和邻居的平均朝向之间的差，love计算出胡萝卜的朝向。
set_goal计算这些目标的加权总和并设定总体目标：
def set_goal(self, boids, carrot):
self.goal = (w_avoid * self.avoid(boids, carrot)
w_center * self.center(boids)
w_copy * self.copy(boids)
w_love * self.love(carrot))最后move更新 boid 的速度，位置和姿势。
def move(self, mu=0.1):
self.vel = (1-mu) * self.vel mu * self.goal
self.vel.mag = 1
self.pos = dt * self.vel
self.axis = b_length * self.vel.norm()新速度是旧速度和目标的加权和。 参数mu决定鸟类能够多快地改变速度和方向。 时间步长dt决定了 boids 移动的距离。
许多参数影响鸟群行为，包括每个行为的范围，角度和权重以及可操作性mu。
这些参数决定了 boids 形成和维持鸟群的能力，以及鸟群中运动和组织的模式。 对于某些设置，boids 类似于一群鸟；其他设置类似于鱼群或一片飞虫。
10.4 涌现和自由意志
作为一个整体，许多复杂的系统具有它们的组件不具有的属性：
- 细胞自动机规则 30 是确定性的，控制其演化的规则是完全已知的。 尽管如此，它会生成一个序列，统计上与随机无法区分。
- 谢林模型中的智能体不是种族主义者，但他们互动的结果就好像他们是。
- 糖域中的智能体形成对角移动的波浪，尽管智能体不能。
- 即使汽车正在向前行驶，交通堵塞会向后移动。
- 兽群和鸟群的行为来自其成员之间的局部互动。
这些例子提出了一个途径，用于解决几个古老而富有挑战性的问题，包括意识和自由意志的问题。
自由意志是做出选择的能力，但是如果我们的身体和大脑受到确定性物理规律的支配，我们的选择就会是确定的。 自由意志的争论无数；我只会提到两个：
- 威廉·詹姆斯（William James）提出了一个两阶段模型，其中可能的行为由随机过程产生，然后由确定性过程选择。 在这种情况下，我们的行为基本上是不可预测的，因为生成它们的过程包含随机元素。
- 大卫休谟（David Hume）认为，我们对于做出选择的感知是一种幻觉；在这种情况下，我们的行为是确定性的，因为产生它们的系统是确定性的。
这些论点以相反的方式调解冲突，但他们同意冲突是存在的：如果这些部分是确定性的，那么系统就不会有自由意志。
本书中的复杂系统提出了另一种选择，在选择和决策层面的自由意志，相当于神经元层面的（或更低层次）的决定论。 就像汽车向前行驶时，交通堵塞后退的方式一样，即使神经元没有，人也可以有自由意志。
10.5 练习
练习 1
在交通堵塞的模拟中，定义一个类，BetterDriver，它继承Driver并覆盖choose_acceleration。 查看你是否可以定义一个驾驶规则，比Driver中的基本实现更好的。 你可能会尝试到达更高的平均速度，或者更少的碰撞。
练习 2
注意：为了做这个练习，你必须安装 VPython，一个用于 3D 显示和动画的库。 如果你使用 Anaconda（我在第？节中推荐过），你可以执行：
代码语言：javascript复制conda install -c vpython vpython然后运行本书仓库中的Boids7.py。 阅读代码来查看，程序开始时定义的参数如何控制 boid 的行为。 试验不同的参数。 如果通过将权重设置为 0 来“关闭”其中一种行为，会发生什么？
为了生成更多类似鸟类的行为，Flake 建议增加第四种行为来保持清晰的视线；换句话说，如果在正前方有另一只鸟，那么它就应该从侧面移开。 你认为这个规则对鸟群的行为有什么影响？ 实现它来看看。
练习 3
在 http://en.wikipedia.org/wiki/Free_will 上深入了解自由意志。 自由意志与决定论相容的观点被称为相容论。 相容论最大的挑战之一是“结果论证”（consequence argument）。 什么是结果论证？ 根据你在本书中读到的内容，你对结果论证有什么样的反应？
