# 十、獸群、鳥群和交通堵塞 > 原文：[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`的這個實現非常簡單：它總是以最大速率加速。 由于汽車起步距離相等，因此我們預計它們都會加速，直到達到限速，或者直到它們的速度超過它們之間的距離。 此時，至少會發生一次“碰撞”，導致一些汽車停下來。  圖 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： ```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 在 <http://en.wikipedia.org/wiki/Free_will> 上深入了解自由意志。 自由意志與決定論相容的觀點被稱為相容論。 相容論最大的挑戰之一是“結果論證”（consequence argument）。 什么是結果論證？ 根據你在本書中讀到的內容，你對結果論證有什么樣的反應？