十, 兽群, 鸟群和交通堵塞
译者: 飞龙 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, 海龟, 白蚁和交通堵塞模型实现了一个简单的高速路模拟.
这是代表 "高速路" 的类:
- 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 的这个实现非常简单: 它总是以最大速率加速.
由于汽车起步距离相等, 因此我们预计它们都会加速, 直到达到限速, 或者直到它们的速度超过它们之间的距离. 此时, 至少会发生一次 "碰撞", 导致一些汽车停下来.
image
图 10.1: 三个时间点中, 环形公路上的驾驶员的模拟. 点表示驾驶员的位置; 十字表示驾驶员必须刹车来避开另一个驾驶员.
图? 展示了该过程中的几个步骤, 从 30 辆汽车和 eps = 0.02 开始. 左边是 16 个时间步后的状态, 汽车排列成一圈. 由于随机噪音, 有些汽车比其他汽车要快, 并且间距变得不均匀.
在下一个时间步骤(中), 两辆车相撞, 用 x 标记表示.
在下一个时间步骤(右), 两辆汽车会与已停车的汽车碰撞, 我们可以看到最初形成的交通堵塞. 一旦堵塞形成, 它就会持续下去, 其它汽车从后面靠近并碰撞, 而前面的汽车加速离开.
在某些情况下, 堵塞本身会向后传播, 如果你观看本章的笔记本中的动画, 你可以看到它.
10.2 随机噪声
image
图 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). 什么是结果论证? 根据你在本书中读到的内容, 你对结果论证有什么样的反应?
来源: http://www.jianshu.com/p/3c4432bcb342