# 十、兽群、鸟群和交通堵塞 > 原文：[Chapter 10 Herds, Flocks, and Traffic Jams](http://greenteapress.com/complexity2/html/thinkcomplexity2011.html) > 译者：[飞龙](https://github.com/wizardforcel) > 协议：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻译](https://translate.google.cn/) 本章的代码位于`chap10.ipynb`中，它是本书仓库中的 Jupyter 笔记本。使用此代码的更多信息，请参见第？节。 ## 10.1 交通堵塞 是什么导致交通堵塞？在某些情况下，有明显的原因，如事故，车速监视或其他干扰交通的事情。 但其他时候，交通堵塞似乎没有明显的原因。 基于智能体的模型有助于解释自发性交通拥堵。 例如，我根据 Resnick，海龟，白蚁和交通堵塞模型实现了一个简单的高速路模拟。 这是代表“高速路”的类： ```py 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`方法简单；它只是移动每个驾驶员： ```py def step(self): for driver in self.drivers: self.move(driver) ``` 这里是`move `方法： ```py 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 += speed ``` `d`是驾驶员与前方驾驶员之间的距离。 这个距离被传递给`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`类的定义： ```py class Driver: def __init__(self, loc, speed=0): self.loc = loc self.speed = speed def choose_acceleration(self, d): return 1 ``` `loc`和`speed `属性是驾驶员的位置和速度。 `choose_acceleration`的这个实现非常简单：它总是以最大速率加速。 由于汽车起步距离相等，因此我们预计它们都会加速，直到达到限速，或者直到它们的速度超过它们之间的距离。 此时，至少会发生一次“碰撞”，导致一些汽车停下来。 ![](img/10-1.png) 图 10.1：三个时间点中，环形公路上的驾驶员的模拟。 点表示驾驶员的位置；十字表示驾驶员必须刹车来避开另一个驾驶员。 图？展示了该过程中的几个步骤，从 30 辆汽车和`eps = 0.02`开始。 左边是 16 个时间步后的状态，汽车排列成一圈。 由于随机噪音，有些汽车比其他汽车要快，并且间距变得不均匀。 在下一个时间步骤（中），两辆车相撞，用`x`标记表示。 在下一个时间步骤（右），两辆汽车会与已停车的汽车碰撞，我们可以看到最初形成的交通堵塞。 一旦堵塞形成，它就会持续下去，其它汽车从后面靠近并碰撞，而前面的汽车加速离开。 在某些情况下，堵塞本身会向后传播，如果你观看本章的笔记本中的动画，你可以看到它。 ## 10.2 随机噪声 ![](img/10-2.png) 图 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），描述了一个基于智能体的兽群行为模型。 你可以从 下载他的论文。 这种模型中的智能体被称为“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： ```py 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 boids ``` `get_neighbors`使用向量减法来计算从`self`到`other`的向量。 这个向量的们是到另一个 boid 的距离。 `diff_angle`计算`self`的速度（也是视线）与另一个 boid 之间的角度。 `center`寻找视野中 boid 的质心，并返回一个指向它的向量： ```py 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`计算这些目标的加权总和并设定总体目标： ```py 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 的速度，位置和姿势。 ```py 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（我在第？节中推荐过），你可以执行： ``` conda install -c vpython vpython ``` 然后运行本书仓库中的`Boids7.py`。 阅读代码来查看，程序开始时定义的参数如何控制 boid 的行为。 试验不同的参数。 如果通过将权重设置为 0 来“关闭”其中一种行为，会发生什么？ 为了生成更多类似鸟类的行为，Flake 建议增加第四种行为来保持清晰的视线；换句话说，如果在正前方有另一只鸟，那么它就应该从侧面移开。 你认为这个规则对鸟群的行为有什么影响？ 实现它来看看。 练习 3 在 上深入了解自由意志。 自由意志与决定论相容的观点被称为相容论。 相容论最大的挑战之一是“结果论证”（consequence argument）。 什么是结果论证？ 根据你在本书中读到的内容，你对结果论证有什么样的反应？