（信号与信息处理专业论文）基于生态特征的进化与协同研究.pdf

摘要 摘要 随着计算机网络技术，计算机通讯技术的发展，分布式人工智能中多主体 系统( m a s ：m u l t i a g e n ts y s t e m ) 的理论及应用研究已成为人工智能研究的一 个热点，如何构造能自适应复杂环境的m a s 成为当前的一个研究重点和难点。 a g e n t 作为具有生命特征的抽象实体，它的个体以及群体的行为与生态环境中 的生命体行为有很多相似之处。r 一7 生命科学与工程科学的相互交叉、相互渗透和相互促进是近代科学技术发 展的显著特点之一，进化行为作为从生命现象中抽取的重要的自适应机制己被 人们普遍认识并得到了广泛的应用，然而现有的进化模型存在一个共同的不足 一未能很好地反映出一个普遍存在的事实：多数情况下，整个系统复杂的自适 j 、v 进化过程，事实上，是一个构成系统的众多子系统局部相互作用的协同进化过 稚。 本文针对这一问题，遵从人工生命的研究方法论，引进目前对个体( a g e n t ) 行为认识最为深入的生态科学的研究成果，对在复杂环境中a g e n t 的进化行为 与相互作用的协同行为进行了深入的研究，提出了以研究进化为主线，强调将 进化行为和协同行为一体化研究的方案，具有一定的创新性。 f 按照一体化研究方案，借鉴生态学对生物个体在生态环境中相互作用行为的 认识，本文提出了基于生态特征的协同进化模型，更全面地反映了自然界生物 进化过程中的行为特征，拓展了进化思想的生物基础。l 基于本文提出的模型，我们构造出新的协同进化算法，该算法能较好地反 映出进化的多样性和多层次性，在与传统的进化算法的比较中，新算法表现出 良好的性能。 同时我们还利用本文提出的协同进化模型，对多a g e n t 系统的构造进行了应 用研究，取得了一定效果，从计算智能的角度，为a g e n t 研究提供了一种新的方 浚、。 摘要 在本文的整个研究过程中，我们将进化与协同紧密联系，所提出的基于生 态特征的协同进化模型，更全面地反映出进化的多样性和多层次性，拓展了进 化模型的生物基础，具有一定的创新性，相信这种对进化的认识对复杂系统的 自适应行为研究具有普遍的借鉴意义。j 关键词：进化模型，人工生命，群体智能，复杂自适应系统 j i 坐墅l a b s t r a c t w i t ht l l ed e v e l o p m e n to ft h ec o m p u t e rn e t w o r ka n dc o m m u n i c a t i o nt e c h n o l o g y , r e s e a r c ho nt h et h e o r ya n da p p l i c a t i o no fm u l t i a g e n ts y s t e m ( m a s ) i n t 1 1 ed i s t r i b u t e d a r t i f c i a li n t e l l i g e n c eh a sb e c o m eah o t s p o to f a r t i f i c i a li n t e l l i g e n c e h o wt oc o n s t r u c ta m a sw h i c hi ss e l f - a d a p tt ot h ec o m p l i c a t e de n v i r o n m e n th a sb e c o m e af o c a la n dh a r d p o i n ti nt h er e s e a r c h a n g e n ti s a l la b s t r a c te n t i t yp o s s e s i n gl i v i n gc h a r a r c t e r t h e p e r f o r m a n c eo fi t s i n d i v i d u a la n dg r o u p h a si ss i m i l a rt o t h a to ft h ec r e a t u r ei n e c o s y s t e m f h ei n t e r s e c t i o na n di n t e r p e n e t r a t eo fl i f es c i e n c ea n de n g i n e e r i n gs c i e n c ea r et h e c o n s p i c u o u s c h a r a c t e ro f r e c e n td e v e l o p m e n to fs c i e n c ea n dt e n o l o g y e n v o l u a t i o n ，a s a l l i m p o r t a n ts e l f - a d a p t m e t h o dd r a w nf r o ml i f e p h e n o m e n a ，h a s b e e ng e n e r a l l y r e c o n g n i z e da n dw i d e l ya p p l i e dt op r o b l e ms o l v i n g b u tt h ec u r r e n te v o l v i n gm o d e l s h a v eac o m l t l o nd e f i c i e n c y ：t h e yc a nn o tw e l lr e f l e c tt h a tt h ee v o l u a t i o no ft h es y s t e m i si nf a c tt h ec o e v o l u t i o nu n d e rn u m e r o u sl o c a lr e c i p r o c i t y a i m e da tt h i si s s u e ，t h i st h e s i sf o l l o w st h er e s e a r c hm o t h e do fa r t i f i c i a l l i f e ， r e f e r st os o m er e c e n te c l o g i c a la c h i e v e m e n t so na g e n tp e r f o r m a n c e ，a n dl u b r i c a t e st h e e 、o l u a t i o no f a g e n t si nt h ee n v i r o n m a n ta n dt h e i ri n t e r a c t i o n w ep r o m p t e da s c h e m e w h i c ht a k e st h ee v o l u a t i o na st h em a i n l i n ea n de m p h e s i z e st h eu n i t a t i o no fe v o l v i n g p e r f o r m a n c ea n di n t e r a c t i o n ，t h i sh a ss o m e i n n o v a t i o n a c c o r d i n gt o t h es c h e m e ，w er e f e r e dt ot h er e c o g n i z a t i o na b o u tr e c i p r o c i t yo f a g e n t o f e c o l o g y , a n d e s t a b l i s h e dac o e v o l u t i o nm o d e lb a s e d o n e c o l o g i c a l c h a r a c t e r s ，e x p a n d e dt h eb i o l o g i c a lb a s i so f e v n u a t i o nm o d e la n db e r e rr e f l e c t e dt h ed i v e r s i t y a n dm u l t i l e v e lo f e v o l u a t i o n h a v i n gt h i sm o d e l ，w ec o n s t r u c t e dan e w c o e v o l u a t i o n a l g o r i t h mt h a t b e t t e r r e f l e c t st h ed i v e r s i t ya n dm u l t i l e v e lo fe v o l u a t i o n t h i sa l g o r i t h ms h o w sab e t t e r p e r f o r n l a n c ec o m p a r e d w i t ht r a d i t i o n a le v o l u a t i o na l g o r i t h m u s i n g t h ec o e v o l u a t i o nm o d e l p r o m p t e d i nt h et h e s i s w e a p p l i e d t h e c o n s t r u c t i o no f m u l t i a g e n ts y s t e mi n t ot h er e a lw o r l d a c h i e v e dc e r t a i nr e s u l t s a n d p r o v i d e da n e wm e t h o do f a g e n tr e s e a r c hf r o m t h ea s p e c to f c o m p u t i n gi n t e l l i g e n c e d u r i n gt h er e s e a r c ho ft h i st h e s i s ，w ei n t e r g r a t e de v o l u a t i o na n dc o o p e r a t i o n ， p r o m p t e dt h e c o e v o l u a t i o nm o d e lb a s e do ne c o l o g i c a l c h a r a c t e r s e x p a n d e d t h e b i o l o g i c a lb a s i so f e v o l u a t i o nm o d e la n db e t t e rr e f l e c t e dt h ed i v e r s i t ya n dm u l t i 1 e v e l o fe v o l u a t i o n t h i sr e s e a r c hh a ss o m ei n n o v a t i o na n dw o r t h sb e i n gr e f e r r e di nt h e s t u d yo fs e l f - a d a p tt oc o m p l i c a t e ds y s t e m k e y w o r d s ：e v o l u a t i o nm o d e l ，a r t i f i c i a ll i f e ，g r o u pi n t e l l i g e n c e c o m p l i c a t e ds e l f - a d a p ts y s t e m i i i 致谢 在攻读博士的三年间，作者的研究工作都是在导师王煦法教授的亲切指导 j 进行的；在本论文的研究过程中，更是得到了王教授多方的指导。王教授渊 博的学识、严谨的治学态度、不倦的工作热情、民主的科研作风，使作者受益 匪浅。正是在王老师的长期鼓励、引导和启发下，作者才得以顺利地完成本文 的研究。 本实验室的曹先彬副教授与作者就本文的相关问题进行过多次富有成效的 讨论，使作者受到很多启发：同作者一起工作的张军、刘克胜两位博士生对本 文的研究工作提出了许多中肯的意见和建议。 本实验室的陈恩红、刘贵全博士，博士生王炜、李金龙、罗文坚、王上飞 等都与作者进行过广泛的讨论和交流。 本系朱领娣老师在三年的学习生活中给了作者多方面的关心和帮助。 敬爱的母亲马守鸾在作者三年的学习生活中给予了最大限度的关心、鼓励 和支持。 在此谨向以上诸位，以及所有关心、帮助过本人的前辈、同仁和朋友，表 示衷心的感谢。 璺= 兰! ! 童型邀塑燮 第一章引言 1 1复杂自适应系统概述 1 1 1 复杂系统的概述 目前，系统科学的研究正处于从无生命系统研究到有生命研究的转变，从 l ：程技术领域到社会科学、生命科学领域转变的对期。这些情况都要求在研究 的选题、研究思路、方法论及研究结果的表达方式上发生相应的改变。 3 0 0 多年来，近现代科学的研究主要是致力于理解系统的物质结构( m a t e r i a l s t r u c t u r e ) ，这就使得物理学成为科学的主宰，同时也取得了巨大的成功。而在 2 1 世纪，人们倾向于认为科学的最基本的改变将是信息代替物质，也就是从关 祖：系统的物质组成，从研究“它们是什么的问题”，转变到关注系统的信息或功 能特征( i n f o r m a t i o n a l f u n c t i o n a lc h a r a c t e r i s t i c s ) ，转变到“它们做什么的问题”【1 】。 现在，复杂性科学正在做着这种开拓性的研究。 什么是复杂性? s a n t af ei n s t i t u t e 的g e o r g ea c o w a n 认为，复杂性往往指 一。些特殊系统所具有的一些现象，这些系统由很多相互作用的部分即予系统组 成，这些子系统之间通过某种目前尚不清楚的自组织过程而变得比处于某个环 境中的热力学平衡态的系统更加有序( o r d e r e d ) ，更加i n f o r m e d ；而且整个系统 具有不能通过子系统的性质来预测的创发( e m e r g e n t ) 特性【2 】。c o w a n 对复杂 性的认识有如下两个关键点：一是复杂性是从属于某个系统的内禀性质或特征： 是这个性质是创现的，是自组织过程的结果，不同于热力学平衡的有序状态 等等，不是在任何一个系统中都可以讨论复杂性的。因此，研究复杂性离不开 系统，而且还要讨论一些特殊的系统。 在美国墨西哥州的s a n t af ei n s t i t u t e ( 简称s f i ) ，以三位诺贝尔奖获得者 m g e l l m a n n ，k a r r o w 及e a n d e r s o n 为代表，聚集了一批不同领域的科学家，发 展他们称为2 1 世纪的科学- 复杂性科学( s c i e n c eo f c o m p l e x i t y ) ，s a n t af ei n s t i t u t e 出版的一套关于复杂性的著作【3 】 4 】【5 】和c o m p l e x i t y 杂志所包含的领域是极其 广泛的。j o h nh o l l a n d 提出了复杂自适应系统的概念来概括它们的一般性特征 【5 i 它概括的系统包括诸如人脑、免疫系统、生态系统、细胞、蚂蚁群以及人 笙二塞! ! 壹 生里型! 皇童型兰型蔓塑 类社会中的政党、组织等等。他认为每一个这样的系统都是由并行的相互作用 的a g e n t 组成的网络。 在我国，学者提炼出“开放的复杂巨系统”来描述具有同样一些性质的系 统【e _ i 。开放的复杂巨系统主要包括如下几类系统：1 ) 具有相互依存关系的社 会、地理和生态环境系统；2 ) 错综复杂的社会系统；3 ) 人体系统；4 ) 人脑系 统。这些系统与外界有物质、能量、信息交换等等 7 8 。但是对这些系统来说， 它们所具有的信息或功能的特征才是最重要的，如进化和共同进化 ( c o e v o l u t i o n ) 特性、适应性、自组织过程、自催化过程、临界性、多层次特 性、相变以及混沌的边缘等等，而它们之中，最重要的就是宏观整体的创现性 质。可以认为，复杂性的研究就是对开放的复杂巨系统的关键信息特征或功能 特钮：的研究。它会随问题不同而有所变化，也就是说，复杂性是开放的复杂巨 系统的特征。 复杂性研究的意义是重大的，以混沌动力学研究而出名的d o y n ef a r m e r 认 为【4 】，复杂性研究是探索生命的秘密，寻求热力学第二定律的另一半，这是很 确启发性的。其实，复杂系统呈现出来的创现特性代表的是另一种看待世界的 哲学观念：以笛卡尔哲学为基础的近现代科学以及文化传统强调的是从上到下 的还原与分析方法，强调有一个中心控制单元的结构，是机械的观点；而复杂 性研究则强调从下到上的集成方法，强调创现，这是非笛卡尔的观点。这样一 种观点在人工智能和认知科学领域里取得了广泛的应用，目前随着s a n t af e i n s t i t u t e 的研究，它的影响慢慢地扩展到了自然科学、生命科学、社会科学、行 为科学等各个领域中。这是一次哲学观念的革新。 1 1 2 作为复杂系统的多a g e n t 系统 自8 0 年代以来，随着计算机网络技术，计算机通讯和并发技术的发展，分 布式人工智能( d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e ，d a i ) 逐渐成为人工智能领域 的一个新的研究热点，它主要研究在物理上或逻辑上分散的智能体如何协调其 智能行为，即协调它们的知识，技能和规划，求解单目标或多目标问题，为设 计和建立大型复杂的智能系统提供有效途径。 2 苎二兰! ! 童 主里型兰垫查查兰堡主堕苎 一般，d a i 的研究可分为两大方向：分布式问题( d i s t r i b u t e d p r o b l e ms o l v i n g ， d p s ) 求解和多主体系统( m u l t i a g e n ts y s t e m ，m a s ) 。它们处于同一范畴的两 个端点上。d p s 的主要目标是要创建协作群体，它们之间共同工作以对某一问 题求解。在一个纯粹的d p s 系统中，问题被分解成任务，并且为求解这些问题， 需要仅为该问题设计一个专用的任务执行系统。所有的交互式策略都被集成为 系统设计的整体部分。这是一种从项向下设计的系统，因为系统是为在顶部所 绘定的需求而设计的。与d p s 系统相反，在一卜纯粹的多主体系统中，主体是 自主且异构的，它们并不限制于为一个单一的任务。多主体系统的研究涉及在 组智能体之间协调其智能行为，以便联合起来采取行动或求解问题。虽然在 这里一个主体也是某一任务的执行者，但它具有“开放的”接口，任何其他智 能体都可以对它进行存取，该主体不仅可以处理单一目标。而且可以处理不同 的多个目标。多智能体系统是由多个在逻辑或物理上分离的智能体组成的集合， 该系统可以协调一组自治的智能体的行为( 知识、目标、方法和规划等) ，以实 现协调的动作和求解问题，可视为一个自底向上设计的系统。 多a g e n t 系统的研究是当前人工智能研究的一个前沿课题，几乎涉及人工智 能的所有深层问题【9 1 7 】。对多a g e n t 系统的研究可以从很多角度展开，基于不 同角度的研究所作出的假设是不相同的，因而对多a g e n t 系统的描述也有很多。 例如，在一个极端的情况下，某些研究假设有一些( 或全部) a g e n t 对系统中其他 a g e n t 没有任何知识，这样的a g e n t 不能意识到其他a g e n t 的存在【1 8 - 2 0 ；这种a g e n t 实际上不具有社会性，完全可以划到单a g e n t 研究的范畴。 不过，无论什么样的多a g e n t 系统，必然涉及：i 单个a g e n t 行为的描述( 即 单a g e n t 规范) ；因为不管什么样的多a g e n t 系统，其系统的行为必然要归约为 单个a g e n t 的行为；我们在研究多a g e n t 系统时必须对单a g e n t 的行为进行规范， 而在实现的时候还必须考虑单个a g e n t 的结构( 他们应具有什么样的功能1 。2 每 个a g e n t 如何与环境及其他a g e n t 进行交互；在协作情况下还要考虑a g e n t 之间 应如何互相帮助、如何避免不同a g e n t 执行相互抵销的行动。 根据以上的观点，我们可以将多a g e n t 系统视是一个典型的复杂计算系 统。 茎二妻! ! 直 一盟型鲨坠塑塑堕 1 1 3 多a g e n t 系统研究现状 多a g e n t 系统( m a s ) 研究的是如何对有多个独立主体( 或a g e n t ) 的系统的行为 进行描述的问题i t 2 。 关于多a g e n t 系统的理论研究大体上可以分为两大类型： 第一类研究往往基于b d l 模型( 很多a g e n t 理论的研究者希望在逻辑的框架下对 具有意向性的概念进行形式推理在这样的框架下，意图、信念、目标等高层认知功能被 看作( 模态) 算子。而相应的理论模型则被称为信念( b e l i e d - 愿望( d e s i f e ) 一意图( i n 把n t i o n ) 模型， 或b d i 横型) 对系统中a g e n t 的行为进行规范和描述，即表述a g e n t 在多a g e n t 系 统中所应具有的高级认知状态；这种研究描述的a g e n t 通常是协作型的a g e n t ， 而研究的目的在于给出多a g e n t 协作的形式化模型 2 1 2 2 】【2 3 】a 另外一种研究往往运用博弈论、信息经济学、社会学等领域的方法对a g e n t 的行为进行描述与控制，控制a g e n t 之间的协商与协调、或控制a g e n t 在社会中 的行为；这种研究主要用于刻画自私a g e n t ( 只考虑自身利益的a g e n t ) 在一个多 a g e n t 系统中的行为、或研究如何让自私的a g e n t 对其所处的( 子) 系统( 或社会) 作 贡献，并已取得了很多成果 2 4 3 2 】。 鉴于本文研究的是计算智能，下面我们就与本论文相关的第二类研究进行 回顾和讨论。 基于非b d i 模型的多a g e n t 理论 当前在多a g e n t 系统的研究中，博弈论、经济学、社会学等方法主要用于表 述或控制自私a g e n t 的行2 为 3 3 3 7 】1 。自私型a g e n t 源于不同的设计者( 更确切地 说是使用者) 。直觉上，如果一个a g e n t 不能增加它所代表的用户的利益，那么 没有用户会使用他她。每个自私的a g e n t 只关心自己的目标( 虽然不同a g e n t 的 目标可能有重合) 与利益( 实际上也就是其设计( 或使用) 者的利益) ，并且采取能 增加其利益的行动 3 7 1 。另一方面，由于a g e n t 是自私的，如果不对它有所激励， 则它是不会对外界作任何贡献的。某些情况下自私的a g e n t 之间也会共享信息、 互相帮助，这是因为他们发现这是最好的做法。如果某些a g e m 的利益受到损 由于博奔论( 特别是非台作博弈论) 已被广泛地运用到了信息经济学中：在不至引起混淆的情况下，我们 在此把两者看作是等同的 4 塑：塞! ! 宣耻墅壁堂塑望望壁型! 燮 害( 甚至不能被最大化) ，协作是不可能的。下面分别就这些问题进行一些讨论。 一、自私a g e n t 之间的协商与协作 自私a g e n t 之间有时也能从协作中获得利益。这时a g e n t 之间的协作可以利 用防商策略得到加强。 自私a g e ，i t 之间的协商与协作目前有两种主要途径，即博弈论方法和社会学 方法。 l 协商和协作的溥弈论方法 博弈论专家经常考虑博弈的结果，也就是博弈的解。博弈的一个结果包含 处于均衡0 9 “f f f 6 r f “m ) 状态的一组策略或行动；2 如果一组a g e n t 的行动达到了 均衡状态，则没有a g e n t 有积极性改变其策略( 或行动) 。处于均衡的策略组合可 有多个( 也可以没有) ，并且均衡的概念也有多种( 例如，n a s h 均衡，精炼均衡 等1 3 8 3 9 ) 。 建立在均衡概念基础上的讨价还价问题为设计具有协商能力的系统提供了 一个有用的途径。在这种方法中，a g e n t 的协商策略就是非合作博弈中的行动， 协商者的理性则通过纳什均衡( n a s h 脚u i l i b r i u m ) 等概念来描述 4 0 】 4 l 】。 而合作博弈论模型可用于描述a g e n t 之间的资源共享与任务的协作完成。在 此情形下每个a g e n t 都有些任务需要他她完成，同时他她还需要资源以完成这 些任务。尽管a g e n t 可以单独完成他她的任务，但他们的协作可能增加其效益。 k r a u s ( 1 9 9 7 ) , 及她的同事将合作博弈论的方法用到了合作的形成当中。 2 协作s 协商的社会学方法 m o s e s ，s h o h a m ，和t e n n e n h o l t z 4 2 , 4 7 建议在人工系统中使用社会法则( 或 社会风俗，s o c i e t y m e t a p h o r ) l 以提高a g e n t 在“社会活动”中的性能。若所有a g e n t 遵守合适的社会法则，他们将不会到达潜在的冲突情形，这使他们在运行时的 协调减少了。 不过，社会学方法假定了那些法则的设计者能完全控制所有的a g e n t ；a g e n t 被假定遵守那些法则仅仅因为他们是被设计成那样的，而不是因为a g e n t 能从 均衡就是各a g e n t 的最优策略的组合。 笺二童! ! 宣 主堕型堂垫查查堂堡坐 中获得利益。 二、激励问题 现在还有不少经济学家或博弈论专家研究如何设计具有特定性质的博弈的 问题，此问题在经济学中被称为机制设计理论e c 口n 括所比s 瑶卵) 或契约理论 ( i m p l e 聊p n t a t i o ，lt h e o r y ) 3 8 】。这个领域研究的是如何设计能达到特定行为的激励 结构。例如，s h o h a m 与t a n a k e 曾研究了一种类似经济学中的公共财产( p u b l i c 掣，o a s ) 问题的多a g e n t 系统【3 6 ：系统采取什么样的激励结构能使至少一个 a g e n t ( 这些a g e n t 本质上是自私的) 愿意对系统作贡献，并且在某一时刻之后，系 统的价值能不断增加。 三、讨论；这类方法的缺点 虽然这类方法已取得了不少成功的应用，但也存在一些问题。例如，对于 基于博弈论与( 信息) 经济学的方法，构造均衡策略有赖于事先证明的定理，但 这只有当可能的协议定义好之后才能做到。这种情况下需要发展一些为自主 a g e n t 寻找合适策略的复杂度低的技术，然而博弈论中并不讨论此问题。而基于 社会学的方法则是“不稳定的”：假定其他所有a g e n t 都遵守法则，一a g e n t 违 背法则可能会得到更大的利益。对于激励方法而言，现在还不知道如何产生所 需的激励结构【3 6 】。另外，这类方法只适合于a g e n t 数量较少的场合 4 0 】。最后， 羽于一个采用此类方法构建的( 多) a g e n t 系统，其行为往往较为固定，因为这样 的a g e n t 总是按照固定的策略选择行动：因此对于动态环境下的多a g e n t 系统并 不是很适合。 1 2 人工生命方法概述 1 2 1 人工生命方法的提出 如前所述，复杂性代表的是另一种看待世界的哲学观念：以笛卡尔哲学为 基础的近现代科学以及文化传统强调的是从上到下的还原与分析方法，强调有 一个中心控制单元的结构，是机械的观点；而复杂性研究则强调从下到上的集 生兰! ! 童一一j 型塑塑拦燮 成疗法，强调创现，这是非笛卡尔的观点。这样一种观点在人工智能和认知科 学领域里取得了广泛的应用，目前随着s a n t af ei n s t i t u t e ( 简称s f t ) 的研究，它 的影响慢慢地扩展到了自然科学、生命科学、社会科学、行为科学等各个领域 中。这是一次哲学观念的革新。 自然生命系统也是一个高度的复杂自适应系统。对于生命现象来说，最先 引起人们注意的特征也许是它的自我繁衍能力，在4 0 年代，v o nn e u m z n n 在他 舒j 同事们的协助下提出了胞自动机( c e l l u l a ra u t o m a t a ) 模型 4 8 】，开拓了用人造 媒体实现某些生命特性的研究：3 0 后由美国s a n t af ei n s t i t u t e 的一位代表人 物c h r i s t o p h e rg l a n g t o n 进一步发展了这一思想，提出了“人工生命”的概念 f 4 9 】。 人工生命是研究能够展示自然界生命系统的行为特征的人工系统的一门科 学，它试图在计算机、机器人等人工媒体上仿真、合成和生命有机体相关的一 些基本现象，如自我复制、寄生、竞争、进化、协同等，并研究和观察可能的 生命现象( 1 i f e a s i t c o u l d b e ) ，从而使人们能加深理解已知的生命现象( 1 i f e a s w e k n o w i t ) 。 人工生命的信条是：生命并不存在于单个物质中，而是存在于物质的组合 之中；生命行为从大量简单的物质的相互作用中自下而上( b o t t o m u p ) 地创现 出来。这意味着构成生命的物质本身并不重要。这就是生命的抽象性。故生命 系统的实现形式有多种。除了我们已知的炭水化合物的形式，还可以是物理的、 符号的、化学的以及程序的形式等。既可以生存于真实的物理环境 5 0 i 5 1 ，也 f j 丁以生存于真实的软件环境( 如计算机操作系统【5 2 】、数据库 5 2 】、 i n t e m e t 5 3 5 4 1 1 5 5 5 6 】) 或者某种模拟环境( 如积木世界、计算机仿真 5 7 】) 。 人工生命更重要的意义或许在于其高度的抽象性。许多实际的复杂的系统， 就是人工生命系统，比如股票系统就是一例。但不要以为实际的复杂的系统均 是人工生命系统，比如树叶飘落的过程。能被视作人工生命的系统在发展变化 的过程中永不停息的生成秩序和结构，不断刨现出永恒的新奇性。这是系统的 一种内禀性质，现在称之为复杂性。人工生命能让我们以新的眼光审查些传 统的学科，比如经济学、社会学与人工智能等等。这些学科所建立的基于形式 的模型由于没有反映出系统的复杂性特征，所得结果往往与实际不符，甚至大 第一章引言 中国科学技术大学博士论文 相径庭，而采用人工生命技术让这一局面大大改观。 人工生命的奋斗目标就是试图获得进化与自组的一般理论。人工生命的研 究为复杂性的研究提供了新的思路与工具。以前，人们试图运用数学模型去解 释复杂性，以及解决复杂性所引起的问题，对实际系统的再三简化，直到能做 精确数学分析的地步，这往往导致极为荒谬的结果，因为这样得到的系统往往 是个死的系统，采用人工生命的手法则得到很逼真的结果。 人工生命是一门综合性很强的学科( 我们可用图1 1 所示的三元交集概括人 生命的定义i s 8 ) 它吸引了计算机科学、认知科学、生物学、生态学、经济 学、社会学等众多领域的研究人员，人工生命能让我们以新的眼光审查一些传 统的学科，它的每一项成果必将对这些领域产生深远的影响。 图1 - 1 人工生命的三元交集定义 1 2 2 人工生命方法的特点 考虑人工生命的基本特征，我们在研究人工生命的上述基本内容时应考虑 如下原则； ( t ) 不是自上而下的原则，而是自下而上的研究策略。 苎二童! ! 童 一里型型型型堂堕 ( 2 )不是全局控制，而是局部控制。 ( 3 )不是复杂行为而是简单行为。 ( 4 )不是预先指定的行为，而是创现行为。 ( 5 )不是个别实体模拟，而是集团模拟。 如果能满足上述原则，则可以构成人工生命研究的大致技术路线，它是个 封闭的状路线，如图1 ，2 。该图表明了局部与全局的相互依赖关系，由局部行为 构成全局动力学，再通过全局动力学形成局部环境，这种局部环境对局部行为 产生影响，受影响的局部行为再次构成新的全局动力学，如此反复，直到 产生人们期望的“生命特有行为”。 图i 2全局与局部的依赖关系 1 2 。3 进化在人工生命方法中的意义 人工生命的奋斗目标就是试图获得进化与自组的一般理论。和自然生态系 统一样，人工生命的精髓也遵循达尔文的生物进化论，即适者生存( s u r v i v a lo f t h e f i t t e s t ) 和自然选择( n a t u r a ls e l e c t i o n ) 。人工生命系统的主要特征表现为：进化 特性( e v o l u t i o n ) 和创现行为( e m e r g e n tb e h a v i o r ) 。进化性为适应动态变化的 环境提供了可能性，即当无法预测的事件发生时，人工生命系统能象自然系统 样通过进化适应新的环境。鉴于进化对系统实现自适应的重要意义，各国研 究人员一直在不断地探询更能全面反映进化过程的进化理论与模型。 堑皇! ! 童堕瞠鲢壁些堕 六十年代初期，h o l l a n d 开始致力于适应性理论的研究。1 9 7 5 年，遗传算法 的经典著作自然和人工系统中的适应性一书出版，该书总结了他十多年来 对学习、进化和创造性之间深刻的内在联系的思考，对遗传算法做了周密的阐 述。在遗传算法中，问题的解表达为由某种有限的固定字符集形成的字符串， 该算法启动时，先随机生成一批字符串，然后依据所得结果的质量对每个串进 行评分，质量高的串用以繁衍后代，质量低的串自动消亡，如此一代代地下去， 能圆满解决问题的字符串将最终占据优势。 七十年代末期，h o l l a n d 又提出了基于遗传算法的认知模型。分类器系统。分 类器系统遵循三个基本原则：知识能够以类似规则的结构表达，这些规则始终 处于竞争之中，经验使得有用的规则越来越强，无用的规则越来越弱；新规则 产生于旧规则的组合之中，分类器系统体现了进化适应性与学习适应性的完美 统，1 9 8 3 年，d a v i dg o l d b e r g 证明了怎样把遗传算法和分类器系统运用于对 个模拟的煤气管网线的控制。该工作为遗传算法和分类器系统赢得巨大的声 誉，以至被h o l l a n d 誉为分类器系统研究的一个里程碑。 在八十年代后期，针对遗传算法中预先将问题的解规定为固定长度的字符 串的情况的不足，s t a n f o r d 大学计算机系的教授j o h nk o z a 提出了遗传程序 ( g e n e t i cp r o g r a m m i n g ，简称g p ) 的概念，在遗传程序中，问题的解表示为由 函数和端点构成的计算机程序，问题的求解归结为在可能的程序空间中通过复 制和杂交寻找一个能较好解决问题的程序。相对于遗传算法，遗传程序中解的 表达方式更自然，而且能在更大的空间中搜索问题的解。 在遗传算法发展的同时，由美国的l j f o g e l 、aj o w e n s 和m j w a l s h 提出， 又由d b f o g e l 进行了完善的进化规划【5 9 ，以及由德国的1 r e c h e n b e r g 和 h p s c h w e f e | 建立的进化策略【6 0 】也得到了广泛的应用，从而构成了目前进化计 算的三种典型的算法。 无论是遗传算法，还是其他的进化算法，存在些共同的不足。第一，就 是适应度量函数是预先定义好的，而真正的适应性应该是局部的，是个体在与 环境作生存斗争的自然形成的以及随着环境变化而变化的。遗传算法或遗传程 序中的选择机制，充其量来说，只是一个人工选择，而非自然选择。第二，遗 传算法或遗传程序等只考虑到生物之间的竞争，而没有考虑到生物之间协作的 塑：童! ! 宣 ! 里型兰童塑立壁兰塑兰：i ! 墨 可能性。真实情况是竞争与协作并存，这也就是所谓的协同演化。生物学证据 表明协同演化能大大加快生物进化的历程。 人工生命的研究者企图在最广泛的意义上回答进化的问题，并使之得到更 加深入的研究，对于进化的研究，最令人感兴趣的事情莫过于由简单的初始状 态出发演化出逐步增长的复杂性。正如老子在道德经中所云：道生一，一 生二：，二生三，三生万物。进化的观点，从最一般的意义上来说，意味着从研 究对象的历史和发展变化中把握对象的实质，而不应将现实与历史割裂开来。 这对复杂性的研究有重大的指导意义。但是，目前还没有形成类似于遗传算法 那样严密完整的一般的进化理论。所得的仅是一些设计进化模型时应遵循的基 本原则。但这并没有防碍人工生命技术在实际中精巧的应用f 5 5 1 1 5 6 3 1 6 1 1 。 1 3 本文的研究动机与研究目标 多主体系统( m a s ：m u l t i a g e n ts y s t e m ) 的理论及应用研究已成为多学科 帮j 人工智能交叉研究的一个热点，针对m a s 理论、框架、体系结构的研究工 作很多，随着m a s 在诸多领域的应用，研究能自适应复杂动态环境( 自学习) 的m a s 更有意义，也成为当前的个研究重点。由于a g e n t 作为- - e o 具有生 命特征和智能行为的抽象实体，必须通过对环境的感知作用于自身和周围环境， 因此对m a s 学习能力的研究应全面考虑环境的动态性，实现学习的手段及a g e n t 诒系统中的行为特征等侧面。针对这些侧面研究相对全面而深入的是生态科学， 牛态学认为生活在自然生态系统中的生物一方面基于变动环境进化，同时又逐 渐形成相互协同关系；进化和协同行为的均衡和统一是实现系统学习能力的主 要手段，并对系统的结构和多样性起着极为重要的作用f 6 ”。我们看到：a g e n t 在 m a s 中的行为在很多方面类似于生物在自然环境中的生态行为。因此，从生态 系统角度，基于生态特征研究m a s 的进化学习模型是很有意义的，对解决国 民经济和社会发展的许多问题( 如大规模复杂系统的优化控制，网上信息获取 等) 有着引入注目的现实意义和发展前景。 需要指出的是：目前对m a s 学习能力的研究主要侧重于用传统的符号人工 智能( a 1 ) 方法研究多a g e n t 的协同，主要方法大体有基于b d i 模型的形式化 墨二兰! ! 宣 主里型兰垫查奎兰堡主! 生坠 方法 6 3 和基于非b d i 模型的博弈法及信息经济学方法 6 4 】，总的来说构造的 m a s 难以自适应动态环境，基本不具有进化能力，因而系统的学习能力较弱； s t o n e 等人为提高其学习能力，采用了机器学习啾 6 5 1 。而以计算智能为工 具，从生态系统角度来研究可以更全面认识多a g e n t 系统，国际上相关研究还 处于萌芽阶段( 如a g e n t 的反应式体系结构【6 6 】就部分体现这思想) ，国内在 这方面尚处于起步阶段，很少见报道。其中国外的研究进展和有代表性的研究 事例有：m o u k a s 提出了一个初步的网络管理平台模型 6 7 ，此模型被模拟为一 生态系统运作，但没有考虑系统环境的复杂性和a g e n t 的复杂行为如何设计， d a v i d o r 的e c o 模型只是一生态进化系统 6 8 1 ，没有个体间协同的指导模型； 而c d r o s i n ，x i ny a o 等人的工作很有代表性，但只是在进化模式层次研究进化 与协同的混合 6 9 1 ，这些工作都没有达到从生态系统行为研究的高度，以计算 智能为工具研究m a s 的进化与学习都不够全面和深入。c f x , j 这一领域，近年 我们开展了些工作 7 0 ，7 1 ，7 2 1 ，根据初步体会，我们认为： ( 1 ) 传统的符号a i 方法采用自上而下的研究思路，难以适应环境的动态变化， 难以描述a g e n t 的进化行为和其他复杂行为，导致相应的多a g e n t 系统的学习能 力很弱。因此有必要同时采用自下而上的人工生命研究策略，计算智能正是这 样的一种方法。 ( 2 ) 生态学认为a g e n t 进化和协同行为的均衡与统一赋予m a s 自适应动态环境 的能力，因此对进化和协同的研究不可分割。现有工作的缺点是：符号a i 方法 不以计算智能为工具就难以同时研究进化，且难以建立多a g e n t 的协同数学模 型。进化算法主要只关注进化行为，近年来的进展也只是在进化算法设计中使 个体( a g e n t ) 交互协同与进化；从生态系统角度，此方面的研究同样层次不高。 我们目前的工作以个体的进化行为为基础，借鉴生态学描述个体协作关系的s 型方程和l o & a - v o l t e r r a 方程，较好描述了a g e n t 在个体层和群体层的协同，但 还没有建立进化与协同的统一模型。另外，以进化行为还是以协同行为为主线 来研究是目前回避的一个问题，多数生态学家强调进化行为的基础作用。 ( 3 ) 虽然已有研究者意识到必须从生态系统的高度，以计算智能为工具来全面 研究m a s 的学习能力，现有工作很少考虑影响a g e n t 智能行为的一些重要生态 特征。我们在此方面做了一些初步工作。另外，现有的研究很少涉及