建模与仿真(MAS部分)

1、建模与仿真主 讲 人：许 良复杂系统建模经济管理学院工业工程系主讲内容主讲内容主体与多主体系统主体与多主体系统多主体建模与仿真多主体建模与仿真多主体模型的实现多主体模型的实现多主体仿真在社会科学中的应用多主体仿真在社会科学中的应用Aspen多主体经济模型多主体经济模型一、一、 主体与多主体系统主体与多主体系统(一一) 主体概念主体概念（1）主体的来源）主体的来源Agent ：主体，智能体，代理：主体，智能体，代理来源于分布式人工智能领域来源于分布式人工智能领域Minsky，1986The Society of Mind 1990s在人工智能领域得到重视在人工智能领域得到重视 1990s 在其他

2、领域广泛应用在其他领域广泛应用 （2）Agent的定义的定义研究人员对研究人员对Agent的理解并不一致，至今还没有一个的理解并不一致，至今还没有一个普遍接受的关于普遍接受的关于Agent的定义。的定义。“Agent”一般用来描述自包含的、能感知环境并能在一般用来描述自包含的、能感知环境并能在一定程度上控制自身行为的计算实体。一定程度上控制自身行为的计算实体。Hewitt:“什么是主体对于基于主体的计算来说是个尴什么是主体对于基于主体的计算来说是个尴尬的问题，就像主流的人工智能研究中什么是智能这尬的问题，就像主流的人工智能研究中什么是智能这个问题一样个问题一样” （3）主体的弱概念）主体的弱概

3、念主体的弱概念从广义的角度规定主体的特性：主体的弱概念从广义的角度规定主体的特性：自治性自治性(autonomy)：n主体的运行不受人或其它物的直接控制，它对自己的行动和内部状主体的运行不受人或其它物的直接控制，它对自己的行动和内部状态有一定程度的控制权。态有一定程度的控制权。社会能力社会能力(social ability)：n主体通过某种主体通信语言与其它主体或人进行信息交互。主体通过某种主体通信语言与其它主体或人进行信息交互。反应能力反应能力(reactivity)：n即对环境的感知和影响。无论主体生存在现实世界还是虚拟世界，即对环境的感知和影响。无论主体生存在现实世界还是虚拟世界，主体都

4、应该可以感知所处环境，并能及时地对环境中发生的变化做主体都应该可以感知所处环境，并能及时地对环境中发生的变化做出反应，通过行为影响环境。出反应，通过行为影响环境。预动性预动性(pro-activeness)：n主体不是简单的对环境被动反应，而是能采取主动，表现出目标导主体不是简单的对环境被动反应，而是能采取主动，表现出目标导向（向（goal-directed）的行为。）的行为。（4）主体的强概念）主体的强概念主体的强概念主要应用在人工智能领域主体的强概念主要应用在人工智能领域认为主体是一个计算机系统，除了上述弱概念认为主体是一个计算机系统，除了上述弱概念说明的特性外，主体还应该具有人类的某些一

5、说明的特性外，主体还应该具有人类的某些一般特性，如知识、信念、意图、承诺等心智状般特性，如知识、信念、意图、承诺等心智状态，甚至具有情感等态，甚至具有情感等 （1）为什么需要多主体系统？）为什么需要多主体系统？n单一主体很难对存在于单一主体很难对存在于动态开放环境动态开放环境之中的大之中的大规模复杂问题进行求解规模复杂问题进行求解 。n人类智能本质上是人类智能本质上是社会性社会性的，人们往往为解决复的，人们往往为解决复杂问题组织起来，这些组织能够解决任何个人都杂问题组织起来，这些组织能够解决任何个人都无法解决的问题。无法解决的问题。(二二) 多主体系统多主体系统(Multi-Agent Sys

6、tems)（2）多主体系统的特点）多主体系统的特点概念：概念：多主体系统是由多个可以相互交互的主体所组成的系多主体系统是由多个可以相互交互的主体所组成的系统。统。多主体系统的特点：多主体系统的特点：n有限视角，即每个主体都面临不完全信息，或只具备有限能有限视角，即每个主体都面临不完全信息，或只具备有限能力；力；n没有系统全局控制；没有系统全局控制；n数据分散；数据分散；n计算是异步的计算是异步的（3）多主体系统的结构）多主体系统的结构各个主体相对独立，主体之间可能存在复杂的各个主体相对独立，主体之间可能存在复杂的关系关系主体之间的关系类型主体之间的关系类型结构相关结构相关结构相关性是指不同主体

7、之间具有结构关系，如小组结构相关性是指不同主体之间具有结构关系，如小组关系、上下级关系等。关系、上下级关系等。这种结构关系将对系统中主体的运行以及主体之间的这种结构关系将对系统中主体的运行以及主体之间的相互作用产生影响。相互作用产生影响。 行为相关行为相关不同的主体对环境的一部分产生影响，不同的主体对环境的一部分产生影响，某些主体的影响范围发生重叠，则它们之间就产生了某些主体的影响范围发生重叠，则它们之间就产生了行为上的相互影响。行为上的相互影响。 (三三) 主体的一般结构主体的一般结构从计算的角度看，主体是一个计算实体，从计算的角度看，主体是一个计算实体，n具有属于自身的具有属于自身的资源资

8、源，n能够能够感知感知环境信息，环境信息，n根据内部的根据内部的行为控制机制行为控制机制确定主体应采取的行动，确定主体应采取的行动，n主体的行动实施后，将对自身状态和环境状态产生主体的行动实施后，将对自身状态和环境状态产生影响影响。要实现这样的主体，可以采用不同的结构。要实现这样的主体，可以采用不同的结构。所谓结构就是定义主体的基本成分以及各成分之间的所谓结构就是定义主体的基本成分以及各成分之间的关系和交互机制。关系和交互机制。对特定的应用场合采用某种结构可能会更自然，也更对特定的应用场合采用某种结构可能会更自然，也更容易理解。容易理解。 （1）标准主体）标准主体形式化形式化假设环境变化可以抽

9、象为一个环境状态序列，环境在任何离散的假设环境变化可以抽象为一个环境状态序列，环境在任何离散的瞬时状态的有穷集合为瞬时状态的有穷集合为:主体有一个可执行动作集合主体有一个可执行动作集合主体在环境中的一次执行主体在环境中的一次执行r是环境状态与主体动作的一个交替序是环境状态与主体动作的一个交替序列：列：主体的动作决策部件可以定义为以下函数：主体的动作决策部件可以定义为以下函数： 为环境演化的状态序列。为环境演化的状态序列。,210eeeE ,210aaaA uaaaaeeeeru1210210:AEChoose*:*E主体的动作将对环境状态产生影响，定义影响主体的动作将对环境状态产生影响，定义影

10、响函数为：函数为：标准主体定义为以下三元组：标准主体定义为以下三元组：ChangeChooseAAgent,)(:EAEChange（2）纯反应式主体）纯反应式主体有一种有一种Agent决策完全基于当前状态，不考虑决策完全基于当前状态，不考虑过去的状态。过去的状态。这种这种Agent只是直接对环境做出反应，因此称只是直接对环境做出反应，因此称为纯反应式为纯反应式Agent。其动作决策部件与标准主体有所不同，决策函其动作决策部件与标准主体有所不同，决策函数为：数为：AEChooser:（3）具有感知部件的主体）具有感知部件的主体 将标准主体的决策部件分解为感知子系统和动将标准主体的决策部件分解为

11、感知子系统和动作子系统，称为具有感知部件的作子系统，称为具有感知部件的Agent。 （4）具有状态部件的主体）具有状态部件的主体一种与标准主体等价的表示方法，思路是认为一种与标准主体等价的表示方法，思路是认为Agent具有内部状态具有内部状态 (四四)主体之间的通信与交互主体之间的通信与交互主体之间实现交互需要三个方面的技术保障：主体之间实现交互需要三个方面的技术保障：n要有一致的消息协议，要有一致的消息协议，n要有实现通信的机制，要有实现通信的机制，n要有高层的交互协议。要有高层的交互协议。这三个方面密切配合，才能实现主体之间的协这三个方面密切配合，才能实现主体之间的协作。作。 （1）主体通

12、信语言）主体通信语言主体通信语言主体通信语言n是一种用于表达主体之间交互消息的描述性语言，是一种用于表达主体之间交互消息的描述性语言，n它定义了交互消息的格式（即它定义了交互消息的格式（即语法语法）和内涵（即）和内涵（即语义语义）。）。影响较大的主体通信语言：影响较大的主体通信语言：nKQML nACLACL 消息结构消息结构一个一个ACL消息是由消息是由通信行为、通信内容通信行为、通信内容以及一以及一组组消息参数消息参数等几部分组成等几部分组成 （2）通信方式）通信方式主体之间常用的通信机制有三种：主体之间常用的通信机制有三种：n黑板机制黑板机制n邮箱机制邮箱机制n消息传递机制消息传递机制

13、（3）交互协议）交互协议 交互协议定义了主体之间为了进行协作，实现交互协议定义了主体之间为了进行协作，实现某个特定目标而进行交互的结构化消息。某个特定目标而进行交互的结构化消息。 FIPA对一些典型的对话定义了交互协议，对一些典型的对话定义了交互协议，n请求请求(request)n查询查询(query)n合同网合同网(contract-net)n代理代理(broking)n订阅订阅(subscribe)n建议建议(propose)查询交互协议查询交互协议二、二、 多主体建模与仿真多主体建模与仿真 (一一) 多主体建模思想多主体建模思想ABM：MAS是对人类或生物群体的自然隐喻，采用多主是对人类

14、或生物群体的自然隐喻，采用多主体观点可以更自然的对这些系统建模，由此形成了基体观点可以更自然的对这些系统建模，由此形成了基于主体的建模方法（于主体的建模方法（Agent-Based Modeling，ABM ）。）。ABM的基本出发点是：的基本出发点是：许多系统可以看作是由多个自治的主体构成的，主体许多系统可以看作是由多个自治的主体构成的，主体之间的相互作用是系统宏观模式出现的根源，通过建之间的相互作用是系统宏观模式出现的根源，通过建立主体模型，可以更好的理解和解释这些系统。立主体模型，可以更好的理解和解释这些系统。 (二二) 多主体仿真研究框架多主体仿真研究框架用多主体思想建立的复杂系统模型

15、往往用仿真技术求用多主体思想建立的复杂系统模型往往用仿真技术求解。这样就形成了多主体仿真解。这样就形成了多主体仿真(Multi-Agent Simulation) 技术。技术。多主体仿真方法的本质特征是采用多主体视角建立实多主体仿真方法的本质特征是采用多主体视角建立实际系统的际系统的概念模型概念模型 n首先辨识组成实际系统的首先辨识组成实际系统的微观个体微观个体，将这些个体抽象为具有，将这些个体抽象为具有自治性的主体，自治性的主体，n主体之间通过主体之间通过相互作用相互作用构成一个多主体系统构成一个多主体系统n以这样的多主体概念模型为基础通过以这样的多主体概念模型为基础通过仿真计算仿真计算展开

16、研究。展开研究。 多主体仿真基本过多主体仿真基本过程程多主体仿真过程的特点多主体仿真过程的特点在对实际系统进行观察时应同时收集微观数据在对实际系统进行观察时应同时收集微观数据和宏观数据。和宏观数据。 概念模型采用多主体视角建立。概念模型采用多主体视角建立。 仿真模型一般采用多主体技术实现。仿真模型一般采用多主体技术实现。 模型验证采用微观和宏观相结合的方法。模型验证采用微观和宏观相结合的方法。 仿真所得到的结论主要用来帮助理解系统微观仿真所得到的结论主要用来帮助理解系统微观和宏观的联系。和宏观的联系。 (三三) 与其它仿真方法的比较与其它仿真方法的比较（1）与离散事件系统仿真的区别）与离散事件

17、系统仿真的区别 基本要素：事件基本要素：事件/主体主体 状态变化：串行状态变化：串行/并发并发 结构变化：无结构变化：无/有有 学习适应：无学习适应：无/有有(四四) 与其它仿真方法的比较与其它仿真方法的比较（2） 与微观分析模拟的区别与微观分析模拟的区别 应用目的：政策效果应用目的：政策效果/理论揭示理论揭示 个体动机：无个体动机：无/有有 个体交互：无个体交互：无/有有(五五) 与其它仿真方法的比较与其它仿真方法的比较（3）与元胞自动机的区别）与元胞自动机的区别 空间结构：规则空间结构：规则/灵活灵活 个体记忆：无个体记忆：无/有或无有或无 学习推理：一般无学习推理：一般无/一般有一般有

18、交互结构：临近交互结构：临近/网络网络 三、三、 多主体仿真的实现技术多主体仿真的实现技术(一一) 主体构建技术主体构建技术（1）产生式系统）产生式系统一个产生式系统包括三个部分：规则集、事实库和控一个产生式系统包括三个部分：规则集、事实库和控制器。制器。n规则集存储有关问题的状态转移、性质变化等过程性知识，规则集存储有关问题的状态转移、性质变化等过程性知识，简单产生式规则的形式为简单产生式规则的形式为“if,then”,每个规则有条件和每个规则有条件和行为两部分组成，当前提条件满足时就执行动作。行为两部分组成，当前提条件满足时就执行动作。n事实库存储关于目前环境事实库存储关于目前环境/自身状

19、态、性质等信息，由此决定自身状态、性质等信息，由此决定某个规则的前件是否满足。某个规则的前件是否满足。n控制器根据主体的性质选择控制策略，将规则与事实进行匹控制器根据主体的性质选择控制策略，将规则与事实进行匹配，消解冲突，进行推理，实现主体决策，产生行动。配，消解冲突，进行推理，实现主体决策，产生行动。（2）面向对象技术）面向对象技术为每类主体设计相应的为每类主体设计相应的类类，用属性表达主体的，用属性表达主体的内部状态，用方法表示主体的行为。内部状态，用方法表示主体的行为。 多主体系统中的主体本质上是并发的。主体的多主体系统中的主体本质上是并发的。主体的主动性主动性和和并发性并发性需要在面向

20、对象框架中采用一需要在面向对象框架中采用一定的技术手段进行模拟。定的技术手段进行模拟。(二二) 主体的学习算法主体的学习算法学习是智能生物的一个重要特征学习是智能生物的一个重要特征n如果一个系统能够通过执行某个过程改进他的性能，如果一个系统能够通过执行某个过程改进他的性能，我们就认为它有学习能力。我们就认为它有学习能力。对主体而言，学习的含义是对主体而言，学习的含义是n主体根据所观察到的事件，在连续交互过程中结构主体根据所观察到的事件，在连续交互过程中结构化的修改化的修改行为策略行为策略，改进它的性能。，改进它的性能。 （1）强化学习）强化学习基本思想：基本思想：n如果某个行动引起的后果较好，

21、则在以后增加使用如果某个行动引起的后果较好，则在以后增加使用该行动的可能，反之则减少。该行动的可能，反之则减少。 强化学习主体的一般结构强化学习主体的一般结构 ：目标是学习一个策略目标是学习一个策略：SA，使系统选择的动作能够获得回报的累计值最大。，使系统选择的动作能够获得回报的累计值最大。 Roth-Erev算法算法 初始化：选择各行动的倾向（初始化：选择各行动的倾向（Propensity）重复重复: n根据各个行动的倾向计算选择概率根据各个行动的倾向计算选择概率n按概率选择行动按概率选择行动n根据该行动的回报调整其倾向根据该行动的回报调整其倾向返回返回 行动倾向的更新方法：行动倾向的更新方

22、法： ),()(1 ) 1(tkEtqtqjjj if 1)( if 1)(),(kjNtqkjtrtkEjkj概率计算概率计算将倾向转换为选择概率有多种方法，较简单的将倾向转换为选择概率有多种方法，较简单的一种是计算相对倾向作为概率：一种是计算相对倾向作为概率：)()()(tqtqtpmjj（2）遗传算法）遗传算法基本思想：基本思想：n首先将状态首先将状态-行动对表达为染色体，行动对表达为染色体，n然后主体在动态环境中感知状态然后主体在动态环境中感知状态选择行动选择行动得到得到回报回报计算适应度，计算适应度，n根据个体适应度指标淘汰低适应度个体，根据个体适应度指标淘汰低适应度个体，n染色体之

23、间进行交叉，以小概率发生变异，产生下染色体之间进行交叉，以小概率发生变异，产生下一代种群，重复进行一代种群，重复进行。 例：多人囚徒困境博弈例：多人囚徒困境博弈状态状态State=(上次行动，上轮对手行动上次行动，上轮对手行动) 主体的行动有两种：合作主体的行动有两种：合作=1，欺骗，欺骗=0 有四种可能的状态，编码为有四种可能的状态，编码为n状态状态1为为(1,1),2为（为（1，0）,3为为(0,1),4为为(0,0) 个体的一个策略就可以用位串表示个体的一个策略就可以用位串表示例如针锋相对（例如针锋相对（TFT）策略就是：）策略就是：n初次选择行动初次选择行动1nif State 1,t

24、hen choose action 1;nif State 2,then choose action 0;nif State 3,then choose action 1;nif State 4,then choose action 0;则该策略可以编码为（则该策略可以编码为（1 1 0 1 0），表示初次选择行），表示初次选择行动动1，以后若状态为，以后若状态为1则选择则选择1，若状态，若状态2则选择则选择0，状，状态态3则选择则选择1，状态，状态4则选择则选择0。 四、多主体仿真在经济中的应用四、多主体仿真在经济中的应用经济系统的特点：经济系统的特点：n经济系统是一个复杂动态系统经济系统是

25、一个复杂动态系统n微观上由许多相对独立的个体组成，个体具有智能微观上由许多相对独立的个体组成，个体具有智能性，存在学习和适应行为性，存在学习和适应行为n个体之间存在复杂的相互作用个体之间存在复杂的相互作用（1） 基于基于Agent的计算经济学的计算经济学ACE ，Agent-based Computational Economics 将经济过程看作是由交互作用的主体构成的动态系将经济过程看作是由交互作用的主体构成的动态系统，采用仿真手段对经济系统进行研究。统，采用仿真手段对经济系统进行研究。研究方法：研究方法： 采用采用“培养皿培养皿”（culture dish）类比）类比 ，对经济过，对经济

26、过程进行理论研究。程进行理论研究。（2） “培养皿培养皿”研究方法研究方法首先构建一个由多种主体构成的虚拟经济世界，首先构建一个由多种主体构成的虚拟经济世界，设定初始条件（如结构条件、制度安排、主体设定初始条件（如结构条件、制度安排、主体行为分配等），行为分配等），然后令虚拟世界自然发展，发展的根本原因是然后令虚拟世界自然发展，发展的根本原因是主体之间的交互；主体之间的交互；研究者对虚拟世界进行观察，收集数据，进行研究者对虚拟世界进行观察，收集数据，进行分析。分析。 主体主体将经济系统中的个人、公司、市场、政府等抽象为主将经济系统中的个人、公司、市场、政府等抽象为主体体主体可能很简单，也可能具

27、有不同程度的认知能力：主体可能很简单，也可能具有不同程度的认知能力：n适应适应n社会交互社会交互n目标导向的学习目标导向的学习n自治自治在主体的交互过程中行为模式或交互模式演化发展在主体的交互过程中行为模式或交互模式演化发展研究过程研究过程（3）ACE的主要研究内容的主要研究内容实证性理解实证性理解规范性理解规范性理解定性洞察定性洞察/理论产生理论产生方法和工具方法和工具实证性理解实证性理解目的目的为实证中经常观察到的规律提供因果解释。为实证中经常观察到的规律提供因果解释。研究方法研究方法 构建一个反映构建一个反映实际系统主要特征的基于主体的虚拟世界，然后的基于主体的虚拟世界，然后研究实证规律

28、是否能够在这个虚拟世界里可靠的研究实证规律是否能够在这个虚拟世界里可靠的再现。研究实例研究实例 金融市场，为观察到的格式化特征提供解释。金融市场，为观察到的格式化特征提供解释。 规范性理解规范性理解目的目的将基于主体的模型作为将基于主体的模型作为“实验室实验室”用于发现比较好的经济设用于发现比较好的经济设计，判断制度设计是否会导致效率、公平、有序的社会结果。计，判断制度设计是否会导致效率、公平、有序的社会结果。研究方法研究方法构造一个反映构造一个反映制度设计主要设计主要特征的基于主体的虚拟世界，引的基于主体的虚拟世界，引入具有不同禀赋、需求、目标、信念等的主体，令虚拟世界入具有不同禀赋、需求、

29、目标、信念等的主体，令虚拟世界自发演进，观察和评价社会结果。自发演进，观察和评价社会结果。研究实例研究实例 设计失业救济计划、电力市场定价等。设计失业救济计划、电力市场定价等。 定性洞察定性洞察/发展理论发展理论目的目的加强对经济系统规律的全面了解加强对经济系统规律的全面了解研究方法研究方法设定不同的初始条件，系统全面的考察系统的演化动设定不同的初始条件，系统全面的考察系统的演化动态态研究实例研究实例分散市场的自组织，瓦尔拉斯均衡的条件分散市场的自组织，瓦尔拉斯均衡的条件方法和工具方法和工具目的目的为通过受控计算实验进行严格的经济理论研究提供方法和工具。为通过受控计算实验进行严格的经济理论研究

30、提供方法和工具。 方法方面方法方面如何建模，如何提出理论命题，如何简明、充分的报告实验过如何建模，如何提出理论命题，如何简明、充分的报告实验过程和结果，如何对实验产生的理论与实际数据进行检验等程和结果，如何对实验产生的理论与实际数据进行检验等 工具方面工具方面建模工具、仿真工具、数据分析工具等建模工具、仿真工具、数据分析工具等（4）ACE的优点的优点主体的决策和交互可以采用直观描述。主体的决策和交互可以采用直观描述。适合对由一群具有不同特性的决策者形成的群适合对由一群具有不同特性的决策者形成的群体进行建模体进行建模 允许对主体之间复杂的关系建模允许对主体之间复杂的关系建模 能够跟踪不同均衡态之

31、间的过渡路径能够跟踪不同均衡态之间的过渡路径 引入学习算法，研究主体行为的变化引入学习算法，研究主体行为的变化 （5）ACE的缺点的缺点需要大量的计算实验需要大量的计算实验 输出结果是随机的输出结果是随机的模型校核验证困难模型校核验证困难（6）近期研究实例）近期研究实例Aspen美国经济模型美国经济模型ASM 股票市场模型股票市场模型SugarScape技术变迁技术变迁产业组织产业组织贸易网络贸易网络五、五、Aspen经济系统多主体模型经济系统多主体模型(一一) Aspen简介简介名称：基于主体的微观分析模拟模型基于主体的微观分析模拟模型 Agent-based Simulation Mode

32、l of the U.S. economy 开发者：开发者： 美国美国Sandia National Lab. 发展历史：发展历史： 1996 原型开发、验证原型开发、验证 研究美国经济、过渡经济、电力市场研究美国经济、过渡经济、电力市场 最近研究突发事件（恐怖袭击）的影响最近研究突发事件（恐怖袭击）的影响Aspen的特点的特点针对美国经济特点抽象出多类主体，各类主体针对美国经济特点抽象出多类主体，各类主体具有比较坚实的微观基础具有比较坚实的微观基础采用学习算法采用学习算法GALCS模拟企业定价，通过学模拟企业定价，通过学习过程模拟企业行为习过程模拟企业行为运行在运行在Paragon并行计算机

33、上并行计算机上主体分散决策，通过消息传递进行交互主体分散决策，通过消息传递进行交互Aspen模型的优缺点模型的优缺点优点：优点：n模拟各类经济政策的影响模拟各类经济政策的影响n对单部门或多部门进行分析对单部门或多部门进行分析n明确放弃了一般均衡论明确放弃了一般均衡论n主体决策比较真实主体决策比较真实n能够模拟新概念能够模拟新概念缺点：缺点：n参数设置困难参数设置困难n计算性能要求太高计算性能要求太高(二二) Aspen基本模型基本模型（1）主体）主体n家庭家庭n企业，又分为四类：企业，又分为四类：w食品生产商、其他非耐用品生产商、汽车制造商、房地产商食品生产商、其他非耐用品生产商、汽车制造商、房地产商n银行银行n政府政府n美联储美联储n资本物品生产商资本物品生产商n金融市场金融市场（2）消息传递技术）消息传递技术主体分布在不同的计算节点上主体分布在不同的计算节点上将连续的时间划分为离散的时期（天），每天又划分将连续的时间划分为离散的时期（天），每天又划分为为11个阶段个阶段多数行动每天只发生多数行动每天只发生1次，且在特定的阶段发生次，且在特定的阶段发生每个主体有一个消息队列，用于存放收到的消息每个主体有一个消息队列，用于存放收到的消息消息分发过程消息分发过程（3）主体之间的交互）主体之间的交互（4）各类主体的行为）各类主体的行为 家庭主体家庭主体14个个人