十、兽群、鸟群和交通堵塞

十、兽群、鸟群和交通堵塞

原文：Chapter 10 Herds, Flocks, and Traffic Jams

译者：飞龙

协议：CC BY-NC-SA 4.0

自豪地采用谷歌翻译

本章的代码位于chap10.ipynb中，它是本书仓库中的 Jupyter 笔记本。使用此代码的更多信息，请参见第？节。

10.1 交通堵塞

是什么导致交通堵塞？在某些情况下，有明显的原因，如事故，车速监视或其他干扰交通的事情。但其他时候，交通堵塞似乎没有明显的原因。

基于智能体的模型有助于解释自发性交通拥堵。例如，我根据 Resnick，海龟，白蚁和交通堵塞模型实现了一个简单的高速路模拟。

这是代表“高速路”的类：

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 += 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类的定义：

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的这个实现非常简单：它总是以最大速率加速。

由于汽车起步距离相等，因此我们预计它们都会加速，直到达到限速，或者直到它们的速度超过它们之间的距离。此时，至少会发生一次“碰撞”，导致一些汽车停下来。

图 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 boids

get_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（我在第？节中推荐过），你可以执行：

conda install -c vpython vpython

然后运行本书仓库中的Boids7.py。阅读代码来查看，程序开始时定义的参数如何控制 boid 的行为。试验不同的参数。如果通过将权重设置为 0 来“关闭”其中一种行为，会发生什么？

为了生成更多类似鸟类的行为，Flake 建议增加第四种行为来保持清晰的视线；换句话说，如果在正前方有另一只鸟，那么它就应该从侧面移开。你认为这个规则对鸟群的行为有什么影响？实现它来看看。

练习 3

在 http://en.wikipedia.org/wiki/Free_will 上深入了解自由意志。自由意志与决定论相容的观点被称为相容论。相容论最大的挑战之一是“结果论证”（consequence argument）。什么是结果论证？根据你在本书中读到的内容，你对结果论证有什么样的反应？