（计算数学专业论文）人工智能算法在nurbs曲线降阶方面的若干研究.pdf

人工智能算法在n u r b s 曲线降阶方面的若干研究 摘要 曲线的降阶一直是c a g d 中的研究热点之一，目前对它的降阶逼近研究 主要是对b 6 z i e r 曲线的降阶逼近，而且形成了相对而言比较成熟的理论和方法。 n u r b s 曲线不仅能表达一般的b 样条和b 6 z i e r 曲线，还能精确描述二次曲线， 并且是定义工业产品几何形状的唯一数学方法。因此n u r b s 曲线的降阶问题 不仅有着重要的理论价值，而且有着迫切的应用需求。 本文将人工智能算法同曲线降阶结合，研究了人工智能算法在n u r b s 曲 线的降阶问题方面的应用。首先介绍了人工智能中一些常见的算法，随后介绍 了n u r b s 曲线降阶的几种方法：( 1 ) 利用曲线的显式矩阵表示和多项式最佳一 致逼近理论的方法。( 2 ) 利用遗传算法进行降阶的方法。其次基于微粒群算法， 给出了一个n u r b s 曲线降阶的一个新的方法。最后给出算法的一个实例，验 证了算法的可行性。 关键字：n u r b s 曲线；降阶逼近；人工智能算法 r e s e a r c ho nt h ea r t i f i c i a li n t e l l i g e n c ea l g o r i t h mf o rd e g r e e r e d u c t i o no fn u r b sc u r v e s a b s t r a c t d e g r e er e d u c t i o no fc u r v e sh a sb e e no n eo f t h er e s e a r c hh o t s p o t si nc a g d c u r r e n t l yt h es t u d yi sm a i n l ya b o u tt h ed e g r e er e d u c t i o na p p r o x i m a t i o no fb 6 z i e r c u r v e s a n di tf o r m e das e to fm a t u r et h e o r i e sa n dm e t h o d s n u r b sc u r v e sc a nn o t o n l ye x p r e s sg e n e r a lb s p l i n e c u r v e sa n db 6 z i e rc u r v e s ，b u ta l s oa c c u r a t e l y d e s c r i b et h eq u a d r a t i cc u r v e s a n dn u r b si st h eo n l ym a t h e m a t i c a lm e t h o do f d e f i n i n gt h eg e o m e t r yo fi n d u s t r i a lp r o d u c t s s ot h ed e g r e er e d u c t i o no fn u r b s c u r v e sh a si m p o r t a n tt h e o r e t i c a lv a l u ea n di m m e d i a t ed e m a n do fa p p l i c a t i o n t h i st h e s i ss t u d i e sh o wt ou s ea r t i f i c i a li n t e l l i g e n c ea l g o r i t h m st os o l v et h e p r o b l e mo fd e g r e er e d u c t i o nc o m b i n i n ga r t i f i c i a li n t e l l i g e n c ea l g o r i t h m sw i t ht h e d e g r e er e d u c t i o no f c u r v e s f i r s t l y ，s o m ec o m m o na r t i f i c i a li n t e l l i g e n c ea l g o r i t h m sa r ei n t r o d u c e d ，a n d t h ed e g r e er e d u c t i o no fn u r b s c u r v e si sd e s c r i b e di ns e v e r a lw a y s ：( 1 ) t h em e t h o d o fu s i n gc u r v e si ne x p l i c i tm a t r i xp r e s e n t a t i o na n dt h et h e o r yo f t h eb e s tp o l y n o m i a l c o n s e n s u sa p p r o a c h ( 2 ) t h em e t h o do fd e g r e er e d u c t i o no fn u r b s c u r v e sb a s e do n g e n e t i ca l g o r i t h m s e c o n d l y ，b a s e do np a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ，t h i st h e s i sg i v e s an e wm e t h o do ft h ed e g r e er e d u c t i o no fn u r b s c u r v e s f i n a l l y ，a ne x a m p l ei sg i v e n t ov e r i f yt h ef e a s i b i l i t yo ft h ea l g o r i t h m k e y w o r d s ：n u r b sc u r v e s ；d e g r e er e d u c t i o na p p r o x i m a t i o n ；a r t i f i c i a li n t e l l i g e n c e a l g o r i t h m 图表目录 图4 1对一段n u r b s 曲线降一阶2 5 图4 2对一段n u r b s 曲线降两阶2 5 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得 金8 巴工些太堂或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 签字日期尸7 。年铲月叫日 学位论文版权使用授权书 本学位论文作者完全了解金g 墨王些太堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金 壁兰些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：户f 护，乍纠 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 牦力五 签字吼厶。舀。问l 日 电话： 邮编： 致谢 随着本次毕业设计的接近尾声，近三年的研究生生活也即将结束。回首既 往，自己一生宝贵的时光能于这样的校园之中，能在众多学富五车、才华横溢 的老师们的熏陶下度过，实是荣幸之极。在这三年的时间里，我在学习上和思 想上都受益非浅。这与各位老师、同学和朋友的关心、支持和鼓励是分不开的。 首先要感谢我的恩师檀结庆老师，感谢檀老师的辛勤栽培、孜孜教诲。檀 老师有着渊博的知识，深厚的学术功底。檀老师虽然工作繁忙，但仍抽出许多 时间给予我学术上的指导和帮助。无论是平常的上课，还是毕业论文的指导， 檀老师对我的学习都倾注了极大的心血，使得我能够顺利的完成学业。在平常 的生活当中，檀老师也教授了我们许多做人和处事的道理，这将是我一生中又 一笔无比宝贵的财富。檀老师对学生认真负责的态度、严谨的科学研究方法、 敏锐的学术洞察力、勤勉的工作作风以及勇于创新、勇于开拓的精神，是我永 远学习的榜样。在此，谨向檀老师致以深深的敬意和由衷的感谢。 还要感谢朱功勤教授、林京教授、唐烁教授、邬弘毅教授、苏化明教授、 黄有度教授、朱晓临教授、王寿城副教授、郭清伟副教授和江平副教授，各位 老师在我学习和生活中也给与了无比的关心，他们渊博的知识和高尚的师德都 给我留下了深刻的印象! 衷心的感谢各位老师。 感谢计算数学专业的全体同学，在三年的时间里，大家一起学习，共同进 步，共同成长，留下了美好的回忆。 作者：潘瑛 2 0 10 年3 月 1 1 曲线降阶问题的背景 第一章绪论 计算机辅助几何设计( 简称c a g d ) ，是涉及数学及计算机科学的一门新兴 的边缘学科，它随着造船、航空、机械设计和制造等工业的发展而逐渐发展起 来，形成了数学的一个重要的分支，它所研究的内容是“在计算机图像系统曲 面的表示和逼近”，、是一门理论联系实际、抽象思维与形象思维相结合的非常重 要的工程基础课程，具有很强的理论性和实践性【l j 。 c o o n s 、b 4 z i e r 早在2 0 世纪6 0 年代就奠定了c a g d 的理论基础，随着图 形工业和制造工业迈向一体化、信息化和网络化步伐的日益加快，c a g d 与数 学中的拓扑学、函数逼近论、代数几何、微分几何、微分方程、最优化、数值 分析和矩阵论联系紧密，并与一些应用性学科知识如数据结构、机械设计与加 工制造、外型检测、计算机图形学、程序语言、三维医学影像学、几何造型、人 体解剖学等交叉渗透【2 j ，随着c a g d 理论的不断发展，它的应用范围也得到了 突飞猛进，从飞机、 船舶、 汽车设计、到工程器件模具设计、到生物医学 图像处理等都有着c a g d 的广泛应用。 随着几何造型系统的不断涌现、跨国公司在全球的遍立和因特网的普及， 异地设计、异地加工已经成为机械和工艺品生产中的常规行为，由此产生出一 种明显的效应，就是各种c a d c a m 系统之间几何描述信息的数据交换、数据 共享或数据集成化曰益频繁，不同的c a d c a m 系统中表示曲线曲面的基函数 的最高次数有不同的限制范围和要求，而且在实际中许多c a d c a m 系统考虑 到有效性，往往只限于处理低次，因而为了实现不同次数的曲线曲线曲面的数 据转换或数据集成，必须对高次几何对象进行降阶，此外，在曲线曲面的方程 推导和设计计算中也经常用到降阶变化，这样，降阶算法的理论研究成了当前 的热点之一【3 1 。 目前作为c a d c a g d 的研究热点之一的曲线的降阶逼近研究，主要是对 b 4 z i e r 曲线的降阶逼近，而且形成了相对而言比较成熟的理论和方法【4 】，早在 19 7 2 年，f o r r e s t i5 】就对b 6 z i e r 曲线的降阶做过研究，取得了一定的成果，但是 他对降阶算法的研究只考虑了升阶算法的逆问题，误差较大。到了8 0 年代， f a r i n 等 6 - 1 2 】从各个方面对该问题进行了探讨，但提出的算法和f o r r e s t 的类似。 国内学者也对该问题进行了探讨，取得了一些成果：19 9 6 年，胡事明等从b 4 z l e r 曲线的退化条件出发，提出基于控制定点扰动的约束优化方法，实现b 4 z i e r 曲 线的降阶，并将这种方法推广解决其他曲线曲面的降阶问题。康宝生【挖】等利用 b 4 z i e r 曲线的几何性质和升阶公式，基于人工智能中的遗传算法，给出了有理 b 6 z i e r 曲线降阶的新算法1 5 j 。 1 2n u r b s 曲线的历史背景、特点以及研究现状 b 6 z i e r 曲线设计在工程上应用较多，人们可以方便地用b 6 z i e r 曲线的设计 方法勾画出基本形状，并通过逐步调整顶点满足设计要求，虽然使用方便，但 也存在着缺点，因为b 6 z i e r 曲线是整体定义的，它不具备局部修改性。假如改 变其中一个控制顶点的位置，曲线的形状都要受到影响。19 6 4 年，s c h o e n b e r g 提出了b 样条理论，g o r d o n 和r i e s e n f e l d 又把b 样条理论应用在形状描述上， 最终提出了b 样条方法，该方法具有表示与设计自由行曲线曲面的强大功能。 b 样条技术在自由曲线、曲面的表示和设计方面显示出了它卓越的优点， 但是在表示初等曲面时却不像自由曲线曲面那样轻松自如，传统的b 样条技术 对除了抛物线、抛物面之外的二次曲线、曲面不能精确表示，只能近似表示【1 3 l 。 非均匀有理b 样条技术在这样的需求背景下应运而生。 早在2 0 世纪7 0 年代，v e r s p r i l l e 在其博士学位论文中提出了n u r b s 这样 的一个描述，接着，美国波音公司、结构动力研究公司等对n u r b s 进行了深 入的理论研究和应用开发工作，1 9 9 1 年，国际标准化组织( i s o ) 颁布的工业 产品数据交换标准s t e p 中，定义n u r b s 作为工业产品几何形状的唯一数学 方法。19 9 2 年，国际标准化组织又将n u r b s 纳入到规定独立于设备的交互图 形编程接口的国际标准p h i g s ( 程序员层次交互图形系统) 中，作为p h i g sp l u s 的扩充部分。目前，b 6 z i e r 、有理b 6 z i e r 、均匀b 样条和非均匀b 样条都被统 一到n u r b s 中【13 1 。 现在，n u r b s 被迅速接受并被采用做为几何造型系统内部的主要表示形 式标准，这是因为n u r b s 有它自身的优点： 1 ) n u r b s 技术可以精确表示规则曲线和曲面，比如圆弧、椭圆弧、圆锥面等。 而其他的b 6 z i e r ，非有理b 样条技术无法做到这一点。 2 ) n u r b s 技术把规则曲面和自由曲面统一起来。 3 ) n u r b s 技术是非有理b 6 z i e r 和b 样条形式的真正推广。 4 ) n u r b s 技术增加了权因子，有利于曲线曲面形状的修改和控制。 1 3 微粒群算法的背景及简介 介绍本文中使用的微粒群算法，就要先介绍最优化问题，最优化问题指的 是在满足一定的约束条件下，从问题的解的所有可能方案中寻找一组方案，这 组方案使问题的某些性能指标达到最大或最小，满足某些最优性度量。最优化 问题随着计算机的广泛应用与发展而变得非常重要，它在工程设计、经济研究、 社会管理等各个领域有着广泛的应用l l 引。 根据其目标函数、约束函数的性质以及优化变量的取值等变量，最优化问 题可以分成许多类型，类型不同，所对应的最优化问题的求解方法就不同。最 优化问题有线性规划问题、非线性规划问题，非线性规划问题又包括约束优化 和无约束优化问题。针对最优化问题中的多种类型，下面介绍几种优化方法。 局部优化方法是目前常见的优化方法【l 引，它是指在给定的范围内从一个初 始点出发，依据一定的方法寻找下一个使得目标函数得到改善的更好解，直至 满足某种停止准则。局部优化方法的求解结果与初始值有关，像我们知道的共 轭梯度法、n e w t o n r a p h s o n 法等等。当目标函数为凸函数、约束域为凸域时， 局部最优与全局最优等效，这样的问题就是常说的凸规划问题。而对于非凸问 题，它的全局最优与局部最优相差甚远，因为在约束域内，非凸问题目标函数 存在多峰值【i 引。迄今为止，全局优化问题已经存在了许多算法，比如填充函数 法等，但相比具有众多成熟方法的局部优化问题，全局优化和局部优化之间还 有很大差距。 针对全局优化的不足，为了可靠地解决全局优化问题，人们开始研究对函 数的解析性质不确定或者对它不做要求的优化算法，这类算法是随机性的。这 类随机性优化算法中最早的是针对具体的问题的特点，用m o n t e c a r l o 方法的 思想，构造一个以概率l 收敛于全局最小点的随机搜索算法。仿生型智能优化 算法是近十多年来人们通过模拟自然界的自然现象丽形成的随机全局优化方 法，它具有而且只有它有普遍的适应性，常见的智能优化算法有模拟退火方法、 进化类算法、群体智能算法等等。 对群体智能算法的研究始于2 0 世纪9 0 年代初，它的基本思想是模拟自然 界生物的群体形为来构造随机优化算法。典型的方法有m d o r i g o 提出的蚁群算 法和j k e n n e d y 与r e b e r t h a r t 提出的微粒群算法。 微粒群算法，又称粒子群算法，由美国社会心理学家j a m e sk e n n e d y 和电 气工程师r u s s e l le b e r h a r t 在19 9 5 年共同提出，它的基本思想是受他们早期对 鸟类群体行为研究结果的启发，并利用了生物学家f r a n kh e p p n e r 的生物群体 模型f 14 1 。 在进化算法的遗传算法、群体智能算法中的蚁群算法之后，人们又提出了 一个新的群体智能算法：微粒群算法，由于算法具有计算快速、容易实现的性 质，在国际上相关领域已经引起了众多学者的关注和研究，目前己成为进化算 法的一个重要分支。现在大家在微粒群算法上所做的主要工作分为：将微粒群 算法应用到别的领域中、对算法进行分析以及为了更好地应用算法而改进算法。 1 4 本文所做工作的概述 本文主要结合人工智能中的算法研究了n u r b s 曲线的降阶逼近问题。 第一章介绍了曲线降阶问题的研究意义和应用背景，综述了n u r b s 曲线 的历史背景和特点，引出本文的研究课题。 第二章给出了本文采用的微粒群算法的预备知识，即一些常见的人工智 能算法：进化计算、基本微粒群算法、微粒群算法的算法分析以 及它的改进算法。 第三章介绍了n u r b s 曲线的基本知识。首先介绍了b 样条曲线的定义以 及分类，在这个基础上，给出n u r b s 曲线的几种等价表示以及 n u r b s 曲线的几何性质 第四章首先介绍了几种曲线降阶的方法，其次在前人工作的基础上，本 文结合微粒群算法提出了n u r b s 曲线降阶的一种新方法，最后给 出了该方法的应用实例，验证了方法是可行的，并且达到了很好 的效果。 第五章对本文工作的一个小结。 4 2 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 ) 是种新颖的模拟进化的计 算理论，一般认为，进化计算包括三个组成部分【15 , 1 6 ：( 1 ) 由美国密歇根大学 j o j n h h o l l a n d 教授提出的遗传算法1 1 7 ，18 1 ，( 2 ) 由美国科学家l a w r e n c e j f o g e l 等人提出的进化规划【1 9 ，20 ，( 3 ) 由德国科学家i n g or e c h e n b e r g 和h a n s p a u l s c h w e f e l 提出的进化策略【zu 2 1 】。由于这些进化类算法在理论和应用两方面发展 迅速、效果显著，并逐渐走向了融合，进化计算逐渐形成。对进化计算的具体 的实现方法和形式称为进化算法( e v o l u t i o n a r ya l g o r i t h m ，e a ) ，进化算法是一 种受生物进化论和遗传学等理论启发而形成的求解优化问题的随机算法，它是 模拟生物进化过程中“优胜劣汰的自然选择机制和遗传信息的传递规律的算 法的总称【1 4 , 2 2 1 。爬山方法，模拟退火方法等是启发式的搜索方法，它同基于导 数的解析方法一样都是迭代的方法，进化算法也不例外，它在形式上也是一种 迭代方法。进化算法是这样的：按照一定方法选取初始解，通过不断的迭代来 逐步改进当前解，直到最后搜索到最优解。在进化计算中，迭代计算过程采用 了模拟生物体的进化机制，从一组解( 群体) 出发，采用类似于自然选择和有 性繁殖的方式，在继承原有优良基因的基础上，生成具有更好性能指标的下一 代解的群体拉川。 一般来说，采用进化算法求解优化问题的过程的步骤如下： 1 ) 随机给定一组初始解； 2 1 根据适应度函数评价当前这组解的性能； 3 ) 根据2 ) 的评价结果，从当前解中选择一定数量的解作为操作的对象； 4 ) 对所选择的解进行操作，得到一组新的解； 5 ) 返回到2 ) ，对该组新的解进行评价； 6 ) 若当前解满足要求或进化过程达到一定的代数，计算结束；否则转向3 ) 继续 进行。 进化算法与其他搜索技术相比，有以下特点【i5 , 2 0 , 2 4 , 2 5 】： 1 ) 进化算法的搜索过程是从一组初始点开始搜索，而不是从一个初始点开 始，在这样的搜索机制下，搜索过程可以有效地跳出局部极值点。 2 ) 在搜索过程中，进化算法使用的是基于目标函数值的评价信息，而不是 像传统方法那样采用的目标函数的导数信息或待求解问题领域内知识。进化算法 的这个特点使它具有良好普适性和可规模化。 3 形式简单，便于计算。 4 ) 进化算法的鲁棒性很强。 5 5 ) 进化算法具有很好的隐式并行性。 上述进化算法的几个分支是由不同的学者独立提出的，它们各自代表了进 化计算的不同侧面，各具特点。由于进化计算的这些分支，它在很多领域中发 挥出了重要的作用，比如人工智能、模式识别、图象处理、决策分析、产品工 艺设计、知识发现、生产调度、科学研究等等【2 6 1 。 2 1 1 遗传算法 对遗传算法( g e n e t i ca l g o r i t h m ，g a ) 的研究始于2 0 世纪6 0 年代，跟其他智 能算法一样，它也是通过模拟自然进化过程来搜索最优解。它既是一种自然进 化系统的计算模型，也是一种通用的求解优化问题的适应性搜索方法【2 3 1 。经过 几十年的发展，遗传算法在理论研究和实际应用方面取得了丰硕的成果和进展， 特别是随着近年来世界范围内形成的进化计算热潮，智能计算以及人工生命研 究的兴起，遗传算法受到了广泛的关注与发展。 2 1 1 1 遗传算法的基本理论 我们都知道：自然世界中，生物的进化过程是从简单到复杂，从低级到高 级的，进化本身就是一个自然的、并行发生的、稳健的优化过程，而优化是为 了让生物种群对环境具有更好的适应性。生物物种通过“优胜劣汰”的自然规 则和遗传变异来实现进化。遗传算法的核心思想就是在上述的基本认识上产生 的。按照d a r w i n 的自然选择与m e n d e l 的遗传变异理论，生物进化通过四种基 本形式来实现进化的过程，这四种基本形式是繁殖、变异、竞争和选择【2 3 1 。基 于这种思想，把待解决的问题描述为对某个目标函数的全局优化，遗传算法求 解问题的基本方法是：从当前种群出发，将待优化的目标函数解释为生物种群 对环境的适应性，生物个体对应于优化变量，利用选择、复制、杂交和变异操 作来生成新的种群。重复这个过程，直到出现满足要求的种群或者达到了规定 的进化限制。 在遗传算法中，通常把待优化的问题看做是某个适应值的极大化，把原问 题变量的某个有限长离散编码称为个体，常见的是，遗传算法不对原优化的变 量进行操作，而是对个体。所有个体组成的集合称为个体空间，母体通常是指 一对个体。全体母体组成的集合称为母体空间。比如在迭代过程中，种群的规 模有一半是固定的，设这一半规模的个体为，则任意个个体组成的集合就 是一个种群。 遗传算子决定了遗传算法的具体迭代过程，也就是由当前种群生成新一代 种群的方法。遗传算法利用一系列遗传算子实现种群的优化，常见的遗传算子 有选择、交叉和变异等。 选择是指按照一定的准则或者概率分布从当前的种群中选择使得目标函数 6 适应值好的个体，然后组成新的个体，选择算子是种群空间到母体空间的随机 映射。目前，最常用的选择算子有适应值比例选择、排序选择、联赛选择以及 r a n k i n g b a s e d 选择等。 遗传交叉算子是对自然界中有性繁殖进行模仿的基因重组过程，与选择算 子不同，它是母体空间到个体空间的随机映射，意即生成新的个体，新个体遗 传了母体的优良基因，并且具有更复杂的基因结构。一般来说，交叉操作的作 用方式是：从交配池中随机取出要交叉的一对个体，对这对个体，随机确定一 个或多个分量位置做为交叉位置，再根据交叉概率p ，实行相互交换，生成新的 一对个体。依据交叉点个数的多少，交叉算子分为单点交叉、两点交叉、多点 交叉和均匀交叉等，其中，均匀交叉是多点交叉的极限形式。 变异算子是个体空间到个体空间的随机映射，在遗传算法中，变异是指按 照变异概率p 。随机改变个体的每个基因的取值来产生新的个体。由于变异概率 小，可能会造成资源的浪费，因此我们在遗传算法的应用中，采取一些措施来 防止资源的浪费，通常首先判断个体变异的概率，然后再进行基因的变异操作 2 3 1 o 我们用z ( f ) 表示第f 代种群的第f 个个体，标准遗传算法的迭代过程的步骤 如下【2 7 】： 1 ) ：取k = o ，初始种群表示为x ( o ) = x l ( o ) ，x2 ( 0 ) ，x ( o ) ) ，初始种群的产生是 随机的。 2 ) ：随机地从当前种群中选取对父代个体； 3 ) ：对所选对母体随机地实施杂交操作，产生个中间个体； 4 ) ：对个中间个体进行变异操作，生成( k + 1 ) 代种群 x ( k + 1 ) = x l ( 后+ 1 ) ，x2 ( 七+ 1 ) ，x ( 尼+ 1 ) ) ； 5 ) ：计算k + 1 代种群的适应值。 6 ) ：当k + l 代种群中的个体具有更好的适应值或者达到了一定的进化代数时， 我们停止操作，否则k = k + 1 ，并返回到2 ) 。 从以上描述可以看出，遗传算法的搜索方法是由它自己的种群提供个体， 而不由某一个方向或者性质来决定它的搜索范围，这一点与通常的优化方法不 一样，因此遗传算法采用的是一种自适应的随机搜索，并且，在初始种群时， 算法提供了多个个体，这些个体经过遗传变异操作后均可能是问题的可能解， 这样遗传算法就扩大了搜索空间，并缩短了搜索时间，以利于算法在更短的时 间内以更大的可能搜索到全局最优解，提高了算法的有效性。 2 1 1 2 遗传算法的性能 前面介绍了遗传算法在很多方面都有应用，它的较好的性能如下 1 6 ，1 8 ，2 4 ，2 8 ，2 9 ，3 0 ，3 1 1 ： 7 1 ) 遗传算法在求解问题时首先要对个体进行编码，它直接处理参数的编码集而 不是问题参数本身，搜索过程既不受优化函数连续性的约束，也没有要求优 化函数的导数必须存在。 2 ) 如果遗传算法在每一代对群体规模为疗的个体进行操作，那么它的复杂度为 o ( n 3 ) ，具有很高的并行性，搜索效率显著。 3 ) 在所求解问题为非连续、多峰以及有噪声的情况下，能够极大可能地收敛到 最优解或满意解，因而具有较好的全局最优解求解能力。 4 ) 具有较好的普适性，容易扩充。 5 ) 基本思想和理论简单，运行方式和实现的步骤规范，便于具体使用。 2 1 2 进化策略 进化策略是进化算法的最主要的算法之一，它是由德国柏林工业大学的 i r e c h e n b e r g 和h ，p s c h w e f e l 在2 0 世纪6 0 年代初提出的，具有较强的搜索能 力，并且搜索速度快。进化策略采用了自适应机制，具有隐含的并行性和群体 全局搜索的特点。进化策略的主要的迭代的步骤跟遗传算法相同，不同的地方 是：遗传算法要对个体进行编码，将个体空间映射到位串空间上，之后再在位 串空间上进行遗传操作，强调个体基因结构变化对个体的适应值的影响，而进 化策略的作用空间直接是个体空间，它侧重于父代到子代行为的自适应性和多 样性。 进化策略分为( 1 + 1 ) 进化策略、( + 1 ) 进化策略、( + 兄) 进化策略和( ，兄) 进 化策略几种形式。( 1 + 1 ) 策略是指在早期的进化策略的群体中只包含一个个体且 只使用变异操作，具体是在每一操作代中，变异后的个体与它的父代个体进行 比较，从中选择优秀的作为新一代个体，使用的变异算子主要是基于正态分布 的变异操作【弱j 。 因为( 1 + 1 ) 策略难以收敛到最优解，搜索效率相对而言是比较低的。对它的 改进的方法就是增加种群内个体的数量，这就演变成了后来的( - i - 1 ) 策略，它 的具体操作是：首先是计算群体内的个个体的适应值，比较它们的优劣，然 后随机抽取一个个体进行变异，形成新的个体，计算其适应值，用它来取代群 体中最差的个体。 在不断的摸索过程中，为了进一步提高搜索效率，人们后来又提出了( - i - 五) 进化策略和( ，五) 进化策略。( + 五) 进化策略是对种群内的个个体进行变异和 重组操作产生五个个体，然后将这+ 五个个体进行比较，从中选择个最优的 个体；而( ，允) 进化策略则是在新产生的五( ) 个个体中比较选择个最优者 【2 3 1 。 8 2 1 3 进化规划 进化规划方法是2 0 世纪6 0 年代由美国科学家l a w r e n c ej f o g e l 等人提出 的。与别的进化算法不同的是，它不对个体进行二进制编码，而是采用实数编 码，操作仅仅有变异和选择，没有交叉重组算子，这是它的优点，同时也是不 好的一点，因为这样容易陷入局部极值。在求解连续参数优化问题时，进化规 划同进化策略的区别很小。与进化策略的变异算子类似，进化规划的变异算子 也是采用基于正态分布的变异操作对父代个体进行变异，然后生成相同数量的 子代个体。进化规划采用随机一竞争选择的方式，从父代和子代的并集中选择 出2 个个体构成下一代群体。它的选择过程是这样的：由父代个体和子代个体 组成了2 的临时群体，对这个群体中的每一个个体，在临时群体中随机地以 相等的概率选出q 个个体与它进行比较，在每次比较中，如果该个体比与它比 较的个体优越，那么该个体就获得了一次胜利。从2 2 个个体中选择出获胜次 数最多的个个体作为新一代群体。 2 2 基本微粒群算法 微粒群优化算法( p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ，p s o ) 是由 k e n n e d y 和e b e r h a r t 于1 9 9 5 年提出的一种新的进化计算算法【3 2 】，近年来发展迅 速，形成了学术界一个新的研究热点【3 3 1 。 微粒群算法也是一种基于迭代的优化算法，每个优化问题的潜在解都是搜 索空间中的一只鸟，称之为“粒子 【3 4 】。所有的粒子都有一个由被优化的函数 决定的适应值，每个粒子还有一个速度决定它们飞翔的方向和距离，然后粒子们 就追随当前的最优粒子在解空间中搜索。 微粒群算法很好地采用简单速度一位移模型，概念简明，设置的参数少，并且 在搜索过程中，它能根据当前的搜索情况动态调整搜索的方法，搜索效果好，因 此对解决复杂环境中的优化问题非常有效。 微粒群算法是这样的：在算法中，设一个微粒群中有m 个微粒，其中 置= ( 。，誓：，薯d ) 表示第i 个微粒的位置( d 为维数) ，它是待求优化问题的一个 潜在的可能解；微粒f 所经历的最优位置( 即具有最好的适应值) 表示为 鼻= ( p ，b ：，只d ) ；气= ( 以。，熙：，如) 表示群体中所有微粒经历过的最优位置； = ( 。，v ：，v d ) 表示微粒f 的飞行速度，对于每一代，每个微粒在其第d 维 ( 1 d d ) 根据下列方程更新【m 1 ： v _ a ( t + 1 ) = c o v i d ( t ) + q r a n d ( ) ( p j d x i d ( t ) ) + c 2 r a n d o ( p 州一硝( ，) ) ( 2 1 ) 一d ( f + 1 ) = x 。，( f ) + v j f ( f + 1 ) ( 2 2 ) 其中 0 9 为惯性权重， c ，、c ：为加速常数，r a n d ( ) 、r a n d ( ) 为两个在 0 ，l 】范 9 围内独立均匀分布的随机函数。 此外，微粒的速度v 还有一个最大速度v m 。，如果在算法中对微粒的加速会 导致它在某一维的速度v 耐超过该维的最大速度v m 删，那么该维的速度就被限制 为该维的最大速度删，也就是说微粒的速度要受到最大速度的限制。 通过将当前位置向量与更新后的速度向量进行叠加，微粒实现自身位置的 调整，这种叠加运算是一种数值关系的叠加。微粒的运动速度增量与它的历史飞 行经验和群体飞行经验相关，并且受到最大飞行速度的限制。因此，这样的运动 模式可被用于各类寻优问题的求解【1 4 】。 从社会学的角度来看，式2 1 中的第一部分是“惯性 部分，由微粒之前的 速度的惯性引起，它是微粒先前的速度乘一个权值进行加速，表示微粒对当前自 身运动状态的信任，依据自身的速度进行惯性运动，因此称这个权值为“惯性权 重”：第二部分是微粒当前位置与在搜索过程中自身最优位置之间的距离， 为“认知”部分，表示微粒本身的思考，意思是微粒的运动来源于自己的经验 的部分，它使微粒有了足够强的全局搜索能力，避免局部极小；第三部分是微粒 当前位置与群体最优位置之间的距离，为“社会”部分，表示微粒间的信息共 享与相互合作，即微粒的运动来源于群体中其它微粒经验的部分，通过认知模 仿较好同伴的运动p 引。在这三部分的共同作用下，为了找到问题的最优解，微 粒根据历史经验并利用信息共享机制，不断调整自己的位置。 标准微粒群算法的算法流程如下： 1 ) 对群体规模为m 的微粒群初始化，包括初始化每个微粒的位置和速度； 2 ) 计算每个微粒的适应值； 3 ) 对于每个微粒，将其适应值与它所经历过的最好位置玩。的适应值进行比 较，如果较好，则将其位置作为它自身当前的最好位置阢。； 4 ) 对于每个微粒，将其适应值与全体微粒所经历过的最好位置g 椭的适应值进 行比较，如果较好，则将其位置作为当前群体的最好位置g 舨，； 5 ) 根据方程( 2 1 ) 、( 2 2 ) 对每个微粒的速度和位置进行更新； 6 ) 如果满足终止条件( 通常达到一个预先设置的最大代数g m ，。或者是一个足够 好的适应值) 则停止，否则转到2 ) 。 2 2 1 基本微粒群算法的参数分析 微粒群算法中有参数惯性权重、加速常数、以及最大速度，下面对它们做 一个简单的分析。 2 2 1 1 惯性权重缈 惯性权重c o 出现在方程( 2 1 ) 的第一部分，它使得微粒保持运动的惯性，有扩 展搜索空间的趋势，进而有能力探索新的区域，对微粒群算法能不能收敛起重 要的作用。国的取值稍大有利于全局搜索，收敛速度快，但这样不容易得到精 l o 确解；而缈取小一些的值有利于局部搜索和得到更精确的解，但收敛速度慢， 并且有时会陷入局部极值。 2 2 1 2 加速常数q 和巳 适当的国值对搜索速度和搜索精度起协调作用，在公式( 2 1 ) 中，如果让 c 1 = c 2 ，并且取值为o ，那么微粒将一直以当前的速度惯性飞行，直到到达边界 为止，由于它搜索的区域有限，所以很难找到最优解。若取c 。为0 ，则微粒只 有社会部分，没有认知能力，在微粒的相互作用下，微粒有能力到达新的搜索 空间，虽然此时收敛速度比基本微粒群算法快，但如果面对的是复杂问题，就 比基本微粒群算法容易陷入局部极值；同样地，如果取厶为0 ，则微粒之间只 有认知部分，没有社会信息共享，这样个体间没有交互，得到最优解的可能非 常小【3 4 1 。 2 2 1 3 最大速度戤 通过调整每次迭代时每个微粒在每一维上移动的距离微粒群算法进行下 去。虽然可以随机的改变微粒的速度，但我们不希望微粒轨道扩展到越来越广 阔的空间，防止它不受控制地达到无穷。所以当最大速度超过戤值时，最大 速度就要被代替。 2 2 2 微粒群算法的几种基本进化模型 2 2 2 1 全局最优模型 全局最优模型指的是既是群体最优，又是个体最优的微粒f 3 7 】。 为了提高算法的收敛速度，全局最优模型损失了算法的鲁棒性，该模型的 具体实现就是基本微粒群算法。在这样的模型中，微粒群算法用某个微粒吸引 所有微粒向它靠拢，使所有微粒最终收敛于它的位置j 如果这个微粒的适应值 不好，在进化过程中，无法有效地更新这个最优解，那么微粒群就会跟遗传算 法类似，出现早熟现象。为了讨论方便，我们将具有s 个微粒的微粒群的进化方 程重新表述为： 乞o ) 异( f ) ，日( ，) ，e ( ，) ) if ( p g ( t ) ) = m i n f ( p o ( t ) ) ，( 片( ，) ) ，厂( 只( f ) ) ) v o ( t + 1 ) = v o ( t ) + q r i ，( f ) 乞( ，) 一b ( ，) 】+ 白吃j ( ，) 巴( ，) 一x u ( t ) 其中，只( f ) 是全局最好位置，对应于称之为全局最好微粒所处的位置。 2 2 2 2 局部最优模型 为了防止在全局最优模型中可能出现的早熟现象，相对于全局最优模型中 的一个微粒做为吸引子，局部模型采用多个粒子吸引其它粒子。算法的具体操 作是：首先将整个微粒群分解成若干个子群，保留每一子群中的局部最好微粒 p ( f ) ，把它叫做为局部最好位置。假设第f 个子群在长度为，的领域内，局部最 优模型可以这样描述： m = 只一，o ) ，一m o ) 9 , 0 9 p 一。o ) ，p ( ，) ，r 。( f ) ，p + ( ，) ，只+ ，o ) ) ( ，+ 1 ) mi 厂( 只( ，) ) = m i n f ( a ) ，v a m v o ( t + 1 ) = 屹( f ) + c l o ) 【乞( ，) 一o ) 】+ c 2 吃( f ) 弓o ) 一而( ，) 】 从上述公式可以看出，如果，= 夕( s 是种群中微粒的个数) ，局部最优模型就跟全 局最优模型相同。实验证明：，= l 时，全局最优模型的收敛速度低于局部最优 模型，当1 ， 1 2 时，算 法则较多地陷入局部极值。 类似于模拟退火中的温度的作用，较大的惯性权重国有较好的全局收敛能 力，丽较小的缈则有较强的局部收敛能力。迭代次数越大，惯性权重国越小， 这就表明微粒群算法在初期具有较强的全局收敛能力，后期局部收敛能力增强。 在文献 3 5 】中，将惯性权重缈看做迭代次数的函数，使其满足下面的等式： c o ( t ) = 0 9 一二一0 5 4(210)m a x n u m b e r 、7 其中，m a x n u m b e r 为最大截止代数，此时缈的范围是从0 9 线性减小到0 4 ，文 献 3 5 用实例证明此时的算法的效果很好。 2 3 1 2 基于模糊系统的惯性因子的动态调整 让惯性权重线性递减，对于某些问题是有效的，但是对于其他问题并不 一定是最好的，在这个基础上，文献【3 8 】提出了基于模糊系统的惯性权重的动 态调整，该模糊系统需要两个输入参数：当前种群最优性能指标和当前的惯性 权重，输出为惯性权重的调节量。 1 4 2 3 2 协同微粒群算法 在基本微粒群算法中，微粒在不断的迭代过程中，总是在自己能搜索到的 范围内寻找全局最优位置并向该位置靠拢，这样微粒的速度会很快地下降直到 接近0 ，但是很可能在速度接近0 的时候，整个算法还没有达到最大进化代数 或者所搜索到的最优位置的适应值不是很好，这样，微粒群算法容易陷入局部 最优，另外在2 3 1 1 节中，指出了当惯性权重大于1 2 时，微粒群算法陷入局 部极值的可能性比较大，因此我们在实际中对微粒群算法进行改进，一般地让 遗传算法等其他进化算法同微粒群算法结合，采用协同进化，让采用微粒群算 法计算得到的最优位置与其他进化算法得到的最优位置相比来得到最优。 协同也可以是在微粒群算法自己本身中实现，基本思想是：把种群分成若 干个独立的子群，让每个子群中的微粒分别在d 维的目标搜索空间中的不同维 度方向上进行搜索，在每一步迭代中，每个子群都独立地搜索自己的局部最优 位置，并进行更新，但是子群之间不共享信息，在计算适应值的时候，将每个 微粒群中最优微粒的位置向量拼接起来，组成d 维向量并代入适应函数计算适 应值1 3 9 1 。 2 4 微粒群算法的收敛性分析 在微粒群算法中，算法收敛是这样定义的： l i m x ( t ) = p ， 其中，p 为搜索空间内任意一点，这种收敛性不是微粒群算法收敛的充分条件， 而是算法在有限次迭代后终止的必要条件1 3 0 1 。 研究表明，对具有惯性权重的微粒群算法，只要满足条件： 缈些丝二三 2 微粒群算法就是收敛的，特别地，当c o = 1 0 ，q = 2 0 ，c ：= 2 0 时，等号成立【3 7 1 。 第三章n u r b s 曲线降阶的预备知识 3 1b 样条曲线的定义 定义3 1 1 【1 3 】：设有一组节点序列 ，f ) ( f - o ，1 ，2 ， + 七+ 1 ) ，由其确定的b 样条基 函数m ( f ) ，有一顶点系列 p ) ( k0 , 1 ，2 ，玎) 构成特征多边形，将j ( ，) 与z 线性 组合，得到k 次( k + 1 ) 阶b 样条