預(yù)測考題

1. Agent的定義/特點(diǎn)
2. 元胞自動機(jī)的特點(diǎn)
3. 一維自動機(jī)規(guī)則編碼
4. GA的偽代碼
5. Wolfram 的分類
6. MAS的控制方法以及舉例
7. MAS和平均場的區(qū)別

1 Agent的特點(diǎn)、MAS的概念、特征

agent是一個(gè)計(jì)算單元，是自動的，能夠與其他的agent互動，從環(huán)境中獲取信息，由目標(biāo)或者行為策略驅(qū)動。
MAS是由大量局部相互作用的個(gè)體組成，不借助中央控制，能夠涌現(xiàn)出宏觀現(xiàn)象的系統(tǒng)

2 平均場 VS MAS

模型和模擬的區(qū)別

• 模型是對某種現(xiàn)象/某個(gè)系統(tǒng)的數(shù)學(xué)刻畫
• 模擬是模型的某種實(shí)現(xiàn)，例如計(jì)算機(jī)實(shí)現(xiàn)
  即使模型完全確定，模擬結(jié)果也不一定可預(yù)測分析（即使是非常簡單的模型：the three bidies）

掌握2種對復(fù)雜系統(tǒng)的建模方式（平均場和Agent-based） 捕食-被捕食的Lotka-Volterra方程和MAS建模方法、傳染病模型

• 微分方程建模：平均場方法（粗）
  • 用統(tǒng)一的長程作用代替局部相互作用

  • 所得到的解，是隨時(shí)間演化的空間上的平均

    
    
• MAS建模：基于Agent的建模（細(xì)）

  • 局部相互作用不能被平均掉，必須考慮局部相互作用在不同 空間位置所帶來的不同的效果

    
    
    0->1

傳染病模型

S (for susceptible，易感), I (for infectious，感染), R (for recovered, 免疫)

• SIS
  無法免疫，但能痊愈，反復(fù)得病
• SIR
  一次得病，終身免疫
• SI
  無法恢復(fù)
• SIRS
  能恢復(fù)，有限免疫

平均場建模

3 元胞自動機(jī)

最簡單的MAS模型
特點(diǎn)：

• 離散狀態(tài)、位置、時(shí)間

• 確定的、相同的更新機(jī)制

• 同步更新

  
  

• John von Neumann的機(jī)器自繁衍 (1940s)

• John Conway 的生命游戲 (1970s)
  0->1：周圍恰好3個(gè)
  1->0：周圍不是2或3

• Stephen Wolfram 的分類(1980s)

  1. 靜止（不動點(diǎn)） homogeneous state
  2. 周期性為（極限環(huán)） a set of separated simple stable or periodic structures
  3. 混沌（初始條件敏感性）* chaotic pattern
  4. 帶結(jié)構(gòu)的有序（復(fù)雜性）complex localized structures, sometimes long-lived.

實(shí)際運(yùn)用舉例：

• 用于教室突然安靜

8,9 集體行為

在整體涌現(xiàn)出個(gè)體單獨(dú)存在時(shí)所不具備的行為特征。簡單規(guī)律造就復(fù)雜現(xiàn)象；被分割的部分如何整合，強(qiáng)調(diào)各部分之間的關(guān)聯(lián)

• 自發(fā)行為的分析 自下而上
  給定agent的局部規(guī)則，系統(tǒng)整體涌現(xiàn)出什么行為？ 自組織行為，統(tǒng)計(jì)物理，Vicsek模型的同步性分析
• 局部規(guī)則的設(shè)計(jì) 自上而下
  給定期望的集體行為，如何設(shè)計(jì)agent的局部規(guī)則？ 群體智能（螞蟻算法），分布式控制設(shè)計(jì)
• 干預(yù)
  給定agent的局部規(guī)則，如何干預(yù)系統(tǒng)的集體行為？
  • 軟控制
    • consistent moving shill
    • leader-follower
      往往有少數(shù)個(gè)體帶目標(biāo)信息（方向明確，固定角度的shill），這些個(gè)體可以幫助誘導(dǎo)整個(gè)群體
      鄰居半徑越大– shill 影響范圍更大，但shill 影響強(qiáng)度變?nèi)? 對于集中的leader，方向固定的話，影響半徑越大越好；方向可變的話，半徑越小越好
      優(yōu)點(diǎn)：
      不需要設(shè)計(jì)leader的運(yùn)動規(guī)則
      不需要每個(gè)時(shí)刻都測量群體的信息
      缺點(diǎn)：
      需要的leader數(shù)目較多
      沒有反饋，對噪聲不具有魯棒性
      是在概率框架下同步，不是確定性框架
  • 牽制控制 Pinning control
    通過有選擇地對網(wǎng)絡(luò)中的少部分節(jié)點(diǎn)施加控制而使得整個(gè)網(wǎng)絡(luò)達(dá)到所期望的行為。
    舉例：廣告商花錢請大V轉(zhuǎn)發(fā)宣傳

10 Vicsek模型的同步分析

同步是一種微觀的趨同行為的涌現(xiàn)
Vicsek模型

其中，角度是直接由相鄰角度確定的，不是增量形式改變；自身的角度當(dāng)作相鄰個(gè)體的角度之一。位置的變化是增量形式的。
定理1：在G不變且連通的情況下，任意的初始角度都會演化到同步角度
定理2：G在每一時(shí)刻都保持連通的情況下，任意初始角度都會演化到同步角度
定理3：存在時(shí)間的一個(gè)劃分，G在每個(gè)時(shí)間區(qū)間上都聯(lián)合連通，則對任意角度都會演化到同步角度。其中，聯(lián)合連通是指G的并
確定性框架下的同步研究的是依賴于初始條件和系統(tǒng)參數(shù)的同步條件
隨機(jī)框架下是指所有個(gè)體的位置和角度的隨機(jī)化假設(shè)

相互作用的圖表示：無向圖，結(jié)點(diǎn)帶環(huán)。圖由系統(tǒng)個(gè)體位置決定，反過來，圖也決定系統(tǒng)的動力學(xué)演化，

11 靜態(tài)局部規(guī)則——離散優(yōu)化

難易問題分類

染色問題（The Coloring Problem， NP-complete; Network problem; Combinatorial Optimization）
Effective ≠ Efficient
P : 易處理 tractable problems iff. it can be solved by a Polynomial time algorithm.
NP : intractable problems iff. it can be solved in Polynomial time by an Nondeterministic algorithm (Nondeterministic Turing Machine). 非確定圖靈機(jī)可以對分支情況同時(shí)處理

算法實(shí)現(xiàn)

特殊結(jié)構(gòu)問題

• 貪心算法
  每步都是找一個(gè)當(dāng)前局部最優(yōu)點(diǎn)， 不考慮未來.
• 動態(tài)規(guī)劃 (DP)
  對前面的決策所形成的狀態(tài)而言，余下的諸決 策必須構(gòu)成最優(yōu)策略。簡而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

通用搜索問題

• 回溯 Backtracking
  assign values to variables sequentially .e.g. 前綴搜索prefix searching
  too slow (but complete)
  將解空間進(jìn)行樹狀劃分，從局部確定到完整確定。

• 啟發(fā)式搜索 Heuristic Search
  local search. a possible configuration of all variables, test. Most practical and powerful one, but Incomplete and it is based on intuition and experience.
  從解空間的一個(gè)點(diǎn)出發(fā)，根據(jù)局部信息，到達(dá)認(rèn)為的一個(gè)最解?？梢钥醋魇且粋€(gè)解的演化過程，也是MAS關(guān)注的求解形式?？梢酝瑫r(shí)處理多少個(gè)解： GA遺傳算法, 粒子群優(yōu)化…

  
  
  兩種搜索方式的對比
  
  
  平面比較
  
  

  我們怎樣在解空間進(jìn)行導(dǎo)航？

  
  
  移動時(shí)僅有局部視野
  
  借助評估函數(shù) Evaluation Function
  
  構(gòu)造評價(jià)函數(shù)對解空間進(jìn)行+1維映射 圖片來源：《模式分類》
  
  沒有一個(gè)算法可以在所有的問題實(shí)例中戰(zhàn)勝其它所有的算法（no free lunch 理論）

Local search 在MAS系統(tǒng)問題求解中的體現(xiàn)

local search 優(yōu)點(diǎn): 1. 并行運(yùn)算Parallel Computing 2. 實(shí)際更可行 More feasible in some cases
MAS系統(tǒng)的最優(yōu)解就是納什均衡點(diǎn)Nush Equilibrium: NE is a system state that no single agent can benefit from unilaterally changing his action
Zero sum games (two-person): Maximin strategy (MS) is a solution 對于零和博弈，極大極小是一個(gè)解
?(xi, xj)=1當(dāng)兩個(gè)頂點(diǎn)相連時(shí)等于1否則等于0. 自身認(rèn)為是相連的。

LEF & GEF in coloring problem

把每個(gè)結(jié)點(diǎn)看作一個(gè)agent，agent的狀態(tài)就是顏色，系統(tǒng)演化就是每個(gè)agent接收周圍agent的狀態(tài)，根據(jù)自己的策略，確定自己的狀態(tài)，直到系統(tǒng)演化到解。
模擬退火sumulated annealing, GA, 粒子群優(yōu)化particle swarm optimization 使用的是GEF.
LEF僅使用局部信息，每次僅改變局部狀態(tài)

Consistency between LEF and GEF

Nash Equilibrium and local optimum 如果連接權(quán)重是對稱的話，則兩者等價(jià)
Symmetrical interaction: if gij(xi , xj) = gji(xj , xi) The LEF is consistent with GEF=∑LEF

12 靜態(tài)局部規(guī)則——復(fù)雜網(wǎng)絡(luò)

網(wǎng)絡(luò)是刻畫MAS系統(tǒng)的一種方式

13 網(wǎng)絡(luò)模型概念

• 平均距離L

是所有的頂點(diǎn)之間距離的平均值

L.png

• 聚類系數(shù)C

C.png

• 度分布

分母為總結(jié)點(diǎn)數(shù)/分子為對應(yīng)度結(jié)點(diǎn)的個(gè)數(shù)
環(huán)形網(wǎng)絡(luò)

環(huán)形網(wǎng)絡(luò).png

其中K是每個(gè)頂點(diǎn)的度數(shù)。所有的頂點(diǎn)度數(shù)相等

• 平均度

<k>為度之和（邊數(shù)兩倍）除以頂點(diǎn)數(shù)

• 團(tuán)組

connections are sparse but within which connections are relatively dense.

結(jié)點(diǎn)的層級

第一級：反復(fù)將1度頂點(diǎn)去掉，這些結(jié)點(diǎn)構(gòu)成第一級
第二級：反復(fù)將2度頂點(diǎn)去掉，這些結(jié)點(diǎn)構(gòu)成第二級
...

• motif

各種模式的子圖，構(gòu)成復(fù)雜網(wǎng)絡(luò)的block
不同類型的實(shí)際網(wǎng)絡(luò)，各種motif的分布不同，相當(dāng)于網(wǎng)絡(luò)的特征

• 介數(shù)

在各種社會網(wǎng)絡(luò)中，如（朋友網(wǎng)，合作網(wǎng)，微博等 ），哪些是最活躍、最具影響力的人?在艾滋病傳播中，哪些是最危險(xiǎn)的人？ 在通信網(wǎng)絡(luò)或者交通網(wǎng)絡(luò)中，那些節(jié)點(diǎn)承受的流量 最大？不是只考慮度的大小。

• 核數(shù)

在一個(gè)網(wǎng)絡(luò)中，我們重復(fù)去掉所有度為k的節(jié)點(diǎn)，剩下的子網(wǎng)絡(luò)稱為k-核，被去掉的的節(jié)點(diǎn)及它們之間的邊稱為k-殼。
平均核數(shù)大 -> 對隨機(jī)失效和有意攻擊都具有 魯棒性

14 復(fù)雜網(wǎng)絡(luò)模型

• 隨機(jī)圖ER

每兩個(gè)頂點(diǎn)之間連接的概率為P.
顯然平均度數(shù)<k>=PN 度分布P(k)服從Poisson分布，度基本集中在<k>附近 聚類系數(shù)C=P遠(yuǎn)小于1

• small-world

平均距離L和聚類系數(shù)C隨著隨機(jī)重連概率p的變化規(guī)律

從規(guī)則圖開始：給定一個(gè)含有N個(gè)點(diǎn)的環(huán)狀最近鄰耦合網(wǎng)絡(luò)， 每個(gè)節(jié)點(diǎn)都與它左右相鄰的各K/2個(gè)節(jié)點(diǎn)相連，K為偶數(shù)
隨機(jī)化重連：以概率p隨機(jī)地重新連接網(wǎng)絡(luò)中原有的每條邊(i,j)， 即把每條邊的端點(diǎn)i保持不變，端點(diǎn)j改取為網(wǎng)絡(luò)中隨機(jī)選擇的一個(gè)節(jié)點(diǎn)，其中規(guī)定不得有重邊和自環(huán)。和社交網(wǎng)絡(luò)很相似：小團(tuán)體中存在與其他團(tuán)體連接的人從生成過程來看，SW模型在p很小的時(shí)候，具有規(guī)則圖的特性； 當(dāng)p慢慢增大時(shí)，逐步向隨機(jī)圖的性質(zhì)轉(zhuǎn)變
因?yàn)橹皇请S機(jī)重連，因此平均度不變，為<K>
例子：
食物鏈網(wǎng)絡(luò)、代謝網(wǎng)絡(luò)、學(xué)術(shù)合作網(wǎng)絡(luò)

• scale-free網(wǎng)絡(luò)

power_law.png

scale-free/ Power-Law distribution. 注意：冪律分布不是指數(shù)分布！
所有的scale-free網(wǎng)絡(luò)都具有小世界特性,但不是所有具有小世界特性的網(wǎng)絡(luò)都有 scale-free特性
前面兩個(gè)網(wǎng)絡(luò)都是固定的頂點(diǎn)數(shù)N，而實(shí)際的網(wǎng)絡(luò)都是頂點(diǎn)數(shù)不斷生長的（具備生長特性的實(shí)際網(wǎng)絡(luò)往往滿足scale-free）。（不過增長的網(wǎng)絡(luò)的關(guān)系一般不滿足對稱性）另外一點(diǎn)是，頂點(diǎn)之間連接不是等可能的，而是有偏好的。
網(wǎng)絡(luò)需要結(jié)合生長性和偏好性連接才能得到scale-free網(wǎng)絡(luò): the combination of growth and preferential attachment is utimately reponsible for the scale-free distribution and power-law scaling observed in real networks. 一開始有m_0個(gè)頂點(diǎn)，沒有邊，每一時(shí)刻增加一個(gè)頂點(diǎn)，并從這個(gè)頂點(diǎn)出發(fā)連接m條邊，
冪律的系數(shù)與m^2成比例

隨著m增大，斜率變?。ń^對值）

例子：

• 論文引用網(wǎng)絡(luò)
• WWW萬維網(wǎng)

網(wǎng)絡(luò)算法 PageRank

假設(shè)有一個(gè)網(wǎng)上的隨機(jī)沖浪者，他從一個(gè)隨機(jī)選擇的頁面開始瀏覽。如果當(dāng) 前頁面的出度大于零，那么以概率s(0<s<1)在當(dāng)前頁面上隨機(jī)點(diǎn)擊某個(gè)超文本鏈接而進(jìn)入下一個(gè)頁面，以概率1-s在整個(gè)www上完全隨機(jī)選擇一個(gè)頁面 做為下一個(gè)頁面; 如果當(dāng)前頁面的出度為零，那么完全隨機(jī)地選擇一個(gè)頁面做為下一步瀏覽的頁面。Page和Brin建議取s為0.85.

15 復(fù)雜的相互作用——個(gè)體適應(yīng)性：博弈

分類

• 合作博弈（具有約束力的協(xié)議）與非合作博弈
• 零和博弈與非零和博弈
• 兩人博弈與多人博弈
• 靜態(tài)博弈與動態(tài)博弈
  靜態(tài)博弈指在博弈中，參與人同時(shí)選擇行動，或 雖非同時(shí)但后行動者并不知道前行動者采取了什么 具體行動；動態(tài)博弈指的是參與人的行動有先后順序，且后 行動者能夠觀察到先行動者所選擇的行動的博弈（下棋）
• 完全信息博弈和不完全信息博弈
  完全信息指的是每一個(gè)參與人都知道其他參與人的策略集合 及收益函數(shù)；否則就是不完全信息

石頭剪刀布屬于：兩人博弈、非合作博弈、零和博弈、靜態(tài)博弈、完全信息博弈

囚徒困境

求解（即雙方非采取什么策略）

占優(yōu)策略、剔除劣策略
占優(yōu)策略一定是NE，NE可能存在多個(gè)，可能不存在純策略NE，但一定存在混合策略NE。NE不一定是全局最優(yōu)解

不存在純策略的NE

零和博弈：納什均衡就是極大極小

與或輸搜索：對于當(dāng)前的局面，我可以有N種選擇，只要有一個(gè)能夠通往勝局，則此時(shí)的局面也是勝局，因此是對我的行為導(dǎo)致的局面的OR運(yùn)算；而對方面臨棋局時(shí)，只要有一個(gè)行動能產(chǎn)生我的敗局，則當(dāng)前局面也是我的敗局，因此是對對方所有可能行為導(dǎo)致局面的AND運(yùn)算。所以我的策略是對當(dāng)前局面進(jìn)行一個(gè)OR-AND Tree進(jìn)行搜索：

上述方法需要依靠最終的勝局和敗局來遞推當(dāng)前局面。這個(gè)樹太大了，所以無法得到底布情況，于是在不到底部就需要對那時(shí)的局面進(jìn)行評估：1表示勝局，0表示敗局的話，中間值就是對一個(gè)局面的評價(jià)值，越大表示對我越有利。OR/AND運(yùn)算就轉(zhuǎn)變成呢MAX/MIN運(yùn)算

評價(jià)函數(shù)的設(shè)計(jì)

16 復(fù)雜自適應(yīng)系統(tǒng)——群體自適應(yīng)：群體從進(jìn)化論到遺傳算法

• 拉馬克：每個(gè)生物在生活中被需求驅(qū)動努力獲得的 并且后天獲得性狀可以遺傳
• 達(dá)爾文：進(jìn)化的驅(qū)動力是自然選擇。自然選擇做功：熵減。變異是連續(xù)漸進(jìn)的，性狀會在繁衍中融合。
• 孟德爾：根據(jù)darvin理論，有用的變異會因其擁有者每次生育而減半，而他提出了遺傳單位 (hereditary element)的概念，不存在連續(xù)變化性狀。
  多遺傳單位決定性狀
• 群體遺傳學(xué)：Fisher et.al 將生物統(tǒng)計(jì)學(xué)與孟德爾的顆粒遺傳理論相結(jié)合，重新解釋了達(dá)爾文的自然選擇學(xué)說，形成了群體遺傳學(xué)?，F(xiàn)代綜合進(jìn)化論徹底否定獲得性狀的遺傳，基因突變和重組是進(jìn)化的基礎(chǔ)，強(qiáng)調(diào)進(jìn)化的漸進(jìn)性，認(rèn)為進(jìn)化是群體而不是個(gè)體的現(xiàn)象，并重新肯定了自然選擇的壓倒一切的重要性，大尺度的進(jìn)化(新物種的產(chǎn)生)可以通過微觀尺度上的基因突變和自然選擇來解釋.
• 間斷平衡論: 生物進(jìn)化是漸變和驟變交替出現(xiàn)的過程
• 中性學(xué)說; 在分子層面的進(jìn)化，主導(dǎo)機(jī)制是變異和漂變，不是自然選擇 (在表型水平上達(dá)爾文的自然選擇起主導(dǎo)作用).
  魯棒性： 基因發(fā)生突變后，表現(xiàn)型不發(fā)生變化 （如果外界環(huán)境不發(fā)生變化，適應(yīng)性就不發(fā)生變化。）
  適應(yīng)性：突變率不變的情況下，一個(gè)群體在環(huán)境改變后，是否很快演化出相對新環(huán)境最適應(yīng)的表現(xiàn)型
  例子：對于基礎(chǔ)理論/全新理論研究的支持。在當(dāng)下與傳統(tǒng)方法相比效果沒那么好，但是對于市場變換適應(yīng)強(qiáng)（理論基礎(chǔ)更強(qiáng)，共容易改進(jìn)）

17 群體自適應(yīng)——遺傳算法

啟發(fā)于：Fisher的群體遺傳學(xué)
如果基因之間是相互獨(dú)立的，那么找到最佳組合的時(shí)間是線性增加的，而如果是兩兩相關(guān)的，那么需要指數(shù)增加的時(shí)間
building block是層級結(jié)構(gòu)的基礎(chǔ)

GA

1. 創(chuàng)建種群
2. 選擇
3. 評估適應(yīng)度
4. 可以是選出兩個(gè)最適應(yīng)的個(gè)體進(jìn)行交配
5. 繁殖
6. 交叉
7. 突變

GA特點(diǎn)

• 遺傳算法從問題解的集合開始嫂索，而不是從單個(gè)解開始。 這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，復(fù)蓋面大， 利于全局擇優(yōu)。
• 遺傳算法求解時(shí)使用特定問題的信息極少，容易形成通用算法程序。
• 有極強(qiáng)的容錯(cuò)能力
• 采用隨機(jī)方法進(jìn)行最優(yōu)解搜索
• 具有隱含的并行性

18 復(fù)雜自適應(yīng)——群體策略演化

多人可重復(fù)的囚徒困境博弈The Evolution of Strategies in the Iterated Prisoner’s Dilemma
一個(gè)策略就是一個(gè)決策規(guī)則，與歷史相關(guān). 策略甚至可以將對方的策略（一般是自己猜測）作為輸入，針對性地做出決策。
好的策略特點(diǎn)：善良、寬容、報(bào)復(fù)、清晰

GA進(jìn)行策略演化

如果記憶長度是１，則編碼序列有4位： CC|CD|DC|DD ，Tic-for-tak的編碼為CDCD
如果記憶長度是3，則編碼序列有2^(2*3)=64位

Evolutionarily stable strategy (ESS)

它不能處理互動作用同時(shí)發(fā)生于多于兩個(gè)個(gè)體的博弈
背叛策略-> （合作策略->針鋒相對）:All-D本身不能入侵TFT，但是All-C可以，而被All-C入侵后，All-D就可以入侵了。

加入噪音

• GTFT(慷慨的一報(bào)還一報(bào))：對于對方的背叛，有一定概率仍然合作，能夠擊敗TFT。
• Pavlov(Win-stay-Lose-shift)
  如果上一局是：對方占我便宜或雙方背叛，那么這一輪我就換另一種策略；如果上一局是：我占了便宜或者雙方合作， 這一局我就維持上一局的策略不變。比TFT更適應(yīng)偶發(fā)失誤（是因?yàn)殡p方背叛不會一直持續(xù)），也能防止AllC（噪音使得Pavlov占便宜）和AllD（AllD對Pavlov，得分是平均3分（5、1、5、1 ….) Pavlov對自己也是平均3分。 但是AllD跟自己打是平均1分。 所以不能入侵Pavlov）的入侵

19 CAS(Complex Adaptive Systems) 復(fù)雜自適應(yīng)系統(tǒng)

概念：

1. 許多小的自主體，沒有中央控制，信息并發(fā)產(chǎn)生
2. 系統(tǒng)呈現(xiàn)模塊化、層次化
3. 系統(tǒng)狀態(tài)不斷變革，平衡只是暫時(shí)的

例子：
細(xì)胞、語言、生態(tài)環(huán)境