（计算机软件与理论专业论文）基于分级行为选择的人工生命体基因进化算法研究.pdf

摘要 人工生命有广泛的概念，一个真正的人工生命体是能够自主决定 自己的行为，而本文研究的问题之一是人工生命体的基于优先度的行 为选择的问题。借鉴已经有的“刺激驱动机制与“基于动机 的机制相结合的办法，考虑了外部刺激和内部动机两方面行为选择的 影响，我们建立了人工生命体的群集、逃跑、捕食等简单行为模型， 依据这些模型进行人工生命体的个人生存和社会活动。我们建立的模 型在较低的代价下获得了较好的性能，便于实时观察与处理。 对于所建立的行为模型，采用c + + 作为程序代码开发语言，来实 现人工生命体的行为，基于行为考虑，选择速度基因和视野基因，并 且采用二进制编码，用遗传进化算法进行分析，通过代码的遗传，交 叉，变异，实现人工生命体的遗传，生殖，以及基因突变。 建立仿真平台，该平台中创建了一个虚拟的世界，里面的人工生 命体对象具有如生长( 衰老) 、应激反应、能进行能量交换( 进食与食 物消耗) 和生殖等等生命特征，构造了个性化的人工生命体，实现了 现实生态系统中的人工生命体逃跑、捕食、生殖、聚集成群等行为， 并且实验得到一系列基因数据，统计分析这些数据后，我们发现人工 生命体基因的进化中实现了自然中的先天遗传、优胜劣汰等基本规 律。 关键词：人工生命，行为选择模型，遗传算法，适应度 a bs t r a c t a r t i f i c i a ll i f eh a v eab r o a dc o n c e p t ，at r u ea r t i f i c i a ll i f eb o d yi sa b l e t oi n d e p e n d e n t l yd e c i d et h e i ro w nb e h a v i o r , a n dt h i sp a p e ri so n eo ft h e i s s u e so fa r t i f i c i a ll i f eb a s e do nt h ep r i o f i 妙o ft h ei s s u eo f c h o i c e s o m e r e f e r e n c eh a sb e e n t os t i m u l a t e d r i v e r ”m e c h a n i s m 件b a s e do nt h e m o t i v a t i o n o fc o m b i n i n gt h em e c h a n i s mt oc o n s i d e rt h ee x t e r n a la n d i n t e m a lm o t i v a t i o nt os t i m u l a t eb o t ht h ei m p a c to fc h o i c e ，w eh a v e c r e a t e da r t i f i c i a ll i f eo ft h ec l u s t e r ，e s c a p e ，p r e d a t i o ns i m p l ea c t s ，s u c ha s m o d e l ，b a s e do nt h em o d e lo ft h ep e r s o n a ll i f eo fs u r v i v a la n ds o c i a l a c t i v i t i e s w eh a v ee s t a b l i s h e dt h em o d e la tal o w e rp r i c eu n d e rab e t t e r p e r f o r m a n c ef o rr e a l - t i m eo b s e r v a t i o na n d t r e a t m e n t t h em o d e le s t a b l i s h e db yt h ea c t ，u s i n g 咔p r o g r a m m i n gl a n g u a g e a sac o d et oa c h i e v et h ea r t i f i c i a l l i f eo ft h ec o n d u c t , b e h a v i o r - b a s e d c o n s i d e r a t i o n s ，c h o i c eo fs p e e da n dv i s i o ng e n e ，a n du s eo fb i n a r yc o d e ， t h ee v o l u t i o n a r ya l g o r i t h mu s i n gg e n e t i ca n a l y s i s ，t h r o u g ht h eg e n e t i c c o d e ，m l ec r o s s o v e ra n dm u t a t i o n ，a n da r t i f i c i a l l i f eo ft h eg e n e t i c ， r e p r o d u c t i v ea n dg e n e t i cm u t a t i o n s 强oe s t a b l i s h m e n to fs i m u l a t i o np l a t f o r m , t h ep l a t f o r mi nt h e c r e a t i o no fav i r t u a lw o r l d ，a r t i f i c i a ll i f ei n s i d et h eb o d ya sat a r g e tg r o w t h ( a g i n g ) ，t h es t r e s sr e s p o n s e ，e n e r g ye x c h a n g ec a nb ec o n d u c t e d ( w i t ht h e c o n s u m p t i o no ff o o dc o n s u m p t i o n ) a n ds oo nl i f ea n dr e p r o d u c t i v e c h a r a c t e r i s t i c s ，c o n s t r u c t e dc u s t o m i z a t i o no ft h ea r t i f i c i a l l i f ea n d r e a l i z e dt h er e a l i t yo ft h ee c o l o g i c a ls y s t e mo fa r t i f i c i a ll i f eo fe s c a p e , p r e d a t i o n ，r e p r o d u c t i v e ，g a t h e r e di ng r o u p ss u c ha c t s ，a n dr e c e i v e da s e r i e so fe x p e r i m e n t a lg e n ed a t a , s t a t i s t i c a la n a l y s i so ft h e s ed a t a , w e f o u n dt h a ta r t i f i c i a ll i f ei nt h ee v o l u t i o no fg e n e si nt h er e a l i z a t i o no ft h e i n n a t en a t u r eo f t h eg e n e t i c ，a n do t h e rb a s i cl a wo fs u r v i v a lo f t h ef i t t e s t k e yw o r d s ：a r t i f i c i a ll i f e ，t h ec h o i c eo fm o d e l s ，g e n e t i ca l g o r i t h m s , f i t n e s s 珏 原创性声明 本入声明，所呈交的学位论文是本人在导搏指导下进行的研究 工作及取得的研究成果尊尽我所知，除了论文中特别加以标注和致谢 的遮方井，论文中不包含其缝人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所侔的贡献均已在论文中作了明确的说明夺 作者签名：弘纽吼雌月监旦 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阗；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数搌库， 并通过丽络向社会公众提供信息服务。 作者签名：舡导师签孝例日期：龇心压日 中南大学硕士学位论文第一章概论 1 1 人工生命科学的简介 第一章概论 生命现象的奥秘和生物的智能行为一直被科学家所关注，生物系统是一个典 型的复杂系统。生命科学是研究生命现象的科学，它以地球上的碳水化合物为基 础的生命为研究对象，包括人类、动物、植物。有生命的物体和无生命的物体之 间是否存在某种联系，是否有着共同的规律，引起了科学家广泛的研究兴趣。生 命从无到有，从单细胞到多细胞，从无机物到有机物，从低等生物到高等生物， 最后诞生人类，经历了亿万年的发展过程，随着进化过程的发生，生物形态趋向 更加复杂和多元化的发展。进化、遗传、新陈代谢等起源于生物学的概念，现在 已经渗透到许多具有类似生物特征的系统中。近些年来，生物学、信息学、系统 学、物理学、认知科学、数学等学科的交叉渗透【l 】，对生命系统做了不同的定义。 正是这些不同领域科学的发展和互相推动，促使人们从更广阔的角度来讨论生 命，用人工的方法去研究生命，从而诞生了人工生命这一独立的学科。 1 1 1 人工生命科学的产生 1 9 8 7 年9 月2 1 日，在美国l o s a l a m o s 的人工生命研讨会上，人工生命作为一门 新的学科诞生。c g l a n g t o n 教授是人工生命这一概念的创始人，被公认为“人 工生命之父 。l a n g t o n 从当时流行的生命游戏中总结出一类具有生命特征的系 统的存在性，初步给出这种系统的描述，并定义为人工生命( a r t i f i c i a ll i f e ) 2 1 。 像许多新兴学科一样，人工生命尚无统一的定义，不同学科背景对人工生命 有不同的理解。l a n g t o n 认为人工生命是“研究那些具有自然生命现象的人造系 统一：“人工生命是这样的一个研究领域：致力于去抽象出生命现象的基本动力 学原理，并把这些原理运用到别的媒体比如说计算机使得它们进入到这 些媒体实现操纵和接受检验 。除了为地球上己知的生命形式提供新的研究方法 外，在“生命之如其能( l i f e a s i t c o u l d b e ) 的广阔图像中将“生命之 如所识 ( l i f e a s w e k n 0 w i t ) 加以定位，从而对生命本质进行研究。t r a y 也曾说过。人工生命用非生命的元素去构建生命现象以了解生物学，而不是把自 然的生物体分解成各个单元，它是一种综合性方法而不是还原的方法。c t a y l o r 则说“人工生命模型有足够强大的功能来获取复杂系统中更多的认知。这种方式 较之自然系统更容易被操纵、重复和精确控制试验 。总的来说，人工生命就是 研究那些具有生命特征的人工系统，该系统能够演示具有自然生命系统特征的行 为。l a n g t o n 认为人工生命的框架具有三点基本规则：由底向上( b o t t o m - u p ) 、分 中南大学硕士学位论文第一章概论 布式( d i s t r i b u t e d ) 、和局部规则决定行为模式( l o c a l - d e t e r m i n a t i o no f b e h a v i o r ) 3 1 。随著研究领域的拓展，不断被丰富和发展。从方法学角度看，人 工生命还具有如下特点嘲： 1 、自底向上的建模策略，属予数据驱动策略； 2 、局部豹控制机理，从磊表现出并行操作特性； 3 、简单的低层次表达单元，以适于计算机仿真； 4 、创发的行为过程，反映了进化仿真的特点； 5 、群体的动态仿真算法。 总丽言之，人工生命没有采用传统的由上而下的分析方法，而是从闯题的底 层开始，由下雨主地进行综合研究，将简单的、局部规则支配的对象构成大的集 合，并且在其交互作用中的非线性得到类似生命的全局动力学支持。 1 1 2 人工生命科学的发展 鑫扶兰顿提磁人工生命的概念以来，人工生命研究已经走过近二+ 年煎历 程。人工生命科学的独立学科的地位已经被囡际学术界所承认。1 9 9 4 年创刊并在 著名的美国麻省理工学院如舨的国际刊物人工生命( a r t i f i c i a ll i f e ) ，是 这个研究领域的权威刊物。成立于1 9 8 4 年美国新墨西哥的圣塔菲研究所，是“复 杂性研究的前沿阵地，该研究所的基本思路是所谓的复杂适应性系统理论与基 于多主题的计算机仿真与模拟，其工作对传统的经济学、社会学、生物学造成了 巨大的影响。欧洲很快对这一新的科学领域产生了浓厚的兴趣，自1 9 9 1 年以来连 续每两年举行一次关于人工生命魏研讨会欧洲入王生命会议移( e u r o p e a no n c o n f e r e n c eo na r t i f i c i a ll i f e ，简称e c a l ) ，每次会议都有论文集出版。日本 学者在这一领域的研究特点是把人工生命的研究和进化机器入的研究结合在一 起。为人工生命学术界所公认的是入工生命大会( a l i f e ) 1 5 j ，己经在欧洲举行了 七届( 包括1 9 8 7 年第一次人工生命学术会议，分别为a l i f ei ，a l i f ei i ，a l i f e i l l ，a l i f ei v ，a l i f ev ，a l i f ev i ，a l i f e ，这七次学术会议构成人工生命 学科发展轨迹在时间维上的重要坐标点。1 9 9 7 年9 月在北京举行的“人工生命与 进化机器入研讨班 是我国第一次举办这样的学术活动，壶中科院自动化研究所 与中科院系统研究所联合发起，邀请参加的专家来自美国的s f i 、m i t 、加拿大、 圜本与中匿。2 0 0 1 年9 胃国家皇然科学基金委员会将搿人工生命系统理论及其应 用 列为基金委信息科学部“十五 优先资助的领域。 1 。3 人互生命学科的研究内容 人工生命学科自创立以：来，在备个领域取得了大量的应用和拓展，人工生命 2 中南大学硕士学位论文 第一章概论 学科不断地被丰富和发展，同时也影响着许多领域。从研究的领域和不同的研究 侧面，大致可以将人工生命学科的研究内容分为以下两类【6 1 ： l 、构成生物体的内部系统，包括脑、神经系统、内分泌系统、免疫系统、 遗传系统、酶系统、代谢系统等； 2 、生物体及其群体的外部系统，包括环境适应系统和遗传进化系统等。 人工生命系统中产生的生命行为一般是在生物学基础上综合仿真，并引用具 有遗传和进化特征的模型及相应的生态算法得到的，单纯采用某种单一方式难以 解释行为的产生和操作机理。人工生命是在基于综合的观点下进行研究的，这是 人工生命研究与生物学研究在方法上的显著区别之二。各种人工生命系统的表现 形式和算法不尽相同，但是从内在的机理出发，人工生命的科学框架可由下列主 要内容构成u 1 ： l 、生命现象仿生系统。这种系统一般是针对某种生物的某种生命现象进行 的，并多以软件形式实现，对生命现象进行人工建模和仿真。这方面典型研究包 括早期的鸟声模拟、细胞自动机及生命游戏、l 一系统等，现在人们还应用人工 生命模拟生物圈，研究生物之间的作用和生态环境对生物的影响。 2 、与数学、进化动力学、混沌学、系统学等相结合，进行复杂性、非线性 研究或者计算理论的开发和应用。圣塔菲研究所主要从事人丁生命复杂性方面的 研究，另外兰顿、卡易纳格尔和斯蒂芬拉斯谬森等也进行这方面的工作。主 要研究生命系统这个复杂对象表现出来的非线性动态特性，其突现性( e m e r g e n c e ) 主要通过混沌( c h a o s ) 机制进行研究。关于人工生命的计算理论，遗传算法、遗 传编程、进化算法是人工生命系统开发的有效工具，同时也在各个领域取得了广 泛的应用。人工生命的局部规则进化的思路可以很好的解决多约束优化问题。 3 、与传统的人工智能应用领域相结合，应用于进化学习日本的a t r 的人工 脑研究、机器智能( 群体智能、进化智能) 、机器人应用( 如最优路径、躲避障碍、 人机的自然交流) 、识别技术等等。其中，r o d n e ya b r o o k s 提出了基于行为的机 器入设计方法，设计出进化机器人，对于同一任务，其编码长度可以是传统的设 计方法的1 1 0 0 0 。目前人工生命这方面的应用距离实用性还相差很远，但是从其 发展趋势来看，应用潜力还是相当巨大的，前景十分诱人。 4 、与其他学科交互作用，进行面向应用的技术研究和系统的开发，例如应 用于图像开发、计算机动画( 著名的“晓媛的鱼 ) 、娱乐游戏等。人工生命还可 以用于字符识别、图像恢复、图像特征提取交通建模等方面l l j 。 人工生命目前的应用偏重于对其基本思想的具体学科运用，具体方法方面偏 重于遗传算法、遗传编程等进化算法人工生命的理论和工具目前还没有取得本 质性的突破，所以使其应用受到了很大的局限性。 3 中南大学硕士学位论文第一章概论 1 1 4 人工生命学科的特点 l a n g t o n 认为人工生命采取自下而上的方法，从组成系统的自主个体开始， 由个体的相互作用，逐渐进化、发展，从而实现突现的复杂行为。突现是人工生 命中重要的特性，关于突现行为目前还没有统一的定义。在系统复杂性研究中， 突现是一种源于低级行为规律的、未预期的高级现象的呈现。l a n g t o n 认为突现 是处于低级与高级行为之间的反馈，“在设定的边界条件下，一组个体局部地按 动力学规律相互作用可以孕育出一种整体范围上的动态结构，并获得稳定。这种 整体范围结构的构建既有局部的基础，又在进化中得到整体上的提炼【8 】 许多生物模型一般假定种群中的个体是相同的，或者用种群中个体的均值来 描述群体现象。因此，生物模型中同一个种群中个体的交互作用也是同一的。尽 管如此，基于个体的生物模型不可避免地需要强调个体差异和局部交互作用。生 物分布模型和形态模型是两类基本的个体生物模型，生物分布模型认为种以群 分、物以类聚，形态模型按个体差别和局部交互对种群中所有个体进行考察。个 体形态模型可以看成是一种人工生命模型，人工生命的创始人l a n g t o n 认为人工 生命模型区别于个体模型有以下四个方面： l 、人工生命模型由多个描述个体行为的简单程序组成； 2 、不存在一个程序起主导作用； 3 、每个程序描述个体在局部环境中的交互方式； 4 、不存在确定种群整体行为的规则，任何高于个体级别的群体行为都是突 现的。 1 2 人工生命研究的方法和目的 人工生命是当前生命科学、信息科学、系统科学及工程技术科学的交叉研究 热点，也是人工智能、计算机、自动化科学技术的发展动向之一，人工生命的意 义不仅在于探索生命的奥秘，它还为工程应用提供了重要的研究方法。 人工生命采取自下而上的方法，从组成系统的自主个体开始，由个体的相互 作用、逐渐进化、发展，从而实现突现的复杂行为。人工生命的思想对于研究非 线形系统有很大的启发性。在研究线性系统时，可以将系统分解为独立的互不干 扰的部分进行研究。分析清楚了每个部分，也就可以根据线性性得到整个部分的 机制和性质。而对于非线性系统，由于它的性质主要体现在各个部分的相互之间 的非线性作用而不是各个部分本身上，所以即使可以分解为各个部分来研究，也 无法得到整体的性质。这时，传统的分析方法显然失效。如果我们采用人工生命 的方法，就可以从部分出发，将部分按照一定的非线性关系加以综合，从而可以 4 中南大学硕士学位论文第一章概论 模仿出系统的行为。 人工生命是自然生命的模拟、延伸与扩展，研究人工生命具有重大意义吼 1 、为自然生命的研究提供新的手段。例如：计算机虚拟生命可以为自然生 命活动机理和进化规律的研究探索提供软件模型和先进的计算机环境；而人工脑 可作为自然脑的机理和功能模型。 2 、可以开发基于人工生命的新系统、新产品、新技术。如基于人工生命的 计算机动画方法可以自动生成逼真的人工生命和虚拟社会；基于人工人的进化机 器人，具有更好的自适应、自学习、自寻优的性能，有助于实现更高智能的自动 化。 3 、利用人工生命研究延伸人类寿命、减缓衰老、防治疾病。 4 、扩展自然生命、人工进化、优生优育。 5 、促进生命科学、信息科学、系统科学的交流与发展。人工生命研究的重 要内容和关键问题是生命信息的获取、传递、变换、处理和利用过程的机理与方 法。而这些正是信息科学面临的新课题，也是信息科学发展面临的新机遇。 所以，人工生命的研究及应用具有重大的科学意义和深远的社会影响。 本论文从人工生命的基本原理出发，运用人工生命系统的遗传算法和人工生 命的计算机模拟对草原生态系统中的捕食者狼和消费者羊行为进行简单模拟研 究【9 】，仿真它们的几种简单行为，达到在计算机上实现生物简单的行为选择，并 且能够进化。 1 3 人工生命行为选择研究的国内外状况 1 3 1 行为选择的目标 行为选择的适当与否应由选择行为的目标来评价。动物是自身基因传播与繁 殖的载体，而它们常常面临着危险，在长期求生存过程中选择合适的行动是非常 关键的。因此，动物选择行为的最终目标是选取那些行为，以增大后代中它的基 因被复制的数量。这最终是通过生存和繁衍来实现的。生存与繁衍这个目标分解 为一系列日常行为的需求，如获取食物、逃避天敌与交配等。对于一个机器人来 说，为了完成分派给它的任务，行动选择机制必须维护机器人的安全。对虚拟动 物和自主的动画角色来说，行动选择的目标是获得令人满意的行为逼真度f l o 】。 由于上述目标的数学表达很复杂，难以通过数学方法，如最优化方法去建立 行动选择机制。所以一般把“行动选择机制 问题作为设计问题来处理，因而主 要的任务是制定适当的设计标准。 虽然真实动物的行为选择目标与人工生物行为选择看来似乎不同，但是，它 5 中南大学硕士学位论文第一章概论 们实质是类似的，行为选择机制使动物能面对不断变化的情况采取合适的行为。 当一个虚拟动物的行为看起来很逼真时，通常是指它所表现出的行为是合理的。 象真实动物那样，虚拟动物也“知道逃避危险、抓住机遇和合理分配资源等f l l 】。 本文的研究重点主要在于人工生命体选择什么样的行为，而不是具体一个行 为由哪些下层行动来完成，虽然我们要为这些行为设计行动控制程序。例如更关 心人工生命体是选择捕食行为还是逃跑行为，而不是它选中一个行为后的具体行 动。从这个意义上说，关注的是行为或行动选择中上一层意图的产生。 1 3 2 行为选择的一些已有研究 在以前的行为动画工作中，有些科学家只用“刺激一驱动 行动选择过程建 立了行为选择模型，行为由环境条件直接激活，如r e y n o l d s 的b o l d 群体 1 2 】。在 一些机器人技术中，也采取了类似策略，其中所采用的应激机制对环境中出现的 意外情况，具很大优越性，但是这种机制没有考虑智能体的内部状态或内部动机。 生态学中动物行为的研究也表明动物的行为除了应答环境因素的刺激所做 出的反应外，还起源于动物机体内部自发的调节变化或生理需要。所以单纯只考 虑“刺激一驱动【1 3 】一不但难以处理好复杂的行为选择问题，而且也和动物行为选 择的研究不符。 d o n n a r t 和m e y e r 设计了一个行为控制系统并进行了仿真，它的控制结构可以 用两个产生式规则1 1 4 】来描述： 行为规则： i f a n d t h e n 计划规则： i f a n d t h e n 日本科学家也采用了相似的方法来实现机器人的行为选择。首先，建立情形 集( s i t u a t i o n s ) ，然后建立基于情形基础上的行为集( s i t u a t e db e h a v i o rs e t s 简写为s b s ) 。行为选择的规则为： i fas t a t et h e na na c t i o n 上述的两种方法均采用行为准则来为机器人选择行为，都是根据当前的形势 或条件来判定应该采用哪种行为。显然当考虑复杂的环境和行为时，当前形势或 条件的归纳会变得非常复杂甚至难于总结。所以这种行为选择方法难以处理复杂 环境中的问题，并且他们是只基于外部刺激驱动的。 国内的一些研究曾用基于生长神经网络的进化机器人行为算法来实现机器 入的行为选择，并进行了模拟。其特点是通过自然选择对神经网络进行进化，能 自主实现机器人避碰、移动、复制和攻击等行为，缺点是进化效率不高，需要较 6 中南大学硕上学位论文第一章概论 多的时间步后才能得到较好的选择效果。 一些特殊用途的机器人行为选择方法如用于足球赛的机器人，它是根据所要 完成的功能或危色来确定如何选择行为，这些行为选择方法幽予其较强的针对性 难以被使用到一般的人工生命体的行为选择模型中来。 其它的行为选择方法中，有代表性的三种典型方法是：行为选择的分级处理 方法、行为选择网、自由流动层。 3 3 行为选择隧 m a e s 提出了个分布式的、不分级的“行为选择阚”，即所谓的“行为选择 的自底向上机制。它在进行行为选择时，考虑了内部动机和外部刺激。网络的 节点代表行为单元，并用有特定网的的链相连，如抑制网络。网络的整体行为是 由节点之间的相互俸曩l ，以及节点与环境的交互作用| | 莠表现蹬来。更明确地说， 激发能量从外部感知和内部动机流向不同的行为节点。不同的行为单元通过网络 来相互激发和抑制。在某些时间艨，激发麓量在表示“最优”的节点积累起来， 这个节点即为最优者，给出了人王生命体的当前状态和动机。 如图l l 所示，不同行为通过翦驱( p r e d e c e s s o r ) ，“后继 ( s u c c e s s o r ) 和“冲突纾( c o n f l i c t e r ) 连接起来。她认为这些行为间的连接是生命体生来具有 的或是通过学习得到的。如果行为b 使得行为a 的条件得到实现，则认为从行为a 到孳亍兔b 有一个前驱连接。例如，如果食物在人工生命体的控制范围内，行为 “e x p l o r i n g ”可能使行为“e a t i n g 的条件成熟。如果行为b 使得行为a 的条件 不成立，则认为行秀矗和嚣之阀有个冲突( c o n f l i c t e r ) 连接。如当附近有另一个 人工生命体时，逃跑行为( f l e e i n gf r o ma n o t h e rc r e a t u r e ) 可能使打架行为 ( f i g h t i n g ) 的条件不成立阻h 】。 行动选择网的主要优点是： l 、激发能量是一种连续流，它允许从一个行为平缓地转变为另一个行为； 2 、它不采用集中控制，更为灵活： 3 、行为选择过程更具有鲁棒性。 儇是行为选择露也具有局限性，如不清楚如何使用它实现全局功能，两且需 要仔细调节参数；每个节点的感觉输入都是二进制形式，一些潜在的有用信息可 能丢失；生态学家认为行为选择的基本结构本质上是分级静，行为选择网的“扁 平静式方法与这一研究不符。这就意味着不能很好地处理动物的行为选择问题。 采用与行为选择网类似的结构，b e e r 和c h i e l 用一个基予神经生态学的人工 神经网络系统实现了昆虫的简单行为选择。后来w e r n e r 为了巍服自由流动层的重 复累计输入信息的缺点，提出了一个与m a e s 的行为选择网相似的基于三级神经连 7 中南大学硕士学位论文 第一章概论 接的枫制，并实现了并行行为的选择隧羹。 1 3 4 自由流动层 、， s u o m s s o rl i n k 露 一p r 嗒s o r l 鼢 广c o n f l i c tl i n k e r 图1 - 1 行为选择网例图 为了允许从不同的候选行为中进行证据组合，以及选择折衷行为，科学家们 提出了另一种行为选择机制。其中所有行为节点对每一组行动都有偏好，而不是 去决策哪个行动是最优的。最终选择是所有的偏好的加权和。这种方法后来被推 广成所谓的“自由流动层一( f r e e - f l o wh i e r a r c h y ) 。一个自由流动层中所有节 点都能影响智能体的后续行为，为较低层的活动表示期权的偏好。这个过程蔓延 到整个层次，其结果不是在每层中做出一个决策，而是当最高偏好的行动被选中 时，仅在最低层做爨一个决定。 仿真结果表明，“自由流动层 的性能超过了m a e s 的“行为选择网和其他 机制。然褥，它的各种偏好需要仔细地权衡来进行设置，两且它必须处理了所有 感觉信息，并计算出各部分的偏好盾，才能做出决策。它是以高复杂性和低效为 代价来获得性能的，所以难以做出实时处理【i j i i 引。 8 中南大学硕士学位论文 第一章概论 1 3 5 行为选择的分级模型 由于上述模型所具有的缺陷，在已经实现的行为选择模型中，很多是用分级 的行为选择模型。文献 1 中，人工鱼的行为选择系统也是典型的分级模型。 采用分级模型的优点是： l 、处理方便：分级结构具有较高的直观性，系统可以用模块方式进行组合。 而且在分级行为中，由于存在固有的优先次序关系，行为之间的矛盾大大减少； 2 、可以进行信息共享，高级行为所获得和处理的知识和信息，可以被低级 行为使用： 3 、生态学中的一些研究也表明，动物的行为选择控制大致是分级的，采用 分级的方法与生态学的观点大致一致。 人工鱼的行动选择由行为系统控制。行为系统包括人工鱼的习性、精神状态、 意图发生器和一系列行为程序。行为系统在人工鱼的仿真回路中连续地运行，在 每一时间步，根据鱼的习性、精神状态和传入的感知信息，意图发生器发布一个 意图，然后选取并执行一个行为程序，该程序依次选取和运行适当的运动控制器。 在给定的任一时刻，在人工鱼的行为系统中，仅有一个意图或一个主动行为。人 工鱼系统中，行动选择过程在两个等级上发生：意图级和行动级。意图级由意图 控制器产生，而行动由聚焦器和行为控制程序控制。从本文的主要研究重心出发， 我们的注意力主要集中在其意图发生器上。在意图级，给定动物的外部和内部条 件，不同的意愿展开竞争，从而产生一个意图。 1 、人工鱼的情感模型【l j f l 3 j 【1 5 】1 6 1 人工鱼系统中建立了一些先天的习性，它们用一组二进制数表示。如1 或o ， 可以用来表示喜欢或不喜欢。不同于其静态习性，鱼的精神状态模型随时间变化。 一个动物的精神状态可以看作是由各种愿望组成的。人工鱼模型中建立了三个精 神状态：饥饿感h ，性欲l ，恐惧感f ，其值在闭区间 o ，1 中变化，当取值较高 时，依次地表明有较强的愿望进食、求偶、躲避捕食者。h 和l 由内部冲动和外部 刺激决定，而f 则由外部刺激，亦即对捕食者的感觉单独引起。这些变量可用下 式( 上面画线部分模拟相应的内部冲动) 表示： h ( t ) = m i n 1 - 1 1 。( t ) r ( a t 日) n 口+ 口 s h ( t ) ，l 】 ( 1 1 ) l ( t ) = m i n i ( 1 - h ( t ) ) c a t ) + 嘶s i ( t ) ，1 】 ( 卜2 ) f ( t ) = m i i l f ，l 】其中，f = m i n d o d ) ，l 】 ( 1 3 ) i 其中，t 表示时间，n 。( t ) 是所消耗的食物量，按食物颗粒数或被捕食鱼的数 目来衡量；r ( x ) = 卜p 。( x ) 是消化率，其中p o 为常数；a t h 是自从上次进食以来的 9 巾南大学硕士学位论文第一章概论 时间；是一个常数，它表甓鱼的胃口大小( 大鱼具有较大的n 口值) ；a t s h ( t ) 体 现外部刺激的影响，如对邻近食物感知；包含常数p 。的l ( x ) - p ；x 是性欲函数，& 是鲁从上次交配以来的时翔；a , s ( t ) 计算对潜在交配的感知豹影响；d o 吃0 0 是一 常数；f 和d 1 分别表示对发现的捕食者i 的恐惧感和距离；m = 0 0 0 0 6 7 ，p 。如0 0 2 5 是标称值。某些值会造成一条贪婪黔鱼( 例如p 萨0 。0 0 5 ) 或是毪饥渴的鱼( 倒如 p 。= 0 0 1 ) 或是懦弱的鱼( 例如d o = 5 0 0 ) 。 2 、机遇1 1 q 模仿外部刺激对h 和l 的影响，其意义是增加“机遇。机遇是动物行为的重 要因素，在为动画设计行动选择机制时，特别受到人们的关注。建立机遇模型是 为了提高人工鱼的行为逼真度。 饥饿感和性欲主要是由相应的内部冲动所支配，是合理的。而外部刺激只有 在内部冲动足够强时，才会有影响。这表骥s “( t ) 和s ( 专) 应该类似于一个阶跃菡 数。其详细计算如下所述。 假定只有最近的食物和配偶对刺激蠡数s “( t ) 和s 1 ( t ) 有影响。蔼且刺激强度 仅依赖于刺激物和鱼之间的随时间变化的距离d ( t ) ，d ( t ) 越小，则刺激越强。令 s ( t ) = l d ( t ) 表示刺激强度，则s “( t ) 和s 1 ( t ) 由下式定： 厂0 蜘 再s ( t ) 而- q , 当s ( t ) q l 时 当q l s 国q ：时 ( 卜4 ) 当蛸p 锻时 这里x 表示h 和l ，而q ，和q ：是阈值。当x = h 时，取q l _ o 0 5 和q 2 _ o 2 ：当x - - l 时，取q 。茹o 0 2 5 和q 2 = o 王。这样得到人工行为系统中的s “( 毫) 和s ( t ) 蓝线如图1 - 2 所示。 3 、意图发生嚣1 1 l 图1 - 3 表示人工鱼的简化的意图发生器，它是一个分级的控制结构。它产生 人工鱼在动态世界中有目的行为的意图，即力人工鱼选择一个要执行的行为。 意图发生器中的行为具有优先级。如碰撞，可能会威胁生存，所以躲避碰撞 具有最高的优先级。意图发生器首先检查感觉信息流，以确定是否有即将发生的 危险碰撞。如果有，英| j 产生意匿i 去躲避碰撞；如果没有，则意图发生器在附近 搜寻捕食者，并计算恐惧感f 值和最危险的捕食者m ，若总的恐惧感f f o ( 这里 0 。圭f o 0 。s 是阕值) ，剡产生逃跑意图。若最危险的捕食者也不是有太大的威 胁，即恐惧感低于阈值，且行为记忆为空，则考虑饥饿感h 和性欲l ，若二者之一 超过阈值o r 矾 ( 2 1 ) 鬲d _ o d ( ，) s i m p l eg e n e t i ca l g o r i t h m s ) 。基本遗传算法只使用选择 算子、交叉算子和变算子这三种基本遗传算子来模拟现实世界中的“优胜劣汰 ， 交配繁殖以及基因变异现象，是其他一些遗传算法的雏形和基础。 3 3 。 基本遗传算法的构成要素 基本遗传算法主要有以下几个部分组成： l 、染色体编码方法。基本遗传算法使用固定长度的二迸制符号串来表示群 体中的个体，其等位基因是由二值符号集 0 ，l 码所组成的。初始群体中各个个 体的基因值可焉均匀分布的随机数来生成。 2 、个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当 前饕体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里 耍求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先 确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标 函数值为负数时的处理方法。 3 、遗传算子。基本遗传算子使用下述三种遗传算子： ( 王) 选择运算使用比铡选择算予 ( 2 ) 交叉运算使用单点交叉算子 ( 3 ) 变异运算使用基本位变异算孑或均匀变异算子 中南大学硕士学位论文 第三章生态系统中人工生命体行为进化模型 4 、基本遗传算法的运行参数，基本遗传算法有下述4 个运行参数需要提前设 定。主要的参数有： 王) 群体大小，帮群体孛所含个体的数量。 ( 2 ) 遗传运算的终止进化代数。 ( 3 ) 交叉概率，一般取为0 。4 一o 。9 9 。 ( 4 ) 变异概率，一般取为0 0 0 0 1 - 0 1 。 需要说明的是，这4 个运行参数对遗转算法的求解结果和求解效率都有一定 的影响，但目前尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往 需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围1 3 7 1 1 3 , 1 1 3 9 1 。 3 3 2 基本遗传算法的原理 基本遗传算法的原理可以用图3 - 1 表示。首先，根据闯题的初始解集把问题 编码为染色体。遗传算法的工作对象是字符串，因此编码是_ 项基本的工作，从 生物学的霜度看，编码相当于选择遗黄物质，每个字符串对应一个染色体。遗传 算法大多采用二进翻 0 1 字符编码。其次，随机地建立由字符串组成初始的群体 作为遗传算法进化的种群。初始群体是遗传算法搜索寻优的出发点，群体规模越 大，搜索的范围越广，但是每代的遗传操作时间越长。反之，群体规模越小，每 代的运算时间越短，然而搜索空间也越小。然后，计算各个个体的适应度。 适应度是衡量个体优劣的标志，它是执行算法搿优胜劣汰黟的依据。因此， 适应度也是驱使遗传算法向前发展的动力。根据遗传操作，利用下列操作产生新 个体：复制，交叉，交舅。 下面根据遗传算法的原理图，简要介绍每一步骤i 柏】： 王、编码。在遗传算法中如何描述闯题的可行解，鄄把一个问题的可行解从 其解空间转换到遗传算法所能处理的搜索空间转换方法就称为编码。基本遗传算 法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是幽二值符号 0 ，l 所组成的。初始群体中的各个个体的基因值可以用均匀分布的随机数来生 成。 2 、初始亿。群体初始纯是指产生第一代一定数量的个体。一般可以先将优 化问题的解初始化转化为个体，第一代群体中的其余个体随机产生。在应用遗传 算法进行优化设计以裁，要对一定的群体规模个体进行初始化，这些经过初始化 后的个体将作为遗传算法的祖先( 下一代的父代) 。作为祖先的初始群体，这些 给定数量的个体是通过随机方法生成的，以保证搜索空间中的每个可能解在初始 群体中有相同的国现机会。 中南大学硕士学位论文 第三章生态系统中人工生命体行为进化模銎 图3 - i 基本遗传算法原理图 3 、个体评价。遗传算法中，适应度是描述个体性能指标的主要指标。根据 适应度的大小，对个体进行优胜劣汰。适应度是驱动遗传算法的原动力，适应度 在遗传过程中具有重要的意义。遗传算法的一个特点就是它仅使用所求问题的目 标函数值就可以得到下一步的有关搜索信息。而对目标函数的使用是通过评价个 体的适应度来体现的。将目标函数转换成适应度函数一般应该遵循两个原则： 适应度必定非负；优化过程中的目标函数的变化方向应与群体进化过程中适应 度函数变化方向一致。 4 、选择运算。模拟自然界“优胜劣汰 的过程，淘汰群体中的适应度低的 个体。 5 、交叉运算。将群体个体之间相互交换编码串，以生成新的个体。 6 、变异运算。群体个体经过变异算子的作用生成新个体。群体p ( t ) 经过选 中南大学硕士学位论文第三章生态系统中人工生命体行为进化模型 择、交叉、变异运算之后得到下一代群体p ( t + 1 ) 。 7 、终止条件判断。若t t j , 于或等于t ，则：t = t + l ，转到2 ：若t 大于t ，则以 进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。 在遗传算法的初期，最优个体的适应度以及群体的平均适应度都较小，以后 随着复制、交换、突变等操作，适应度值增加。到了遗传算法的后期，这种增加 已趋缓和或停止，一旦这种增加停止，即终止遗传算法。但本文的遗传算法没有 一个确定的适应度函数来判断个体是否是最优的。他借助的是不同的判断方式， 在下面章节再研究。 3 4 模式定理与算法性能指标 3 4 1 模式定理 模式定理是由h o l l a n d 教授在上世纪7 0 年代提出，是遗传算法理论基础。模 式定理揭示出了群体中的优良个体的样本数将以指数级规律增长，因而从理论上 保证了遗传算法是一个可以用来寻求最优可行解的优化过程。 为了解释模式定理 3 4 j ，首先介绍几个定义： 定义3 1 ：模式表示一些相似的模块，描述了在某些位置上具有相似结构特 征的个体编码串的一个子集。 以二进制编码方式为例，个体是由二值字符集v = o ，l 中的元素所组成的一 个编码串，而模式却是由三值字符集u = 宰，0 ，l 中的元素所组成的一个编码串， 其中“宰一表示通配符，它既可被当作“1 。，也可被当作。0 那么模式h = il 木：i c l 描述了长度为5 ，且在位置1 ，2 ，5 取值为“l 一的所有字符串的集合 1 1 0 0 1 ，i i 0 1 1 ， 1 1 1 0 1 ，i i i i i ) 。 定义3 2 ：在模式h 中具有确定基因值的位置数目称为该模式的模式阶，记为 o ( h ) 。 以二进制编码为例，模式阶就是模式中所含有的l 和0 的数目。例如： 0 ( i i * * i ) = 3 。 定义3 3 ：模式h 中第一个确定基因值的位置和最后一个确定基因值的位置 之间的距离称为该模式的模式定义长度，记为6 ( h ) 。 以二进制编码为例，6 ( 1 1 木0 料) = 3 ，而6 ( 料木1 料) 只有一个确定的基因值， 这个位置既是第一个确定基