（测试计量技术及仪器专业论文）进化计算应用于计量测试技术的理论研究.pdf

摘要 摘要 进化计算是基于模拟自然进化思想而发展起来的一类随机搜索技术，它从生 物底层对智能行为进行模拟和研究，拓展了传统的搜索方法，为复杂问题的求解 提供了新的途径。进化计算主要包括遗传算法( g a ) 、进化规划但p ) 和进化策略( e s ) 等方法，这些方法在科学研究和工程技术的应用越来越广泛。 本文将标准遗传算法、进化规划和进化策略同时用于对测试函数优化，发现 不同的进化算法甚至是同一种算法在设置不同的控制参数时，算法的执行时间及 解决不同优化闻题的能力明显不同，鉴于此本文提出了一种对进化算法优化效率 进行定量评价的方法，实验评价结果与理论分析完全吻合，证实了所提出评价准 则的科学性、合理性。 总结了国内外现有的有关形状误差评定的各种方法：针对形状误差评定的特 点，提出了一种能够实现形状误差统一评定的改进遗传算法，该算法显著特点是 算法简单、计算精度和稳定性高、鲁棒性强、优化效率高，便于在坐标测量仪中 推广应用，从而解决了形状误差迄今为止无法实现统一评定的难题。在深入分析 各种形状误差特点的基础上，建立了基于遗传算法求解平面直线度、空间直线度、 平面度、圆度、圆柱度、球度误差目标函数的数学模型，通过大量实例证实了算 法的有效性。 为了克服现有进化算法在解决高维、复杂优化问题时个体的自适应环境能力 较弱等缺陷，本文基于生物免疫系统的细胞克隆选择学说和生物进化过程中的变 异思想，提出一种新颖的免疫进化计算方法。建立了能够实现对混沌信号预测的 前向神经网络结构，并将提出的免疫进化算法用于对神经网络优化，通过对l o g i s t i c 混沌信号和太阳黑子数进行预测，并与b p 算法、模糊遗传算法、遗传规划等多种 方法进行比较，结果表明本文提出的方法预测精度明显高于其它方法，可以用来 解决实际非线性时间序列预测问题。最后对本文提出的改进遗传算法和免疫进化 算法进行了比较阐明了各自的最佳适用场合。 关键词：进化计算、形状误差评定、混沌信号预测、优化效率、免疫算法、神经 网络 东南大学博士学位论文 a b s t r a c t e v o l u t i o n a r yc o m p u t a t i o n c ) i sa s t o c h a s t i c s e a r c h i n gt e c h n o l o g yb a s e do n s i m u l a t i n g n a t u r a le v o l u t i o ni d e a s ，w h i c hs i m u l a t e sa n dr e s e a r c h e st h e i n t e l l i g e n t b e h a v i o rf r o mt h el o w e s tl e v e lo ft h ec r e a t u r e e cd e v e l o p st h et r a d i t i o n a l s t y l e o f c o m p u t a t i o na n dp r o v i d e san e wa p p r o a c hf o rs o l v i n gc o m p l e xp r o b l e m se ci n c l u d e s g e n e t i ca l g o r i t h m ( g a ) ，e v o l u t i o n a r yp r o g r a m m i n gc e p ) a n de v o l u t i o n a r ys t r a t e g y ( e s ) a n ds oo n ，w h i c ha r eu s e d w i d e l y i ns c i e n t i f i cr e s e a r c ha n d e n g i n e e r i n gt e c h n o l o g y t h ee x p e r i m e n tr e s u l t sf o rt e s tf u n c t i o n sb ys t a n d a r dg 九e pa n de ss h o wt h e c o m p u t a t i o nt i m ea n do p t i m i z a t i o nc a p a b i l i t yo fd i f f e r e n te v o l u t i o n a r ya l g o r i t h m si n s o l v i n gd i f f i c u l tp r o b l e m sa r ee v i d e n t l yd i f f e r e n t c o n s i d e r i n gt h i sf a c t ，t h eq u a n t i t a t i v e e v a l u a t i o nm e t h o df o ro p t i m i z a t i o ne f f i c i e n c yo f e v o l u t i o n a r ya l g o r i t h m si sp r o p o s e d t h ee v a l u a t i o nr e s u l t so ft h ee x p e r i m e n t sa r ec o n s i s t e n tw i t ht h et h e o r e t i ca n a l y s i sa n d i td e m o n s t r a t e st h e p r o p o s e da l g o r i t h m i se f f e c t i v ea n dv a l i d e x i s t i n gm e t h o d so nf o r me r r o r s e v a l u a t i o na r es u m m a r i z e d a c c o r d i n gt ot h e c h a r a c t e r i s t i c so ff o r me r r o r se v a l u a t i o n ，a ni m p r o v e dg a ( i g a ) i s p r o p o s e dt h a tc o u l d a c c o m p l i s ht h e i ru n i f i e de v a l u a t i o n t h ep r o m i n e n tc h a r a c t e ro fi g a i s s i m p l e ，h i g h p r e c i s ea n ds t a b l e ，s t r o n gr o b u s ta n dh i g he f f i c i e n t a n di t i s e a s yt ob ea p p l i e di n c o o r d i n a t em e a s u r e m e n tm e t r o l o g y ( c m m ) c o n s e q u e n t l yt h ed i f f i c u l t p r o b l e mi n w h i c hs of o rt h ef o r me r r o r sh a v en o tb e e ne v a l u a t e d u n i f o r m l yh a sb e e ns o l v e d b a s e d o nf u r t h e ra n a l y z i n ge a c hf o r me r r o r , t h eo b j e c t i v ef u n c t i o nm a t h e m a t i c sm o d e l so f p l a n a rs t r a i g h t n e s s , s p a t i a ls t r a i g h t n e s s ，f l a t n e s s ，c i r c u l a r i t y , c y l i n d r i c i t ya n ds p h e r i c i t y e r r o r sb a s e do ng aa r ef o u n d e d a n dl a r g en u m b e r so f p r a c t i c a le x a m p l e sd e m o n s t r a t e t h ee f f e c t i v e n e s so f t h e p r o p o s e di g a i no r d e rt oo v e r c o m et h ed r a w b a c k so f e x i s t i n ge v o l u t i o n a r ya l g o r i t h m si ns o l v i n g m u l t i - d i m e n s i o n a la n dc o m p l e xp r o b l e m s ，an o v e li m m u n ee v o l u t i o n a r yc o m p u t a t i o n m e t h o d ( c ) i sp r o p o s e db a s e do nt h ee e u u l a rc l o n a ls e l e c t i o nt h e o r yo fb i o l o g y i m m u n e s y s t e ma n dt h em u t a t i o ni d e a so fb i o l o g ye v o l u t i o np r o c e s st h ef e e df o r w a r d n e u r a ln e t w o r ks t r u c t u r ei sc o n s t r u c t e dt or e a l i z et h ef o r e c a s to f c h a o s s i g n a la n di e c i s u s e dt o o p t i m i z e t h en e u r a l n e t w o r k c o m p a r e d w i t h b e , f u z z yg a , g e n e t i c p r o g r a m m i n g ( g p ) a n d o t h e rm e t h o d sf o rl o g i s t i cc h a o ss i g n a la n ds u n s p o t sf o r e c a s t t h ef o r e c a s tp r e c i s i o no f t h e p r o p o s e di e c i s h i g h e r t h e r e b y , i tc o u l db eu s e dt os o l v e t h ef o r e c a s tp r o b l e mo fa c t u a ln o n l i n e a rt i m e s e r i e s f i n a l l y , t h ep r o p o s e di g aa n di e c a r ec o m p a r e dw i t he a c ho t h e r , a n dt h e i rb e s ta p p l i c a t i o n r e g i o n sa r es e tf o r t h k e yw o r d s ：e v o l u t i o n a r yc o m p u t a t i o n ，f o r me r r o r se v a l u a t i o n ，c h a o ss i g n a l f o r e c a s t ， o p t i m a le f f i c i e n c y , i m m u n ea l g o r i t h m , n e u r a ln e t w o r k 声明 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 另外，未经作者本人或导师允许，任何人不得以本文的内容作为论文发表。 研究生签名：湟盘之 日 期：竺生：至窜 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论 文的复印件瓤电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电 子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文 被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。另外，未经作者本人或导师允许，任何人 不得以本文的内容作为论文发表。 研究生签名：丝盘兰导师签名： 日期：御争；面 第一章课题研究的意义及国内外研究现状 第一章课题研究的意义及国内外研究现状 i i 进化计算的特点及其优越性 从本世纪四十年代起，对自然界的模拟就构成了计算科学、人工智能、信息 处理和自动控制学科的一个组成部分。进化计算( e v o l u t i o n m yc o m p u t a t i o n ，e c ) 是 基于模拟自然进化思想而发展起来的一类随机搜索技术，是将自然界生物学原理 应用于科学研究的智能信息处理技术。进化计算的研究起源于2 0 世纪5 0 年代末， 成熟于8 0 年代。自6 0 年代中叶，h o l l a n d 提出遗传算法( g e n e t i ca l g o r i t h m s ，g a ) ”】， s c h w e f e l 提出进化策略( e v o l u t i o n a r ys t r a t e g y , e s ) t 2 j ，f o g e l 提出进化规划 f e v o l u t i o n a r yp r o g r a m m i n g e p ) t 3 1 ，形成了进化计算的三大分支。这三种方法具有 共同的本质，分别强调了自然进化中的不同方面：遗传算法强调染色体的操作， 进化策略强调个体级的行为变化，而进化规划则强调种群上的行为变化。9 0 年代 初，在遗传算法的基础上又形成了一个分支：遗传规划( g e n e t i cp r o g r a m m i n g ， g p ) 【4 1 。虽然这几个分支在算法实现方面有一些差别，但是这些差别正逐渐缩小， 它们共同的特点是借助生物进化的思想和原理来解决实际问题，在利用生物进化 机制提高计算机求解问题能力的目标和基本问题思路上是一致的，即都是基于群 体中个体间相互竞争和信息交换进化出适应度高的个体。 由于进化计算采用随机变换规则，以目标函数的值信息指导进化搜索，无需 目标函数的导数信息或其它问题相关的特殊信息，因此与传统的优化算法相比， 受噪声和干扰的影响小、对初始值的选择不敏感，具有较强的“鲁棒性”，特别适 合于复杂、多态、不可微、高度非线性的优化问题，尤其是梯度信息难以获取以 及优化目标函数难以定义的优化问题。相比于单纯形法、梯度法、模拟退火法、 神经网络等优化算法，进化计算的优越性主要表现在：( 1 ) 以优化变量的遗传编码 为运算、搜索对象。传统的优化算法往往直接利用优化变量的实际值本身进行优 化计算，但进化计算是以优化变量的某种形式的遗传编码为运算对象。这使得我 们在优化计算过程中可以借鉴生物学中染色体和基因等概念，可以模仿自然界中 生物进化机制与遗传变异原理，也使得我们可以方便地应用遗传、进化等操作算 子。特别是对一些非数值优化问题，进化计算显示其独特的优越性。( 2 ) 只应用“适 应值”信息，而无需应用目标函数的具体值及其辅助信息。传统优化算法不仅依 赖于直接应用目标函数的具体值，而且也往往需要应用目标函数的导数值等其它 一些辅助信息来确定搜索方向。而进化计算通常仅使用目标函数变换来的适应值 ( 或目标函数) 指导搜索，这使得进化计算不仅可以方便地应用于那些有目标函数 的，但很难求导数，或导数不存在的优化问题( 特= j j j 如组合优化与非光滑优化问题) ， 而且更重要地，可应用于那些目标函数无明确表达，或有表达但不可精确估值的 东南大学博士学位论文 优化问题。( 3 ) 使用群体搜索策略，非单点操作。传统优化算法往往是从解空间的 一个初始点出发的单点迭代，因而搜索效率不高，易于使搜索过程陷于局部极值 而停滞不前。进化计算是从由多个个体所组成的初始种群起始的种群空间中的迭 代过程( 从而形成个体空间中的多条轨迹) ，其搜索过程中的每一步利用了种群中各 个体所提供的信息( u p 群体信息) 。这些信息可以避免一些不必要搜索的点或区域， 从而既提高了搜索效率，也更大程度上避免了局部极值。另外，进化计算的群体 搜索机制使其具有自然的并行性。( 4 ) 使用概率搜索机制。很多传统优化算法使用 的是确定性的搜索方法，一个搜索点到另一个搜索点的转移有确定的转移关系， 这种确定性使得算法的搜索具有定向性，从而很难达到问题的全局最优解，而且 数值稳定性不好。进化计算在计算的各个步骤多使用概率转移规则，因而是一类 导向的随机搜索技术，它能以一定概率接受不一定好的个体，从而大大提高了算 法跳出局部极值陷阱的能力。另外，概率搜索机制的一个自然优点是相应算法的 稳健性( r o b u s t n e s s ) 。由于进化计算容易介入到已有的模型中并且具有可扩展性，以 及易于同其它的技术混和等因素，进化计算目前已经在最优化、机器学习和并行 处理等领域得到了越来越广泛的应用。 正是进化计算的上述优点，使得越来越多的研究人员对进化计算产生浓厚兴 趣，从不同角度对其进行研究并将其应用于解决各种困难的优化问题。 1 2 进化计算理论的基本框架 进化计算作为一门新兴学科，其框架结构可以用图1 1 表示。 图1 1 进化计算理论框架结构 基因型与表现型之间的关系是进化计算中的一个基本关系，在其复杂的非线 性关系中“一因多果”和“一果多因”是突出的两个特点。表现型的变化是对象 2 第一章课题研究的意义及国内外研究现状 遗传结构和当时环境条件交互作用所致的结果，非线性效果很明显，甚至相差很 大的遗传结构可能会导致类似的行为。这样在研究基因型一表现型相互关系及其 在进化过程中的规律时就必须充分利用非线性系统工具和随机过程的统计测度理 论，动力学机制也是必须加以研究的动态属性。在进化计算中算子占有重要的地 位，相应的操作也应反映动态的机制。因此，进化计算体系可归纳为： 进化计算= 进化算子+ 进化操作+ 选择策略+ 进化计算理论 进化计算作为完整的体系，应包括最优性、统计分析、选择策略和相应判据 等内容。 1 3 进化计算的结构 生物的进化过程主要是通过选择与染色体之间的交叉和基因变异来完成的。 与此相对应，进化计算搜索最优解的过程就是模仿生物的这个进化过程，使用所 谓的选择算子( s e l e c t i o no p e r a t o r ) 、交叉算子( c r o s s o v e ro p e r a t o r ) 与变异算子( m u t a t i o n o p e r a t o r ) 等来模拟进化，从而产生一代又一代种群。 n 选择算子：是模拟自然选择的操作，反映“优胜劣汰”原理。它根据每一 个个体的适应度，按照一定规则或方法，从t 代种群x ( r ) 中选择出一些优 良的个体( 或作为母本，或让其遗传到下一代种群牙o + 1 ) ) 2 ) 交叉算子：是模拟有性繁殖的基因重组操作，它将从群体g ( t ) 所选择的每 一对母体依一定概率( 称为交叉概率，c r o s s o v e rr a t e ) 交换它们之间的部分 基因。 3 ) 变异算子：是模拟基因突变的遗传操 作，它对种群j ( f ) 中的每一个个体， 依一定概率( 称为变异概率，m u t a t i o n r a t e ) 改变某一个或某一些基因座上 的基因值为其它的等位基因。 交叉算子与变异算子其作用都在于改 变染色体基因，以生成新的个体，因而它们 之一或复合也称为繁殖( 或重组， r e c o m b i n a t i o n ) 算子。 进化算法的基本流程如图1 2 ，实现流 程如下： 1 ) ( 初始化) 确定种群规模及终止准 则( 如设置最大进化代数、所期望达到的近似 精度或最优解无改善的代数) ；随机生成 个个体作为初始种群贾( f ) ；置进化代数计数 图1 2 进化算法的基本流程 东南大学博士学位论文 器f o 。 2 ) ( 个体适应度的评价) 计算或评估种群贾( f ) 中每一个个体的适应度。 3 ) ( 种群进化) ( 1 ) 选择将选择算子作用于种群x ( f ) ： ( 2 ) 繁殖将繁殖算子作用于选择后的种群，并生成下一代种群x ( t + 1 ) ： 4 ) ( 终止检验) 如果j ( f + 1 ) 满足终止准则，则输出2 ( t + 1 ) 中具有最大适应度 的个体作为最优解，终止计算；否则置f 一什l ，转2 ) 。 1 4 进化计算的发展简史 进化计算的三种主要算法：遗传算法、进化规划和进化策略是彼此独立发展 起来的。 虽然进化计算的起源可以追溯到2 0 世纪5 0 年代末期p 】，但是当时从事这方面 研究的主要是一些生物学家，研究的目的主要是为了更深入地理解自然遗传与自 然进化现象。6 0 年代，美国密歇根( u n i v e r s i t yo f m i c h i g a n ) 大学的心理学教授、电 子工程学与计算机科学教授j o h n h o l l a n d 受达尔文进化论适者生存的启发，认识 到在机器学习的研究中，为了获得一个好的学习算法仅靠单个策略建立和改进是 不够的，还要依赖于一个包含许多候选策略的群体的繁殖，因此他提出在研究和 设计人工自适应系统时，可以借鉴生物自然遗传的基本原理，模仿生物自然遗传 的基本方法。1 9 6 7 年，他的学生j d b a g l e y 在博士论文中首次提出“遗传算法” 一词。此后，h o l l a n d 指导学生完成多篇博士论文。到7 0 年代初，h o l l a n d 提出了 “模式定t 里( s c h e m at h e o r e m ) ”，从而奠定了遗传算法研究的理论基础。1 9 7 5 年， h o l l a n d 出版了著名的自然系统和人工系统的自适应性，这是第一步论述遗传 算法的专著，因此有人把1 9 7 5 年作为遗传算法的诞生年。同年，d e j o n g 6 】首先将 遗传算法应用于函数优化，并建立起了目前人们所熟悉的遗传算法工作框架，从 而为这一应用技术奠定了基础；1 9 8 9 年，g o l d b e r g 提出了一种变长度染色体遗传 算法，该算法在不影响模式定义距的情况下，使优良的模式得以增殖，并出版了 搜索、优化和机器学习中的遗传算法【_ “，总结了遗传算法研究的主要成果，对 遗传算法及其应用作了全面而系统的论述。此后，以优化问题为背景，遗传算法 的各种改进层出不穷，有d a v i s 引、e s h e l m a n p l 、f o r r e s t i ”1 、k o z a 1 、m i t c h e l l i t 2 】、 r i o l o 【l ”、s e h a f f e r t l 4 1 等学者对遗传算法进行的改进与发展。近年来，人们对原来的 遗传算法或称为标准遗传算法( s g a ) 进行了大量的改进，使遗传算法应用于更广泛 的领域。从1 9 8 5 年在美国卡耐基梅隆大学召开的第一届国际遗传算法会议 ( i n t e r n a t i o n a lc o n f e r e n c e0 1 1g e n e t i ca i g o r i t h m s ，i c g a8 5 ) 到1 9 9 7 年5 月i e e e 的 t r a n s a c t i o n so n e v o l u t i o n a r yc o m p u t a t i o n 创刊，有关遗传算法的研究和应用日益普 遍，遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐 4 第一章课题研究的意义及国内外研究现状 趋成熟。 6 0 年代中期，lj f o g e l 等人在设计有限状态机( f i n i t es t a t em a c h i n e ，f s m ) 时提出了进化规划f ”】。他们借用进化的思想对一组f s m 进行进化，以获得较好的 f s m 。这些机器的状态变化表是通过在对应的离散、有界集上进行一致随机变异 来修改。进化规划根据被正确预测的符号数来度量适应值。通过变异，父辈和子 代中最好的那一半被选择生存下来。基于正态分布变异，f o g e l 将进化规划扩展到 解实值问题。1 9 6 6 年，f o g e l 等出版了基于模拟进化的人工智能1 3 】，系统阐述 了进化规划的思想。之后由b u r g i n 、a t m a r i ”咖f o g e l t l 8 1 等人对进化规划进行发 展。1 9 9 2 年，在美国举行了进化规划第一届年会，之后，此会每年举行一次，从 而迅速吸引了大批各行业的研究人员和工程技术人员。 进化策略的思想与进化规划的思想有很多相似之处，但它是在欧洲独立于遗 传算法和进化规划而发展起来的【”】。1 9 6 3 年，德国柏林工业大学的两名学生i r e c h e n b e r g 和hp s c h w e f e l 利用流体工程研究所的风洞做实验时提出了进化策 略。他们在进行风洞实验时，由于设计中描述物体形状的参数难以用传统方法进 行优化，因而利用物体生物变异的思想来随机改变参数值，并获得了较好的结果。 随后他们对这种方法进行了深入的研究，1 9 7 0 年，r e c h e n b e r g 完成了有关进化策 略研究的博士论文并获得博士学位；1 9 7 4 年，s c h w e f e l 把有关进化策略研究的成 果作了归纳整理1 2 0 l ，形成了进化计算的另一分支。后经h e r d y l 2 、k u r s a w e 2 2 1 、 o s t e r m e i e r l 2 3 1 、r u d o l p h “1 、s c h w e f e l t 2 孔等人发展。1 9 9 0 年，在欧洲召开了第一届 “基于自然思想的并行问题求解( p p s n ，p a r a l l e lp r o b l e ms o l v i n gf r o mn a t u r e ) ”国际 会议。此后该会每两年进行一次，成为在欧洲召开的有关进化计算的主要国际会 议。 由于遗传算法、进化规划和进化策略是不同领域的研究人员分别提出的，在 相当长的时期里相互之间没有正式沟通 2 6 11 2 7 。直到1 9 9 0 年，遗传算法才开始与进 化规划和进化策略有所交流；1 9 9 2 年，进化规划和进化策略这两个不同领域的研 究人员首次接触到对方的研究工作，通过深入交流，他们发现彼此在研究中所依 赖的基本思想都是基于生物界的自然遗传和自然选择等生物进化思想，具有惊人 相似之处。于是他们提出将这类方法统称为“进化计算( e c ) ”，而将相应的算法统 称为“进化算法( e v o l u t i o n a r ya l g o r i t h m s ，e a y 【2 8 】。 国内从1 9 9 3 年起，先后有武汉大学、中国科技大学、华中理工大学、东南大 学、上海交大、清华大学、西安交通大学、南京航空航天大学、天津大学、中科 院等高校和科研机构开展了进化计算及其应用研究工作，并取得了不少研究成果1 2 9 3 8 l 。 1 5 进化计算的近期发展与研究趋势 s 东南大学博士学位论文 1 5 1 有关理论基础研究 进化计算产生于2 0 世纪6 0 年代，但真正引起普遍关注和广泛应用则始于2 0 世纪8 0 年代。除2 0 世纪7 0 年代初h o l l a n d 本人对遗传算法提出模式理论， r e c h e n b e r g 及他的学生们对进化策略所作的收敛性分析之外，对进化计算的基础 理论研究基本上无大的进展，较为系统的工作则出现在近十年。进化计算的理论 研究主要集中于对进化计算( 主要是针对遗传算法艘索机理、收敛性、收敛速度、 复杂性、有效性、能解性等基本理论问题的探索，其目的在于从理论上阐明进化 计算的工作原理与性态，从而为进化计算技术的发展、比较与应用提供理论依据。 2 0 世纪7 0 年代到8 0 年代初人们所普遍关注的基础问题是搜索机理，即试图 澄清遗传算法到底是如何有效工作的。这方面代表性的工作是由h o l l a n d 本人所提 出的模式定理，以及由此派生的积木块假设与隐含并行性分析。模式定理，积木 块假设与隐含并行性一起构成遗传算法所谓的模式定理。这一理论长期被接受为 遗传算法的基本理论，特别地，模式定理与积木块假设常被用以解释遗传算法的 搜索机制，而隐含并行性被用以解释遗传算法的有效性。然而，遗憾的是，除模 式定理外，模式理论中的大部分结论都未得到严格的数学证明，而且在一定意义 上也是似是而非的陈述。所以，用以解释遗传算法的搜索机制与有效性，模式理 论难以令人信服( 由此引起的大量有关遗传算法欺骗问题的研究从一个侧面说明了 这一点) 。文献 3 9 1 从遗传算法诸进化算子搜索能力的角度阐述了遗传算法的搜索 机制。有关遗传算法的收敛性研究是过去十年间遗传算法基础研究的核心，已有 一系列重要工作。这些工作依所采用的研究方法与所使用的数学工具可大致分为 四类，即马氏链模型、v o s e - l i e p i n s 模型瑚1 、公理化模型阁与连续( 积分算予) 模 型【4 1 2 j 。马氏链模型是描述遗传算法的最直接和最直观的模型，有表述清晰和精 确的优点。然而由于马氏链理论本身的限制，使用马氏链模型通常只能刻画二迸 制或特殊非二进制遗传算法。v o s e - l i e p i n s 模型是v o s e 和l i e p i n s 所发展的分析标 准遗传算法的一类确定性方法。这类方法的核心思想是用两个确定型矩阵算子分 别描述选择与繁殖操作，而通过研究这两个不动点的存在性与稳定性来刻画相应 g a 的渐近行为。公理化模型的核心是通过公理化描述进化计算中的各种进化算 子，并引进各进化算予的本质特征数( 如选择压、选择强度、进化吸收率、散射率 等) ，而应用进化算子特征数来刻画算法的各种收敛性态。这一方法的最大优点是： 直接和适应性强，能产生直接指导应用的进化参数设置策略，但缺点是对连续型 进化算法，计算相应进化算子特征数比较困难。对于连续编码遗传算法的收敛性 分析，多位作者采用了连续( 积分算子) 模型。例如q i 和p a l m i e r i 通过导出连续g a 在使用比例选择、均匀交叉、选择与变异以及三个遗传算子联合作用等情形，当 种群规模趋于无穷时，种群的概率分布所对应的密度函数应满足的递归公式，而 研究了g a 种群平均适应度的收敛性。使用连续( 积分算子) 模型研究遗传算法通常 6 第一章课题研究的意义及国内外研究现状 需要或对适应度函数、或对种群规模施加限制。p e c k 和d h a w a n l 4 3 】将g a 纳入一般 的全局随机搜索方法框架，而将g a 迭代过程描述作可行解空间上某些抽象分布 的构造与演化，然后运用有关全局随机搜索的已有收敛性理论来研究连续编码遗 传算法的收敛性。 与收敛性分析紧密相关的另一基本理论问题是遗传算法能以多快的速度收 敛。这方面的研究不仅可从另一侧面来阐述g a 的收敛性，而且对于建立合适的 停机准则即恰当的度量标准以全面、客观地评判g a 各种执行策略有重要意义。 然而，到目前为止，有关g a 收敛速度与计算复杂性研究仅有少量且基本限于二 进制情形，或是对特殊的适应度函数，或是对仅使用某一个或两个遗传算子操作 情形的g a ，仍不具有普遍性。 关于遗传算法的有效性与能解性研究，目前尚无完善的理论及定量分析方法。 遗传算法的理论基础研究无疑是当前进化计算研究最倍受关注的热点领域， 它不仅受理论探索自身的促动，而且也是解决进化算法发展与应用诸多瓶颈问题 的关键所在。 1 5 2 有关算法设计方面 算法设计是进化计算的核心，从进化计算的产生到此后长时期内，它一直是 人们所关注的主要方面。该方面的研究始终围绕两个永恒的主题：一是扩大可应 用领域：二是使之更加有效。算法研究主要是从更宏观、更本质的角度模拟自然 进化原理与机制，模拟生物智能的生成过程，并用以求解问题，进而融合数学、 生物、计算机技术等各领域的原理与技巧，使所设计出的进化计算执行策略有预 期性态、有效。 近年来人们特别关注发展对于多目标优化、多态优化与各种组合问题的进化 算法执行策略。基于对种群小生境进化的模拟和采用适应值共享策略，g o l d b e r g 和r i c h a r d s o n 4 们。d e b 和k u m a f 4 5 等发展了一系列有效的多目标优化问题遗传算 法，这些算法己充分显示出较传统多目标优化算法的优越性与有效性。另外，不 限于遗传算法框架，c o l o r i 和d o r i 9 0 1 4 6 1 等人所发展的蚁群算法( a n tc o l o n y o p t i m i s a t i o n ) 也是一类值得注意的求解组合问题的模拟进化算法。针对专门领域发 展进化算法执行策略是进化计算算法设计的又一侧重点与有效途径。h o l l a n d 4 7 1 等 人所发展的分类系统是基于遗传算法的机器学习系统；y a o l 4 s l 等人所发展的进化神 经网络是基于进化计算设计与训练人工神经网络的自适应系统；d o r i g o 【4 9 1 等人所 发展的进化机器人则是进化计算与机器人学相互结合的产物。所有这些系统都可 以认为是自适应机器学习系统，而进化计算是这些自适应学习系统中搜索、调整 结构的核心技术。 有关进化计算执行策略的进一步研究，可以从以下几方面进一步展开：1 ) 综 7 东南大学博士学位论文 合运用各种领域的各种技巧( 如融合其它领域知识、专家知识、采用自适应操作、 并行算法等) ，提高现有进化计算的计算效率：2 ) 结合神经网络、模糊理论、人 工生命、免疫系统等相关领域知识深化进化计算执行策略；3 ) 将各种进化计算执 行策略与相关算法进行比较研究，进而澄清进化计算的能解性与难易度。 1 5 3 有关进化计算的应用 进化计算提供了一种求解复杂、困难优化问题的通用框架，它不依赖于问题 的具体领域，不要求目标函数有明确的解析表达，对问题的种类有很强的鲁棒性， 已成功地应用于如下领域： 1 ) 多目标规划、多态优化等函数优化问题。函数优化是进化计算的经典应用 领域，也是对进化计算进行性能测试的常用算例。除e s 主要应用于函数优化问题 外，g a 和e p 也常应用于离散函数、随机函数、非凸函数等复杂函数的优化，而 且已显示出较古典方法优越得多的本质优点。 2 ) 组合优化问题。随着问题规模的增大，组合优化问题的搜索空间也急剧扩 大，有时在目前的计算机上用传统的枚举法很难甚至不可能求出其精确最优解， 而实践证明g a 对于大部分组合优化问题( 如旅行商问题、背包问题、装箱问题等) 都十分有效，是求解这类问题满意解的最佳工具之一。 3 ) 信号处理。进化计算在i i r 自适应滤波器设计、f i r 数字滤波器设计、非 线性校正、噪声控制、语音信号处理中得到了很好的应用。 4 ) 自动控制。在自动控制领域有很多与优化相关的问题需要求解，这些优化 问题通常要么是通过积分表达的，要么是写不出明确而严格的解析表达式，进化 计算在求解这类自动控制问题方面己显示出其独特优点。例如用g a 设计模糊控 制器。 5 ) 机器人学。机器人是一类复杂的难以精确建模的人工系统，而进化计算来 自于对人工自适应系统的研究，所以机器入学自然也是进化计算的一个重要应用 领域。例如，进化计算已在机器人的运动轨道设计等方面取得成功应用。 6 ) 人工神经网络。进化计算在人工神经网络的应用可分为支持性与协作性两 大类。进化计算对神经网络的支持性表现在：利用进化算法为神经网络分类器选 择特征矢量或对特征矢量进行空间变换，使变换后的特征矢量更为适合神经网络 分类器；用进化算法选择神经网络的学习规则与学习算法参数，如学习速率，动 量系数等；利用进化算法分析神经网络的性能。 7 ) 机器学习。学习能力是高级自适应系统所应具备的特征之。基于g a 的 机器学习在很多方面都得到成功应用。 8 ) 人工生命。人工生命是用计算机、机械等人工媒体模拟或构造出具有自然 生物系统特有行为的人造系统。人工生命与g a 有密切的关系，基于g a 的进化模 第一章课题研究的意义及国内外研究现状 型是研究人工生命现象的重要基础，虽然人工生命的研究尚处于初级阶段，但g a 已在其中的进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的 应用能力，并且必将得到更为深入的应用和发展。 1 6 进化计算应用于计量测试技术的意义 计量测试技术是机械工业发展的基础和先决条件，机械加工精度的提高总是 与测量技术的发展水平紧密相关，测量的精度和效率在一定程度上决定着科学技 术的水平。随着科学技术的不断进步，在机械、仪表等制造业中，人们对加工和 装配的精度要求越来越高，而机械零件几何要素的形状精度是零件的主要质量指 标之一，在很大程度上影响着整台机器或仪器的质量，因此正确地检测和评定形 状误差对保证零件和产品的质量和互换性具有重大的意义。i s 0 1 1 0 l i ”】和 g b t 1 1 8 2 1 9 9 6 t ”】规定：形状误差的评定应符合最小区域法即最小条件，并以此为 仲裁方法。为此近年来国内外许多学者一直致力于最小区域法评定形状误差的研 究，先后出现许多新的算法。但因这些算法无法对各种形状误差以及同一种误差 不同的测点形式寻找出统一的误差表达式，导致算法太烦琐、不易在计算机上实 现或因运算时间太长，不能很好满足诸如三坐标测量机等新型测量设备对计算软 件的需要，为此目前的三坐标测量机在对形状误差检测时，其评定结果依然根据 最小二乘法计算求得【咒 】，但最小二乘法提供的仅是形状误差的近似评定结果， 并不保证解的最小区域性，因而不适宜于精密、超精密零件评定。而在当今的机 械、仪表等制造业中，人们对加工和装配的精度要求越来越高，这就要求有精密 的计量技术与之相适应，三坐标测量机、轮廓机和粗糙度测量机等许多新型测量 设备的出现，使得测量数据坐标化，为满足高速测量的要求，这些新型测量设备 都需要配备相应的计算软件，而以往的图解法、逐次搜索迭代法已不适应新的发 展要求，因此为了很好地满足新型测量设备对应用软件的要求，迫切需要研究一 种简单、快速、鲁棒性强而计算精度高的统一评定算法。进化计算作为一种新的 全局优化搜索算法，以其简单通用、鲁棒性强、适应并行处理以及应用范围广等 显著特点，奠定了它作为二十一世纪关键智能计算之一的地位，为我们建立计算 精度高、速度快、便于在三坐标测量机等新型设备上推广使用的形状误差统一评 定算法提供可能。 近年来，非线性理论中的混沌信号处理为人们提供了分析自然现象的全新方 法。混沌信号兼有确定性信号和随机过程的特性，它一般具有不规则的波形。人 们发现，自然界中的大量现象如气候变化、地震发生、太阳黑子、人脑电波、股 票行情和社会发展等都是混沌的，或近似混沌的。因而能否根据混沌系统提取的 非线性时间序列对系统的未来进行预测，意义重大。 由于混沌时间序列在内部有着确定的规律性，这种规律性产生于非线性，它表 9 东南大学博士学位论文 现出时间序列在时间延迟状态空间中的相关性，这种特性使得系统似乎有着某种 记忆能力，同时又难于用通常的解析方法把这种规律表达出来。而这种信息处理 方式正好是神经网络所具备的，即可以通过人工神经网络来学习混沌时间序列， 然后进行预测和控制。但是传统的神经网络学习方法多是基于梯度下降法的优化 算法，不可避免地会存在局部极小问题。而进化算法及其新近发展的免疫算法能 够克服传统神经网络的不足，因此研究新的智能优化算法以实现对神经网络快速、 高效训练，进而实现对混沌信号理想预测，具有重要的实际意义。 1 7 本课题研究的主要内容和所要解决的问题 尽管进化计算的理论和应用研究已取得了许多进展，但是尚存在下述关键问 题亟待解决： 1 ) 现有有关遗传算法的理论分析多是在离散空间针对标准遗传算法进行的， 而许多工程问题都需要在实空问求解，因此有必要对连续解空间遗传算法的理论 及执行策略进行分析研究。 2 ) 由于进化计算的应用越来越广泛，应用对象日趋复杂，因此目前新的进化 算子不断涌现，而如何针对具体问题对进化算子进行高效、合理地选择，这对解 决工程实际问题至关重要，其前提是如何定量评价进化算法的效率，为此有必要 研究进化算法效率的定量评价方法。 3 ) 形状误差的大小对产品质量及其使用寿命至关重要，实现形状误差快速、 准确的评定，具有重要的实际意义。形状误差的评定应符合最小区域法，并以此 为仲裁方法。但是因为现有的最小区域评定算法不能很好满足诸如三坐标测量机 等新型测量设备对计算软件的需要，导致目前的三坐标测量机只能给出形状误差 的最小二乘评定结果，使得产品可能因过估计而出现误废，直接影响产品的质量 和成本，因此研究进化计算在形状误差评定中的应用，以寻求一种简单、快速、 鲁棒性强且适易于在新型测量设备上推广使用的最小区域统一评定算法意义重 大。 4 ) 生