（计算机应用技术专业论文）基于可拓变换的进化算法优化研究.pdf

摘要 智能化是计算机发展的必然趋势，无论是计算机控制，还是商用民 用软件，都要求含有越来越高的智能因素，因此人工智能的研究越来越 受到重视。2 0 世纪8 0 年代，基于结构演化的人工智能理论一一计算智 能理论迅速成为人工智能研究新的主流。计算智能包含广泛的研究领域， 各领域之间存在着深刻的联系，且相互促进，进化计算就是其中一个重 要领域。 进化机器人的思想主要来源于进化计算。在进化机器人中，设计者 的工作主要是决定进化框架和评估策略，评估中所采用的适应度函数在 很大程度上决定了系统的行为。常用的适应度函数的设计方法有线性变 换法、幂函数变换法、指数变换法和方差调整法等。同时，进化框架中 的进化参数，如选择概率、交叉概率和变异概率等对进化过程和结果非 常关键。通过研究机器人进化计算中适应度函数及进化参数的设计，达 到群体多样性与收敛性、进化性能与进化速度的统一，从而优化进化机 器人中进化框架和评估策略的设计。这对于进化计算和进化机器人学的 发展都具有重要的意义。 可拓学是一门新学科，由于它专门处理矛盾问题的思维模型，因此 必将渗入到人工智能及其相关学科中，并产生了一种新型的智能机器人 一可拓机器人。 本文在介绍现有的遗传算法与可拓遗传算法的基础上，利用基于可 拓变换的可拓遗传算法，对机器人避障问题的性能优化进行了研究。通 过对避障机器人的可拓分析，提出了一种避障机器人物元模型，并设计 了相应的可拓适应度函数。通过e v o r o b o t 平台实验与仿真，结果表明， 本文设计的可拓适应度函数性能要优于原适应度函数，同时在特定的环 境下，其性能提升比较明显。通过引入了可拓变换的原理，考虑了在特 定情况下障碍物的可拓转换，提出对智能机器人传感信息进行表达的新 方法和对周围环境进行建模的新方法，提高了避障机器人对于环境的认 广东t 业大学1 = 学硕十学位论文 知，进而增加了避障机器人的适应能力。 本文创新之处：在基于可拓遗传算法的基础上，提出了一种避障机 器人物元模型，分析了其物元的可拓性。对避障机器人的周围环境信息 进行了物元变换方式的扩展，并以此设计了避障机器人的可拓适应度函 数，达到了对机器人进化算法优化的目的。根据新的模型与算法，在 e v o r o b o t 系统中仿真实现，并对仿真结果进行分析与评价，得出相应结 论。 关键词：进化机器人，进化计算，可拓变换，可拓遗传算法 a b s t r a c t t h ec o m p u t e ri st e n d i n gt om o r ea n dm o r ei n t e l l i g e n c e ，a n dn o m a t t e rw h a tk i n do fa p p l i c a t i o n s ，i n 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 o l 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 i s t so faw i d er a n g eo fr e s e a r c ha r e a s ，w h i c hh a v ep r o f o u n d 1 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 n a r yc o m p u t a t i o ni sj 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 e t h i n k i n go fe v o l u t i o n a r y r o b o t i c sm a i n l yc o m e sf r o m e v o l u t i o n a r yc o m p u t a t i o n i ne v o l 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 k o fd e s i g n e r si s t 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 ts 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 r i 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 r t 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 m e n t ， e t c m e a n w h il e ，t h e p a r a m e t e r s i ne v o l 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 ri st 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 dc o n v e r g e n c e ，e v o l 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 m 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 ht h ed e s i g no ff i t n e s sf u n c t i o na n de v o l u t i o n a r y p a r a m e t e r s t h i si so 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 e x t e n s i o ns t u d yi san e ws u b j e c t ，w h i c hd e a l ss p e c i f i c a l l y w i t ht h ei s s u eo fc o n f l i c t so ft h i n k i n gm o d e l 。i ti sb o u n dt o i n f i l t r a t ei n t oa r t i f i c i a li n t e l l i g e n c ea n dr e l a t e dd i s c i p l i n e s ， a n dp r o d u c ean e wt y p eo fi n t e l l i g e n tr o b o t se x t e n i c s b a s e dr o b o t t h i s p a p e r i n t r o d u c e st h e e x is t i n gg e n e t i ca l g o r i t h ma n d e x t e n s i o ng a o nt h eb a s i so ft h ee x t e n s i o nt r a n s f o r m a t i o n o f e x t e n s i o ng a t h i sp a p e rs t u d i e st h ep e r f o r m a n c eo p t i m i z a t i o no f r o b o to b s t a c l ea v o i d i n g t h r o u g ht h ee x t e n s i o na n a l y s i so ft h e o b s t a c l e a v o i d i n gr o b o t ，ih a v eb r o u g h tf o r w a r da m a t t e re l e m e n t m o d e lo ft h eo b s t a c l e a v o i d i n gr o b o ta n dd e s i g nt h ec o r r e s p o n d i n g e x t e n s i o nf i t n e s sf u n c t i o n t h r o u g he x p e r i m e n t sa n ds i m u l a t i o ni n t h ee v o r o b o tp l a t f o r m ，r e s u l t ss h o w e dt h a t ，t h ep e r f o r m a n c eo ft h e e x t e n s i o nf i t n e s sf u n c t i o ni sb e t t e rt h a n t h eo r i g i n a l f i t n e s s a n di nc e r t a i nc i r c u m s t a n c e s ，i t sp e r f o r m a n c ei m p r o v e s m o r e o b v i o u s l y b yi n t r o d u c i n gt h ee x t e n s i o nt r a n s f o r m a t i o nt h e o r y ， c o n s i d e r i n gt h ee x t e n s i o nc o n v e r s i o n o ft h eb a r r i e r si nt h e s d e c i f i cc i r c u m s t a n c e s ，t h i sp a p e ri n t r o d u c et h en e wm e t h o d so f e x p r e s s i o nf o rt h ei n t e l l i g e n tr o b o ts e n s o ri n f o r m a t i o na n dt h e n e wm e t h o d sf o rm o d e li n go ft h es u r r o u n d i n ge n v i r o n m e n t i th a s r a i s e dt h ea w a r e n e s so f t h eo b s t a c l e a v o i d i n gr o b o tt ot h e e n v i r o n m e n t a n dt h e r e b yi th a si n c r e a s e dt h ea d a p t a b i l i t yo ft h e o b s t a c l e - a v o i d i n gr o b o t t h ei n n o v a t i o no ft h i sp a p e r ：b a s e do f ft h ee x t e n s i o ng e n e t i c a l g o r i t h m ，i th a sc o n s t r u c t e di t so w no b s t a c l ea v o i d a n c er o b o t e l e m e n tm o d e l 。a n da n a l y z e dt h ee x t e n s i b i l i t y i th a se x p a n d e dt h e m a t t e r e l e m e n t a lt r a n s f o r m a t i o n m o d eo ft h es u r r o u n d i n g i n f o r m a t i o nt ot h eo b s t a c l e - a v o i d i n gr o b o t a n di t h a sd e s i g n e d t h ec o r r e s p o n d i n ge x t e n s i o nf i t n e s sf u n c t i o n i th a sr e a c h e dt h e p u r p o s eo fe v o l u t i o n a r ya l g o r i t h mo p t i m i z a t i o n a c c o r d i n gt ot h e n e wm o d e la n da l g o r i t h m ，ih a v es i m u l a t e di ti nt h ee v o r o b o ts y s t e m s i m u l a t i o n t h r o u g ha n a l y s i sa n d e v a l u a t i o no f t h e s i m u l a t i o n r e s u l t s ih a v ed r a w nt h ec o r r e s p o n d i n gc o n c l u s i o n s k e y w o r 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 ，t h e e x t e n s i o l lc o i l v e r s i o i l ，t h ee x t e n s i o ng e n e t i ca l g o r i t h m sb a s e do n t h em a t t e re l e m e n t v 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是 我个人在导师的指导下进行的研究工作及取得的研究成果。尽我所知， 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，不包含本人或其他用途使用过的成果。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明，并 表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取 得的，论文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此 声明。 指导教师签 论文作者签 2 0 0 7 年5 月话日 第一章绪论 第一章绪论 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 o l u t i o n a r yr o b o t ，e r ) 的思想主要来源于进化计 算，它是嵌入了进化机制的具有较强环境适应能力的机器人，属于智能 机器人研究中比较新的技术领域【l 】。它受达尔文自然进化和优胜劣汰的 广东下业大学丁学硕十学位论文 思想启发，把机器人作为一个自主个体，在与外界环境的交互中生长、 发展、进化。这个进化过程是一个类似于自然生命系统的自组织过程， 不受人为因素的干预。进化机器人的这种设计思想在理论上是非常简单 的：对于一个机器人群，给定其性能评价函数( 适应度函数) ，计算各 个机器人对环境的适应度，选择适应度最好的进行杂交、遗传、变异， 产生下一代种群，对下代进行类似的操作，直至产生满足要求的机器人 的性能2 1 。 进化机器入学( e v o l u t i o n a r yr o b o t i c s ) 是研究进化机器人的学科。 在进化机器人学中，设计者的工作主要是决定进化框架( 编码模式、进 化算子、算法参数) 和评估策略( 适应度函数) ，机器人控制系统的实际设 计过程则是自动进行的，设计工作量显著减少3 1 。编码摸式中融入了设 计者的先验知识和设计倾向，评估中所采用的适应度函数在很大程度上 决定了系统的行为。这样，系统全局任务和所需的反射式行为，就自然 地融合到传感一马达映射中了。由此可见尽管设计过程不需人工干预，设 计者仍然可以对进化过程和结果进行控制。 对不同性质的矛盾，可拓学中有着不同的解决方法。可拓学理论和 应用成果与计算机相结合，在人工智能领域得到广泛应用 1 , 4 1 。将可拓学 理论与成果应用于智能机器人领域从而提出了可拓机器人【5 1 的概念。 本文的工作基于这样一个背景展开的，因此本文将可拓学引入到遗 传算法中，根据已知系统模型构造了进化机器人的物元模型，并通过可 拓评价方法建立遗传算法的适应值函数，以e v o r o b o t 系统为仿真平台， 进一步优化进化机器人的性能。 1 2 国内外相关领域的研究现状 1 2 1 人工智能研究进展 智能是个体有目的行为、合理的思维以及有效地适应环境的综合能 力【6j 。智能如果用作名词，是指人类所能进行的脑力劳动，包括感觉、 认知、记忆、学习、联想，计算、推理、判断、决策、抽象、概括等； 如果用作形容词，则指柔性的、自学习的、自组织的、自适应的、自治 的等。 2 第一苹绪论 智能理论的研究也分为两个方面：一方面是对智能的产生、形成和 工作机制的直接研究，称为自然智能理论；另一方面是研究如何用人工 的方法模拟、延伸和扩展智能，称为人工智能理论。 人工智能理论以自然智能理论为基础，一旦搞清了各种自然智能的 工作机制及其各个功能部件的结构关系，就可以通过已经高度发达的电 子的、光学的和生物的器件构筑类似的结构对其进行模拟、延伸和扩展， 从而实现人工智能。但由于人脑结构高度复杂，目前自然智能理论还没 有搞清一些基本智能活动的机制和结构，总体进展十分有限。人工智能 理论的主流也从结构模拟的道路走向了功能实现的道路。功能实现的道 路使人工智能理论摆脱了自然智能理论进展缓慢的束缚，通过几十年的 发展已经形成较为系统的理论体系，包含极为丰富的内容，并在实际中 得到了广泛的应用，发挥了显著的作用。 传统人工智能的研究开始于1 9 5 6 年，致力于以语言或符号规则的形 式来表达和模拟人类的智能形为，主要目标是应用符号逻辑的方法模拟 人的问题求解、推理和学习等方面的能力。 传统人工智能以n e w e l l 和s i m o n 提出的物理符号系统假设为基础。 物理符号系统假设认为物理符号是智能行为充分和必要条件。该系统由 一组符号实体组成，可在符号结构的实体中作为组分出现，可以进行建 立、修改、复制、删除等操作，以生成其他符号结构。 问题求解是传统人工智能的核心问题，当机器有了对某些问题的求 解能力以后，在应用场合遇到这类问题时便会自动找出正确的解决策略 1 6 。推理是人的思维的一个重要方面，主要有归纳推理、演绎推理和模 糊推理三种形式。传统人工智能中推理的研究就是要模拟这三种推理形 式，以解决一些实际问题。 由于知识获取和表示是复杂而艰巨的任务，符号运算限制了传统人 工理论的应用领域，更多的研究开始向模仿产生自然智能的生物机制， 从而也弥补了符号机制的缺点。 2 0 世纪8 0 年代在传统人工智能理论发展出现停顿而人工神经网络 理论出现新的突破时，基于结构演化的人工智能理论一一计算智能理论 迅速成为人工智能研究新的主流。1 9 9 4 年，i e e e 在美国佛罗里达州举 3 广东t 业大学t 学硕七学位论文 行了关于模糊系统、神经网络和进化计算的首届计算智能世界大会，进 行了“计算智能：模仿生命_ 的主题讨论会，与会人士取得了关于计算 智能的共识。由于计算智能与生命科学、系统科学密切联系的突出特点， 使其继人工智能之后，不仅吸引计算机科学家，而且众多其他学科的学 者也投身于这一领域，极大地促进了它的发展。 计算智能以生物进化的观点认识和模拟智能，以数据为基础，通过 训练建立联系而进行问题求解【6 1 。按照这一观点，智能是在生物的遗传、 变异、生长以及外部环境的自然选择中产生的。在生存竞争、优胜劣汰 的过程中，适应度高的结构被保存下来，智能水平也随之提高。 计算智能以连接主义的思想为主，并与模糊数学和迭代函数系统等 数学方法相交叉，形成了众多的发展方向【6 l 。它的主要方法有模糊逻辑、 神经网络、遗传算法、遗传程序、演化程序、人工免疫系统、人工生命、 生态计算、d n a 计算、局部搜索，模拟退火、多a g e n t 系统等。这些方 法具有一些共同的要素，即自适应的结构、随机产生的或指定的初始状 态、适应度的评测函数、修改结构的操作、系统状态存储器、终止计算 的条件、指示结果的方法、控制过程的参数等。计算智能的这些方法具 有自学习、自组织、自适应的特征，以及简单、通用、鲁棒性强、适于 并行处理的优点，在并行搜索、联想记忆、模式识别、知识自动获取等 方面得到了广泛的应用。 计算智能包含广泛的研究领域，各领域之间有着深刻的内在联系。 与传统的符号主义不同，计算智能的各领域用不同方式实现了连接主义 的计算，即研究简单个体如何在简单交互规则指导下构成具有复杂智能 行为的高层系统。由此带来各种算法的统一特点，如社会性、并行性、 单元的智能性和开放性等。 计算智能作为一个整体，具有明确的研究思路、理论背景、数学手 段和应用前景，其各个领域和计算智能的一般理论均有极大的理论意义 和应用能力。 进化计算是计算智能中一个重要领域，也是一种新兴的搜索寻优技 术。进化计算对待求解问题本身一无所知，但只要给出了表示方案、适 应度函数、遗传算子、控制参数、终止准则等内容，算法就可以按不依 4 第一章绪论 赖于问题本身的方式对未知空间进行有效的搜索，最后找出问题的解1 7 j 。 进化计算还具有简单、通用、稳健性强、适合于并行处理等特点，及自 组织、自适应、自学习等智能特性，已被成功地应用到那些难以用传统 的方法进行求解的复杂问题之中。特别是在系统识别、故障诊断、机器 学习及神经网络设计等领域，进化计算已经显示出它的魅力。然而，作 为一个新的、跨学科的研究课题，进化计算的理论研究还有待进一步完 善，其中包括基础理论、编码机制、控制参数的选择策略、收敛性分析 等等。在发达国家，它已被成功地用于机械、化工、建筑、计算机等领 域，着重用于解决结构性优化、非线性优化、并行计算等复杂问题；在 我国，也已成功用于许多领域中。 1 2 2 进化机器人概述 虽然进化机器人是近年来才出现的新术语，但是把机器人控制系统 表示成服从遗传规律和自然选择的人工染色体的思想却可以追溯至r 2 0 世 纪8 0 年代8 1 。当时，第一个带有传感电动系统的人工仿真器官在计算机 虚拟世界里得到了进化。但真正的机器人仍然需要精确编程，小心操纵。 到了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 机器人实现了一个进化系统【9 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 tl e a r n i n g ) 实现六足g e n p h i s 机器人的步态协调b o l 。 t a k a s h ig o m i 用进化的方法在八足o c t l b 机器人上实现步态协调【l “。 1 9 9 2 年至1 9 9 3 年，s w i s sf e d e r a li n s t i t u t eo ft e c h n o l o g 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 等大学相继报告了自主机器人人工进化的尝试。这 些研究的成功尝试带动了欧洲、日本及美国的一大批研究者进行进化机 器人的研究。近几年，来自不同领域( 包括人工智能、机器人、生物工 广东t 业大学1 = 学硕十学位论文 程、认知科学以及社会行为学) 的科研工作者也越来越多地投入到进化 机器人的研究热潮中。 国内的进化机器人研究还处于起步阶段，代表性成果不多，但在其 相关领域已有研究基础【3 l 。文献 3 ，1 2 ，1 3 对进化机器人的理论基础及发 展状况作了集中概述。 目前，进化机器人学应用研究还只限于小规模的较为简单的问题， 所采用的机器人也大多是小型的3 1 。进化机器人研究主要有两个方面如】： 第一，开发人工系统的控制方法；第二，通过对人工系统的研究，更好 地理解自然生物系统。研究的内容包括机器人控制器结构设计、编码策 略、适应度函数( 评价函数) 的选择、多机器人的共同进化以及硬件系 统的进化等等。进化机器人学是设计机器人的一种新方法，缺乏严格的 定义和公式化描述，目前在进化自主机器人的控制系统时，常用的研究 方法有两种。一种是直接进化真实的实体机器人；另一种是借助于仿真 系统，在仿真环境里进化机器人控制系统，进而把仿真的进化结果转变 成真实的机器人两种策略各有利弊。第一种方法无疑是耗时的：而第 二种策略虽然可以加快进化的步伐，但是仿真环境毕竟只是实际环境的 简化，现实环境中的很多动力学因素很难在仿真环境里再现。因此，有 时在仿真环境里工作良好的控制器在真实环境中却是失败的。不过，这 种由于模型不匹配造成的性能下降可以在后续的进化中加以改进。有些 研究人员已经成功地证实了第二种方法的有效性。这样，大大减少了对 真实机器人的进化代数，既减少了时间，又能保证最终结果满足要求【h 】。 在进化机器人实验中，大多数的研究者都没有考虑机器人形体的进 化( 假定机器人在进化过程中形体不变) ，而只是进化了机器人控制系 统。但也有一小部分的研究人员同时进化了机器人的形体和控制系统。 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 m s 在虚拟的世界中( 遵循牛顿物理定律) 进化了一个会游泳和爬行的生物， 其适应度函数是当生物水平移动时就给与相应的奖励，这样奖励的结果 就使生物被赋予了运动能力 1 5 1 。j o r d a np o l l a c k 和p a o l of u n e s 进化的 不是生物，而是机构，其适应度函数是机构的强度，机构的强度大，其 结构遗传到下一代的可能性就大。他们把最后的仿真结果用l e g o 积木块 6 第一章绪论 搭建起来，证明进化的机构比人工设计的机构强度要大得多1 6 】。 1 2 3 可拓学领域 在可拓学的应用领域，文献 1 7 中，有学者用物元的表示方法与遗 传算法中的编码相结合对企业的客户进行描述，然后应用可拓理论中的 关联函数对客户进行细分，进而在遗传算法中的遗传和变异方法和可拓 变换的思想结合的基础上，提出了新的可拓遗传方法，并进一步对客户 数据进行挖掘与转化，继而通过实例说明了可拓遗传算法的有效性和优 越性。 文献 1 8 有学者提出了：在分析现有概念设计求解策略的基础上， 提出了基于可拓学理论与遗传算法相结合的概念设计求解模型。利用遗 传算法模拟物元变换过程，建立了产品方案物元描述的内部模型和外部 模型，探讨了内、外模型的转换关系并通过关联函数将内、外部模型联 系起来。根据内部模型给出了遗传算法的编码形式以及与之相适应的交 叉、变异策略，并通过可拓评价方法建立了遗传算法的适应值函数，基 本解决了产品概念设计中的知识组合爆炸和矛盾冲突问题。 可拓学与进化算法的结合也产生了新的成果，有学者提出了可拓机 器人【5 1 的概念。可拓机器人用基元理论表达环境模型与先验知识，采用 基元的可拓方法解决认知环境过程中出现的矛盾问题，用菱形思维方法 模仿人类的思维方式认知环境。该概念的提出，是对智能机器人环境认 知技术的一个突破和改进。在可拓学基元理论的基础上，提出对传感信 息进行表达的新方法，可成为一种新兴的环境建模方法。将可拓学成果 应用于智能机器人系统中，丰富和发展了可拓学的成果，扩大了可拓学 的应用领域。在文献 1 9 基于可拓遗传算法的机器人路径规划一文中提 出，在遗传算法基础上，用扩展物元来表示机器人的位置信息，使计算 机能够较容易读懂这种语言，加快了计算速度；用关联函数作为遗传算 法的适应度函数，使算法更容易找到最优化路径：采用可拓工程方法中 的三种可拓变换形式，丰富了遗传算法的变异方式。经证明，可拓遗传 算法的机器人路径规划能有效提高的机器人避障问题的速度和准确性。 7 广东t 业大学t 学硕十学位论文 1 3 本文研究的主要内容与创新 本文研究基于可拓变换的进化机器人性能优化。通过结合可拓学的 可拓遗传算法，提出了特定环境下机器人避障问题的物元模型，设计院 了相应的遗传算法，达到研究进化机器人系统优化的目的。 本文主要研究内容： 1 在介绍现有的遗传算法与可拓遗传算法的基础上，利用基于可拓 变换的可拓遗传算法，对机器人避障问题的性能优化进行了研究。通过 对避障机器人的可拓分析，提出了一种避障机器人物元模型，并设计了 相应的可拓适应度函数。结合e v o r o b o t 平台实验。所设计的可拓适应度 函数性能要优于原适应度函数，在特定的环境下，其系统性能提升比较明 显。 2 通过引入可拓变换的原理，考虑在特定情况下，对于障碍物的可 拓转换，提出对智能机器人传感信息进行表达的新方法和对周围环境进 行建模的新方法，提高了避障机器人对于环境的认知，进而增加了避障 机器人的适应能力。 本文创新之处：在基于可拓遗传算法的基础上，提出了一种避障机 器人的物元模型，分析了其物元的可拓性。在基于可拓变换的基础上， 对避障机器人的周围环境信息进行了物元变换方式的扩展，并以此设计 了避障机器人的可拓适应度函数，达到了对机器人进化算法优化的目的。 根据新的模型与算法，在e v o r o b o t 系统中仿真实现，并对仿真结果进行 分析与评价，得出相应结论。 1 4 本文组织 本文的内容安排如下：第二章介绍了可拓理论和遗传算法的基本理 论，包括可拓理论，遗传算法的基本原理以及本文的仿真平台一一 e v o r o b o t 系统；第三章介绍了基于物元的可拓遗传算法，包括可拓遗传 算法基本概念和基本理论；第四章是可拓遗传算法的具体应用：基于可 拓遗传算法的机器人避障问题研究，包括：基于物元的可拓遗传算法， 机器人避障问题的可拓遗传算法，进行了实例分析，并通过仿真平台进 行了性能分析与评价。 3 第二章可拓理论和遗传算法的摹本理论 第二章可拓理论和遗传算法的基本理论 2 1 可拓理论 2 1 1 基本概念和理论 ( 1 ) 物元理论 在客观世界中，事物是质和量的统一体，事物的量变与质变是紧密 联系互相制约的。经典数学从客体中抽象出它的量与形，研究数量关系 与空间形式。由于它撇开了事物质的方面，因此，对于涉及质的变换的 矛盾问题，就暴露出其局限性。为此，可拓论引进了物元的概念，以描 述既考虑量变又考虑质变的思维过程。它把客观世界看成一个物元世界， 把处理客观世界中的矛盾问题变成处理物元之间的矛盾问题。 ( 2 ) 物元的概念 以有序的三元组r = ( n ，c ，v ) 作为描述事物的基本元，简称为物元j 其中，表示事物，c 表示特征的名称，v 表示关于c 所取的量值。这 三者称为物元的三要素。 物元概念中，v = c ( ) 反映了事物的质和量的关系，特征元m ( c , v ) 由 特征的名称c 和相应的量值v 组成，描述了人们常说的特征。一个事物具 有众多的特征元，用n 维物元描述。而动态物元 r ( f ) = ( ( f ) ，c ，v ( f ) ) = ( ( f ) ，c ，c ( ( f ) ) ) 则描述了事物随时间的变化。 以有序的三元组，= ( d ，h ，“) 作为描述事情的基本元，称为一维事元。 其中d 为动词，h 为特征，包括支配对象、施动对象、时间、地点、程度、 方式和工具等基本特征。如果动词d 以疗个特征啊，吃，吃和相应的量值 岣，“：，描述，则以n 维事元表示。 2 1 2 物元的可拓性 解决矛盾问题的关键是对物元基本特性的研究由此形成了物元理 论。在解决矛盾问题的过程中，人们必须跳出原有的习惯领域，拓展问 9 广东t 业大学t 学硕卜学位论文 题中所涉及的事物，提出创造性的方法。物元的可拓性包括发散性、共 扼性、相关性、蕴含性和可扩性。从事物向外、向内、平行、变通和组 合分解的角度提供事物拓展的多种可能性，成为进行创造性思维和提出 解决矛盾问题的方案的依据。 ( 1 ) 物元的发散性一事物具有多种特征，一特征、一特征元又为多 个事物所具，这类性质称为物元的发散性。从一物元出发，根据不同的 规则，可以发散出相应的物元集。 性质1 一个事物具有很多特征，简称一物多征。记为 0 一i ( 0 ，c o ，v 0 ) 一i r i r = ( n o ，c o ，c ( 0 ) ) ，c e ( c ) 它表示事物具有一个特征c ，也可具有多个特征c l ，c 2 ，q 。符号“一” 表示可拓。e ( c 1 表示特征的全体。 性质2 具有同一特征的事物有无数个，简称一征多物。记为 ( o ，c 0 ，v o ) - i r i r = c n o ，c o ，c ( 0 ) ) ，e ( ) 】 其中，e ( n ) 表示事物的全体。 性质3 具有同一特征元的事物有很多个，简称一特征元多物。记为 ( o ，v o ) - i r i r = ( n o ，c o ，v o ) ，n ee ( ) ) ( 2 ) 物元的共扼性对事物内部结构的研究，有助于利用事物的各个 部分及其关系和相互转化去解决矛盾问题。系统论从系统的组成部分和 内外关系去研究事物，这是对事物结构的一种描述，通过对大量现实事 物的分析，除了系统性以外，事物的结构还可以从物质性、动态性和对 立性等角度去研究。 从事物的物质性考虑，任何事物都由虚实两部分组成。可以说：“实 以为基，虚以为用”，虚实结合，方成一物。房子的墙壁、天花板和地板 是实部，但我们是生活在它们围成的空间( 虚部) 里；产品的实体是实部， 而它的“牌子”是虚部。虚部分为主观虚部和客观虚部，如茶杯的空间、 房子的空间、大门的门洞等，都是客观虚部；而人的意识感觉到的东西 如牌子、名声、形象等是主观虚部。对事物，用咖表示事物的 虚部，用r e n 表示事物的实部，记 l o 第二章可拓理论和遗传算法的基本理论 n = i m n r e n 把砌和r en 作为事物，可以用虚部物元与实部物元来描述虚部和实 部，如： i m ，c l ，v l c 2 ，v 2 巳，咋 为事物的虚部物元。在一定条件下，某些虚部分物元与实部分物 元可以相互转化，这一性质称为事物的虚实共轭性。与事物的物质性相 仿，从系统性、动态性和对立性考虑，相应地可以把事物的结构分别分 为软部和硬部、潜部和显部、关于某特征的负部和正部，并用物元表示 相应的共轭部，对应的可转换性分别称为软硬共轭性、潜显共轭性和负 正共轭性。 ( 3 ) 物元的相关性一个事物与其它事物关于某特征的量值之间，同 一事物或同族事物关于某些特征的量值之间，如果存在一定的依赖关系， 称之为相关。由于相关性的存在，一个事物的量值的变化会导致与之相 关的事物的变化，一个事物或一族事物关于某一特征的量值的变化会导 致关于别的特征的量值的变化，这种变化互相传导于一个物元相关网中。 因此，可以利用相关关系去处理求知问题和求行问题。另一方面，由于 物元相关网的存在，进行物元变换时必须考虑其相关物元的变化，因此， 相关性是研究变换的连锁作用的依据。应用相关性与物元变换解决求知 与求行问题的方法称为相关网方法。物元的相关性是事物因果关系的形 式表示，相关 物元构成的物元相关网和物元传导变换描述了事物变化所产生的传导作 用。 ( 4 ) 物元的蕴含性对蕴含的概念作如下的定义： 若a ，必有b ，则称a 蕴含口，记作a b ，符号 表示存在。 a 与8 之间的关系称为蕴含关系。蕴含关系可以产生于事物、特征、量 值、特征元和物元间。若干元素垦，岛，e 以及它们之间的蕴含关系构 成一个蕴含系统口。 广东1 = 业大学t 学硕十学位论文 ( 5 ) 物元的可扩性物元的可扩性描述物元与其它物元结合和分解 的可能性。 2 1 3 物元变换 可拓论引进物元以后，就能够把对事物的变换，对特征的变换和对 量值的变换作为特定的运算引入其中，因而能描述包含量的变换，又包 含质的变换的过程。在解决问题时，物元的可拓性指出了可能解决问题 的途径，而人们提出的各种点子、窍门和策略则可以用物元变换或其组 合来描述。 ( 1 ) 物元变换物元r o - - ( n o ，c o ，v o ) 改变为物元r = ( j v ，c ，v ) 或若干物元 r i = ( l ，c t ，u ) ，恐= ( 2 ，岛，也) ，民= ( 帆，厶，h ) ，称为物元民的变换。 由物元的概念可见，物元的三个要素之间有着非常密切的关系，其 中某一要素的变换可能会引起别的要素的变换，这种变换称为同物传导 变换；对一个事物l 关于某一特征c 的量值c ( 1 ) 的改变，会引起另一事 物2 关于c 的量值f ( 2 ) 的改变，叫做异物传导变换。 ( 2 ) 物元的基本变换在物元变换中，有四种最基本的变换方式，其 他的物元变换都是由他们的运算得到的，因此我们首先讨论物元的四种 基本变换。 置换变换，用某事物代替另一事物、用某特征代替另一特征、用某 量值代替另一量值的变换称为物元的置换变换。如给定物元 民= ( 0 ，c o ，) ，若c 0 变换为c ，n o 与不变。则称此变换为对物元r 中 特征的置换变换，记作 瓦c 0 2 c 毛r = 毛( n ，c o ，v o ) = ( n o ，c o