（计算机应用技术专业论文）高维优化进化算法及其应用研究.pdf

摘要 进化算法( e v o l u t i o n a r ya l g o r i t h m ) 是由生物进化规律而演化出的一种搜索 和优化的计算方法，其主要特点是群体搜索策略和群体中个体之间的信息交 换，搜索不依赖于梯度信息。主要包括：遗传算法、进化策略、进化规划， 也称之为广义遗传算法。它的主要特点是原理简单、参数少、收敛速度较快， 所需领域知识少。该算法的出现引起了学者们极大的关注，己在函数优化、 神经网络训练、组合优化、机器人路径规戈i j 等领域获得了广泛应用，并取得 了较好的效果。尽管进化算法发展数十年，但无论是理论分析还是实践应用 都尚未成熟，仍有大量的问题值得研究。 本论文围绕多移动机器人领域抽象出的若干高维空间优化问题进行了深 入研究。就如何改进传统进化算法性能以及该算法在高维复杂函数优化、约 束优化、进化神经网络、大规模组合优化以及多机器人系统软故障检测等领 域的应用作了详细的论述。本文的主要研究工作和创新点可归纳如下： 1 提出了一种基于佳点集原理的实数域进化算法，该算法对于高维约束 优化问题和高维函数优化问题围绕如何设计有效的约束处理技术和高效的进 化算法两方面展开；吸取正交、差异、粒子群等进化算法的成功经验；在佳 点集理论研究的基础上，构造一种适应度不受维数限制的进化算法。佳点集 的构造与空间维数无关，因此克服了用正交设计法的不足，也为高维近似计 算提供了一个非常好的算法。多组标准测试函数的测试结果对算法进行了有 效地证明。 2 针对进化神经网络中网络结构和权值同时可调整存在的困难，利用 l e u n g 的编码基础，用基于差异技术和佳点集技术相结合的高维优化进化算法 同时调整网络结构和参数。差异进化的全局搜索能力结合佳点集交叉算子的 局部搜索能力，能有效避免目标函数的局部最优，特别是参数的数目非常大 时。网络的权值与结构一同进化，进化结果使具有全连通的三层神经网络变 成一个部分连接的前馈网络。从硬件实现和处理时间的角度出发，此法的优 点在于实现神经网络的耗费明显减少。 3 针对多移动机器人任务分配和路径规划中提出了大规模组合优化问 题，提出了一种新的编码方法，能将离散的组合空间映射到一段连续的区间， 结合成熟进化算法的搜索机制使新算法的性能大大提高。新编码与问题的组 合向量一一对应。所有编码均为可行方案，有效避免了以往算法中的冗余运 算。在新编码的基础上通过理论证明进一步缩小了问题的搜索空间；其次， 进化策略中加入了一个精英队列，并且建立了相应的精英学习策略。在整个 群体进化的同时，精英个体也按照相应的策略不断优化，从而能有效吸收以 往算法在组合优化问题上的成功经验，有利于保留较好的基因段。最后证明 了新算法的收敛性全局最优。仿真实验的结果表明了算法的有效性。 4 针对多机器人系统中的软故障检测，提出了一种基于( + 五) 进化策略的 阴性选择算法；构造匹配信噪比方法综合运用海明规则和r 位连续匹配规则， 使检测器分布更均匀；同传统的阴性选择算法相比，进化机制使得检测器的 搜索不再盲目。对于较大规模的自体集也可以快速准确生成成熟检测器。数 值实验表明新算法产生成熟检测器的迭代次数、黑洞数量均大幅下降，同时 检测率显著提高。在此基础之上，引入正交选择机制更有效降低了算法的运 算复杂度。 关键词佳点集，进化算法，进化神经网络，大规模组合优化，阴性选择，软 故障诊断 i i a bs t r a c t e v o l u t i o n a r ya l g o r i t h m ( e a ) i sa ne v o l u t i o n a r yc o m p u t a t i o nt e c h n i q u ef o r s e a r c h i n g a n d o p t i m i z a t i o ni n s p i r e db yb i o l o g i c a l e v o l u t i o n i t sm a jo r c h a r a c t e r i s t i c sa r ec o l o n ys e a r c h i n gt a c t i c sa n de x c h a n g eo fi n f o r m a t i o n b e t w e e ni n d i v i d u a l si nc o l o n y i t ss e a r c h i n gp r o c e s sd o e sn o tr e l yo nt h e g r a d i e n t i n f o r m a t i o n i tm a i n l y i n c l u d e s g e n e t i ca l g o r i t h m ，e v o l u t i o n a r y s t r a t e g y a n de v o l u t i o n a r yp r o g r a m m i n g ，a l s oc a l l e d a sg e n e r a l i z e dg e n e t i c a l g o r i t h m e ai ss i m p l e i n c o n c e p t ，f e w i n p a r a m e t e r s ，a n de a s y i n i m p l e m e n t a t i o n i tw a sp r o v e dt ob ea ne f f i c i e n tm e t h o dt os o l v eo p t i m i z a t i o n p r o b l e m s ，a n dh a ss u c c e s s f u l l y b e e na p p l i e di nt h ea r e ao ff u n c t i o n o p t i m i z a t i o n ，n e u r a ln e t w o r kt r a i n i n ga n df u z z yc o n t r o ls y s t e m s ，e t c h o w e v e r ， b o t ht h e o r ya n da p p l i c a t i o no fe aa r es t i l lf a rf r o mm a t u r e t h i sp a p e rp u tt h ee m p h a s i so nt h es e v e r a lo p t i m i z a t i o np r o b l e m si nh i g h d i m e n s i o n a l i t yd r a w e do u tf r o md o m a i no fm u l t i p l em o b i l er o b o t ss y s t e m t h ed i s s e r t a t i o nf o c u s e so nt h ep r i n c i p l e s ，t h e o r y ，a n da p p l i c a t i o no fe a ， e s p e c i a l l y ，a ni n - d e e pa n ds y s t e m i cs t u d yo nh o wt oi m p r o v et h ec o n v e n t i o n a l e aa l g o r i t h m ，s o l v i n gt h e p r o b l e m s s u c ha s h i g h d i m e n s i o n a l f u n c t i o n o p t i m i z a t i o n ，c o n s t r a i n e do p t i m i z a t i o n ，e v o l v i n gn e u r a ln e t w o r k ，l a r g e - s c a l e c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e ma n ds o f tf a u l td i a g n o s i si nm u t i m o b i l e r o b o t sc o n t r o ls y s t e m s t h em a i na c h i e v e m e n t so ft h i sd i s s e r t a t i o ni n c l u d e ： an e wa p p r o a c hi s p r o p o s e dt o h a n d l eh i g hd i m e n s i o n a lc o n s t r a i n e d o p t i m i z a t i o np r o b l e m sa n dh i g hd i m e n s i o n a lg l o b a ln u m e r i c a lo p t i m i z a t i o ni n r e a ld o m a i nu s i n ge v o l u t i o n a r ya l g o r i t h mb a s e do ng o o dp o i n ts e t i tf o c u s e s o nt h ee f f e c i t v ec o n s t r a i n t h a n d l i n gt e c h n i q u e sa n dt h ee f f i c i e n te v o l u t i o n a r y a l g o r i t h m s b a s e do nt h es u c c e s s f u le x p e r i e n c e sf r o mo r t h o g a n a lm e t h o d ， d i f f e r e n t i a le v o l u t i o na n dp a r t i c l es w a r mo p t i m i z a t i o n ，t h ep r o p o s e dm e t h o d i sn o tr e l a t e dt ot h ed i m e n s i o n a l i t yo fs e a r c h i n gs p a c e t h eg e n eo p e r a t o r so f t h en e wm e t h o da r ec o n s t r u c t e da c c o r d i n gt og o o dp o i n ts e tp r i n c i p l ew h o s e p r e c i s i o ni sn o tb ec o n f i n e dt ot h ed i m e n s i o no ft h es e a r c hs p a c e i ti sab e a e r i d e af o rh i g hd i m e n s i o n a lo p t i m i z a t i o np r o b l e m st h a no r t h o g o n a la p p r o a c h t h er e s u l t so b t a i n e do fb e n c h m a r kf u n c t i o n ss h o wt h a tt h en e wa p p r o a c hi sa g e n e r a l ，e f f e c t i v ea n dr o b u s tm e t h o d a ne v o l u t i o n a r ys t r a t e g yb a s e do ng o o dp o i n ts e ta n dd e f f e r e n t i a l i e v o l u t i o ni sa p p l i e dt os o l v et h ep r o b l e mo f t u n i n gb o t hn e t w o r ks t r u c t u r ea n d p a r a m e t e r so faf e e d f o r w a r dn e u r a ln e t w o r k a d o p t i n gc o d eo fl e u n g ，t h e m e t h o dr e m a i n sb o t ht h eg l o b a ls e a r c ha b i l i t yo fd e f f e r e n t i a le v o l u t i o na n d t h e g o o dl o c a ls e a r c ha b i l i t yo fg o o dp o i n ts e t t h el o c a lo p t i m u m sa r e e f f e c t i v e l ya v i o d e d ，e s p e c i a l l yi nt h es i t u a t i o nw i t hh u g ep a r a m e t e r s t h e n u m b e r so fh i d d e nn o d e sa n dt h el i n k so ft h ef e e d f o r w a r dn e u r a ln e t w o r ka r e c h o s e nb yi n c r e a s i n gt h e mf r o ms m a l ln u m b e r su n t i lt h el e a r n i n gp e r f o r m a n c e i sg o o de n o u g h a sar e s u l t ，ap a r t i a l l yc o n n e c t e df e e d f o r w a r dn e u r a ln e t w o r k c a nb eo b t a i n e da f t e r t u n i n g t h i si m p l i e st h a tc o s to fi m p l e m e n t i n gt h e p r o p o s e dn e u r a ln e t w o r k ，i nt e r m so fh a r d w a r ea n dp r o c e s s i n gt i m e ，c a nb e r e d u c e d an o v e le n c o d i n ga p p r o a c hi sp r o p o s e dw h i c hc a nc o n s t r u c tam a p p i n g f r o mad i s c r e t e s p a c et o ac o n t i n u o u ss e c t i o nf o r s o l v i n gt h e1 a g r e s c a l e c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sd r a w e do u tf r o mt a s ka l l o c a t i o na n dp a t h p l a n n i n go fr o b o t b a s e do nt h en e we n c o d i n gs c h e m ea n da s s e m b l e dw i t ht h e s u c c e s s f u lm e c h a n i s mo ft h ee v o l u t i o n a r ya l g o r i t h m s ，t h ep e r f o r m a n c eo ft h e p r o p o s e da l g o r i t h mh a sl a r g e l yp r o m o t e d t h e r ei so n et oo n em a p p i n g b e t w e e nt h en e wc o d e sa n dt h ec o m b i n a t i o n a lv e c t o r s t h en e we n c o d i n g s c h e m ea l w a y sg e n e r a t e sf e a s i b l es o l u t i o n s ，w h i c hc a nh e l pa l g o r i t h mt oa v o i d r e d u n d a n tc o m p u t a t i o ne x i s t i n gi ns o m ea l g o r i t h m se f f e c t i v e l y b a s e do nt h e n e w e n c o d i n gs c h e m ea n dt h e o r e t i c a lp r o o f , t h es e a r c hs p a c ei sf u r t h e rr e d u c e d s e c o n d ，a ne x c e l l e n tq u e u ei sa d d e di ne v o l u t i o n a r ym e c h a n i s mc o m b i n e dw i t h p a r t i c u l a rl e a r n i n gs t r a t e g y d u r i n gt h ee v o l u t i o n a r yc o u r s e ，t h ee x c e l l e n t q u e u ei sr e f r e s h e df r e q u e n t l y t h i sc a nh e l pt h ep r o p o s e da l g o r i t h mm a i n t a i n t h er e l a t i v e l yg o o dg e n eb l o c k s f i n a l l y ，i t sc o n v e r g e n c et o g l o b a lo p t i m a l s o l u t i o nw i t hp r o b a b i l i t yo n ei sp r o v e d t h en u m e r i c a le x p e r i m e n t ss h o wt h e e f f e c t i v e n e s so ft h ea l g o r i t h m an e wn e g a t i v es e l e c t i o na l g o r i t h mb a s e do n ( + 五) - e si sp r o p o s e d ，w h i c h s o l v e st h ep r o b l e m so fs o f tf a u l td i a g n o s i si nm u t i m o b i l e r o b o t sc o n t r o l s y s t e m s a s s e m b l i n gt h eh a m m i n ga n dr - c o n t i n u o u sm a t c hr u l e sw i t ht h e s i g n a l - t o n o i s er a t i om e t h o d ，d e t e c t o r so ft h ew h o l es y s t e ma r ed i s t r i b u t e d m o r ee v e n c o m p a r e dw i t ht h et r a d i t i o n a l n e g a t i v es e l e c t i o na l g o r i t h m ，t h e n e wa l g o r i t h mi sn ol o n g e rb l i n d n e s si n s e a r c h i n gm a t u r ed e t e c t o r sf o rt h e e v o l u t i o n a r ys t r a t e g y e s p e c i a l l yf o rt h ec a s eo nl a r g e - s c a l es e l f , t h en e w i v a l g o r i t h mc a ng e n e r a t et h em a t u r ed e t e c t o r sr a p i d l ya n da c c u r a t e l ya l s o t h e r e s u l t so b t a i n e ds h o wt h a tb o t ht h en u m b e ro fi t e r a t i o nt og e n e r a t em a t u r e d e t e c t o r sa n dt h en u m b e ro fh o l e sd e c l i n eq u i c k l y ，w h i l et h er a t eo fd e t e c t i n g a b n o r m i t y r a i s e s k e yw o r d s g o o dp o i n ts e t ， n e t w o r k ，l a r g e s c a l ec o m b i n a t o r i a l d i a g n o s i s e v o l u t i o n a r ya l g o r i t h m ，e v o l v i n gn e u r a l o p t i m i z a t i o n ，n e g a t i v es e l e c t i o n ，s o rf a u l t v 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外j 论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 垂过日期：吐年月翠日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：导师签趣日期：三竺卫年互月三= 日 博士学位论文第一章绪论 第一章绪论 正如宋健院士在国际自动控制联合会第1 4 届大会报告中所指出的：“机器人学的 进步和应用是本世纪自动控制最有说服力的成就，是当代最高意义上的自动化n 1 。 机器人体现出广泛的学科交叉，包括自动控制、人工智能、电子技术、机械工程、传 感器技术以及计算机科学等。 对多机器人系统乜7 1 ( m u l t i p l er o b o ts y s t e m 简称m r s ) 研究始于上世纪8 0 年代， 其关键技术的研究包括：体系结构、任务分配、运动规划、通信、合作与协调、协进 化与协同适应性等等。多机器人系统中存在很多优化问题，例如：任务分配、运动规 划问题很大程度可以抽象转化为组合优化或大规模组合优化问题呻。引；通信问题里研 究a dh o c 网络节点的分布等问题可以转化为函数的优化问题；除了前面提及的合作与 协调、协进化与协同适应性，在机器人的学习以及软故障检测等领域，很多关键问题 也都可以抽象转化为组合优化和函数优化等问题。目前，已有很多智能算法应用于这 些方面，也取得了一定的成果。不过，进化算法对于高维函数优化、大规模组合优化 问题的研究和基础应用并不多见。 本文的研究工作是基于自行改造的a m i g o 移动机器人实验平台为背景展开。用于 高维优化的进化算法及其应用研究主要目的是针对多移动机器人系统中抽象出的高维 函数求解、大规模组合优化、机器人智能的训练和学习和该系统中软故障的检测等问 题的。重点围绕高维优化进化算法的新框架和应用展开研究：分为连续域优化和离散 域优化来进行。把进化算法与具体的应用领域相结合，针对应用领域采用相应的进化 技术，并对进化技术进行改进和提高。 1 1 优化技术与进化计算 1 1 1 优化技术 优化技术是一种以数学为基础的古老课题。就是在众多方案中寻找最优方案，即 在满足一定的约束条件下，寻找一组参数值，以使某些最优性度量得到满足，或者使 系统的某些性能指标达到最大或最小。长期以来，人们对优化问题进行了探讨和研究， 从1 7 世纪开始，先后有了n e w t o n 和l e i b n i t z 的微积分法，c a u c h y 的最速梯度下降法， 以及后来针对约束优化问题的l a g r a n g e 乘数法等等n l1 8 1 。近年来，由于计算机日益广 泛应用以及其它相关学科迅猛地发展，使优化问题的研究不仅成为一种迫切需要，而 且有了求解的有力工具。因此，优化的理论和算法迅速发展起来，优化技术在实际应 博士学位论文 第一章绪论 用中正发挥越来越大的作用。 传统的优化方法如牛顿法、共扼梯度法、模式搜索法、单纯形法、r o s e n b r o c k 法 和p o w e l l 法，在面对某些大型问题时，需要遍历整个搜索空间，从而会产生搜索的组 合爆炸，无法在多项式时间内完成搜索。许多工程优化问题，由于其性质十分复杂， 常常需要在复杂而庞大的搜索空间中寻找最优解或者准最优解。这样在计算速度、收 敛性、初值敏感性等方面都远不能满足要求，工程优化问题的求解很困难，因此高效 的优化算法成为科学工作者的研究目标之一。 随着生物学中的进化论被广泛地应用于工程技术、人工智能等领域中，形成了一 类新的搜索算法。它们主要是模仿生物学中进化和遗传过程，遵循达尔文的“适者生 存、优胜劣汰 的竞争原则，从一组随机生成的初始可行解群体出发，借助复制、重 组以及突变等遗传操作，在搜索过程中自动获取并积累解空间的有关知识，逐步向问 题的最优解或者次优解逼近。遗传算法( g a ) 是应用比较广泛的一种算法，除了遗传算 法( g a ) 外，一些新颖的优化算法也得到了迅速发展，如人工神经网络 在一定程度上 模拟了人脑的组织结构n 争2 妇：蚁群算法( a c o 算法) 受启发于自然界蚂蚁的寻径方式； 模拟退火( s a ) 思路源于物理学中固体物质的退火过程等等。这些算法有个共同点，都 是通过模拟或揭示某些自然界的现象和过程得到发展，在优化领域，称之为智能优化 算法，或者计算智能。因此从实质上来说，智能优化算法是一类具有自适应调节功能 的搜索寻优技术，目前它们己经被广泛地应用到组合优化问题、机器学习、人工生命、 自动控制以及动态系统的故障诊断等领域中。 1 1 2 进化算法 进化算法乜2 1 ( e a ：e v o l u t i o n a r ya l g o r i t h m ) 是由生物进化规律而演化出的一种搜索 和优化的计算方法，通常包括三个部分：遗传算法( g e n e t i ca l g o r i t h m ) 、进化策略 ( e v o l u t i o n a r ys t r a t e g y ) 、进化规划( e v o l u t i o n a r yp r o g r a m m i n g ) ，也称之为广义遗传算法 ( g e n e r a l i z e dg e n e t i ca l g o r i t h m ) 。其基本框架如图1 - 1 所示。在过去几十年的研究中， 研究者们已在进化计算领域取得了不菲的成果。与传统的算法相比，进化算法最主要的 差别在于进化计算具有智能性和本质并行性的特征。也有很多文献将目前研究的进化 算法主要分成四种典型算法：遗传算法( g e n e t i ca l g o r i t h m s ，g a s ) 乜3 。2 引、进化规划 ( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 心9 30 i 、进化策略( e v o l u t i o ns t r a t e g y , e s ) 口1 3 2 1 和遗传编 程( g e n e t i cp r o g r a m m i n g ，g p ) 口朝。前三种算法是彼此独立发展起来的，最后一种是在 遗传算法的基础上发展起来的一个分支。虽然这几种方法在实现手段上各有特点、互 不相同，但它们所遵循的进化原则是一致的，即都是借助生物进化的思想和原理来解 决实际问题。 2 博士学位论文第一章绪论 遗传算法 图1 - 1 进化算法的基本框架 遗传算法的创始人是美国的著名学者密西根大学教授h o l l a n d 乜引。他在二十世纪 五十年代末期开始研究自然界的自适应现象，并希望能够将自然界的进化方法用于实 现求解复杂问题的自动程序设计。h o l l a n d 认为，可以用一组二进制串来模拟一组计算 机程序，并且定义了一个衡量每个“程序 正确性的度量：适应值。h o l l a n d 模拟自然 选择机制对这组“程序 进行“进化 ，直到最终得到一个正确的“程序 。1 9 6 7 年， b a g l e y 发表了关于遗传算法应用的论文乜钔，在其论文中首次使用了“遗传算法 来命 名h o l l a n d 所提出的“进化方法。7 0 年代初，h o l l a n d 教授提出了遗传算法的基本定 理一模式定理，从而奠定了遗传算法的理论基础。模式定理揭示出群体中的优良个体 的样本数呈指数级增长的规律。1 9 7 5 年，h o l l a n d 总结了自己的研究成果，发表了在 遗传算法领域具有里程碑意义的著作一自然系统和人工系统的适应性。在这本书中， h o l l a n d 为所有的适应系统建立了一种通用理论框架，并展示了如何将自然界的进化过 程应用到人工系统中去。h o l l a n d 认为，所有的适应问题都可以表示为“遗传”问题， 并用“进化 方法来解决。8 0 年代，h o l l a n d 教授实现了第一个基于遗传算法的机器 学习系统一一分类器系统，开创了遗传算法机器学习的新概念乜朝。 1 9 7 5 年，d ej o n g 在其博士论文中结合模式定理进行了大量纯数值函数优化计算 实验，建立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。它还构 造了著名的五个d ej o n g 测试函数乜引。1 9 8 9 年，g o l d b e r g 出版了专著搜索、优化和 机器学习中的遗传算法。该书系统总结了遗传算法的主要研究成果，全面而完整地论 述了遗传算法的基本原理及应用，这本书奠定了现代遗传算法的科学基础。1 9 9 1 年， d a v i s 编辑出版了遗传算法手册一书，书中包括了遗传算法科学计算、工程技术 3 博士学位论文第一章绪论 和社会经济中的大量应用实例，它为推广和普及遗传算法起到了重要的作用。 标准遗传算法具有如下主要特点： ( 1 ) 遗传算法必须通过适当的方法对问题的可行解进行编码。解空间中的可行解是 个体的表现型，它在遗传算法的搜索空间中对应的编码形式是个体的基因型。 ( 2 ) 遗传算法基于个体的适应度来进行概率选择操作。 ( 3 ) 在遗传算法中，个体的重组使用交叉算子。交叉算子是遗传算法所强调的关键 技术，它是遗传算法中产生新个体的主要方法，也是遗传算法区别子其它进化算法的 一个主要特点。 ( 4 ) 在遗传算法中，变异操作使用随机变异技术。 ( 5 ) 遗传算法擅长对离散空间的搜索，它较多地应用于组合优化问题。 遗传算法除了上述基本形式外，还有各种各样的其它执行策略，如溶入退火机制 口4 q 6 1 、结合已有的局部寻优技巧7 删，并行进化机制h p 4 副、协同进化机制h p 4 8 1 等等。典 型地，例如退火型遗传算法、f o r k i n g 遗传算法h 9 5 1 1 、自适应遗传算法、抽样型遗传 算法、协作型遗传算法、混合遗传算法晒3 1 、实数编码遗传算法、动态参数编码遗传算 法嘲5 9 1 等等。 进化规划 二十世纪6 0 年代中期，f o g e l 等人为有限状态机的演化提出了利用进化规划来求 解预测问题口引，这些机器的状态变化表示通过在对应的离散、有界集上进行一致随机 变异来修改。进化规划根据被正确预测的符号数来度量适应度。通过变异，父代群体 中的每个机器产生一个子代，父代和子代中最好的那一半被选择生存下来。9 0 年代， f o g e l 又将进化规划的思想拓展到实数空间，使其能够用来求解实数空间中的优化 计算问题，并在其变异运算中引入正态分布技术，这样，进化规划就演变成一种优化 搜索算法，并在很多实际领域得到了应用哺9 。6 引。进化规划主要具有下面几个特点： ( 1 ) 进化规划不使用个体重组方面的操作算子，如不使用交叉算子。 ( 2 ) 进化规划中的选择运算着重于群体中个体间的竞争选择。 ( 3 ) 进化算法直接以问题的可行解作为个体的表现形式，无需对个体进行编码，也 无需考虑随机扰动因素对个体的影响，便于应用。 ( 4 ) 进化规划以n 维实数空间上的优化问题为主要处理对象。 进化策略 进化策略是二十世纪6 0 年代由德国的r e c h e n b e r g 和s c h w e f e l 首先提出的一种优 化算法引。当初主要用于处理流体动力学问题，如弯管流体动力学优化。进化策略主 要用于求解多峰非线性函数的优化问题，随后，人们根据算法的不同选择操作机制提 4 博士学位论文第一章绪论 出了多种进化策略，例如：( 1 + 1 ) e s ，( 1 + ) e s ，( + a ) e s ，( ，旯) e s 等卜7 3 1 。 进化策略具有下面一些特点： ( 1 ) 进化策略以n 维实数空间上的优化问题为主要处理对象。 ( 2 ) 进化策略的个体中含有随机扰动因素。 ( 3 ) 进化策略中个体的适应度直接取为它所对应的目标函数值。 ( 4 ) 个体的变异运算是进化策略中所采用的主要搜索技术，而个体间的交叉运算只 是进化策略中所采用的辅助搜索技术。 ( 5 ) 进化策略中的选择运算是按照确定的方式进行的，每次都是从群体中选取最好 的几个个体，将它们保留在下一代群体中。 遗传编程 1 9 9 2 年，k o z a 将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗 传编程的概念口引，并成功地将遗传编程方法应用于人工智能、机器学习、符号处理等 方面。遗传程序设计采用遗传算法的基本思想，但使用一种更为灵活的表示方式一分 层结构来表示解空间。这些分层结构的叶节点是问题的原始变量，中间节点则是组合 这些原始变量的函数。遗传程序设计即是使用一些遗传操作动态地改变这些结构以获 得解决问题的可行的计算机程序。 由于遗传程序设计采用一种更自然的方式，使得其应用领域非常广泛，不仅可以 演化计算机程序，而且可以演化任何复杂的系统h 4 。7 8 1 。 1 1 3 进化算法的应用 进化算法是多学科结合与渗透的产物，它己发展成一种自组织、自适应的综合技 术，广泛用在计算机科学、工程技术、管理科学和社会科学等领域。进化算法的研究 工作主要集中在以下几个方面口9 。眈1 ： ( 1 ) 基础理论：包括进一步发展进化算法的数学基础，从理论和实验研究它们的计 算复杂性。在进化算法中，群体规模和遗传算子控制参数的选取是非常困难的，同时 又是必不可少的实验参数，这方面已有一些具有指导性的实验结果。遗传算法还存在 一个过早收敛问题，怎样阻止过早收敛也是人们感兴趣的问题之一。 ( 2 ) 函数优化：函数优化是进化算法的经典应用领域，也是对进化算法进行评价的 常用领域。 ( 3 ) 组合优化：这一类问题随着规模的增大，其搜索空间也急剧扩大。对这类复杂 问题，人们往往寻求其满意解，而进化算法是寻求这种满意解的最佳工具之一。实践 证明，进化算法对于组合优化中的n p 完全问题非常有效。 5 博士学位论文第一章绪论 ( 4 ) 分类系统：分类系统属于基于进化算法的机器学习中的一类，它包括一个简单 的基于串规则的并行生成子系统，规则评价子系统和进化算法子系统。分类系统正被 人们越来越多地应用在科学、工程和经济等领域中。目前，分类系统是进化算法研究 中一个非常活跃的领域。 ( 5 ) 并行进化算法：进化算法在操作上具有高度的并行性，许多研究人员都正在探 索在并行计算机上高效执行进化算法的策略。通过保持多个群体和恰当地控制群体间 的相互作用来模拟并行执行过程，即使不使用并行计算机，也能提高算法的执行效率。 ( 6 ) 图像处理：在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存 在一些误差，这些误差会影响图像处理的效果，如何使这些误差最小是使计算机视觉 达到实用化的重要要求。目前进化算法己在模式识别、图像恢复、图像边缘特征提取， 图像分割等方面得到了应用。 ( 7 ) 进化神经网络：包括连接权、网络结构和学习规则的进化。进化算法与神经网 络相结合正成功地用于从时间序列分析来进行财政预算。在这些系统中，训练信号是 模糊的，数据是有噪声的，一般很难正确地给出每个执行的定量评价如果采用进化算 法来学习的话，就能克服这个困难，显著地提高系统的性能。m u h l e n b e i n 分析了多层 感知器网络的局限性，并猜想下一代神经网络将会是遗传神经网络。 ( 8 ) 人工生命：自组织能力和自学习能力是人工生命的两大主要特征。基于遗传算 法的进化模型是研究人工生命现象的重要理论基础。虽然人工生命的研究处于启蒙阶 段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了 初步的应用能力，并且必将得到更为深入地应用和发展。 1 2 高维进化在多机器人领域的国内外研究现状分析 1 2 1 国内外研究现状分析 近年来，进化算法因其算法简单，在组合优化问题和复杂的函数优化问题上有很 强的计算能力，进化算法得到国际学术界普遍重视。然而，在进化算法中，针对不同 的求解问题，采用不同的进化个体的编码方式、不同的进化技术以及不同的进化框架 等等，都会在结果上带来很大的差异。有很多成熟的进化技术因为没有很好的进化框 架模型还没有广泛应用，也有很多进化技术在具体领域尚待改进。下面，结合多移动 多机器人领域抽象出的几个基础应用对进化算法进行介绍： 约束优化问题旧3 1 简称c o p s ，是多机器人领域，同时也是其他科学和工程应用领域经常会遇到的 6 博士学位论文第一章绪论 一类数学规划问题。约束优化问题求解已成为进化计算研究的一个重要方向。基于进 化算法进行约束处理的方法常见的有：1 ) 惩罚函数法【“1 ；2 ) 多目标法【驺1 ；3 ) 其它方法 1 拍- 1 0 2 1 。作为进化算法的一个重要部分，近年来进化策略在处理约束优化问题时受到了 极大的重视。对此有以下两个原因：1 ) 具有理论背景支持进化策略收敛；2 ) 进化策略 的自适应机制对其处理约束搜索空间有一定的帮助。实验结果表明，在相同的约束处理 技术下，采用进化策略时算法的整体性能明显优于遗传算法。通过融合三个简单的个体 比较准则，m e z u r a 和c o e l l o 对几种不同的进化策略进行了实验比较。结果表明对于具 有高维搜索空间、非线性等式约束条件的测试函数，利用进化策略不能得到很好的结 果。因为进化策略本身存在着一个缺陷，即在进化策略中交叉操作往往被忽略。然而， 就约束优化问题而言，可行解与不可行解在一些重要的区域进行交叉对于找到全局最 优解却很有帮助，特别是当全局最优解位于可行域边界上时。尽管在进化策略中也可 以使用交叉操作，但其搜索能力十分有限。运用正交表技术来指导交叉操作在高维搜索 空间取得了许多成果。然而，为了达到精度，当正交表因素个数和等级增多时，实验 的规模迅速增加，相应的正交表构造起来也很麻烦，这些对于进化算法在高维空间求 解带来了一定的困难。 进化神经网络n 叫惦1 2 0 世纪8 0 年代，美国物理学家j j h o p f i e l d 建立全互连神经网络模型和r u m t h a r t 提出反向传播算法( b p 算法) 以来，神经网络( n e u r a ln e t w o r k s ) 研究获得飞速发展。神 经网络的通用近似能力是一个非常突出的特点。在信号处理、模式识别、目标跟踪、 机器人控制、专家系统、组合优化、预测系统和网络管理等众多领域获得了广泛的应 用，多机器人领域综合了上述的很多方面。一个多层的人工神经网络能近似任何非线 性连续函数达到任意精度。由于其特殊结构，神经网络适合用遗传算法和常用的反演 算法作为学习算法。在多机器人系统中，要求用于机器学习的进化神经网络功能较强。 如果权值和结构同时调整那么要解决以下几个问题：( 1 ) 如何开发出一种新的编码方 式，使算法能同时进化神经网络的连接权、结构甚至学习规则；( 2 ) 如何提高进化算 法对构造新型神经网络的适应性和算法的计算性能。由于网络编码方法的多样性以及 对不同应用的侧重不同，就要求进化算子及其参数值具有较好的适应能力；由于进化 算法的局部搜索性能的缺陷，就要求考虑如何把进化算法和具有较好局部搜索能力的 其他算法相结合以提高算法的计算性能；( 3 ) 如何改进适应度评价函数，过于单一的适