（计算机应用技术专业论文）基于线性变换的适应度函数及机器人进化计算研究.pdf

摘要 摘要 智能化是计算机机发展的必然趋势，无论是计算机控制，还是商用 民用软件，都要求含有越来越高的智能因素，因此人工智能的研究越来 越受到重视。2 0 世纪8 0 年代，基于结构演化的人工智能理论一一计算 智能理论迅速成为人工智能研究新的主流。计算智能包含广泛的研究领 域，各领域之间存在着深刻的联系，且相互促进，进化计算就是其中一 个重要领域。 进化机器人的思想主要来源于进化计算。在进化机器人中，设计者 的工作主要是决定进化框架和评估策略，评估中所采用的适应度函数在 很大程度上决定了系统的行为。常用的适应度函数的设计方法有线性变 换法、幂函数变换法、指数变换法和方差调整法等。同时，进化框架中 的进化参数，如选择概率、交叉概率和变异概率等对进化过程和结果非 常关键。通过研究机器人进化计算中适应度函数及进化参数的设计，达 到群体多样性与收敛性、进化性能与进化速度的统一，从而优化进化机 器人中进化框架和评估策略的设计。这对于进化计算和进化机器人学的 发展都具有重要的意义。 本论文研究内容：运用线性变换法研究机器人进化计算中的适应度 函数的选择及进化参数的改进，着重研究适应度函数的选择。在线性变 换法中，比率系数和幅度系数最终决定线性变换的结果，而幅度系数由 比率系数和适应度平均值系数决定。根据不同的进化阶段，建立比率系 数和适应度平均值系数自适应变换的表达式，得到按比率、幅度及比率 和幅度三种基于线性变换的适应度函数的进化计算。而进化参数表达式 的建立，则需要根据进化阶段的不同和个体适应度的大小而定。 本文创新之处：通过建立根据进化前期或后期自适应变换的比率系 数、适应度平均值系数及选择概率、交叉概率和变异概率等进化参数表 达式，构造了三种基于线性变换的适应度函数及进化参数的数学模型， 设计相应算法，然后在e v o r o b o t 系统中进行了相关的仿真实验，并对仿 广东工业大学工学硕= | = 学位论文 真结果进行了分析，最后得出相应结论。 关键词：进化机器人，进化计算，线性变换，适应度函数 i i a b s t r a c t n o wt h ec o m p u t e rist e n d i n gt om o r ea n di i l o r ei n t e l l i g e n t ， a n d n om a t t e rw h a tk i n do fa p p l ic a t i o n s ，jn t e l l i g e n c eh a sb e e nt h em o s t i m p o r t a n tf a c t o r i nt h e1 9 8 0 s ，t h ea r t i f i c i a li n t e l l i g e n c et h e o r y b a s e do nt h ee v 0 1 u t i o no fs t r u c t u r e 一一c o m p u t a t i o n a li n t e l l i g e n c e w a sf a s tb e c o m i n gt h en e wm a i n s t r e a m c o m p u t a t i o n a li n t e l l i g e n c e c o n s is t so faw i d er a n g eo fr e s e a r c ha r e a sw h i c hh a v ep r o f o u n d l i n k sa n dp r o m o t ee a c ho t h e r ，a n de v o l u t i o 兀a r yc o m p u t a t i o nisj u s t a ni m p o r t a n tf i e l do ft h e s ea r e a s t h et h i n k i n go f e v o l u t i o n a r yr o b o t ic sm a i n l y c o m e sf r o m e v 0 1 u t i o n a r yc o m p u t a t i o n i ne v 0 1 u t i o n a r yr o b o t i c s ，t h ep r i m a r y w o r ko fd e s i g n e r sist od e c i d ee v o l u t i o n a r yf r a m e w o r ka n d a s s e s s m e n t s t r a t e g i e s t h es y s t e mb e h a v i o r sd e p e n dt oah i g h d e g r e eo nt h ef i t n e s sf u n c t i o nu s e di na s s e s s i n g i nd e s i g n i n g m e t h o d so ff i t n e s sf u n c t i o nt h e r ea r em a n yw a y s ，f o re x a m p l e s ： 1 i n e a r t r a n s f o r m a t i o n ，p o w e rt r a n s f o r m a t i o n ， i n d e x t r a n s f o r m a t i o n ， v a r i a n c e a d j u s t e n t ， e t c m e a n w h i l e ， t h e p a r a m e t e r si ne v 0 1 u t i o n a r yf r a m e w o r k ， s u c ha st h es e l e c t i o n p r o b a b i l i t y ， c r o s s o v e rp r o b a b i l i t ya n dm u t a t i o np r o b a b i l i t ya r e c r u c i a lt ot h ee v o l u t i o n a r yp r o c e s sa n dr e s u l t s t h et a r g e to ft h i s p a p e rist oa c h i e v et h ei n t e g r a t i o no ft h ep o p u l a t i o n s d i v e r s i t y a n d c o n v e r g e n c e ， e v 0 1 u t i o ns p e e da n dp e r f o r m a n c e ， t h e r e b y o p t i m i z et h ed e s i g no fe v o l u t i o n a r yf r a l i l e w o r ka n da s s e s s m e n t s t r a t e g i e s ， w i t h t h ed e s i g no ff i t n e s sf u n c t i o na n de v 0 1 u t i o n a r y p a r a 【i l e t e r s t h i siso fg r e a ts i g n i f i c a n c et ot h ed e v e l o p m e n to f e v o l u t i o n a r yr o b o t i c sa n de v o l u t i o n a r yc o m p u t a t i o n t h i sp a p e ri n c l u d e st h ef o l l o w i n gs t u d i e s ：r e s e a r c ho ft h e i i i 厂东一l 一业大学工学硕士学位论文 c h o i c e so ff i t n e s sf u n c t i o na n dt h ei m p r o v e m e n to fe v 0 1 u t i o n a r y p a r a m e t e r sw i t hl i n e a rt r a n s f o r m a t i o n ，f o c u s in go nt h ec h o ic e so f f i t n e s sf u n c t i o n i nl i n e a rt r a n s f o r m a t i o n ， t h er a t i oc o e f f ic i e n t a n dt h es c o p ec o e f f i c i e n tu l t m a t e yd e t e r m i n et h eo u t c o m e s ， a n d t h es c o p ec o e f f i c i e n ti sd e t e r m i n e db yt h er a t i oc o e f f ic i e n ta n d t h ef i t n e s s a v e r a g e c o e f f ic i e n t d e p e n d i n g o nd i f f e r e n t e v o l u t i o n a r ys t a g e s ， w ew i l le s t a b 】is ht h e s e l f a d a p t i n g e x p r e s s i o n so f t h er a t i oc o e f f i c ie n ta n dt h ef i t n e s sa v e r a g e c o e f f i c i e n t ， a n dt h e no b t a i nt h r e e k i n d so fe v o lu t i o n a r y c o m p u t a t i o nb a s e do nl i n e a rt r a n s f o r m a t i o nw h i c hh a v ed i f f e r e n t f i t n e s sf u n c t i o n sa c c o r d i n gt or a t i o ， s c o p e ， r a t i oa n ds c o p e a n d t h ec o n s t r u c t i o no fe v o l u t i o n a r yp a r a m e t e r sd e p e 兀d so nd i f f e r e n t s t a g e so fe v 0 1 u t i o na n dt h es i z e o ff i t n e s s t h ei n n o v a t io n sa r ei n c l u d e di nt h iss t u d y t h es e l f a d a p t i n g e x p r e s s jo n so fr a t i oc o e f f i c i e n t ，f i t n e s sa v e r a g ec o e f f c ie n ta n d e v o l u t i o n a r yp a r a m e t e r sw h i c ha l t e r n a t eb yt h ee a r l yo r1a t es t a g e o fe v 0 1 u t o na r ee s t a b l is h e d a n dt h e nt h ei i l a t h e a t ic a lm o d e l sf o r t h r e ef i t n e s sf u n c t i o n sa n d e v o l u t i o n a r yp a r a m e t e r sb a s e do n l i n e a rt r a n s f o r m a t i o na r e p r o p o s e d a n dt h e c o r r e s p o n d i n g a l g o r i t h m sa r ed e s i g n e d a f t e rt h a t ，t h er e l a t e ds i m u l a t i o n e x p e r i m e n t sa r ei m p l e m e n t e do np l a t f o r me v o r o b o t ， t h e n t h e s i m u l a t i o nr e s u l t sa r ea n a l y z e da n dt h ec o r r e s p o n d i n gc o n c l u s i o n s a r eg o t k e y w or d s ：e v o l u t i o n a r yr o b o t ，e v o l u t i o n a r yc o m p u t a t i o n ，l i n e a r t r a n s f o r m a ti o n f it n e s sf u n c ti o n 第一章绪论 第一章绪论 1 1 研究背景及选题意义 根据达尔文的自然选择学说，生物在繁殖过程中，大多数生物通过 遗传，使物种保持相似的后代；部分生物由于变异，后代具有明显差别， 甚至形成新物种。而自然界中生物赖以生存的资源是有限的。因此，生 物需要通过竞争来生存。生物在生存竞争中，根据对环境的适应能力， 适者生存，不适者消亡。自然界中的生物，就是根据这种优胜劣汰的原 则，不断地进行进化。进化计算( e v o l u t i o n a r yc o m p u t a t i o n ，e c ) 就是 借用生物的进化规律，通过繁殖一竞争一再繁殖一再竞争，实现优胜劣汰， 一步一步地逼近问题的最优解。 进化计算遵从“生存竞争，优胜劣汰”的原则，从一组随机生成的 初始个体出发，经过复制( 选择) 、交叉( 交叉或重组) 、突变( 变异) 等操作，并根据适应度大小进行个体的优胜劣汰，提高新一代群体的质 量，再经过多次反复迭代，逐步逼近最优解。因此，进化计算实质上是 一种搜索寻优的方法。但进化计算和传统的搜索方法有很大的不同，它 是有指导的搜索。指导进化计算执行搜索的依据是适应度。在适应度的 驱动下，使进化计算逐步逼近目标值。 适应度是衡量个体优劣的标志，它是执行进化计算“优胜劣汰”的 依据，也是进化计算向前发展的动力。此外，适应度函数对群体的平均 适应度和最优个体的适应度均有重要影响。因此，设计能够反映不同进 化阶段的群体状态并选择尽可能多的好的基因进入下一代的自适应性适 应度函数将尤为重要。同时，所设计的适应度函数既能保持群体多样性， 又能保证群体收敛性和进化速度。 进化参数是影响进化效率和性能的重要因素。进化参数的设计也需 要考虑群体的状态及各个体的适应度高低等因素，并能够自适应地调整。 进化机器人( e v 0 1 u t i o n a r yr o b o t ，e r ) 的思想主要来源于进化计 算，它是嵌入了进化机制的具有较强环境适应能力的机器人，属于智能 机器人研究中比较新的技术领域【l ”。它受达尔文自然进化和优胜劣汰的 广东工业大学工学硕士学位论文 思想启发，把机器人作为一个自主个体，在与外界环境的交互中生长、 发展、进化。这个进化过程是一个类似于自然生命系统的自组织过程， 不受人为因素的干预。进化机器人的这种设计思想在理论上是非常简单 的：对于一个机器人群，给定其性能评价函数( 适应度函数) ，计算各 个机器人对环境的适应度，选择适应度最好的进行杂交、遗传、变异， 产生下一代种群，对下代进行类似的操作，直至产生满足要求的机器人 的性能j 。 进化机器人学( e v o l u t i o n a r yr o b o t i c s ) 是研究进化机器人的学科。 在进化机器人学中，设计者的工作主要是决定进化框架( 编码模式、进 化算子、算法参数) 和评估策略( 适应度函数) ，机器人控制系统的实际设 计过程则是自动进行的，设计工作量显著减少1 4 。编码摸式中融入了设 计者的先验知识和设计倾向，评估中所采用的适应度函数在很大程度上 决定了系统的行为。这样，系统全局任务和所需的反射式行为，就自然 地融合到传感一马达映射中了。由此可见尽管设计过程不需人工干预，设 计者仍然可以对进化过程和结果进行控制。 本文的工作基于这样一个背景展开的，以e v o r o b o t 系统为仿真平台， 通过分析机器人进化计算中不同阶段的特征，建立根据不同进化阶段自 适应调整的适应度函数及进化参数( 选择概率、交叉概率、变异概率) 的数学模型，并通过仿真加以实现。经过改进的适应度函数及进化参数 能够提高最大个体适应度和群体适应度平均值，具有更强的鲁棒性和收 敛速度等。这对于控制和优化进化过程与结果及提高机器人的进化水平 具有重要意义。 1 2 国内外相关领域的研究现状 1 2 1 人工智能研究进展 智能是个体有目的行为、合理的思维以及有效地适应环境的综合能 力5 1 。智能如果用作名词，是指人类所能进行的脑力劳动，包括感觉、 认知、记忆、学习、联想、计算、推理、判断、决策、抽象、概括等； 如果用作形容词，则指柔性的、自学习的、白组织的、自适应的、自治 的等。 第一章绪论 智能理论的研究也分为两个方面：一方面是对智能的产生、形成和 工作机制的直接研究，称为自然智能理论；另一方面是研究如何用人工 的方法模拟、延伸和扩展智能，称为人工智能理论。 人工智能理论以自然智能理论为基础，一旦搞清了各种自然智能的 工作机制及其各个功能部件的结构关系，就可以通过已经高度发达的电 子的、光学的和生物的器件构筑类似的结构对其进行模拟、延伸和扩展， 从而实现人工智能。但由于人脑结构高度复杂，目前自然智能理论还没 有搞清一些基本智能活动的机制和结构，总体进展十分有限。人工智能 理论的主流也从结构模拟的道路走向了功能实现的道路。功能实现的道 路使人工智能理论摆脱了自然智能理论进展缓慢的束缚，通过几十年的 发展已经形成较为系统的理论体系，包含极为丰富的内容，并在实际中 得到了广泛的应用，发挥了显著的作用。 传统人工智能的研究开始于1 9 5 6 年，致力于以语言或符号规则的形 式来表达和模拟人类的智能形为，主要目标是应用符号逻辑的方法模拟 人的问题求解、推理和学习等方面的能力。 传统人工智能以n e w e l l 和s i m o n 提出的物理符号系统假设为基础。 物理符号系统假设认为物理符号是智能行为充分和必要条件。该系统由 一组符号实体组成，可在符号结构的实体中作为组分出现，可以进行建 立、修改、复制、删除等操作，以生成其他符号结构。 问题求解是传统人工智能的核心问题，当机器有了对某些问题的求 解能力以后，在应用场合遇到这类问题时便会自动找出正确的解决策略 【5 】。推理是人的思维的一个重要方面，主要有归纳推理、演绎推理和模 糊推理三种形式。传统人工智能中推理的研究就是要模拟这三种推理形 式，以解决一些实际问题。 由于知识获取和表示是复杂而艰巨的任务，符号运算限制了传统人 工理论的应用领域，更多的研究开始向模仿产生自然智能的生物机制， 从而也弥补了符号机制的缺点。 2 0 世纪8 0 年代在传统人工智能理论发展出现停顿而人工神经网络 理论出现新的突破时，基于结构演化的人工智能理论一一计算智能理论 迅速成为人工智能研究新的主流。1 9 9 4 年，i e e e 在美国佛罗里达州举 广东工业大学工学硕士学位论文 行了关于模糊系统、神经网络和进化计算的首届计算智能世界大会，进 行了“计算智能：模仿生命”的主题讨论会，与会人士取得了关于计算 智能的共识。由于计算智能与生命科学、系统科学密切联系的突出特点， 使其继人工智能之后，不仅吸引计算机科学家，而且众多其他学科的学 者也投身于这一领域，极大地促进了它的发展。 计算智能以生物进化的观点认识和模拟智能，以数据为基础，通过 训练建立联系而进行问题求解 5 】。按照这一观点，智能是在生物的遗传、 变异、生长以及外部环境的自然选择中产生的。在生存竞争、优胜劣汰 的过程中，适应度高的结构被保存下来，智能水平也随之提高。 计算智能以连接主义的思想为主，并与模糊数学和迭代函数系统等 数学方法相交叉，形成了众多的发展方向【5 1 。它的主要方法有模糊逻辑、 神经网络、遗传算法、遗传程序、演化程序、人工免疫系统、人工生命、 生态计算、d n a 计算、局部搜索、模拟退火、多a g e n t 系统等。这些方 法具有一些共同的要素，即自适应的结构、随机产生的或指定的初始状 态、适应度的评测函数、修改结构的操作、系统状态存储器、终止计算 的条件、指示结果的方法、控制过程的参数等。计算智能的这些方法具 有自学习、自组织、自适应的特征，以及简单、通用、鲁棒性强、适于 并行处理的优点，在并行搜索、联想记忆、模式识别、知识自动获取等 方面得到了广泛的应用。 计算智能包含广泛的研究领域，各领域之间不是相互独立的，而是 有着深刻的内在联系。与传统的符号主义不同，计算智能的各领域用不 同方式实现了连接主义的计算，即研究简单个体如何在简单交互规则指 导下构成具有复杂智能行为的高层系统。由此带来各种算法的统一特点， 如社会性、并行性、单元的智能性和开放性等。 计算智能作为一个整体，具有明确的研究思路、理论背景、数学手 段和应用前景，其各个领域和计算智能的一般理论均有极大的理论意义 和应用能力。 进化计算是计算智能中一个重要领域，也是一种新兴的搜索寻优技 术。进化计算对待求解问题本身一无所知，但只要给出了表示方案、适 应度函数、遗传算予、控制参数、终止准则等内容，算法就可以按不依 d 第一章绪论 赖于问题本身的方式对未知空间进行有效的搜索，最后找出问题的解 【” 。进化计算还具有简单、通用、稳健性强、适合于并行处理等特点， 及自组织、自适应、自学习等智能特性，已被成功地应用到那些难以用 传统的方法进行求解的复杂问题之中。特别是在系统识别、故障诊断、 机器学习及神经网络设计等领域，进化计算已经显示出它的魅力。然而， 作为一个新的、跨学科的研究课题，进化计算的理论研究还有待进一步 完善，其中包括基础理论、编码机制、控制参数的选择策略、收敛性分 析等等。在发达国家，它己被成功地用于机械、化工、建筑、计算机等 领域，着重用于解决结构性优化、非线性优化、并行计算等复杂问题： 在我国，也已成功用于许多领域中。 1 2 2 进化机器人概述 虽然进化机器人是近年来才出现的新术语【36 1 ，但是把机器人控制系 统表示成服从遗传规律和自然选择的人工染色体的思想却可以追溯到2 0 世纪8 0 年代。当时，第一个带有传感电动系统的人工仿真器官在计算机 虚拟世界里得到了进化。但真正的机器人仍然需要精确编程，小心操纵。 到了8 0 年代末期，一些工程师对机器人设计的基本原理提出质疑，并提 出了新一代机器人的设计思想一一机器人具有类似生物系统的简单特 性，比如：鲁棒性、简易性、灵活性、模块性。这期间最具代表性的人 物是r o d n e ya b r o o k s 。他提出了基于行为的设计方法，设计出了比传统 设计方法行动更快和更灵活的机器人，对于同一任务，其编码的长可以 是传统设计方法的千分之一。d f l o r e a n o 和f m o n d a d a 成功地用k h e p e r a 机器人实现了一个进化系统37 1 。1 9 9 0 年，p a t t i em a e s 用增强学习策略 ( r e i n f o r c e m e n t1 e a r n i n g ) 实现六足g e n p h i s 机器人的步态协调【3 8 】。 t a k a s h ig o m i 用进化的方法在八足0 c t 一1 b 机器人上实现步态协调 39 1 。 1 9 9 2 年至1 9 9 3 年，s w is sf e d e r a li n s t i t u t eo ft e c h n 0 1 0 9 yi n l a u s a n n e、 u n i v e r s i t yo fs u s s e xa tb r i g h t o n 、u n i v e r s i t yo f s o u t h e r nc a l i f o r n i a 等大学相继报告了自主机器人人工进化的尝试。这 些研究的成功尝试带动了欧洲、日本及美国的一大批研究者进行进化机 器人的研究。近几年，来自不同领域( 包括人工智能、机器人、生物工 广东工业大学工学硕士学位沦文 程、认知科学以及社会行为学) 的科研工作者也越来越多地投入到进化 机器人的研究热潮中【】。 国内的进化机器人研究还处于起步阶段，代表性成果不多，但在其 相关领域已有研究基础【h 。文献 1 1 ，1 2 ，1 4 对进化机器人的理沦基础及 发展状况作了集中概述。 目前，进化机器人学应用研究还只限于小规模的较为简单的问题， 所采用的机器人也大多是小型的【14 1 。进化机器人研究主要有两个方面 【1 0 】：第一，开发人工系统的控制方法；第二，通过对人工系统的研究， 更好地理解自然生物系统。研究的内容包括机器人控制器结构设计、编 码策略、适应度函数( 评价函数) 的选择、多机器人的共同进化以及硬 件系统的进化等等。进化机器人学是设计机器人的一种新方法，缺乏严 格的定义和公式化描述，目前在进化自主机器人的控制系统时，常用的 研究方法有两种。一种是直接进化真实的实体机器人；另一种是借助于 仿真系统，在仿真环境里进化机器人控制系统，进而把仿真的进化结果 转变成真实的机器人。两种策略各有利弊。第一种方法无疑是耗时的； 而第二种策略虽然可以加快进化的步伐，但是仿真环境毕竟只是实际环 境的简化，现实环境中的很多动力学因素很难在仿真环境里再现。因此， 有时在仿真环境里工作良好的控制器在真实环境中却是失败的。不过， 这种由于模型不匹配造成的性能下降可以在后续的进化中加以改进。近 几年，有些研究人员已经成功地证实了第二种方法的有效性。这样，大 大减少了对真实机器人的进化代数，既减少了时间，又能保证最终结果 满足要求【4 们。 在进化机器人实验中，大多数的研究者都没有考虑机器人形体的进 化( 假定机器人在进化过程中形体不变) ，而只是进化了机器人控制系 统。但也有一小部分的研究人员同时进化了机器人的形体和控制系统。 k a r ls i m s 、j o r d a np o l l a c k 、p a o l of u n e s 就是其中的小部分人。k a r ls i s 在虚拟的世界中( 遵循牛顿物理定律) 进化了一个会游泳和爬行的生物， 其适应度函数是当生物水平移动时就给与相应的奖励，这样奖励的结果 就使生物被赋予了运动能力4 。j o r d a np o l l a c k 和p a 0 1 0f u n e s 进化的 不是生物，而是机构，其适应度函数是机构的强度，机构的强度大，其 6 第一章绪论 结构遗传到下一代的可能性就大。他们把最后的仿真结果用l e g o 积木块 搭建起来，证明进化的机构比人工设计的机构强度要大得多【42 1 。 1 3 本文研究的主要内容与创新 在机器人进化计算中，不同的进化阶段，机器人群体的状态各有不 同。在进化初始阶段，机器人个体的适应度分布较广，多数好的基因存 于适应度高的个体中，但某些适应度低的个体也具有一些好的基因；而 在进化后期，适应度的分布逐渐缩小，好的基因基本存于适应度高的个 体中。因此，设计能够反映不同进化阶段的群体状态并选择尽可能多的 好的基因进入下一代的自适应性适应度函数是本文所要解决的问题。同 时，所设计的适应度函数既能保持群体多样性与收敛性，又能保证进化 性能与进化速度。 进化参数是影响进化效率和性能的重要因素。进化参数的设计也需 要考虑群体的状态及各个体的适应度高低等因素，并能够自适应地调整。 本课题研究的主要内容： ( 1 ) 运用线性变换法建立适应度函数的数学模型。讨论了适应度的 缩放原理及常用适应度函数的改进方法，并在此基础上分析了几种基于 线性变换适应度函数的进化计算。 ( 2 ) 运用线性变换法建立选择概率、交叉概率、变异概率等主要进 化参数的数学模型。讨论了主要进化参数的改进方法，并在此基础上分 析了基于线性变换的进化参数模型。 ( 3 ) 根据新的模型与算法，在e v o r o b o t 系统中仿真实现，并对仿真 结果进行分析与评价，得出相应结论。 运用线性变换法设计机器人进化计算中的适应度函数和进化参数， 是从数学优化的角度出发，以智能化的方式解决机器人进化问题，这对 于进化计算及进化机器人学的发展都具有重要的意义。 本文创新之处：通过建立根据进化前期或后期自适应变换的比率系 数、适应度平均值系数及选择概率、交叉概率和变异概率等进化参数表 达式，构造了三种基于线性变换的适应度函数及进化参数的数学模型， 设计相应算法，然后在e v o r o b o t 系统中进行了相关的仿真实验，并对仿 广东：f 业大学工学硕士学位论文 真结果进行了分析，最后得出相应结论。 1 4 本文组织 本文的内容安排如下：第二章介绍了进化计算的理论基础，包括进 化计算基本理论、进化计算中适应度函数的发计，以及本文的仿真平台 一一e v o r o b o t 系统；第三章运用了线性变换法对适应度函数进行设计， 给出了相应的数学模型、算法流程及仿真结果，并对仿真结果进行了分 析与评价；第四章也是运用了线性变换法对选择概率、交叉概率和变异 概率等进化参数进行设计，给出了相关的数学模型及部分仿真结果，并 对仿真结果进行了分析与评价。 第二章进化计算理论基础 第二章进化计算理论基础 在介绍了人工智能和进化机器人的研究现状与发展趋势的基础上， 将对本文所需的相关理论与技术，包括进化计算基本理论、进化计算中 适应度函数的设计进行分析与讨论，然后介绍本文的仿真平台一一 e v o r o b o t 系统。 2 1 进化计算概述 l8 5 9 年达尔文创立的进化论，曾经作为生物界和人类文明史上的一 个里程碑，促进了科学技术的发展。2 0 世纪6 0 年代以来，生物学的进 化论又被推广应用于工程技术，形成一种新型的计算方法一一进化计算， 又称进化算法( e v o l u t i o n a r ya 1 9 0 r i t h m s ，e a ) 。 进化计算通常包括遗传算法( g e n e t i ca l g or i t h m s ，g a ) 、遗传程序设 计( g e n e t i cp r o g r a m m i n g ，g p ) 、进化策略( e v o l u t i o ns t r a t e g i e s ，e s ) 和 进化规划( e v 0 1 u t i o n a r yp r o g r a m m i n g ，e p ) ，其中遗传算法是进化计算的 应用基础。它们都是借鉴生物学中进化与遗传的机理，用于解决复杂的 工程技术问题。 2 1 1 生物的进化与遗传 ( 1 ) 生物的进化 地球上的生物，都是经过长期进化而形成的。根据达尔文的自然选 择学说，地球上的生物具有很强的繁殖能力。在繁殖过程中，大多数生 物通过遗传，使物种保持相似的后代；部分生物由于变异，后代具有明 显差别，甚至形成新物种。正是由于生物不断繁殖后代，生物数目大量 增加，而自然界中生物赖以生存的资源却是有限的。因此，为了生存， 生物就需要竞争。生物在生存竞争中，根据对环境的适应能力，适者生 存，不适者消亡。自然界中的生物，就根据这种优胜劣汰的原则，不断 地进行进化。 进化计算就是借助生物进化的规律，通过繁殖一竞争再繁殖一再竞争， 实现优胜劣汰，一步一步地逼近问题的最优解。 9 广东 ：业大学工学硕士学位论文 ( 2 ) 遗传物质 众所周知，细胞是生物结构和功能的基本单位，细胞通常由细胞膜、 细胞质与细胞核三部分组成。细胞核位于细胞的最内层，由核膜、染色 质、核液三者组成，是遗传物质贮存和复制的场所。 细胞核中的染色质，在细胞分裂时形成光学显微镜下可以看见的染 色体。染色体主要由蛋白质和d n a 组成，d n a 又称脱氧核糖核酸，是 一种高分子化合物，组成它的基本单位是脱氧核甘酸。d n a 可以传递遗 传信息。生物上下代之间传递遗传信息的物质称作遗传物质。绝大多数 生物的遗传物质是d n a 。由于细胞中的d n a 大部分在染色体上，遗传 物质的主要载体是染色体。 控制生物遗传的物质单元称作基因，它是有遗传效应的d n a 片段。 每个基因含有成百上千个脱氧核甘酸。它们在染色体上呈线性排列，这 种排列顺序就代表遗传信息。 在进化计算中，为了形成具有遗传物质的染色体，就用不同字符组 成的字符串表达所研究的问题。这种字符串相当于染色体，其上的字符 就相当于基因。 ( 3 ) 遗传方式 生物的主要遗传方式是复制。遗传过程中，父代的遗传物质d n a 分子被复制到子代，以此传递遗传信息。 生物在遗传过程还会发生变异。变异方式有三种：基因重组、基因 突变、染色体变异。基因重组是控制物种性状的基因发生重新组合。基 因突变指基因分子结构的改变。染色体变异指染色体在结构或数目上的 变化。 进化计算中，仿效生物的遗传方式，主要采用复制、交叉、突变这 三种遗传操作，衍生下一代个体。 2 1 2 进化计算发展分支 ( 1 ) 遗传算法分支 把计算机科学与进化论结合起来的尝试开始于2 0 世纪5 0 年代者 但当时缺乏一种通用的编码方案，使得人们只能依赖变异而不是7 1 0 第二章进化计算理论基础 产生新的基因结构，故而收效甚微。到了6 0 年代中期，美国m i c h i g a n 大学的j o h nh o l l a n d 在f r a s e r 和b r e m e r m a n n 等人的工作基础上提出了 位串编码技术。这种编码既适合于变异又适合于交配( 即杂交、交叉等 操作) ，并且强调将交配作为主要的遗传操作。随后，h 0 1 l a n d 将该算法 用于自然和人工系统的自适应行为的研究之中，并于1 9 7 5 年出版其开创 性的著作a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s 【43 1 。后来，h o l l a n d 与他的学生们将该算法加以推广并应用到优化及机器学习等问题之中， 并正式定名为遗传算法。g a 的通用编码技术及其简单有效的遗传操作 为其广泛的应用和成功奠定了基础【4 4 1 。 h o l l a n d 的g a 常被称为简单遗传算法( s g a ) ，操作对象是一群二 进制串( 称为染色体、个体) 即种群( p o p u l a t i o n ) 。这里每个染色体都 对应于问题的一个解。从初始种群出发，采用基于适应度比例的选择策 略在当前种群中选择个体，使用交叉和变异操作来产生下一代种群。如 此一代一代进化下去，直到满足期望的终止条件。 ( 2 ) 进化策略分支 在2 0 世纪6 0 年代初，当时在柏林工业大学的r e c h e n b e r g 和s c h w e f e l 等在进行风洞实验时，由于在设计中难以用传统的方法对描述物体形状 的参数进行优化，他们利用生物变异的思想来随机地改变参数值并获得 了较好的结果。随后，他们便对这种方法进行了深入的研究和发展，形 成了进化计算的另一个分支一一进化策略【4 5 ，4 6 1 。 早期e s 的种群中只包含一个个体，而且只使用变异操作。在每一 进化代，变异后的个体与其父体进行比较后再选择两者之优。它使用的 变异算子是基于正态分布的变异操作。这种e s 称为( 1 + 1 ) e s 或二元 ( t w o m e m b e r e d ) e s 【5 1 。 ( 1 + 1 ) e s 存在很多弊端，如有时收敛不到全局最优解、效率较低 等。它的改进即是增加种群内个体的数量，从而进化为( “+ 1 ) e s 。此 时种群内含有u 个个体，随机地选取一个个体进行变异，然后取代群体 中最差的个体。( u + 1 ) e s 与( 1 + 1 ) e s 的相似之处是每次只产生一个后 代。为了进一步提高效率，后来又发展为( 肛+ ) e s 和( 肛，五) e s ， 并且引进重组( r e c o m b i n a t i o n ) 操作，即由两个个体按类似于杂交的方 广东工业大学工学硕士学位论文 式生成一个个体。( + 五) e s 根据种群内的“个个体产生五个个体( 用 变异和重组) ，然后将这+ 兄个个体进行比较再在其中选取肛个最优者。 ( ，兄) e s 则是在新产生的五( u ) 个个体中选择个最优者。 e s 与g a 的另一不同之处在于：g a 要将原问题的解空间映射到位 串空间之中，然后再施行遗传操作，强调个体基因结构的变化对其适应 度的影响；而e s 则是直接在解空间上进行操作，强调进化过程中从父 体到后代行为的自适应性和多样性。从搜索空间的角度来说，e s 强调的 策略是直接在解空间上进行操作，强调进化过程中搜索方向和步长的自 适应调节。 ( 3 1 进化规划分支 进化规划的方法最初是由f o g e l 等在2 0 世纪6 0 年代提出的，他们 在人工智能的研究中发现，智能行为即是要具有能预测其所处环境的状 态，并按照给定的目标做出适当的响应能力。在研究中，他们将模拟环 境描述成由有限字符集中的符号组成的序列，于是问题便转化为怎样根 据当前观察到的符号序列做出响应以获得最大的收益。这里，收益的计 算是按照环境中将要出现的下一个符号及预先定义好的效益目标来确定 的。e p 中常用有限态自动机( f s m ) 来表示这样的策略。这样，问题便 成为如何设计出一个有效的f s m ? f o g e l 等借用进化的思想对一群f s m 进行进化以获得较好的f s m 。他们将此方法应用到数据诊断、模式识别 和分类以及控制系统的设计等问题之中，并取得了较好的结果。后来， f o g e l 借助于e s 方法对e p 进行了发展，并应用到数值优化及神经网络 的训练等问题之中。 e p 的基本思想也源于对自然界中生物进化过程的模仿【4 7 。49 1 。在e p 中，搜索空间是一个n 维空间，搜索点就是一个n 维向量x e r “。算法中 组成进化群体的每一个个体x 就直接用这个n 维向量表示，即： = 石月“。 个体的适应度f ( x ) 是由它所对应的目标函数f ( x ) 通过某种比例变换而得 到的。这种比例变换为了既保证各个个体的适应度总取正值，又维持各 个个体之间的竞争关系，即个体的适应度由下式确定： f ( x ) = 5 f ( x ) 第二章进化计算理论基础 式中，占为比例变换函数。 在进化规划中，不使用个体交叉之类的遗传操作，个体的变异操作 是唯一的一种最优化个体搜索方法。这也是e p 的独特之处。在e p 中， 变异操作使用高斯变异算子，而选择操作是按照一种随机竞争方式进行 的，其基本做法类似于g a 中的排序选择。首先将个父代个体p ( t ) 和 经过一次变异运算后所产生的个子代个体p ( f ) 合并在一起，组成一个 共有2 “个个体的集合 p ( t ) up ( f ) ) 。对于这个集合中的每一个个体 五 j p ( f ) u p ( f ) ，再从这个集合中随机选择q 个个体，比较这q 个个体 与个体五之间的适应度大小，以其中适应度比五的适应度高的个体的数 目作为个体五的得分哌( k = 1 ，2 ，2 “) 。最后对这2 斗个个体按降序排列， 选择前“个个体组成进化过程中的新一代群体p ( t + 1 ) 。由上述选择过程 可以获知，每个群体中最好的个体总被赋予了最高的得分，从而这个最 好的个体能够被保留到下一代群体中。 与g a 和e s 相比，e p 具有下述特点： e p 对生物进化过程的模拟主要着眼于物种的进化过程，算法中不 使用个体交叉算子，而主要依靠变异操作； e p 中的选择运算着重于群体中个体之间的竞争选择，当竞争数目 q 较大时，这种选择也就类似于e s 中的确定选择过程： e p 直接以问题的可行解作为个体的表现形式，无需再对个体进行 编码处理，也无需再考虑随机扰动因素对个体的影响，因而便于应用。 e p 以n 维实数空间上的优化问题为主要处理对象。 ( 4 ) 遗传程序设计分支 遗传程序设计采用g a 的基本思想，但使用一种更为灵活的表示方 式一一分层结构来表示解空间。这些分层结构的叶结点是问题的原始变 量，中间结点则是组合这些原始变量的函数。这样，每一个分层结构对 应问题的一个解，也可以理解为求解该问题的一个计算机程序。g p 即是 使用一些遗传操作动态地改变这些结构以获得解决该问题的可行的计算 机程序。g p 的思想是s t a n f o r d 大学的k o z a 在2 0 世纪9 0 年代初提出的， 并于1 9 9 1 年出版了专著g e n e t i cp r o g r a m m i n g 5 0 】。 广东工业大学工学硕士学位论文 2 1 3 进化计算的特征 ( 1 ) 进化计算的实质 进化计算中，无论是遗传算法、进化策略、进化规划或遗传程序设 计，都是从一组随机生成的初始个体出发，经过复制、交叉、突变等操 作，并根据适应度大小进行个体的优胜劣汰，提高新一代群体的质量， 再经过多次反复迭代，逐步逼近最优解。从数学角度讲，进化计算实质 上是一种搜索寻优的方法4 1 。 假设有数学关系“x ，y ) ，现在要求它的最大值m a x f ( x ，y ) ) 。传统的 寻优方法有三种： 基于导数的方