动态持久环境中的自适应与进化：计算机科学与多智能体系统设计

理论计算机科学电子笔记141（2005）163-179www.elsevier.com/locate/entcs适应与进化在动态持久环境中David Keil和Dina Goldin1计算机科学工程系美国康涅狄格州斯托尔斯大学摘要与动态持久环境（DPE）交互的代理的优化（自适应）提出了与静态优化不同的一类问题。这样的环境必须纳入交互式计算的模型。根据没有免费午餐定理（NFLT），不存在优于随机搜索的通用函数优化算法。但是，在持久状态的环境中的交互式适应超出了NFLT的范围，并且存在用于DPE的有用的通用交互式优化协议，如我们所示。状态持久化支持间接交互。基于观察到的相互因果关系是固有的交互式计算，并在多智能体系统中的持久状态的关键作用，我们建立了间接交互是必不可少的多智能体系统（MAS）。这项工作将有助于研究人员在协调，进化计算，多智能体和自适应系统的设计。关键词：自适应系统，协调，动态持久环境，进化计算，交互计算，计算模型，多智能体系统1介绍自适应或智能代理的环境具有五个维度的特征：（1）可访问与不可访问;（2）确定性与非确定性;（3）情节与非情节;（4）静态与动态;（5）离散与连续[28]。开发智能系统最困难的环境是那些接近真实世界的环境，即1电子邮件：{dkeil，dqg}@ engr.uconn.edu1571-0661 © 2005 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.05.021164D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）163不可访问的、非确定性的、非情节性的、动态的和连续的。对于图灵机捕获的基于函数的计算，环境的属性是无关紧要的，因为算法的一次执行只是在来自环境的任何单个输入上计算函数。（非确定性图灵机计算产生输出集的一些关于进化计算的工作以类似的方式描述了现实世界的环境，并指出代理相比之下，关于环境的声明（例如，约束）是交互式问题具体化的一部分。例如，为了设计汽车，我们假设它们将在铺好的道路上行驶，重力和温度条件在地球上正常。我们可能会进一步限制环境用于研究目的，假设道路具有车道分隔器并且没有障碍物。进化计算的出现是为了利用自然界中发现的选择、突变和重组的交互过程来解决困难的优化问题[15]。然而，根据主导计算机科学的基于函数的范式，EC传统上被认为是对算法问题的解决方案的算法搜索。因此，“进化算法”适用于静态“函数优化”问题。 在第2节中，我们将展示这种传统的提出问题的方式是如何导致矛盾的结果的，比如没有免费的午餐定理，这些结果似乎（错误地）导致悲观的结论。适用于现实世界环境中的进化计算的模型必须包含环境[20，10]。一个重要的研究趋势将计算问题从静态优化问题重新定义为动态环境中的问题[8，5]。我们建议在这样的环境中关注持久状态（内存）。正是状态的持久性使非情景性的被体验成为可能。我们的兴趣比进化计算更广泛，因为可以从动态持久环境（DPE）中学到的教训可以推广到任何自适应系统。根据没有免费午餐定理（NFLT），没有函数优化算法优于随机选择。然而，对于动态持久环境，我们展示了有用的通用优化原型的存在（第3节）。例如，生命形式和人类社会通过具有广泛适用性的学习方法在动态环境由于持久性的力量，适应持久性环境的问题可能比非持久性环境更具挑战性由于持久状态支持访问该状态的代理之间的间接交互，因此出现D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）163165当然，在dps。本文提出了一些新的研究方向和新的概念框架，并对多智能体交互和多智能体系统的多学科理论做出了一些贡献• 我们定义交互作用的方式是承认存在于所有真正交互系统中的主体之间的相互因果关系（定义2.1）。• 我们表明，没有免费的午餐定理（NFLT）是不适用于优化的交互行为的DPEs（第3节）。• 我们表明，多智能体与持久状态的相互作用需要使用间接相互作用（定理4.5）。我们注意到本文中的非正式背景或动机与范围较窄的正式和技术部分之间存在差距。后一个方面是一个研究挑战，我们只是在这里开始攻击。我们认为，为当前的问题提供适当的动机和范围本身就是一种贡献。2交互和动态持久环境在这里，我们将相互因果关系确定为交互的基本特征，并定义了具有持久状态的动态环境2.1交互计算交互是一种计算形式，其中通信发生在计算过程中，而不仅仅是之前或之后[18]。交互作用的语义包含相互因果关系。定义2.1交互式计算是参与者（代理或其环境）之间持续的数据交换，使得每个参与者的输出可能会导致其后来的输入。Q数据交换从来不影响接收者的行为，也从来不影响发送者的输入，这不是真正的交互。一个人对着电视屏幕上显示的内容做出反应，对着电视说话或大喊大叫，并不是在与电视互动，麦克风和放大器也不会与电视互动，除非有反馈五十年前，控制论的研究认识到反馈或相互影响是区分系统耦合的一种重要特征[2]。请注意，两个智能体的输出可能会因果地影响它们后来的输入，而无需智能体直接通信;它们可以通信，166D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）163通过中间人。在这种情况下，因果关系和相互作用是间接的（第4节）。算法是对将输入有效地转换为输出的步骤的描述，其中输出是输入的（可计算）函数[22];环境在此描述中不起作用，因为所有关于它的信息都被假定为在输入中捕获。相比之下，在交互式计算中，环境的作用得到了加强;它是计算中的一个积极伙伴。定义2.2主体的环境是它与之交互的实体的集合。Q单个智能体与其环境之间的通信定义了各种交互：定义2.3顺序交互式计算通过交替接受输入字符串和计算相应的输出字符串来不断与其环境交互[17]。Q顺序交互计算是只涉及两个参与者的交互。每个参与者都可以被认为是另一个参与者的环境。顺序交互式计算可以由持久图灵机形式化[17]。存在许多其他模型，例如[31]中提出的在环境中操作的代理模型。Fig. 1. 主体与环境在第4节中，我们将正式定义间接交互，并将表明它可以用多智能体交互来识别，这是顺序交互的替代方案。2.2具有持久状态的对于一个计算主体这一概念与皮亚杰对于图灵机捕获的基于函数的计算，环境的属性（如持久性）是无关紧要的，因为算法的一次执行只是计算一个函数，不管它是什么。D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）163167来自环境的输入。另一方面，对于交互式计算，计算代理的动作如何改变其环境对代理做出的任何选择都至关重要让我们定义一些我们感兴趣的环境属性。持久环境是那些可以从以前的交互中记住的环境：定义2.4一个环境是持久的。如果一个环境不是持久的，那么它就是健忘的。Q当电灯亮时，用户按下按钮开关，但当电灯亮时，用户按下同一个按钮，则电灯关闭，这就定义了一个相对于用户的持久环境。一张纸定义了一个持久的环境w.r.t.一个人在纸上写字，但却失忆了。w.r.t.一个人谁只是读它。空气是健忘症w.r.t.一个人对着它唱歌，执着地对着它。喷香水的人。定义2.5如果A从环境E的输入严格依赖于A向环境E的输出，则环境E相对于主体A是静态的。动态环境不是静态的。Q当按钮开关被按下时，灯依赖地点亮，当再次按下时熄灭，定义了一个静态环境w.r.t.。操作灯的人。带有光传感器的灯，只有在房间黑暗时才能打开，为用户定义了一个动态环境任何可以被图灵机建模的环境都是静态的，因为无论在这样的环境中的代理发出什么输出，环境都将以作为代理输出的（可计算）函数的值进行响应这样的环境不会记住以前的交互，就像图灵机的每次计算都从一个空白磁带开始，而不是从以前的计算结果开始。一个目标函数，例如在进化计算研究中使用的，定义了一个静态环境。我们关注的是结合活力和持久性的环境。相对于代理的动态持久环境（DPE）是持久的但相对于它不是静态的环境。DPEE与代理M交互，使得M例如，汽车行驶的环境是动态的和持久的（参见[11]关于汽车驾驶问题的讨论）。当汽车移动时，它会随着汽车的变化而变化。汽车、行人和其他潜在的-168D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）163障碍物的出现和消失部分取决于汽车的动作。我们描述为动态和持久的环境类型的一个模型是马尔可夫决策过程（MDP），特别是部分可观察的MDP [19]。最近的表现力的交互式计算模型的结果，使我们能够表明，动态持久的环境更难适应比动态环境中没有持久状态。定义2.6 A类环境比B类环境更难，对于主体集合S，A类环境的可观察行为范围是B类环境的严格超集。Q引理2.7在DPE中可观察到的系统行为集合严格包括在失忆环境中可观察到的行为集合。Q证明草图：我们可以将DPE形式化为具有状态的持久图灵机[17]。记忆环境可以被形式化为遗忘的PTM，即那些不能存储或记忆任何东西或不使用存储的信息的PTM。根据[17]中的一个定理，PTM的流语言集合PSL严格包含遗忘PTM的流语言集合ASL从定义2.6和引理2.7可以直接得出，与健忘的环境相比，DPE更难适应在下一节中，我们将展示动态持久环境的概念可以帮助进化计算研究摆脱与适应问题相关的一些明显的理论僵局。3没有免费的午餐定理不适用没有免费的午餐定理（NFLT）[30]向进化计算（EC）的研究人员提出了一个悖论一方面，通过NFLT，没有算法（如进化算法）在解决一般函数优化问题时比随机搜索更有效。另一方面，自然进化被证明比随机搜索更能产生适应各种环境的生物体。我们解决了这个悖论，表明NFLT不适用于优化的DPE，如自然环境。3.1进化计算研究简而言之，我们通过NFLT得出，当算法的效率在所有成本函数的集合上平均时，没有算法过程比任何其他算法过程更有效地优化成本函数例如，如果某个进化算法可以快速收敛以解决某个优化问题，D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）163169问题（午餐），那么对于其他问题（午餐价格），该算法的性能比随机搜索差得多。因此，作为一个通用的问题求解器，没有EA比随机搜索更好形式上，NFLT建立了对于任何两个算法a1和a2以及任何成本函数f，以下等式成立：Σ→ ΣP（c |f，m，a1）=f f→→P（c |f、m、a2）哪里c是算法针对给定m eval获得的值的直方图。→F的评价 概率表达式P（c |f，m，ai），i∈ {1，2}是直方图的条件概率[30]。从NFLT可以看出，要构建一个好的函数优化器，需要事先了解函数的一些信息。NFLT的证明经受住了检验，但大自然似乎已经产生了一个反例，地球上的生命似乎正在通过进化进行通用（如果缓慢）优化[6]，而人类似乎正在这样做，以更快的速度通过情报自相矛盾的是，尽管受到NFLT的限制，但在对环境没有先验假设的广义过程中，适应性系统始终存在。一些研究通过严格限制所考虑的代价函数集的类而取得了成功某些算法的性能，在有限个代价函数集F上平均，可能优于其他算法的性能如果集合F在置换（c.u.p.）下不闭。此外，几乎所有的集合F都不是c.u.p.在几乎所有的EC研究中使用的限制或先验知识的适合景观进一步的重量的想法，即使是类的3.2解决悖论NFLT排除了一般优化的算法过程从NFLT可以看出，每一个有用的进化算法在某种程度上都是问题特异性的，因为它有一些有用的关于适应性景观的内置知识。自然和人工系统通过与环境的相互作用获得必要的知识，有时需要数千年。摆脱困境的一种方法是，上述定理将1和2定义为算法，而不是交互式策略，定理所考虑的可能环境集是函数，而不是可能在与解的种群的交互中进化的第一类对象170D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）163算法不能探索环境，适应输入，或改变它们的行为;算法的执行只有在获取所有输入后才开始。动态持久环境的概念为这个悖论提供了一个解决方案。在这样的环境中，代理或群体的成本函数可以在整个优化过程中改变。 函数f被替换为一系列代价函数ft。 由于DPE中的进化不是一种算法，优化函数，NFLT不适用于DPE中的优化，无论是自然的还是人工的。在[23]的意义上，智能体及其环境都是反应系统。已经注意到，在反应性环境中运行的反应性系统关注的是效用最大化，而不是像功能系统设计中那样满足谓词。换句话说，随着生命形式的进化，它们改变了自己和环境。相比之下，进化算法 例如，NFLT不适用于以下情况：• 随着微生物在海洋中进化，改变海洋• 随着市场的发展，它倾向于优化生产数量和价格，但通过经济中代理人之间的相互作用，而不是通过算法。与人类主导的优化过程不同，自然进化缺乏全局目标;此外，物种，甚至通常是有机体，缺乏生存的意志或心理意图。然而，自然进化的过程往往会优化物种个体的生存能力在EC研究人员中，NFLT的重要性反映了将问题视为函数的数学世界观，即，作为单输入到单输出的变换[18]。承认DPE的重要性就是要从传统的数学世界观出发，接受更广泛的交互式世界观。著名的EC研究员Kenneth DeJong观察到，函数优化的有效策略对于顺序决策问题不一定是有效的，并提醒我们John Holland对EC的基础工作的动机是对自适应系统的关注。一般来说，进化是一种“探索和适应复杂和随时间变化的适应性景观”的方式结合交互的计算概念化将建议寻求最小化或最大化函数的代理应该学习D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）163171虽然没有算法可以体现所有成本函数的知识，但可以构建一个交互过程，通过与诱导成本函数的环境交互来学习和引导自己，包括与过程交互时动态变化的成本。一些这样的交互式学习过程将比盲目搜索表现得更好。这一事实解释了复杂生命形式的存在。地球上的自然进化已经获得了比随机搜索更好的结果，而且许多形式的生命本身就是比随机搜索更好的通用优化器，这些事实证明存在比随机搜索更有效地找到极值的过程。由于它们不是算法过程，NFLT并不排除它们的存在。观察到主体与其环境之间的相互适应（相互适应）以有利的方式塑造了适应性景观[12]，突出了相互作用在允许逃离NFLT的不利含义方面的作用。事实上，正是物种的共同进化反驳了William Dembski声称NFLT意味着智能设计在解释复杂生命形式中的必要作用[25]。共同进化和共同适应的定义是，对于他们的参与者来说，环境是动态的和持久的。NFLT限制了我们寻找最优通用算法的能力，因为丘奇-图灵命题有助于定义算法计算的极限。正如[17]建议对Church-Turing命题进行交互式扩展一样，交互式计算理论研究的挑战是提供了一个正式的否定的NFLT，包括反例，在这样一种方式，以占在交互式上下文中的有用的通用优化协议的存在。3.3走向正式成果我们提出了我们的结论，NFLT和DPE半正式的，作为两个观察和一个猜想，都遵循上述讨论。观察：动态持久环境下交互计算的优化问题一般不能归结为函数优化问题。假设环境E与计算主体A以这样一种方式交互，即A172D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）163因此，随着时间的推移优化A的输入的问题 另一个参数是环境的变化状态。观察：考虑自地壳冷却生命形式的进化和生存几十亿年的地壳自然史证实了这一观察。那么，让我们大胆猜测一个具有类似一般有效性的人工协议。猜想：假设π是一个协议，它包括开发和完善一个环境模型，并使用这个不断发展的模型来预测和从环境中交互地获得所需的输入（它可以被描述为科学方法加上良好的工程实践）。然后，π接近人类迄今为止或在可预见的未来遇到的所有环境的最优性。π比随机选择更适合于获得适合人类生存和舒适的结果。显然，可以开发类似于NFL的定理，但是描述了DPE中优化的限制，因为优化成本函数的最简单的DPE是遗忘的（无记忆的）DPE，等同于静态环境，即，交互式优化等价于函数优化。然而，同样清楚的是，只有那些行为在某种程度上可以被描述为合理的环境才是感兴趣的;在所有可想象的环境中，这只是一小部分。特别是，很可能只有动态环境是可学习的，即，可以开发可计算模型来帮助优化与环境交互的奖励的环境4间接交互和多智能体系统环境中状态的持久化使得环境中的代理可以通过该环境而不是直接相互交互。我们定义了间接相互作用，并表明它不同于直接相互作用，而且不能还原为直接相互作用（4.1节）。第4.2节列举了这方面的例子，说明了多智能体系统研究领域的多学科方面。我们表明，正是间接的相互作用，区分多智能体D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）163173序贯相互作用（第4.3节）。如果以间接交互为特征的系统可能比没有间接交互的系统显示出更大范围的行为，那么具有间接交互的DPE（多智能体DPE）比那些只有直接交互的DPE提出了更具挑战性的问题因此，需要多智能体4.1直接与间接互动人们普遍认为，互动与沟通是一样的。通信与消息传递[24]或目标发送/接收（TSR）[14]的概念相关联;我们将其称为直接交互。定义4.1直接交互是通过消息进行的交互;接收者的标识符在消息中指定。Q当两个实体拥有关于彼此的识别信息时，消息传递是合适的。然而，缺乏这样的信息，通信实体可以通过改变其公共环境的持久状态来匿名地通信。这是第二类互动。定义4.2间接交互是通过共同环境中持续的、可观察的状态变化进行的交互;接收者是将观察这些变化的任何代理。Q例4.3（哲学家进餐问题）[9]在这个关于并发和共享资源的经典问题中，哲学家们坐成一圈吃饭，每对用餐者之间有一个盘子。用餐者各自拿起两根筷子（一次一根），吃，放下，思考，无休止地重复着这些步骤。问题是要避免因僵局而饿死;例如，如果每个用餐者都拿着左边（或右边）的盘子，直到另一个盘子空出来，那么所有人都会饿死。图二. 哲学家进餐这个问题的目的是定义一个协议，用于通信进程的环形排列，每个进程只与它的两个邻居通信在这里，筷子充当环境（共享数据）的一部分，其持久状态174D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）163（在餐桌上或与用餐者）使他们能够被用作交流的媒介，从而导致相邻哲学家之间的间接互动。Q由于间接交互依赖于环境状态随时间的持续性，因此通信信息的接收者的身份由动态（后期）绑定确定。间接交互中发送者和接收者之间的解耦意味着匿名性和匿名性。匿名交互发生在计算实体在不知道彼此间接交互中的非同步性来自于时间延迟，这是由于使用了可观测变化随时间的持续性除了匿名性和匿名性之外，间接互动通常还具有局部性和非意图性的特征[16]。前者意味着有效的间接交互只允许代理访问（感知或修改）环境的一小部分。后者意味着参与者可以在没有任何预先存在的通信目标或意图的情况下进行交互。也就是说，当行动者对环境做出要被其他人感知的改变时，他可能是出于没有明确意图让他人感知他的改变例4.4（哲学家进餐问题，续）这个问题具有以下性质：（1）局部性，因为用餐者只能看到相邻的筷子;（2）匿名性，因为用餐者不需要知道彼此(4) 非意向性的沟通，因为用餐者拿起筷子吃饭，把它们放下思考，而不是沟通。Dining Philosophers是一个DPE问题的例子。 每一位哲学家的环境都是桌子和周围的其他用餐者;环境的状态是持久的，以一种任何一位用餐者都无法控制的方式变化。哲学家用餐也被建模为哲学家和餐具之间的直接互动，如并发理论。在这个模型中，筷子是自主的计算过程，就像哲学家一样。然而，这违背了这个问题的语义，即筷子不是自主实体。他们是被动的，不采取任何行动，他们唯一的作用是反映他们旁边的哲学家的状态。这个问题的语义是食客之间的互动，而不是食客和餐具之间的互动。这种互动是间接的，通过筷子;一个基于直接互动的模型不会不再表现出上述四种特征性质。Q由于上面讨论的属性，间接交互对于其认知资源（诸如计划、感知和认知资源）的代理来说是自然的。D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）163175在他们的环境中采取行动，相对于他们的任务的复杂性是有限的[32]。4.2自然界中的间接相互作用（污名化）几乎所有现实世界的优化问题都是多智能体（多组件）系统（MAS）对动态持久环境的适应问题。MAS中的自适应可以是集中式的，基于产生算法解决方案的理性演绎。或者，在缺乏合理的解决问题和规划机制的情况下，它可能是分散的。去中心化适应的例子包括蚂蚁、白蚁和黏菌.在StarLogo白蚁模拟中，尽管白蚁没有规划或协调的能力，而且感知能力也很低，但它们会建造一个圆形的木片堆。它们不断地应用一个简单的协议：随机移动，每当遇到一个芯片时就捡起它，当白蚁碰到另一个芯片时就放下它。最后，一个单一的桩出现。白蚁群体的这种整体行为比个体携带芯片行为的组成更重要。白蚁以自我维持的方式完成这种桩形成任务，而没有目标的内部表征[27]。蚁群通过分散的多智能体交互解决了高效觅食的问题，每个蚂蚁在行走时都会沉积信息素（蒸发气味化学物质），每个蚂蚁都会跟随信息素和食物气味。大量旅行（因此强大，因此有吸引力）信息素踪迹对应于食物的短路径。 当食物在一个地点耗尽时，通往它的痕迹就会消失。在没有计划的情况下，蚂蚁会找到一组趋向于最优的食物路径[3，4]。图三. 蚂蚁觅食当它们的食物稀缺时，黏菌变形虫有机体通过使用释放到环境中的化学信号相互吸引。信号在生物体之间传递，这些生物体向这些信号的螺旋中心迁移，最终聚集成一个单一的爬行鼻涕虫样器官[21]。同样，这种集体行为是从个体互动中176D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）163没有集中的指导。所有这些情况在本质上都是多智能体系统，而不是以顺序交互为特征的系统（定义2.3）。上述例子的一个共同特征是，生物体通过共享环境而不是直接交换信息进行交互。4.3多智能体系统需要间接交互多智能体交互（MAI）是无处不在的，无论是在原子，分子，细胞，有机体，社会，或行星的水平。虽然计算机科学将计算建模为一个计算代理的输入到输出的转换，虽然并发理论将交互建模为两个代理或进程之间的直接通信，但现实世界中的复杂系统比这两种模型都要丰富。 系统通常是开放的，可以创建或销毁。非同步性和匿名性通信已经形成了MAS的协调模型领域[1，14]。MAI模型仅代表代理对的直接和同步交互，显示出明显的局限性。由于MAI不仅仅是多个顺序交互实例的组合，因此需要一个反映其特殊特性的多智能体交互模型。MAI与顺序交互作用的不同之处在于它涉及间接交互作用。在下文中，我们试图通过证明间接交互对MAI的识别来明确区分顺序交互和多智能体交互。直觉上，这种识别是显而易见的。然而，迄今为止的并发模型并没有明确表示这种形式的交互; [24]将并发下的所有交互建模为直接目标发送和接收（TSR）。定理4.5设S是一个多智能体系统，它包含一些智能体和可能共享的变量，这些变量形成一个DPE w.r.t.其他探员然后在S中发生间接相互作用。Q证据1.假设S是一个多智能体系统，其中的一些子集的代理，并可能共享变量，形成一个动态的持久环境相对于其他。2. 假设S仅以直接相互作用为特征。3. 根据定义2.1（交互作用），S中的一对主体只有在每个主体都通过其行动来接受其后来的输入时才进行交互。但根据定义4.2（间接交互），S中没有一对主体通过一个主体所创造的、另一个主体在共同环境中可观察到的D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）1631774. 因此，S的任何部分都没有持久状态，因此任何部分都不能是DPEw.r.t.另一部分（定义2.4），与（1）相矛盾。因此，（2）导致了矛盾，必须予以拒绝。[29]调查了MAS的环境领域，经常提到间接相互作用。一类特殊的MAS是那些分散的，但在一个共同的任务合作。有关由多个合作代理控制的MDP的讨论，包括通过间接交互，请参见[19]。它提出了一个分散的部分可观察马尔可夫决策过程（POMDPs）的模型，强调使用间接的相互作用。间接交互对于MAS模型的充分表达是必要的，但并不足够。间接交互可以在没有更大表现力的情况下发生如果组件代理不是真正并发的话。请注意，任何模块化算法都可以通过用代理替换子例程和用共享变量（间接交互）替换输入/输出关系来转换为MAS但很明显，尽管有间接的相互作用，在这种情况下，行为的范围并没有增加5结论在本文中，我们已经确定了相互因果关系的相互作用，并定义了动态和持久的环境类别。引入动态持久环境的概念为多学科提出了新的研究方向，并为代理和交互式计算提供了新的思维方式。例如，它可能会为进化计算和自适应系统的研究提供方向。正如我们所展示的，认识到对动态持久环境的适应不是一种函数优化，使我们能够解决没有免费午餐定理的困境。利用相互因果关系是交互作用的定义属性这一观察结果，我们已经证明了具有持久性的多智能体系统必然具有间接交互的特征。因此，需要新的模型来明确公司内部的间接互动.未来的研究挑战包括：• 证明了自适应代理在具有持久状态的情况下在DPE中的性能更好;• 对NFLT和DPE的观察进行形式化（第3.3节）;• 证明多智能体/间接交互模型比顺序交互模型具有更强的表现力;• 形式化的多智能体系统的方式，明确纳入indi，178D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）163rect交互，解决动态持久环境中问题的关键概念。鸣谢：我们感谢匿名推荐人的宝贵意见和参考。引用[1] 法哈德·阿巴布Reo：一个基于通道的组件组合协调模型。CWI Report SEN-0203，2002.[2] W. 罗斯·阿什比控制论导论。大学平装书，1964年。[3] Eric Bonabeau，Marco Dorigo，and Guy Theraulaz. 群智能：从自然到人工系统牛津大学出版社，1999年。[4] 埃里克·博纳博和盖伊·瑟拉拉兹群体智慧。《美国科学》，第72-74页，2000年3月。[5] 尤尔根·布兰克 动态环境中的进化优化。 Kluwer，2002年。[6] Joseph C.卡伯森盲目搜索的徒劳：“没有免费的午餐”的算法观点演化计算，6（2）：109[7] 肯尼斯·德容遗传算法不是函数优化器。遗传算法基础2，D。Whitley，编， 摩根·考夫曼1993年。[8] 肯尼斯·德容演化计算：统一的概述。参加CEC-2001，韩国首尔，2001年。[9] Edsger Dijkstra 顺序过程的层次排序。 Acta Inform. ，1：115[10] 尤金·艾伯巴赫进化计算的表现力：EC是算法的吗？世界计算智能大会，2002年。[11] Eugene Eberbach，Dina Goldin，and Peter Wegner.图灵In Christof Teuscher，ed.，艾伦·图灵：一个伟大思想家的生活和遗产，施普林格，2004年。[12] 加里·威廉·弗雷克 大自然的计算之美 MIT Press，1999.[13] David B. Fogel，Lawrence J. Fogel，and Wirt Atmar.进化规划的分层方法。Proc. 1st Ann.Conf. on Evolutionary Programming，pages 175[14] D. Gelernter和N.卡列罗协调语言及其意义。CACM，35（2）：97[15] David E.金伯格创新的设计：从胜任的遗传算法中吸取的教训。Kluwer，2002年。[16] 迪娜 戈尔丁 大卫·凯尔间接交互的领域独立形式化。TAPOCS研讨会，Proc. WETICE 04，2004年。[17] 放大图片作者：Scott A. Smolka，Paul Attie，and Elaine Sonderegger.图灵机、转换系统和交互。Information and Computation Journal，194（2）：101-128，Nov. 2004年[18] 迪娜·戈尔丁和彼得·韦格纳。丘奇-图灵论文：打破神话。LNCS 3526，Springer，第152-168页[19] C.V. 高盛 和S. 齐伯斯坦合作系统的分散控制：分类与复杂性分析。 J. 人工智能研究，22：143 -174，2004。D. Keil，D.Goldin/Electronic Notes in Theoretical Computer Science 141（2005）163179[20] 大卫·凯尔和迪娜·戈尔丁 开放计算系统中间接交互作用的建模。TAPOCS研讨会，Proc. WET ICE 03，2003年。[21] 詹姆斯·肯尼迪和罗素·埃伯哈特。 群体智慧。 摩根·考夫曼2001年。[22] Donald E. 高德纳计算机程序设计的艺术，第1卷：基本算法。艾迪森-韦斯利1968年[23] 佐哈尔·曼纳和阿米尔·普努埃利反应和并发系统的时序逻辑：规范。Springer Verlag，1992年。[24] 罗宾·米尔纳互动的元素 Comm. ACM，36（1）：78 -89，1993.[25] H.艾伦·奥尔权力下放：为什么智能设计不是。纽约客，第40-52页，2005年5月30日。[26] 让·皮亚杰 行为与进化 万神殿，1978年。[27] 米切尔·雷斯尼克海龟，白蚁，和Tra jam. MIT Press，1994.[28] 斯图尔特·罗素和彼得·诺维格。人工智能：一种现代方法。Addison-Wesley，1995年。[29] D. Weyns，H. Parunak，F. Michel，T. Holvoet和J. Ferber.多智能体系统的环境：最新技术和研究挑战。LNCS 3374，第1-48页[30] David H.作者声明：William G.麦克里迪搜索没有免费的午餐定理。Santa Fe Institute technicalreport SFI-TR-0，10，1996.[31] 迈克尔·伍德里奇论Agent设计中复杂性的来源。应用人工智能，14（7）：623-644，2000。[32] Franco Zambonelli和H.范·戴克·帕鲁纳克计算机科学和软件工程革命的标志。Proc.ESAW02，第13-28页