第5單元——Agent的復(fù)雜系統(tǒng)建模與模擬方法

1、第5單元 基于Agent的復(fù)雜系統(tǒng) 建模與模擬方法本章內(nèi)容 主體與多主體系統(tǒng) 多主體建模與仿真 多主體模型的實(shí)現(xiàn) 多主體仿真在社會(huì)科學(xué)中的應(yīng)用 Aspen多主體經(jīng)濟(jì)模型5.1 主體與多主體系統(tǒng)5.1.1 主體概念（1）主體的來(lái)源Agent ：主體，智能體，代理來(lái)源于分布式人工智能領(lǐng)域Minsky，1986The Society of Mind 1990s在人工智能領(lǐng)域得到重視 1990s 在其他領(lǐng)域廣泛應(yīng)用 （2）Agent的定義 研究人員對(duì)Agent的理解并不一致，至今還沒(méi)有一個(gè)普遍接受的關(guān)于Agent的定義。 “Agent”一般用來(lái)描述自包含的、能感知環(huán)境并能在一定程度上控制自身行為的計(jì)算

2、實(shí)體。 Hewitt:“什么是主體對(duì)于基于主體的計(jì)算來(lái)說(shuō)是個(gè)尷尬的問(wèn)題，就像主流的人工智能研究中什么是智能這個(gè)問(wèn)題一樣” （3）主體的弱概念主體的弱概念從廣義的角度規(guī)定主體的特性：自治性(autonomy)： 主體的運(yùn)行不受人或其它物的直接控制，它對(duì)自己的行動(dòng)和內(nèi)部狀態(tài)有一定程度的控制權(quán)。社會(huì)能力(social ability)： 主體通過(guò)某種主體通信語(yǔ)言與其它主體或人進(jìn)行信息交互。反應(yīng)能力(reactivity)： 即對(duì)環(huán)境的感知和影響。無(wú)論主體生存在現(xiàn)實(shí)世界還是虛擬世界，主體都應(yīng)該可以感知所處環(huán)境，并能及時(shí)地對(duì)環(huán)境中發(fā)生的變化做出反應(yīng)，通過(guò)行為影響環(huán)境。預(yù)動(dòng)性(pro-activeness

3、)： 主體不是簡(jiǎn)單的對(duì)環(huán)境被動(dòng)反應(yīng)，而是能采取主動(dòng)，表現(xiàn)出目標(biāo)導(dǎo)向（goal-directed）的行為。（4）主體的強(qiáng)概念 主體的強(qiáng)概念主要應(yīng)用在人工智能領(lǐng)域 認(rèn)為主體是一個(gè)計(jì)算機(jī)系統(tǒng)，除了上述弱概念說(shuō)明的特性外，主體還應(yīng)該具有人類的某些一般特性，如知識(shí)、信念、意圖、承諾等心智狀態(tài)，甚至具有情感等 5.1.2 多主體系統(tǒng)(Multi-Agent Systems)（1）為什么需要多主體系統(tǒng)？單一主體很難對(duì)存在于動(dòng)態(tài)開(kāi)放環(huán)境之中的大規(guī)模復(fù)雜問(wèn)題進(jìn)行求解 。人類智能本質(zhì)上是社會(huì)性的，人們往往為解決復(fù)雜問(wèn)題組織起來(lái)，這些組織能夠解決任何個(gè)人都無(wú)法解決的問(wèn)題。（2）多主體系統(tǒng)的特點(diǎn) 概念：多主體系統(tǒng)是由

4、多個(gè)可以相互交互的主體所組成的系統(tǒng)。 多主體系統(tǒng)的特點(diǎn)： 有限視角，即每個(gè)主體都面臨不完全信息，或只具備有限能力； 沒(méi)有系統(tǒng)全局控制； 數(shù)據(jù)分散； 計(jì)算是異步的（3）多主體系統(tǒng)的結(jié)構(gòu) 各個(gè)主體相對(duì)獨(dú)立，主體之間可能存在復(fù)雜的關(guān)系主體之間的關(guān)系類型 結(jié)構(gòu)相關(guān)結(jié)構(gòu)相關(guān)性是指不同主體之間具有結(jié)構(gòu)關(guān)系，如小組關(guān)系、上下級(jí)關(guān)系等。這種結(jié)構(gòu)關(guān)系將對(duì)系統(tǒng)中主體的運(yùn)行以及主體之間的相互作用產(chǎn)生影響。 行為相關(guān)不同的主體對(duì)環(huán)境的一部分產(chǎn)生影響，某些主體的影響范圍發(fā)生重疊，則它們之間就產(chǎn)生了行為上的相互影響。 5.1.3 主體的一般結(jié)構(gòu) 從計(jì)算的角度看，主體是一個(gè)計(jì)算實(shí)體， 具有屬于自身的資源， 能夠感知環(huán)境信息

5、， 根據(jù)內(nèi)部的行為控制機(jī)制確定主體應(yīng)采取的行動(dòng)， 主體的行動(dòng)實(shí)施后，將對(duì)自身狀態(tài)和環(huán)境狀態(tài)產(chǎn)生影響。 要實(shí)現(xiàn)這樣的主體，可以采用不同的結(jié)構(gòu)。 所謂結(jié)構(gòu)就是定義主體的基本成分以及各成分之間的關(guān)系和交互機(jī)制。 對(duì)特定的應(yīng)用場(chǎng)合采用某種結(jié)構(gòu)可能會(huì)更自然，也更容易理解。 （1）標(biāo)準(zhǔn)主體形式化假設(shè)環(huán)境變化可以抽象為一個(gè)環(huán)境狀態(tài)序列，環(huán)境在任何離散的瞬時(shí)狀態(tài)的有窮集合為:主體有一個(gè)可執(zhí)行動(dòng)作集合主體在環(huán)境中的一次執(zhí)行r是環(huán)境狀態(tài)與主體動(dòng)作的一個(gè)交替序列：主體的動(dòng)作決策部件可以定義為以下函數(shù)： 為環(huán)境演化的狀態(tài)序列。,210eeeE ,210aaaA uaaaaeeeeru1210210:AEChoose*

6、:*E 主體的動(dòng)作將對(duì)環(huán)境狀態(tài)產(chǎn)生影響，定義影響函數(shù)為： 標(biāo)準(zhǔn)主體定義為以下三元組：ChangeChooseAAgent,)(:EAEChange（2）純反應(yīng)式主體 有一種Agent決策完全基于當(dāng)前狀態(tài)，不考慮過(guò)去的狀態(tài)。 這種Agent只是直接對(duì)環(huán)境做出反應(yīng)，因此稱為純反應(yīng)式Agent。 其動(dòng)作決策部件與標(biāo)準(zhǔn)主體有所不同，決策函數(shù)為：AEChooser:（3）具有感知部件的主體 將標(biāo)準(zhǔn)主體的決策部件分解為感知子系統(tǒng)和動(dòng)作子系統(tǒng)，稱為具有感知部件的Agent。 （4）具有狀態(tài)部件的主體 一種與標(biāo)準(zhǔn)主體等價(jià)的表示方法，思路是認(rèn)為Agent具有內(nèi)部狀態(tài) 5.1.4主體之間的通信與交互 主體之間實(shí)現(xiàn)

7、交互需要三個(gè)方面的技術(shù)保障： 要有一致的消息協(xié)議， 要有實(shí)現(xiàn)通信的機(jī)制， 要有高層的交互協(xié)議。 這三個(gè)方面密切配合，才能實(shí)現(xiàn)主體之間的協(xié)作。 （1）主體通信語(yǔ)言 主體通信語(yǔ)言 是一種用于表達(dá)主體之間交互消息的描述性語(yǔ)言， 它定義了交互消息的格式（即語(yǔ)法）和內(nèi)涵（即語(yǔ)義）。 影響較大的主體通信語(yǔ)言： KQML ACLACL 消息結(jié)構(gòu) 一個(gè)ACL消息是由通信行為、通信內(nèi)容以及一組消息參數(shù)等幾部分組成 （2）通信方式 主體之間常用的通信機(jī)制有三種： 黑板機(jī)制 郵箱機(jī)制 消息傳遞機(jī)制 （3）交互協(xié)議 交互協(xié)議定義了主體之間為了進(jìn)行協(xié)作，實(shí)現(xiàn)某個(gè)特定目標(biāo)而進(jìn)行交互的結(jié)構(gòu)化消息。 FIPA對(duì)一些典型的對(duì)話

8、定義了交互協(xié)議， 請(qǐng)求(request) 查詢(query) 合同網(wǎng)(contract-net) 代理(broking) 訂閱(subscribe) 建議(propose)查詢交互協(xié)議查詢交互協(xié)議5.2 多主體建模與仿真 5.2.1 多主體建模思想ABM：MAS是對(duì)人類或生物群體的自然隱喻，采用多主體觀點(diǎn)可以更自然的對(duì)這些系統(tǒng)建模，由此形成了基于主體的建模方法（Agent-Based Modeling，ABM ）。ABM的基本出發(fā)點(diǎn)是：許多系統(tǒng)可以看作是由多個(gè)自治的主體構(gòu)成的，主體之間的相互作用是系統(tǒng)宏觀模式出現(xiàn)的根源，通過(guò)建立主體模型，可以更好的理解和解釋這些系統(tǒng)。 5.2.2 多主體仿真研

9、究框架 用多主體思想建立的復(fù)雜系統(tǒng)模型往往用仿真技術(shù)求解。這樣就形成了多主體仿真(Multi-Agent Simulation) 技術(shù)。 多主體仿真方法的本質(zhì)特征是采用多主體視角建立實(shí)際系統(tǒng)的概念模型 首先辨識(shí)組成實(shí)際系統(tǒng)的微觀個(gè)體，將這些個(gè)體抽象為具有自治性的主體， 主體之間通過(guò)相互作用構(gòu)成一個(gè)多主體系統(tǒng) 以這樣的多主體概念模型為基礎(chǔ)通過(guò)仿真計(jì)算展開(kāi)研究。 多主體仿真基本過(guò)多主體仿真基本過(guò)程程多主體仿真過(guò)程的特點(diǎn) 在對(duì)實(shí)際系統(tǒng)進(jìn)行觀察時(shí)應(yīng)同時(shí)收集微觀數(shù)據(jù)和宏觀數(shù)據(jù)。 概念模型采用多主體視角建立。 仿真模型一般采用多主體技術(shù)實(shí)現(xiàn)。 模型驗(yàn)證采用微觀和宏觀相結(jié)合的方法。 仿真所得到的結(jié)論主要用來(lái)

10、幫助理解系統(tǒng)微觀和宏觀的聯(lián)系。 5.2.3 與其它仿真方法的比較（1）與離散事件系統(tǒng)仿真的區(qū)別 基本要素：事件/主體 狀態(tài)變化：串行/并發(fā) 結(jié)構(gòu)變化：無(wú)/有 學(xué)習(xí)適應(yīng)：無(wú)/有5.2.3 與其它仿真方法的比較（2） 與微觀分析模擬的區(qū)別 應(yīng)用目的：政策效果/理論揭示 個(gè)體動(dòng)機(jī)：無(wú)/有 個(gè)體交互：無(wú)/有5.2.3 與其它仿真方法的比較（3）與元胞自動(dòng)機(jī)的區(qū)別 空間結(jié)構(gòu)：規(guī)則/靈活 個(gè)體記憶：無(wú)/有或無(wú) 學(xué)習(xí)推理：一般無(wú)/一般有 交互結(jié)構(gòu)：臨近/網(wǎng)絡(luò) 5.3 多主體仿真的實(shí)現(xiàn)技術(shù)5.3.1 主體構(gòu)建技術(shù)（1）產(chǎn)生式系統(tǒng)一個(gè)產(chǎn)生式系統(tǒng)包括三個(gè)部分：規(guī)則集、事實(shí)庫(kù)和控制器。 規(guī)則集存儲(chǔ)有關(guān)問(wèn)題的狀態(tài)轉(zhuǎn)移

11、、性質(zhì)變化等過(guò)程性知識(shí)，簡(jiǎn)單產(chǎn)生式規(guī)則的形式為“if,then”,每個(gè)規(guī)則有條件和行為兩部分組成，當(dāng)前提條件滿足時(shí)就執(zhí)行動(dòng)作。 事實(shí)庫(kù)存儲(chǔ)關(guān)于目前環(huán)境/自身狀態(tài)、性質(zhì)等信息，由此決定某個(gè)規(guī)則的前件是否滿足。 控制器根據(jù)主體的性質(zhì)選擇控制策略，將規(guī)則與事實(shí)進(jìn)行匹配，消解沖突，進(jìn)行推理，實(shí)現(xiàn)主體決策，產(chǎn)生行動(dòng)。（2）面向?qū)ο蠹夹g(shù) 為每類主體設(shè)計(jì)相應(yīng)的類，用屬性表達(dá)主體的內(nèi)部狀態(tài)，用方法表示主體的行為。 多主體系統(tǒng)中的主體本質(zhì)上是并發(fā)的。主體的主動(dòng)性和并發(fā)性需要在面向?qū)ο罂蚣苤胁捎靡欢ǖ募夹g(shù)手段進(jìn)行模擬。5.3.2 主體的學(xué)習(xí)算法 學(xué)習(xí)是智能生物的一個(gè)重要特征 如果一個(gè)系統(tǒng)能夠通過(guò)執(zhí)行某個(gè)過(guò)程改進(jìn)他

12、的性能，我們就認(rèn)為它有學(xué)習(xí)能力。 對(duì)主體而言，學(xué)習(xí)的含義是 主體根據(jù)所觀察到的事件，在連續(xù)交互過(guò)程中結(jié)構(gòu)化的修改行為策略，改進(jìn)它的性能。 （1）強(qiáng)化學(xué)習(xí) 基本思想： 如果某個(gè)行動(dòng)引起的后果較好，則在以后增加使用該行動(dòng)的可能，反之則減少。 強(qiáng)化學(xué)習(xí)主體的一般結(jié)構(gòu) ：目標(biāo)是學(xué)習(xí)一個(gè)策略目標(biāo)是學(xué)習(xí)一個(gè)策略：SA，使系統(tǒng)選擇的動(dòng)作能夠獲得回報(bào)的累計(jì)值最大。，使系統(tǒng)選擇的動(dòng)作能夠獲得回報(bào)的累計(jì)值最大。 Roth-Erev算法 初始化：選擇各行動(dòng)的傾向（Propensity） 重復(fù): 根據(jù)各個(gè)行動(dòng)的傾向計(jì)算選擇概率 按概率選擇行動(dòng) 根據(jù)該行動(dòng)的回報(bào)調(diào)整其傾向 返回 行動(dòng)傾向的更新方法： ),()(1 )

13、1(tkEtqtqjjj if 1)( if 1)(),(kjNtqkjtrtkEjkj概率計(jì)算 將傾向轉(zhuǎn)換為選擇概率有多種方法，較簡(jiǎn)單的一種是計(jì)算相對(duì)傾向作為概率：)()()(tqtqtpmjj（2）遺傳算法 基本思想： 首先將狀態(tài)-行動(dòng)對(duì)表達(dá)為染色體， 然后主體在動(dòng)態(tài)環(huán)境中感知狀態(tài)選擇行動(dòng)得到回報(bào)計(jì)算適應(yīng)度， 根據(jù)個(gè)體適應(yīng)度指標(biāo)淘汰低適應(yīng)度個(gè)體， 染色體之間進(jìn)行交叉，以小概率發(fā)生變異，產(chǎn)生下一代種群，重復(fù)進(jìn)行。 例：多人囚徒困境博弈 狀態(tài)State=(上次行動(dòng)，上輪對(duì)手行動(dòng)) 主體的行動(dòng)有兩種：合作=1，欺騙=0 有四種可能的狀態(tài)，編碼為 狀態(tài)1為(1,1),2為（1，0）,3為(0,1)

14、,4為(0,0) 個(gè)體的一個(gè)策略就可以用位串表示 例如針?shù)h相對(duì)（TFT）策略就是： 初次選擇行動(dòng)1 if State 1,then choose action 1; if State 2,then choose action 0; if State 3,then choose action 1; if State 4,then choose action 0; 則該策略可以編碼為（1 1 0 1 0），表示初次選擇行動(dòng)1，以后若狀態(tài)為1則選擇1，若狀態(tài)2則選擇0，狀態(tài)3則選擇1，狀態(tài)4則選擇0。 5.4 多主體仿真在經(jīng)濟(jì)中的應(yīng)用 經(jīng)濟(jì)系統(tǒng)的特點(diǎn)： 經(jīng)濟(jì)系統(tǒng)是一個(gè)復(fù)雜動(dòng)態(tài)系統(tǒng) 微觀上由許多相對(duì)獨(dú)

15、立的個(gè)體組成，個(gè)體具有智能性，存在學(xué)習(xí)和適應(yīng)行為 個(gè)體之間存在復(fù)雜的相互作用（1） 基于Agent的計(jì)算經(jīng)濟(jì)學(xué) ACE ，Agent-based Computational Economics 將經(jīng)濟(jì)過(guò)程看作是由交互作用的主體構(gòu)成的動(dòng)態(tài)系統(tǒng)，采用仿真手段對(duì)經(jīng)濟(jì)系統(tǒng)進(jìn)行研究。 研究方法： 采用“培養(yǎng)皿”（culture dish）類比 ，對(duì)經(jīng)濟(jì)過(guò)程進(jìn)行理論研究。（2） “培養(yǎng)皿”研究方法 首先構(gòu)建一個(gè)由多種主體構(gòu)成的虛擬經(jīng)濟(jì)世界， 設(shè)定初始條件（如結(jié)構(gòu)條件、制度安排、主體行為分配等）， 然后令虛擬世界自然發(fā)展，發(fā)展的根本原因是主體之間的交互； 研究者對(duì)虛擬世界進(jìn)行觀察，收集數(shù)據(jù)，進(jìn)行分析。 主體

16、 將經(jīng)濟(jì)系統(tǒng)中的個(gè)人、公司、市場(chǎng)、政府等抽象為主體 主體可能很簡(jiǎn)單，也可能具有不同程度的認(rèn)知能力： 適應(yīng) 社會(huì)交互 目標(biāo)導(dǎo)向的學(xué)習(xí) 自治 在主體的交互過(guò)程中行為模式或交互模式演化發(fā)展研究過(guò)程（3）ACE的主要研究?jī)?nèi)容實(shí)證性理解規(guī)范性理解定性洞察/理論產(chǎn)生方法和工具實(shí)證性理解 目的為實(shí)證中經(jīng)常觀察到的規(guī)律提供因果解釋。 研究方法 構(gòu)建一個(gè)反映實(shí)際系統(tǒng)主要特征的基于主體的虛擬世界，然后研究實(shí)證規(guī)律是否能夠在這個(gè)虛擬世界里可靠的再現(xiàn)。 研究實(shí)例 金融市場(chǎng)，為觀察到的格式化特征提供解釋。 規(guī)范性理解 目的將基于主體的模型作為“實(shí)驗(yàn)室”用于發(fā)現(xiàn)比較好的經(jīng)濟(jì)設(shè)計(jì)，判斷制度設(shè)計(jì)是否會(huì)導(dǎo)致效率、公平、有序的社

17、會(huì)結(jié)果。 研究方法構(gòu)造一個(gè)反映制度設(shè)計(jì)主要特征的基于主體的虛擬世界，引入具有不同稟賦、需求、目標(biāo)、信念等的主體，令虛擬世界自發(fā)演進(jìn)，觀察和評(píng)價(jià)社會(huì)結(jié)果。 研究實(shí)例 設(shè)計(jì)失業(yè)救濟(jì)計(jì)劃、電力市場(chǎng)定價(jià)等。 定性洞察/發(fā)展理論 目的加強(qiáng)對(duì)經(jīng)濟(jì)系統(tǒng)規(guī)律的全面了解 研究方法設(shè)定不同的初始條件，系統(tǒng)全面的考察系統(tǒng)的演化動(dòng)態(tài) 研究實(shí)例分散市場(chǎng)的自組織，瓦爾拉斯均衡的條件方法和工具 目的為通過(guò)受控計(jì)算實(shí)驗(yàn)進(jìn)行嚴(yán)格的經(jīng)濟(jì)理論研究提供方法和工具。 方法方面如何建模，如何提出理論命題，如何簡(jiǎn)明、充分的報(bào)告實(shí)驗(yàn)過(guò)程和結(jié)果，如何對(duì)實(shí)驗(yàn)產(chǎn)生的理論與實(shí)際數(shù)據(jù)進(jìn)行檢驗(yàn)等 工具方面建模工具、仿真工具、數(shù)據(jù)分析工具等（4）ACE的

18、優(yōu)點(diǎn) 主體的決策和交互可以采用直觀描述。 適合對(duì)由一群具有不同特性的決策者形成的群體進(jìn)行建模 允許對(duì)主體之間復(fù)雜的關(guān)系建模 能夠跟蹤不同均衡態(tài)之間的過(guò)渡路徑 引入學(xué)習(xí)算法，研究主體行為的變化 （5）ACE的缺點(diǎn)需要大量的計(jì)算實(shí)驗(yàn) 輸出結(jié)果是隨機(jī)的模型校核驗(yàn)證困難（6）近期研究實(shí)例 Aspen美國(guó)經(jīng)濟(jì)模型 ASM 股票市場(chǎng)模型 SugarScape 技術(shù)變遷 產(chǎn)業(yè)組織 貿(mào)易網(wǎng)絡(luò)5.5 Aspen經(jīng)濟(jì)系統(tǒng)多主體模型5.5.1 Aspen簡(jiǎn)介名稱：基于主體的微觀分析模擬模型 Agent-based Simulation Model of the U.S. economy 開(kāi)發(fā)者： 美國(guó)Sandia

19、National Lab. 發(fā)展歷史： 1996 原型開(kāi)發(fā)、驗(yàn)證 研究美國(guó)經(jīng)濟(jì)、過(guò)渡經(jīng)濟(jì)、電力市場(chǎng) 最近研究突發(fā)事件（恐怖襲擊）的影響Aspen的特點(diǎn) 針對(duì)美國(guó)經(jīng)濟(jì)特點(diǎn)抽象出多類主體，各類主體具有比較堅(jiān)實(shí)的微觀基礎(chǔ) 采用學(xué)習(xí)算法GALCS模擬企業(yè)定價(jià)，通過(guò)學(xué)習(xí)過(guò)程模擬企業(yè)行為 運(yùn)行在Paragon并行計(jì)算機(jī)上 主體分散決策，通過(guò)消息傳遞進(jìn)行交互Aspen模型的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)： 模擬各類經(jīng)濟(jì)政策的影響 對(duì)單部門或多部門進(jìn)行分析 明確放棄了一般均衡論 主體決策比較真實(shí) 能夠模擬新概念 缺點(diǎn)： 參數(shù)設(shè)置困難 計(jì)算性能要求太高5.5.2 Aspen基本模型（1）主體 家庭 企業(yè)，又分為四類： 食品生產(chǎn)商、其他非耐用品生產(chǎn)商、汽車制造商、房地產(chǎn)商 銀行 政府 美聯(lián)儲(chǔ) 資本物品生產(chǎn)商 金融市場(chǎng)（2）消息傳遞技術(shù) 主體分布在不同的計(jì)算節(jié)點(diǎn)上 將連續(xù)的時(shí)間劃分為離散的時(shí)期（天），每天又劃分為11個(gè)階段 多數(shù)行動(dòng)每天只發(fā)生1次，且在特定的階段發(fā)生 每個(gè)主體有一個(gè)消息隊(duì)列，用于存放收到的消息消息分發(fā)過(guò)程（