复杂适应系统的博弈分析研究

复杂适应系统的博弈分析研究

李振龙

（中国科学院自动化研究所智能控制与系统工程中心，北京%"""’"）

F>0792：A.9829I;/EJ$./0

摘

要

复杂适应系统理论是复杂系统理论的一个崭新的研究方向，复杂适应系统是很普遍的复杂系统。该文通过分析

复杂适应系统的特性，用环境、资源、智能体、流四要素来描述复杂适应系统，并从智能体的竞争>合作关系出发，应用博弈论的相关知识对复杂适应系统进行了分析研究，文章最后以城市交通系统为例进行了分析说明。关键词

复杂适应系统

智能体

演化博弈

微分博弈文献标识码5

中图分类号KL%’

文章编号%""!>’##%>（!""#）%#>""!G>"-

!"#$%&’()’*+,-.!%/+#01-"&2#-*3/2-%’4#5-6/*-75-’8&

90:5-4,’4;（KE3,A83229C3A8=/A8D/27A6*<;830;FAC9A33D9AC=3A83D，,A;898J83/M5J8/0789/A，

=E9A3;35.7630</M*.93A.3;，N39O9AC%"""’"）

!<2#8/=#：KE38E3/D</M./01234767189:3;<;8309;/A3/M8E3A3P3;863:32/103A8;9A8E38E3/D</M./01234;<;830，

7A68E3./01234767189:3;<;8309;:3D<./00/A./01234;<;830$FA:9D/A03A8，D3;/JD.3，7C3A87A6M2/P7D371129368/63;.D9Q38E3./01234767189:3;<;830，PE9.E9;;8J6936Q7;36/A8E3C7038E3/D<MD/08E31/9A8:93P/M8E3./0138989/A7A6.//13D789/A/M7C3A8;$5827;8，8E3JDQ7A8D7MM9.;<;830，7;7A3470123，9;7A72<R36$>-&?’8%2：=/01234567189:3*<;830，5C3A8，F:/2J89/A7D<B703，S9MM3D3A8972B703

%前言

人类正面临着生态、环境、政治、经济、社会、军事等各种各

!复杂适应系统的特点和复杂性

与其他复杂系统相比，复杂适应系统的独特特点在于组成

样的复杂性问题的挑战，面临着诸如物理系统、人脑系统、生物系统、互连网系统、交通系统、军事系统、经济系统、社会系统等各种各样的复杂系统的挑战。复杂系统已成为前沿研究的焦点，在!%世纪的科学发展趋势中，复杂系统的研究将占据重要的位置。复杂性问题的提出起源于奥地利。%&!’年，贝塔朗菲在他撰写的《生物有机体系统》一文中首次提出了复杂性问题，钱之后，许多科学家对此进行了多方面的研究并做出了贡献(%)。学森教授于%&’&年提出了开发的复杂巨系统理论

(!)

单元（个体）众多，个体具有适应性、智能性、主动性、并发性、随

?，&)

：机性，并由此特点带来了其独特的复杂性(G，

!$%基于个体适应性、智能性的复杂性

由于具有适应性和智能性，个体会根据环境来调整自身的

状态和行为，并且个体能够辨识环境，预测未来，在经验中学习，以形成新的行为规则，使自身发生适应性变化。同时通过个体相对低等的智能行为，系统在整体上显现出更高层次、更加复杂的智能行为，因而必定是复杂的。

，!"世纪

-)

美国圣塔菲研究院（提出复杂适应系统理论(#，。&"年代，*+,）

!$!基于个体主动性、并发性的复杂性

不同个体之间、个体与环境之间互动互应（所有个体都既

复杂系统研究是当前系统科学的主要研究方向之一，复杂适应系统（是一类很具有代表./01234567189:3;<;830，=5*）性的复杂系统，它的基本思想是：系统的复杂性起源于个体的适应性，系统中的个体在与环境和其它个体的交流中不断进行着演化学习，并且根据学到的经验改变自身的结构和行为方式，在整体上突现出新的结构、现象和更复杂的行为(#>?)。对于这样一类系统，@/227A6教授在他首先提出的遗传算法（B3A389.基础上，建立了所谓“回声”（模型，用于模拟和52C/D98E0）F.E/）研究一般的复杂适应系统的行为。作为复杂系统中的重要的一类，复杂适应系统的建模和研究目前已经成为一个热点。该文在总结分析复杂适应系统的特点和复杂性的基础上，用环境、资源、智能体、流四要素来描述复杂适应系统，主要应用博弈论

(H，’)

(G)

是主动作用者，又是被作用者），系统中的个体并行地作出决策，每个个体的决策不仅要考虑过去和当前的状态，还要考虑其他个体的行为，系统的整体行为源于这些个体间的竞争、合作等局部的相互作用。这样一连串的、网络式的相互作用与影响就会产生复杂性。

!$#基于个体随机性、模糊性的复杂性

由于个体的差异必然会出现随机性、模糊性。物理系统随

机性的规律可用大数定律进行分析处理；然而经济系统、社会系统等却不能，例如，不可能从个人特性出发通过统计获得整个社会系统的特性，模糊性可表现在个体的信息、策略和状态等方面。这些随机性和模糊性必然会带来复杂性。

以上是复杂适应系统的独特复杂性，除此之外，开放性、突现性、非线性等也是复杂适应系统的复杂性根源。

的相关知识对复杂适应系统进行分析研究。

基金项目：国家杰出青年基金（编号：?"%!G#%"）

，）

计算机工程与应用!""#$%#!G

#复杂适应系统的描述

为了描述这样的系统，就需要从各个层次和各个方面对复

杂适应系统进行分析，弄清复杂适应系统内部的差异和联系，揭示复杂适应系统各部分的关系，选择最能代表复杂适应系统的结构、性状和运动的信息，从而更准确地描述复杂适应系统。复杂适应系统具有大量的基本组成单元，这些单元之间存在着复杂的相互作用和相互影响，该文用环境、资源、智能体、流四要素来描述复杂适应系统。其中：

是系统所处的情况，任何系统都是处于一定环境环境（’）中的，或说都有其边界条件。系统的环境是系统的外在约束之一；

资源（是系统中一切可利用的物质资源和精神资源等，(）例如信息资源、土地资源、水资源、道路资源等等；

是具有适应性、自主性、移动性、协作性，有思智能体（)）维能力的基本单元。每个智能体都拥有一定的信息和知识（；*）每个智能体有他自己可能的策略或行动的集合，一个智能体的全部可行策略称为它的策略空间（；每个智能体都有自己的+）盈利（。信息知识、策略空间、盈利共同构成智能体的状态-，,）

#

)（*"）+!-"’（*"，*,）%,%%"+!-)（)*"）"$"%

"）)（*"）/)-"（%.-"+%

")&

其中：

-"表示智能体选择纯策略*"的概率；

（#）

表示智能体采用策略*"，其对手采用策略*,时的’（*"，*,）收益；

表示智能体采用策略*"的适应度函数；)（*"）

方程（描述了智能体策略行为的动态调整过程，根据方#）

程（可以画出系统相图进行分析研究。在系统的发展过程中，#）

每个智能体可以选择不同的策略，并因此获得相应的收益（适应度），经过一段时间的演化后，一种策略行为的采用会引起其收益（适应度）的增加或减少，从而使智能体根据“适者生存”的原则发生演化，由此可以分析某种策略行为的长期结果。而获

%!，

得这种长期结果时智能体所采用的策略是演化稳定策略8%"，%#:，演化稳定策略的基本思想是：如果某一策略是演化稳定策略，那么个体采用它的适应度函数就会大于采用任何可能的突变策略的适应度函数。演化稳定策略的数学定义如下：

如果

（’（0，0）1’（0，2）97B）

或

且’（（’（0，0）+’（0，2）0，2）1’（2，2）97F）

那么0为演化稳定策略。

复杂适应系统的发展过程是智能体演化博弈的过程，是智能体策略行为的动态调整过程。当智能体采取演化稳定策略时，系统也达到一种相对稳定的状态，即演化稳定状态。因此，可以通过分析智能体的相互作用寻求演化稳定策略，研究群体达到均衡的行为调整过程，研究个体行为到集体行为的形成机制，从而分析研究复杂适应系统的发展。

-./*，+，,0；

智能体的状态是随时发生变化的，记在时刻1的状态为-（，在时刻12%第3个智能体的状态是由时刻1的第3个智能1）

体、与其有相互关系的4个智能体的状态以及一定的资源环境所决定的。

，，，…，，!"（#$%）.%（!"（#）!%（#）!!（#）!&（#）’，(）能量流动、信息传递等。

上述四要素就构成了整个复杂适应系统，即：

（%）

流（是指智能体之间、智能体与环境资源间的物质循环、5）

6)+./’，(，)，50（!）

在系统的发展过程中，智能体的聚集&形成更高一级的主体7介主体，介主体再聚集，产生介介主体，这个过程重复几次后，就得到了复杂适应系统的层次结构89:。

9$!

9

基于博弈论的复杂适应系统的分析研究

复杂适应系统的内容广泛、关系复杂，在各个智能体或智能体与周围的环境之间进行物质、信息和能量的交换过程中，必然会产生竞争与合作，这样智能体之间就会产生博弈，该文就是以这个博弈关系为出发点分两个部分分析复杂适应系统：系统发展过程的分析和系统控制优化的分析。

基于微分博弈的系统控制优化的分析

9$%基于演化博弈的系统发展过程的分析

任何系统的发展与运动都是有动力或目标的，复杂适应系

认识复杂适应系统是为了更好地控制和优化它，使其具有人们希望的功能，令其向人们所希望的方向发展。而复杂适应系统由众多具有不同目的和利益的智能体组成，它们的行为是互动的，它们的状态和策略是动态的，因此对复杂适应系统的

%G:

控制优化采用由博弈论和控制论相结合而产生的微分博弈8%9，来进行分析研究。微分博弈起源于军事上的需要，现在已被广泛应用于社会、经济、生态环境等各个方面。;个智能体3"的微分博弈为：

统发展的动力源于每个智能体的适应性、主动性、智能性。复杂适应系统的每个智能体都有一定的认知能力和学习能力，整个复杂适应系统的发展都有其知识论基础和智能特性。每个智能体不是完全理性的，也不是严格按照效用最大化进行决策，在多数情况下是通过了解博弈的历史，通过学习模仿，动态调整决策，并且智能体在相互作用中不断学习、积累经验。一组组单个的智能体在寻求相互适应中不断发展，从而推动了整个复杂适应系统的发展。

假设复杂适应系统存在一个智能体数为;的大群体（<=>?，其中;是一个充分大的数。群体中每个智能体都有相@AB13=C）

同的纯策略集合（行动集）+D./E%，E!，$$$，ED0。由演化博弈论

&

4./3，5，60*

%…，5./7%，7!，780%…，6+/6，6，680%%!%%.+%（…，#，9，7%，7!，78）$9

#"）.9"%9（%

((…，）6"（7%，7!，78）.:"（#，9（#）2%

%(

%#;（，，，…，）#，9（#）7%（#）7!（#）78（#）H#&#"

’

（G）

)

"

其中：

（%）7"为局中人3"的控制函数；

8%"，%%:

有：

%$!I!""#$%#计算机工程与应用

（!）!（"）#!"&

，，，…，）!，!（!）&（!）&（!）&（!）’!为相!$（

"""%

%

!

’

约束条件：

’

’

&&

2!3（8）

’

（）（）2"#98’".

2!:（8）

&7

’2

（"）（F4;）（F4’）

…，应于&%，&!，&’的轨迹。

"$$（）相应于控制函数#）"#()*+#",（"，!（"）!(-称为轨迹!（"）

…，称为&%，&!，&’的捕获时间。(是.""，)"/0*空间中的闭子集，

+

（!2（"）""，&2（"）""，2!3，’!;，"!."，)/其中：

;表示网络节点的集合；

路段）的集合；3表示有向弧（

表示"时刻路段2上的流量；!2（"）

目标集或终端集。

""…，）（1）,%（&%，&!，&’）2-%（"，!（"）.

（，…，）居中人0%的支付泛函。"）&’（"）’"，

，，"，!（"）&（"）&%/（

""""

%

%

!

）表示车辆在路段2上的出行时间；42（!（"）表示"时刻路段2上的流入率；&2（"）表示"时刻路段上2的流出率；72（"）表示"时刻节点8产生的出行量；98’（"）表示进入节点8的路段集合；3（8）表示离开节点8的路段集合。:（8）

驾驶员为实现自己的目的而希望使车辆在路口的延误时间尽可能小，可用下面的模型表示，该模型的含义是使各个路口的车辆的延误最小：

目标函数：,<#

2

居中人的目的就是选取控制函数（策略）使其支付取得极值。微分博弈分为定性微分博弈、模糊多目标微分博弈、分层递阶微分博弈等.%3/。定性微分博弈不研究支付泛函的极值，而研究某些结局能否实现；模糊多目标微分博弈主要研究模糊性出策略集等时的情况；现在支付函数、状态方程（组）、目标集(、分层递阶微分博弈是一种重要的微分博弈，同一层次可以采取合作、非合作、协商谈判等方式参与博弈优化，不同层次采取主从策略、诱导策略、激励策略等进行博弈优化。

应用微分博弈进行控制优化复杂适应系统关键是要针对系统的特点和具体情况正确选择上述不同的微分博弈类型和解的概念。如果只分析复杂适应系统中个体在博弈中的结局能否实现，就用定性微分博弈和界栅理论；如果分析复杂适应系统中多层次多目标的决策问题，将根据具体的层次和个体的数量可用一主多从微分博弈、多主多从微分博弈和多层递阶微分博弈来进行分析。

8#%

&!=

)"?

;

8

（）>（"）’"

2

（G48）（G47）（G4;）

22182?

5（）（）（）状态方程：>"#&"6#&"6"982，88898

82，

约束条件：>8（"）""

2

"#1()*#18#1(8H

其中：

8，228，2

（8!;，"!."，)/）（G4’）

3示例4城市交通系统的控制优化

随着经济的飞速发展，城市化进程的加快，城市交通矛盾

8表示路口号；4表示信号周期；

18表示路口8的绿灯时间；"8表示路口8的绿信比；

表示以路口8为终点路段2上的等待车辆数；>8（"））表示车辆在路口8的等待延误时间；=8（>（"）

（）表示进入以路口8为终点路段2的等待区的流入率；&2，

8"

将式（和（结合在一起就得到如下的交通控制优化的F）G）

（E）

微分博弈模型：

?22’5（）（）>"#&"6"82，898)8

’

’’

(5（!"）#&（"）67（"）?222

日益突出。如何控制、优化整个交通系统便是向人们提出的挑战。城市交通系统（是一个复杂适应系5678*968::);<=>?@(）统，它由交通管理部门、机动车辆、自行车、行人、道路、路口控制器等以及一定的经济环境组成，按照对复杂适应系统的描述，将交通管理部门、机动车辆、自行车、行人、路口控制器都视为智能体，并具有各自的状态（包括信息知识，策略，盈利），用下面的公式表示城市交通系统：

59<2+A，B，C，D-其中：

交通规则-A2+社会经济条件，

桥梁，其他设备-B2+道路，

车辆，自行车，行人，路口控制器-C2+交通管理部门，

D2+交通信息的发布等-

整个交通系统中，每个智能体有着各自不同的目的和利益：交通管理者希望整个交通通畅；每个驾驶员或行人只从个体的角度出发，追求自己的效用最大化。他们的行为是互相影响的，它们的状态和策略也是动态的，因此对交通系统的控制优化采用微分博弈进行讨论。

交通管理者为实现自己的目的而通过交通诱导将交通需求进行合理配置，改变交通网络的流量模式，尽可能减小车辆的总的行程时间，可用下面的模型表示，该模型的含义是使系统总的行程时间最小.%E/：

目标函数：,1#

’

+

))

222

)2’’)>%（"）2"!2（"）""&2（"）"")*

,;)

)）,<#&=8（>（"）’"

"8#%)

))

)）,1#&42（!（"）’"

"2!3-

2

%

（I）

%

该模型的总体思想是交通诱导系统应用一定的诱导策略将交通流诱导到合理的路网上，由交通控制系统应用一定的控制策略来适应这些交通流，使交通管理者和驾驶员的利益都得到满足。该模型的求解将另文讨论。

）!（"）’"&!4（

)

2!3

"

2’

’

E

（F48））

结论

该文以个体的博弈关系为出发点，应用演化博弈和微分博

弈对复杂适应系统中个体间的合作与竞争进行了分析，指出复计算机工程与应用

5!）#&2（"）67"2

!""#$%#!F

对复杂适应系统的控制优化可采用微分博弈，当然对复杂适应系统的研究用一种理论是远远不够的，必须使用各种相关的理论和知识根据系统的具体情况进行研究探索。（收稿日期：!""#年%月）

参考文献

：%$王正中$复杂系统仿真方法及其应用>?@$计算机仿真，!""%；%M（%）#ED于景元，戴汝为$一个科学的新领域———开放的复杂巨系统!$钱学森，

：及其方法论>?@$自然杂志，%BB"；%#（%）#E%"

#$?4P’FF4&&2’/$F:/0’47/07：F4H2/28929:4’X6:&/<G418&0]:9L>3@$+//&<4’-I0<&0L86=&:<P:’JG4182’L，%BB(

隐秩序，周晓牧等译>3@$上海科技教育出版社，C$霍兰，!"""

：($谭跃进等$复杂适应系统理论及其应用研究>?@$系统工程，!""%；%B（(）

%ED

内容与启示>?@$系统辨证学D$陈禹$复杂适应系统理论及其应用-由来、

学报，：!""%；B（C）#(E#BV$3+NRQ*?[AX[N*\，+NQ\.NYXQ*AR\Q*著$魏玉根译$博弈论教程>3@$中国社会科学出版社，!"""

博弈论$上海财经大学出版社，M$施锡铨，!"""

B$苗东升$论复杂性>?@$自然辩证法通讯，!"""；D：MVEB!

%"$?4P’32L’27/A1:9P$\K4&69:4’2’/9P0RP047L4;O210<>3@$G21-%BM!=7:/J0Y’:K07<:9L,70<<，

%%$贲金锋$市场行为的进化和控制—一个出租车市场的例子>?@$系统工程理论与实践，（%BBM；V）

均衡与演进博弈论>?@$南开经济研究，（：%!$李军林$理性、!"""；C）CME(!

（：%#$张良桥$进化稳定均衡与纳什均衡>?@$经济科学，!""%；#）%"#E%%%

H:&0LQ’907<5:0’50，%BV%%C$S7:0/12’+$):;;070’9:2&O210<>3@$*0HT47U，

!"""%($李登峰$微分对策及其应用>3@$国防工业出版社，

%D$陆化普$动态交通分配理论的回顾与展望>?@$公路交通科技，%BBD

（上接D页）

化。由图#还可看出，图!中的圆的,G**细化结果很好地保留了原始圆的圆心与大小的信息，而若用其他的一些算法，如骨架法>%@，圆则被细化成一点，从而丢失了大小的信息。图C为一文字，图(为图C的,G**细化结果。由图(可看出，用提取其骨架，取得令人满,G**可有效地进行二值图像细化，意的结果。

而迅速地对各种形状的二值图像进行细化，提取其骨架。,G**发出的脉冲可快速而并行地传播，使得细化的过程非常迅速。同时，给出了脉冲相遇判为细化结果的条件及细化完成的条件，从而用该算法可自动地进行二值图像细化。另外，该文的研究进一步拓宽了有视觉生物学背景的,G**在图像处理方面的应用范围。（收稿日期：!""#年%月）

参考文献

董海，周文灵$计算机图象处理技术基础>3@$第一版，北京大%$张远鹏，

学出版社，%BBD：%#ME%CM

!$N\5UP47’，F?N0:9=405U，3+7’/9092&$S029670&:’U:’JK:2<L’5P-74’:Z29:4’214’J/:<97:=690/2<<01=&:0<：A:16&29:4’4;70<6&9<;741529：54790]>?@$*0672&G4186929:4’，%BB"；!（#）!B#E#"V

图!

一较复杂的二值图像

图#

图!的,G**细化结果

#$?.?4P’<4’，3.,2/J099$,G**14/0&<2’/288&:529:4’<>?@$Q\\\R72’<：4’*0672&*09H47U<，%BBB；%"（#）CM"ECBM

郭仕德，余道衡$一种基于,G**的图像去噪新方法>?@$电子C$顾晓东，

与信息学报，：!""!；!C（%"）%#"CE%#"B

($O^6’9:12/，FAN2’J2’29P$,07;059:12J0<0J10’929:4’6<:’J86&<05468&0/’0672&’09H47U<>?@$Q\\\R72’<4’*0672&*09H47U<，%BBB；%"（：#）(B%E(BM

O^6’9:12/$[=_059/09059:4’6<:’J86&<05468&0/D$FAN2’J2’29P，

图C

一文字二值图像

图(

图C的,G**细化结果

：’0672&’09H47U<>?@$Q\\\R72’<4’*0672&*09H47U<，%BBB；%"（#）

D%(ED!"

V$F?526;:0&/，?3^:’<07$S:’/:’J<P4790<9829P:’9P0<P4790<99:10：6<:’J,G**‘<>?@$Q\\\R72’<4’*0672&*09H47U<，%BBB；%"（#）D"CED"D

(结论

文章根据,G**的脉冲传播特性，首次提出了基于,G**

)N:9907$[=<07K29:4’4;807:4/:5H2K0<:’286&<0-5468&0/M$?.?4P’，

：’0672&’09H47U>?@$[89.099，%BB#；%M（%(）%!(#E%!((

的二值图像细化算法，计算机仿真结果表明，用该算法可自然（上接!%页）

法的时间复杂性是!（。"&’"）

命题!在一个出度和入度不超过!的有向线图中，能在多项式时间内找到最优的欧拉路（或圈）。

参考文献

%$+.+/&012’$34&056&275418629:4’4;<4&69:4’<94541=:’2947:2&874-：=&01<>?@$A5:0’50，%BBC；!DD（%）%"!%E%"!#

!$FG74H/07，3I,2/=07J$A4&K:’J&27J0-<52&0<L11097:5972K&:’J<2&0<%BM"；!D：CB(E("B12’874=&01<94489:1:2&:9L>?@$32’2J010’9A5:，

#$3NO720L，)A?4P’<4’$G41869072’/Q’972592=:&:9L--+O6:/0949P0RP047L949P0*,-G418&090’0<<>3@$S70012’，*0HT47U，%BVBC$)O6<;:0&/$+&J47:9P1<4’<97:’J<，R700<2’/A0W60’50<：G4186907G21=7:/J0Y’:K07-A5:0’502’/G4186929:4’2&X:4&4JL>3@$G21=7:/J0，<:9L,70<<，%BDV

($AF2’’0’P2&&:，IS0&&4H<，F.0H:<092&$,4<:9:4’2&<0W60’5:’J=L+88&$X:4A5:，%BBD；%!：%BE!CPL=7:/:Z29:4’>?@$G41869，

?GN425P，G32J’0<<092&$[,9:1:Z29:4’4;70<97:59:4’D$+SA:0J0&，

X:4&，(）(结论

在)*+计算中，其基本思想是借助于实验的手段来解决

实际中的大量*,-完备问题。这种实验的手段有其长处，也有其不足之处。事实上，人们更关心实验中的某些现象的数学本质。通过给出的算法，能在多项式时间内找到最优的哈密顿路（或圈），但在什么条件下该有向哈密顿路（或圈）才是唯一的？这是一个尚未解决的问题。同时，根据该文所建立的旅行售货员模型，发现所构造的线图#（还有其内在的代数结构。限于

$）!M!""#$%#

计算机工程与应用