复杂自适应系统研究

来源:系统科学进展时间:2020-08-19


John Holland

摘要:复杂自适应系统(CAS)——由很多通过相互作用而相互适应和学习的组成部分构成的系统,它是很多当代重要问题的核心。针对CAS的研究存在着独特的挑战:一些最强有力的数学工具,特别是不动点、吸引子等类似方法,对理解CAS的发展演化只能提供很有限的帮助。本文建议改进研究方法和工具,特别强调用基于计算机的模型去加深我们对CAS的理解。

关键词:基于自主体的系统,分类器系统,复杂自适应系统,基于计算机的模型, 信誉分配,遗传算法,并行性,规则发现,信号传递,标签。

当代很多困难问题的核心就是复杂自适应系统(CAS)问题。CAS指包含大量被称为自主体(agent)的组成单元所构成的系统,它们之间相互作用、适应和学习。下面列出的一些问题展示了CAS的普遍程度:

    ·动态演化经济系统内的创新激励;
    ·对人类可持续发展的支持;
    ·预测全球贸易中的变化;
    ·对市场的深入理解;
    ·为生态系统提供保护;
    ·控制互联网(例如控制病毒和垃圾邮件);
    ·增强免疫系统。

尽管在细节上有本质不同,各种CAS都具有如下四大共同特征:

(1)并行性。CAS包含大量的通过发送和接收信号相互作用的自主体。进一步,自主体同时互动,产生了大量的并发信号。

例如生物细胞使用蛋白质作为信号。这些蛋白质操控反射级联和回路,为其它级联和回路提供正反馈和负反馈。这些蛋白质的相互作用必须紧密协调以使得细胞能持续正常工作。

(2)基于条件的行动。CAS中自主体的行动通常取决于它们收到的信号。这就是说,自主体有一个IF/THEN结构:IF[信号向量x出现]THEN[执行行动y]。这个行动本身可能是一个有可能导致形成非常复杂反馈的信号,或者是自主体在环境中的一个行动。

这个信号一处理规则组成的连锁序列成为可以并行运行的程序,具有灵活性和广度。

(3)模块性。在一个自主体中,一组规则通常组合在一起行动形成“子程序”。例如,自主体通过执行一系列的规则能够对目前的情形作出反应。这些“子程序”形成了积木模块,它们组合起来能够应对新情况,而不是分别用不同的规则来应对所有不同的情况。因为潜在有用的积木会经常被测试,所以对更大范围的情形,他们的有效性是会被快速证实或者排除的。

例如在生物细胞内,三羧酸(Krebs)循环是由8个相互作用的蛋白质形成的一个反应环。这个三羧酸循环是所有氧生物体(从细胞到大象)的一个基本组成部分。

(4)适应和演化。CAS里的自主体会随着时间而改变。这个改变通常就是适应,从而改进性能,而不是随机的变化。适应性要求解决两个问题:信用分配和规则发现。

信用分配问题的产生是由于有关性能的公开信息(报酬,回报等类似概念)通常是非常规的和局部的。这就是说,一个自主体的性能是时空上错综交杂的相互作用的结果。能因信息可以明确地指出哪个“状态配置”能取得最终的性能改善的情况是少见的。

策略类博弈,例如围棋或者象棋,提供了一个有用的隐喻。在一长串行动后,博弈者会获知自己是“赢”还是“输”,或者是输赢的大小。但是他在整个博弈行动序列中很难得知哪个“状态配置”的行动是对结局至关重要的。那么,问题来了:如何判断哪些状态走步会对将来的博弈有借鉴作用呢?类似的,对于一个生物细胞来说,繁衍作为一种“回报”,是通过成百上千的蛋白质日日夜夜信号传递相互作用的结果。

规则发现这个问题产生于一些自主体的规则是明显无效或有害的情况下。此时用随机生成的新规则来代替这些无效的规则是行不通的,这类似于在计算机程序中随机插入的一些程序语句。而我们的目的是产生基于自主体经验的合理的新规则。

在解决规则发现这个问题中,还有一个有助于降低问题难度的特性。尽管CAS具有永恒的新奇性,它也有类似于棋类游戏中的那些不断重复的子模式。在国际象棋中,这些子模式有“击双”、“牵制”、“开局”等。在CAS中这些子模式构成积木可以被重复搭建利用。换句话说,产生合理规则的关键是在已经成功使用的好规则中发现积木模块。这是一个重要的问题,将在文章后面部分讨论。


1.什么是研究CAS的技术?

研究CAS的第一步,是挖掘几个相关的常用研究方法的共性:

控制论       经济学      生物细胞          博弈
过程变量   经济活动   表现型特征       棋局
操作代价   活动代价   新陈代谢代价    棋局评估
目标函数   收益          适应性              回报
控制律      规划          相互作用网络    策略

第一行是系统状态的形式化刻画,第二行是系统中每种行动的代价费用,第三行是对预先设定的目标给出数值,而最后一行是引导系统达到目标的技术手段。

这些相似性立刻展示了运用学科交叉的方法来研究CAS的价值。每个形式化系统概念都是多年深入研究的结果,并且各项都具备长处和短处。比较这些不同形式系统的相关部分,我们可以找到与CAS研究相关的部分,从而能从对系统的研究历史中获得经验,避免重蹈覆辙。
所有这些形式化刻画的共同特点是对微分方程的依赖,特别是偏微分方程。然而,偏微分方程对于CAS的研究具有局限性。自主体的条件性(IF/THEN)行为意味着一个自主体的行为并不能用偏微分方程的简单线性近似来刻画,而这种线性化近似是偏微分方程的强有力方法。用偏微分方程去刻画IF/THEN行为就像是试图用偏微分方程来刻画电脑程序。

因为自主体的规则是不断变化的,这就导致了研究困难的加剧。自主体很少达到均衡态,因为基于条件的规则组合、常规创新和永恒的新奇性会破坏吸引子的形成。最优的和稳定的状态最多是在一个特定情景下短暂存在。另外,自主体能像天气预报中的常规更新那样持续地修改和更新它们的信息,因此混沌效应只会偶尔影响系统。

简单地说,偏微分方程这个最强大的理论工具只和CAS的一小部分内容相关。类似的,标准的统计分析例如回归和贝叶斯网络也是这个情况。传统的还原论方法f研究每部分,然后把每部分的行为加起来还原整个系统的行为)并不能有效地解决问题。我们必须要研究每部分之间的相互作用。

基于这种考虑,我们转而应用其它的技术来为CAS建模:探索性的计算机模型。探索性的计算机模型和传统的物理思想实验有很多共性,其中之一是它们都要选择一些有趣的机制,仔细配置运行条件,然后探索由这些机制相互作用所产生的结果。这些配置通常不能在实验室实现,只能在头脑中实现。

可编程计算机极大地提高了这些思想实验的实现可能性。使用一台计算机,这些探索模型就可以被严格描述,并可以不受思考偏见影响而运行。值得指出的是,在过去,可执行计算机模型的定义和执行甚至比数学证明更严格。在数学证明中,我们用约定的简化表达式和快捷方式,从而不需要把每步推理都写出来。否则的话,即使是最简单的证明都会变得无法忍受的长[1]然而,计算机程序中的每一步必须被明确地指定,否则程序不能如愿运行。当然,可执行计算机模型通常会定义一些特殊的情形,这样它可以在数学证明和实验室实验中走中间路线。

作为思想实验,探索性的计算机可执行模型定义了可能性,而不是现实。它们帮助我们建立对这些定义在程序中的机制及其相互作用的直觉。这是研究CAS的至关重要的一点,因为基于条件的相互作用是CAS中非常重要的部分。即使简单的机制和简单的相互作用也会产生复杂行为。让我们再次考虑国际象棋和围棋:游戏规则定义了对应的机制,即使规则的数量少于一打(12个),也能产生一个具有永恒新奇性的系统。尽管已经探索了几百年了,我们仍然在这些博弈游戏中不断地发现新模式和策略。对一个CAS来说,定义一个自主体行为的规则与博弈中的规则无异。


2.自主体定义

为了形式化地研究CAS,我们必须提供一个精确定义自主体及其相互作用的方式。在这个模型中,每个自主体有一组条件性(IF/THEN)的信号一  传输规则。其中的IF部分是定义规则中寻求的某种信号,如果这些信号出现了,THEN部分定义的信号就被传输出去。

更具体一点,IF部分由一组条件组成,每个条件是定义了一类信号。如果条件中任何一个被定义的信号出现,这个条件就被满足。如果一个规则中的所有的条件都被满足,那么这个规则就被满足。因为有可能很多规则被同时满足,所以它们必须竞争以使得自己的THEN部分定义的信号能被发送出去。更进一步,不只一个规则会赢得这个竞赛,所以有多个规则会同时发送信号。系统内部具有冲突的规则并不是一种危害,因为额外的被激发的规则只是简单地发送额外的信号。这个“并行性”是一个重要的特性:一个自主体能通过一组规则的组合来构建自己的行动,而不是对每一个情形都要一个单独特定的规则来指定行动。这种信号传输系统的形式化描述被称为分类器系统(classifier system,简称cfs)[2]。

发出去的信号被存储在一个信号列表里。形式上,这个信号列表是自主体的内部状态。一个自主体的行为策略完全由它的规则集决定,它在任意时刻的行动由它的信号列表里的信号决定。一个信号储存在信号列表中的时间是一个时间步。想要这个信号保持在信号列表里,必须由胜出的分类器不断地发送这个信号。也就是说,系统要像电视机图像一样,需要在每个时间步不断地刷新信号。

虽然在信号列表内的大部分信号是在内部产生的,但是仍有一些信号是通过自主体的感知器从环境中采集而来的。有些信号列表中的信号会激发效应器产生行动。因此,自主体内部的策略系统和自主体与外界自主体的交互,都是通过信号这个中介。一个特殊的基于分类器系统的自主体,有五个主要要素:

(1) 一个关于分类器的列表。
这个列表会随着自主体对环境的适应而通过不同的途径进行更新。
(2) 一个关于信号的列表。
这个列表在每个时间步都会根据竞赛中胜出的分类器输出来进行更新。
(3)一组感知器。
感知器把从环境收集到的信息编码成信号。
(4) 一组效用器。
效用器有使用条件,像分类器一样,当信号满足条件才会被激发。当它的行动被激发,自主体就会行动从而改变环境。
(5)一组仓库。

仓库定义了自主体的“需求”(相当于食物、居所等等)。当某些效用器在合适环境中被激发而行动,会满足和填充某些仓库。在一些典型的模型中,仓库的库存会以恒定速率被消耗。当一个仓库接近空,一个“低库存信号”就会持续出现在信号列表上。自主体填充仓库的效率可以看作性能的衡量指标。由此定义了一个隐式的适应性。


3.分类器的形式描述

一个基于计算机模型的分类器系统需要合适的语言来描述分类器。为了论述简单起见,尽管分类器系统有很多不同的版本,但我会使用一个特别简单的版本。在这个版本里,所有的信号都是长度为k的字符串,每个位置上包含一个字符,字符从{1,0)中取值。例如,如果k=5,一个可能的信号会是11010。所有可能的信号组成的集合表示为A={1,0}k。类似地,所有可能的条件组成的集合C={1,0,#}k,它是字符集{1,0,#)上所有长度为k的字符串。一个分类器规则的条件部分有一个条件,即c∈C,或者两个条件,即c∈C和c′∈C。分类器的Then部分是一个信号a∈A。一个规则可以写成c/a(一个条件的规则)或者c,c′/a(两个条件的规则)。我会着重论述两个条件的规则。

[讨论带有多个条件并且长度可变的信号不难,但是会使我们的论述复杂化。有意思的是,我们这里讨论的受限系统仍然是具有计算完备性的。]

如果下列条件成立,则条件c∈C被信号m∈M满足:
(1)在c的每个具有1的位置,信号m在该位置也是1;
(2)在c的每个具有0的位置,信号m在该位置也是0;
(3)在c中具有#的位置,对信号m该位置上的字符没有要求(这就是说,这个对应#字符的位置具体是任意字符都是“无所谓”的)。

例如,当k=5,信号10011满足条件1####和10#11,但是它不满足条件0####或者10111。

3.1  规则强度(信用分配)

每个分类器规则都有一个强度值来表示这个规则过去在整个分类器系统(CFS)中的贡献大小。
分类器中的强度值更新有两种途径。当一个效用器被激发执行从而填充仓库的需求时,发送信号激发这个效用器的分类器的强度值都会增加。所有强度值的改变都是通过在整个分类器系统——这个被认为是某种意义上的市场里竞争的结果。每个分类器被看作是这个市场里的一个中介(经纪人)。在任意给定的时间,一个分类器的“供给者”是那些发送满足这个分类器条件的信号的其它分类器。当一个分类器赢得竞争时,它就是那些发送满足它条件的信号的分类器的“消费者”。

更细一步,一个分类器碰到满足自己条件的信息时,它会根据自己的强度来竞价,把自己的强度当作手里的现金。最高的投标者会赢得这个竞赛,并必须以标价“付费”给它的供给者。接着,这些赢家可以根据自己的分类器把输出信号放在信号列表上。为了让自己的强度增加,它必须找到买家以高价购买它输出的信号,从而获得更大的回报来填补之前的支付。总的来说,这些规则必须“赚钱”。这个过程被称为“传递水桶算法”(详情见参考文献[4])。这个算法的巨大优势是,这些规则不用回溯,因为这些交易都是局部的。

3.2规则发现

在这些模型里,规则被当作自主体对环境的初步假设,包括在环境中对其它自主体的假设。作为一个假设,一个规则会被后续事件的结局而逐步肯定,或者被逐步否定。这就是说,被确定的规则会更有能力和其它规则竞争,而被否定的规则会逐步被减弱。

规则发现的目标是产生新的假设(规则)去替换那些被否定的规则。这些新规则必须是基于前面经验的合理假设。在这一过程中,用随机的方式去产生新规则是疯狂的、难以置信的做法。它的成功率和在计算机程序中插入随机新指令的做法差不多。

一个产生貌似合理的新规则的直接方法是使用遗传算法。遗传算法把强度大的规则当作父母,通过交叉产生后代。这些后代规则组合了父母辈的优点,就像人工培育优良马种和优良玉米品种那样。

3.3总结

这个分类器系统的基本运行周期如下:

(1)所有从环境发出的信号经过自主体的感知器进入并被加入到该自主体的信号列表;
(2)所有的规则会检查信息列表上的所有信号,看看哪个规则能够被满足;
(3)信息列表中的所有信号都被删除;
(4)条件被满足的规则根据自己的强度竞价,参与竞争,胜出的规则发送(THEN部分定义的)信息到信息列表上;
(5)用传递水桶算法来调整胜出规则的强度;
(6)使用遗传算法来生成新规则替换强度弱的规则;
(7)更新环境,包括被信号激发的效用器对环境产生的影响变化。
(8)回到步骤(1)。

模块化(即一组子规则)可以通过标签来实现。标签是信号中的一部分,一组相关规则的满足条件中都有相同的标签。当一组拥有公共标签的规则协同工作时就会产生模块性效果。从这个角度来说,标签就像因特网上的信息标头( header)。因为规则会被遗传算法改造,标签使得模块能在系统演化适应过程中出现[6]。这就是说,会生成一些具有格式IF(带有合适标签的信号出现)THEN(发送具有那个标签的信息)的规则。在生物回路里,标签就像主题( motif),用来标记和调整各个模块。通过增加或者减少一个模块里的分类器规则的条件字符串里的#符号来提高或者降低激活这个模块的条件的精确度。

这类基于规则和信号处理的系统已经在不同的背景中得到检验。感兴趣的读者可以在参考文献[7]中找到更多关于分类器系统的细节。

4.挑战 

看起来尽管我们没有“复杂性”、“涌现”等概念的精确定义,但仍然可以快速推动复杂系统的研究。这就像虽然没有“生命”,“物种”和很多生物学关键概念的精确定义,生物科学却能迅猛地发展。然而,正如生物学那样,我们确实需要严格的模型让我们可以探索CAS的独特性质。

下面列出的一些特性提供了理解和控制CAS的新机遇:

(1)所有被仔细研究过的CAS都展现出杠杆点    在这个点上的一个简单干预就会引起系统持续的、直接的效果。例如疫苗引起免疫系统持续的、按照我们预期的改变,加入一些掺杂物就可以导致高温超导特性的出现。目前没有理论能告诉我们CAS的杠杆点在哪里以及怎么去寻找这些点。

(2)所有的CAS都有带着相关信号的边界层级组织,且边界里包含边界。没有边界就没有个体的历史,没有个体的历史,就不能根据适应性来选择。因此,达尔文的自然选择是基于边界的产生及其发展的。但是,目前没有理论告诉我们什么机制足以使得一个初始同质的系统产生边界。

(3)所有的CAS看起来都具有开放式(open-ended)演化的风格,即初始很简单的系统,其相互作用和信号传输的多样性会在演化中不断增加。虽然现在已经有了遗传算法和其它人工演化技术,但是目前还没有任何计算机模型能够展现开放式演化。

还有一些合理的假设是根据下面的观察而来的:

(1)由反馈、资源回收和边界导致的资源局部集中,提供了形成新自主体的机会。
(2)自主体形成的过程导致了共同演化和自主体多样性的增加,在这个过程中,大量资源会逐步被自主体占据。
(3)在一些“静止”的条件下,会出现自主体的分化增多的现象。

这些无处不在的性质和假设,给我们提供了一些探索性的计算机模型:

(1)种子机器:构建一个能够仿照从简单单细胞发育到形成多细胞器官的模型。这类模型可能是冯·诺依曼划时代的自繁衍模型[8]的一个自然拓展。

(2)演化的相互作用网络:构造一个从一组基于标记(活性位点)的基本反应式开始的人工化学系统。目的是观察带有标记的边界和与这些边界相互作用的带有标记的信号所组成的网络逐步形成的过程[9]。这类模型如果成功便能提供更好的途径来刻画具有反馈、共同演化和可塑表现型的生态网络[10]。

(3)语言获得和演化模型:构造情景化的自主体模型,自主体在环境中的生存有赖于其与其它自主体的相互作用。目的是观察从前语言(pre-linguistic)认知能力涌现出结构化的、基于语法的语言的条件(如果这个条件存在的话)。

最后,在一个元层次观察CAS创新的不断产生(例如演化的生态系统)会告诉我们应该怎样改变我们通常构思研究的方式:

(1)勇于冒险。在经费资助的研究中允许高的失败率。因为未来成功及其副产品的指数增长,从“全垒打”得到的回报会大大地超过之前因为失败所遭受的损失。

(2)多样性和并行性。探索一个问题的时候同时从不同的路径出发。

(3)信誉分配。对阶段性工作设定回报机制。在科学研究或者做生意中,最困难的行动是开始阶段的、有时候代价很高的、但是最终被证明是个好决策的行动。例如在国际象棋中,通常早期牺牲一个棋子能造出后面的一步好棋。对这个问题的研究实物期权理论比标准的决策理论更好[12]。

长期来说,我们能期待什么结果呢?

(1)针对组织机构的“飞行模拟器”。飞行模拟器是由专家测试的,而不是程序员。这类模型通过提供类似电视游戏的界面,使得飞行专家可以像操控真实飞机那样操控这个模型。专家验证这个模型,给程序设计者提出改进意见。
(2)能够发现CAS杠杆点的相关理论。这样的理论应该可以导致各方面的重大改进,包括从药物设计到关怀帮助穷人等问题。
(3)能赋予探索性研究“底线”价值的新的评价方法。这里的关键是改变那些在征税和净收益估算中使用的“标准”核算方法。目前唯一的

考虑未来效益的重要核算技术就是备抵折旧。对CAS的更清晰的认识使得我们能把这类备抵折旧方法用于贴现可以探索性研究的评价中。

CAS的研究是困难的,同时又激动人心。困难越大,将来的回报很可能也越大。


参考文献

[1]  A. N. Whitehead and B. Russell. Principia Mathematica. Cambridge: Cambridge Univ    Press, 1927.
[2]  L. Bull and T. Kovacs. Foundations of Learning Classifier Systems. New York: Springer 2005.
[3]  P. L. Lanzi, W. Stolzmann and S. W. Wilson. Learning Classifier Systems. New York     Springer, 2000.
[4] J. H. Holland, K. J. Holyoak, R. E. Nisbett and P. R. Thagard.  Induction: Processes of Inference, Learning, and Discovery (2nd Edition). Massachusettes: MIT Press, 1989,71-75.
[5] L. Booker, S. Forrest, M. Mitchell and R. Riolo. Perspectives on Adaptation in Natural and Artificial Systems. Oxford: Oxford Univ. Press, 2005.
[6] J. H. Holland. Hidden Order: How Adaptation Builds Complexity. New Jersey: Addison Wesley, 1995. Chinese translation: Shanghai Scientific & Technological Education Publishing, 2000.
[7] L. Bull. Applications of Learning Classifier Systems. New York: Springer, 2004.
[8] J. von Neumann. Theory of Self-Reproducing Automata. Illinois: Univ. of Illinois Press, 1966.
[9] J.  H.  Holland. Hidden Order:How Adaptation Builds Complexity. Chapter 3.   New Jersey: Addison-Wesley, 1995. Chinese translation, Shanghai Scientific & Technological Education Publishing House, 2000.
[10] F. J. Odling-Smee, K. N. Laland, M. W. Feldman.  Niche Construction: The Neglected Process in Evolution. Princeton: Princeton Univ. Press, 2003.
[11] J. H. Holland. Language acquisition as a complex adaptive system, in Language Acquisition, Change and Emergence. J. W. Minett and Wm. S.-Y Wang ed. Hong Kong: City University of Hong Kong Press, 2005, 411-435.
[12] L. Trigeorgis. Real Options: Managerial Flexibility and Strategy in Resource Allocation. Massachusettes: MIT Press, 1996.

 

本文摘自由郭雷、张纪峰、杨晓光编撰的《系统科学进展》,(英文)发表于Journal of Systems Science and Complexity 2006年第19卷第1期.译者是中国科学院数学与系统科学研究院韩靖副研究员.

 

作者简介:

John Holland (1929.2.2-2015.8.9),生前为密歇根大学的心理学系教授、电机工程和计算机科学系教授。他一生从事适应性研究,早年提出了著名的遗传算法,被誉为“遗传算法之父”,后来提出“复杂自适应系统”理论,产生广泛影响。他是美国圣菲研究所的创始人之一,复杂性科学领域的先驱者和杰出代表人物之一。曾获得美国“麦克阿瑟天才奖”、IEEE Nerual Network Societv颁发的先锋奖、进化程序学会颁发的终身成就奖、计算机科学世界大会颁发的终身成就奖等。他出版了六本专著,其中三本《自然与人工系统的适应性》《隐次序》和《涌现》已经翻译成中文版出版。生前曾不下七次访问中国。