（计算机应用技术专业论文）基于群智能的几何约束求解技术研究.pdf

长春工业大学硕士学位论文 摘要 近年来，参数化设计技术以其强有力的草图设计、尺寸驱动修改图形等功能，成 为产品设计过程中初始设计、产品建模及修改、多方案比较和动态设计的有效手段， 越来越得到人们的重视。国外一些先进的c a d 系统己经具有一定的参数化设计功能， 因而拥有较强的参数化设计能力己经成为现代c a d 系统的重要标志之一。参数化设计 技术的基础是约束技术。那么深入研究约束理论及其在图形设计中的应用对提高参数 化设计技术是很有意义的。 几何约束求解是基于约束满足的参数化设计方法中的最核心技术。几何约束求解 技术的好坏和成熟与否已经成为衡量一个基于约束的参数化设计系统优良的关键。 围绕着如何更好的建立几何约束模型及约束求解技术这一重要问题，国内外的专 家学者在理论和实践上进行了广泛的研究，产生了很多解决约束问题的方法。当前求 解约束问题的方法主要可概括为：整体求解法、稀疏矩阵法、连接分析法、归约构造 法、约束传播法、符号代数法和辅助线法等等。这些方法从不同的角度出发，大大提 高了计算机辅助设计的约束求解能力，同时这些方法也有各自的局限性，使得在约束 求解中，有许多问题没有得到很好的解决。例如数值迭代法只能得到解空间中的一个 解，无法对解空间中的多个解进行比较的问题，并且对初始值比较敏感，不当的初始 值将导致算法不能收敛到用户想要的解；算法收敛的快速性和全局性阅题；几何约束 的欠约束和过约束问题等等。本文着重从算法的快速求解和全局性问题入手，借用群 智能算法，力求提高算法的求解能力。 粒子群优化算法源于鸟群运动行为的研究，是一种启发式全局优化技术，一种基 于群智能的演化计算方法。群体中的每一个微粒代表待解决问题的一个候选解，算法 通过粒子间信息素的交互作用发现复杂搜索空间中的最优区域。 本文提出建立记忆表的方法，详尽描述了粒子搜寻求解的过程。并对固定惯性权 重和时变权重在粒子搜寻求解的不同阶段的影响和作用进行了评估和总结。最后，针 对基本粒子群算法易陷入局部极优点，搜索精度不高等缺点，采用常规遗传算法控制 p s o 算法的启发式参数，形成复合粒子群优化算法。 关键词：几何约束求解，粒子群优化算法，群智能，启发式，优化，惯性权重 长春工业大学硕士学位论文 a b s t r a c t i nr e c e n ty e a r s ，p a r a m e t e r i z a t i o nd e s i g nt e c h n i q u eh a sb e c o m ea ne f f e c t i v e w a yo ft h ep r o d u c ti n i t i a ld e s i g n ，p r o d u c tm o d e l ，r e v i s i o na n dm u l t i s c h e m e c o m p a r i s o na n dd y n a m i c a ld e s i g ni nt h ed e s i g np r o c e s sw i t hi t sp o w e r f u ls k e t c h d e s i g na n dr e v i s i o no nt h eg r a p h sb ys i z e d r i v e n a n di th a sg o tp e o p l e sm o r e a n dm o r ea t t e n t i o n s o m ef o r e i g na d v a n c e dc a ds y s t e m sh a v eh a dt h ef u n c t i o n s o fp a r a m e t e r i z a t i o nt oac e r t a i nd e g r e e i th a sa l r e a d yb e c o m eo n eo ft h e i m p o r t a n ts y m b o l si nm o d e r nc a ds y s t e mt h a th a sas t r o n gp a r a m e t e r i z a t i o nd e s i g n c a p a c i t y t h ef o u n d a t i o no fp a r a m e t e r i z a t i o nd e s i g nt e c h n i q u ei st h ec o n s t r a i n t t e c h n o l o g y i ti sv e r ym e a n i n g f u lf o ri m p r o v i n gp a r a m e t e r i z a t i o nd e s i g n t e c h n i q u et os t u d yt h ec o n s t r a i n tt h e o r ya n di t sa p p l i c a t i o ni nt h eg r a p h d e s i g n g e o m e t r yc o n s t r a i n ts o l v i n gi st h em o s tc e n t r a lt e c h n o l o g yi nt h ep a r a m e t e r d e s i g nm e t h o d so nt h eb a s i so fc o n s t r a i n ts a t i s f a c t i o n i ti st h ek e yo ft h e q u a l i t yo ft h ep a r a m e t e r i z a t i o nd e s i g ns y s t e mt ow e i g hw h e t h e rt h eg e o m e t r i c c o n s t r a i n tt e c h n o l o g yi sg o o da n dm a t u r eo rn o t a r o u n dt h e i m p o r t a n tp r o b l e m o fh o wt oe s t a b l i s ht h em e t h o do f p a r a m e t e r i z a t i o nd e s i g na n dg e o m e t r yc o n s t r a i n tm o d e l ，d o m e s t i ca n d i n t e r n a t i o n a le x p e r t sh a v ec a r r i e do nal a r g ea m o u n to fr e s e a r c hw o r k a n dh a v e g o tal o to fe f f e c t i v ea c h i e v e m e n t sw i t hp r a c t i c ea n dt h e o r y t h ep r e s e n t s o l v i n gm e t h o d sc a nb es u m m a r i z e di n t o ：w h o l es o l v i n ga p p r o a c h ，s p a r s em a t r i x a p p r o a c h ，c o n n e c ta n a l y t i ca p p r o a c h ，s t i p u l a t i o nc o n s t r u c t i o na p p r o a c h ， c o n s t r a i n tp r o p a g a t i o na p p r o a c h ，s y m b o la l g e b r aa p p r o a c ha n da u x i l i a r y1 i n e a p p r o a c he t c v i e w do ft h ed i f f e r e n ta n g l e s ，t h e s em e t h o d si m p r o v et h e c o n s t r a i n ts o l v i n gc a p a b i l i t yo ft h ec a dg r e a t l y h o w e v e r ，b e c a u s eo ft h e i r 1 i m i t a t i o n ，t h e r ea r e al o to fp r o b l e m ss h o u l db es o l v e d f o ri n s t a n ce ， n u m e r i c a l i t e r a t i o nm e t h o dc a ns o l v eo n ep r o b l e mi nt h es o l u t i o ns p a c e ，b u t f o rt h em u l t i s o l u t i o n ，i tc a n tc o m p a r e b e c a u s eo ft h es e n s i t i v ef o rt h e i n i t i a lv a l u e ，i m p r o p e ri n i t i a lv a l u ew i l l l e a du s e rt ou n e x p e c t e da n s w e r c o n v e r g e db yt h ea r i t h m e t i c s t i l l ，t h e r ei st h ep r o b l e mo fr a p i d n e s sa n dw h o l e p r o b l e mo ft h ea r i t h m e t i cc o n v e r g e n c ea n dt h ep r o b l e m so fu n d e r c o n s t r a i n ta n d o v e r c o n s t r a i n ti nt h eg e o m e t r yc o n s t r a i n t s ，e t c t h i st h e s i sa t t e m p t st os o l v e t h eq u i c ks o l u t i o no fa l g o r i t h ma n dt h eg l o b a lp r o b l e m 长春工业大学硕士学位论文 p a r t i c l es w a f mo p t i m i z a t i o n ( p s o ) a l g o r i t h mi sah e u r i s t i cg l o b a l o p t i m i z a t i o nt e c h n o l o g ya n da l s oak i n do fe 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 o l o g y ， w h i c hb a s e do ns w a r mi n t e l l i g e n c e i tc o m e sf r o mt h er e s e a r c ho nt h eb i r df l o c k m o v e m e n tb e h a v i o r e a c hp a r t i c l eo ft h es w a r mr e p r e s e n t so n ec a n d i d a t es o l u t i o n o ft h ep r o b l e mb e i n go p t i m i z e d t h ea l g o r i t h mf i n d so p t i m a lr e g i o n so fc o m p l e x p r o b l e ms p a c e st h r o u g ht h ep h e r o m o n ei n t e r a c t i o no fp a r t i c l e s t h et h e s i sg i v e sap r o p o s a lt h a ts e tm e m o r yt a b l ed e s c r i b i n gt h es e e k i n g p r o c e d u r eo fp a r t i c l e si np s o a l s ot h ep a p e re s t i m a t e sf i x e da n dt i m e v a r i a n t i n e r t i aw e i g h td i f f e r e n ti n f l u e n c ep l a y i n gi nd i f f e r e n ts t a g e s a tt h el a s t ，ac o m p o s i t ep s o ( c p s o ) u s i n gs i m p l eg e n e t i ca l g o r i t h m ( s g a ) t oo p t i m i z et h ei m p o r t a n tc o n t r o lp a r a m e t e ri sd e v e l o p e d ，i no r d e rt oo v e r c o m e t h ed i s a d v a n t a g eo fc h o o s i n gh e u r i s t i cp a r a m e t e rf o rp s o k e y w o r d s ：g e o m e t r yc o n s t r a i n ts o l v i n g ，p a r t i c l es w a r mo p t i m i z a t i o n ，s w a r m i n t e l l i g e n c e ，h e u r i s t i c ，o p t i m i z a t i o n ，i n e r t i aw e i g h t 长春工业大学硕士学位论文 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经 发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本声明的法律结果由本人承担。 论文作者签名：枸葛鸸 日期呷够月；日 长春工业大学硕士学位论文 第一章绪论 1 1 引言 对一个国家来说，制造业的水平反映了一个国家的总体工业水平；对一个制造企 业来说，设计水平的高低是一个企业兴衰成败的关键因素之一。科研开发力量和高新 技术的应用是支撑企业设计的强有力后盾。随着计算机技术的发展和普及，作为直接 支持设计的高新技术，计算机辅助设计和制造( c a d c a | 1 1 ) 技术得到了迅猛的发展。由 于该技术将计算机高速而精确的计算能力、大容量存储和处理数据的能力与人的逻辑 判断分析及创造性思维结合起来，在机械、建筑、汽车、电子、航空航天等国民生产 的重要领域得到了广泛应用，从而产生了巨大的生产力。因而，c a d c 栅技术的发展和 应用水平已经成为衡量一个国家现代化水平的重要标志之一。c a d 作为信息技术的一个 重要组成部分，对加速工程和产品的开发、缩短设计制造周期、提高质量、降低成本、 增强企业市场竞争力与创新能力发挥着重要作用。c a d 技术是企业信息化的重要技术基 础，也是企业进入国际市场的入场券。随着i n t e r n e t i n t r a n e t 网络和并行、高性能 计算机及事物处理的普及，异地、协同、虚拟设计以及即时仿真也在c a d c w 中得到 了广泛应用，使 ：导c a d c a m 系统从最初的只能应用于制图发展到现在的c a d c a m 系统 的可视化、集成化、智能化、网络化。其中参数化设计在当今的c a d c a m 中扮演了一 个越来越重要的角色。 一般讲，一个c a d 系统基本上只适用于某一类产品的设计，如电子产品c a d 只适 用于设计印制板或集成电路，而机床的c a d 只适用机床的设计制造。这些系统不仅基 础和专业软件不一样，而且硬件配置上也有差异，但就系统的逻辑功能和系统结构角 度来看还是基本相同的。不管是用于何种产品设计和制造的c a d 系统，从其逻辑功能 角度来看，c a d 系统基本上是由计算机和一些外部设备( 计算机和外部设备通常硬件) 及相应的软件组成( 其中包括系统软件、支撑软件及应用软件，如图1 1 所示) 。 图1 1c a d 系统的基本框架 长春工业大学硕士学位论文 但对于一个具体的c a d 系统来讲，其硬件、软件相互的配置是需要进行周密考虑 的，同时对硬软件的型号、性能以及厂家都需要进行全方位的考虑。 由于在机械c a d 中，参数化可变异特征造型业已成为当前的常规，产品的尺寸参 数允许随意修改，软件系统中需要加强相应的几何约束求解能力。 1 2c a d 技术的发展历史及国内外研究现状 从古至今，设计一直是人类认识和改造世界的重要活动，我们周围世界中的广泛 领域，从飞机、轮船、建筑、器皿、家具乃至计算机程序，一切人类的创造物无不需 要设计。设计过程是由信息检索、分析、计算、综合、修改及文件编制等诸多环节构 成，其中形状的分析、综合、修改及图纸绘制是最具有特色的典型设计环节。 c a d ( c o m p u t e ra i d e dd e s i g n ) 即计算机辅助设计的简称，其含义是使用计算机帮 助人们进行产品和工程设计，也就是将计算机高速而精确的计算能力、大容量存储和 数据处理能力与设计者的综合分析和逻辑判断能力以及创造思维结合起来，从而大大 加快设计进度、缩短设计周期、提高设计质量。这一技术是最近4 0 年来迅速发展起来 的一门新兴的综合性计算机应用系统技术。经过几十年的发展，c a d 技术己被广泛应用 于工业生产的各个领域。由于它具有提高产品与工程设计水平、降低消耗、缩短产品 开发与制造周期、提高产品质量便于管理等特点，c a d 技术越来越受到广大企业的重视， 并在企业中得到广泛应用和迅速推广“。 上个世纪6 0 年代初，美国麻省理工学院的研究生i e s u t h e r l a n d ”1 在美国计算机 联合会的年会上首次提出了计算机辅助设计的概念，介绍了一个能在1 0 1 5 分钟内完 成用手工通常要数周时间才能完成的设计工作的系统，实现了从概念设计到生产设计 的过程。c a d 是指利用计算机硬件和软件进行的设计活动，包括使用计算机的数据库、 程序库及通讯等技术来完成设计过程的信息检索、分析、计算、综合、修改及文件编 制工作。它可以使原非单纯人脑所能承担的设计和制造任务当作日常工作处理，其处 理的复杂程度，将随着一代代新的计算机硬件和软件的出现而不断提高。 在c a d 软件发展的初期，c a d 的含义仅仅是图板的替代品，即c o m p u t ea i d e d d r a w i n g ，而不是我们现在讨论的计算机辅助设计( c o m p u t e ra i d e dd e s i g n ) 所半酣 的全部内容。7 0 年代初，美国的a p p l i n c o n 公司开发了第一个完整的c a d 系统。那时 的c a d 系统主要采用以超级小型机为寄出的集中分是方式开始商品化。为了减少用户 和开发者的工作量，图形标准被着手研究。到了7 0 年代末，光栅显示屏开始出线，并 由此引导计算机图形学算法研究进入了一个新天地。c a d 技术进入了实用阶段。 8 0 年代，随着超大规模集成电路技术的发展，微处理器技术不断改进，分布式联 网的工程工作站已成为c a d 典型硬件环境。其性价比年复一年的迅速提高，光栅扫描 显示器及算法统治图形学软硬件。c a d 方法从绘图进入造型，实体模型系统逐渐成熟， 计算机动画开始兴起，集成c a d 系统开始商品化。c a d 应用迅猛发展，市场十分繁荣。 长春工业大学硕士学位论文 1 9 8 9 年美国国家工程科学院将c a d c m l 技术评为当代( 1 9 6 4 1 9 8 9 ) 十项最杰出的工程 技术之一。 9 0 年代以来，随着计算机硬件技术的提高，c a d 已经广泛应用到个人计算机上， 各种模型描述方法也逐步趋于标准化。c a d 技术逐步智能化、多媒体化。因而使得c a d 系统便得更加灵活、易用、高效，并有创造性，设计的结果也更易控制。由于c a d 系 统性价比的提高，工程、制作和娱乐行业普遍使用c a d 技术。c a d 逐步成为计算机应用 最重要的领域。各种新的输入输出设备不断涌现，特别是3 d 彩色数字化仪的出现，使 得造型和数据库的建立越来越容易。c a d 系统向集成化、智能化方向发展，二维c a d 技术全面普及，三维特征造型技术和参数化技术以及并行工程等技术获得了巨大的发 展。 我国推广使用c a d 技术起步较晚，在上世纪8 0 年代，随着p c 机的出现以及 a u t o o 、d 等国外软件进入中国，一些大型企业和设计院开始使用c a d 技术。“七五” 期间，我国在8 6 3 高科技计划中，将c a d 技术的开发推广作为一个重点。8 6 3 计划实 施十年来，我国o 、d 、c a p p 和c a m 技术都取得了长足的发展，除对许多国外软件 进行了汉化和二次开发以外，还诞生了不少具有独立版权的二维绘图、工艺设计、数 控加工、三维造型系统，为企业实现设计现代化提供了支持。“九五”期间，国家科委 又将c a d 技术列为科技推广的“重中之重”项目的首项，建立了一批示范省、市和企 业，大力推进“甩图板”工程。 上世纪8 0 年代后期，以p r o e n g i n e e r 为代表的基于参数化特征造型技术的新一 代实体造型系统的出现，被认为是c a d 发展史上的又一次质的飞跃，极大地简化了产 品建模过程。此后许多c a d c a m 公司都推出了自己的参数化特征造型系统，主要有： a u t o d e s k 公司的m d t ，u g s 公司的u n i g r a p h i c s ，s d r c 公司的i d e a sm a s t e rs e r i e s ， 生信国际公司的s o l i d w o r k s ，d a s s a u l ts y s t e m 和i b m 公司的c a t i a 等。国内很多单 位也积极地投入到参数化特征造型系统的研制和开发，如清华同方的g e m s 5 0 ，华中科 大i n t e c a d 和开目c a d ，北航海尔的c a x a e b ，中科院凯思博宏p i c a d 和大恒h m c a d ， 浙江大学的大天g s - - 2 d d s 等。与传统的几何造型系统相比，参数化特征造型系统引入 了两项重要的技术：特征技术和基于约束的设计技术。特征技术是适应c a d c a m 集成 和加速设计自动化而逐渐发展起来的，在特征技术的研究中g o s s a r d ，p r a t t ，d i x o n ， s h a h ，w o o 等国外学者以及华中科技大学，西北工业大学，西安交通大学，中科院计算 所c a d 开放实验室，中科院数学与系统科学研究院，清华大学，北京航空航天大学， 大连理工大学，浙江大学等国内高等院校和科研院所都对特征技术的开发和应用做出 了贡献。 1 3c a d 的几次技术变革 早期的c a d 系统只支持简单的二维图素，到7 0 年代中期三维c a d 系统现时，为 长春工业大学硕士学位论文 了表示三维形体引入了三维线框模型的概念。线框模型仅定义产品的基本轮廓，不能 表示产品的表面和内部实体。为了满足复杂曲面造型及实体造型的需要，相继产生了 曲面模型和实体模型。曲面模型由若干块小曲面片拼接而成，通过建立点、线( 边) 、 面的信息表，达到建立表面模型的目的。但是曲面模型不能明确指出实体究竟处于表 面的哪一侧，在实体的表示上仍然缺乏完整性。实体造型是一种最为有效的形体表示 方法，可以完整地描述形体的几何形状信息以及物体各部分之问的连接关系跚。 第一次技术变革一一曲面造型技术“， 六十年代出现的c a d 系统只是极为简单的线框式系统。这种初期的线框造型系统 只能表达基本的几何信息，不能有效表达几何数据间的拓扑关系。由于缺乏形体的表 面信息，c a m ( c o m p u t e rr i d d e dm a n u f a c t u r i n g ) 计算机辅助制造及c a e ( c o m p u t e r r i d d e de n g i n e e r i n g ) 计算机辅助工程均无法实现。此时法国人提出贝赛尔算法，使得 人们在用计算机处理曲线及曲面问题时变得可以操作，能在二维绘图系统c a d a m 的基 础上，开发出以表面模型为特点的自由曲面建模方法，推出了三维曲面造型系统c a t i a 。 它的出现，标志着计算机辅助设计技术从单纯模仿工程图纸的三视图模式中解放出来， 首次实现以计算机完整描述产品零件的主要信息，同时也使得c a m 技术的开发有了现 实的基础。 第二次技术革命一一实体造型技术 有了表面模型，c a m 的问题可以基本解决。但由于表面模型技术只能表达形体的表 面信息，难以准确表达零件的其它特性，如质量、重心、惯性矩等，对c a e 十分不利， 最大的问题在于分析的前处理特别困难。基于对c a d c a e 一体化技术发展的探索，s d r c 公司于1 9 7 9 年发布了世界上第一个完全基于实体造型技术的大型c a d c a e 软件。由于 实体造型技术能够精确表达零件的全部属性，在理论上有助于统一c a d ，c a e ，c a m 的 模型表达，它代表着未来c a d 技术的发展方向。可以说，实体造型技术既带来了算法 的改进和未来发展的希望，也带来了数据计算量的极度膨胀。 第三次技术变革一一参数化技术 在实体造型技术逐渐普及之时，c a d 技术的研究又有了重大进展。如果说在此之前 的造型技术都属于无约束自由造型的话，进入8 0 年代中期，c v 公司的设计师们提出了 一种比无约束自由造型更新颖、更好的算法一一参数化实体造型方法。参数化设计 ( p a r a m e t r i cd e s i g n ) 技术也叫尺寸驱动( d i m e n s i o n d r i v e ) ，它不仅可使c a d 系统具 有交互式绘图功能，还具有自动绘图的功能。它主要的特点是：基于特征、全尺寸约束、 全数据相关、尺寸驱动设计修改。早期的参数化设计方法是把交互绘图的过程程序化， 因此也叫做参数编程法。该方法一般是由程序人员利用高级编程的方式来建立图形与 尺寸参数的约束关系，通过c a d 系统为用户提供的二次开发接口生成参数化图形。由 于该方法适应能力差，现在基本上很少有人使用了。目i j 应用的参数化设计方法主要 是基于特征模型的造型方法，该方法的思想是造型操作与约束之问有着对应的关系： 4 长春工业大学硕士学位论文 造型过程能够用来管理和维护反映约束关系的数据结构，设计的修改可以通过修改造 型过程的某一参数得到。r o l l e r s ”1 扩展了传统c a d 系统的数据结构，在设计过程中增 加了设计约束以便更好的捕捉设计者的意图。s o l a n o 给出了一个内部的模型定义语 言，它能对定义模型进行参数化建模，不仅支持二维和三维，而且能够实现拓扑结构 的修改。经过多年的发展，参数化设计技术目前己经成为c a d 技术应用领域内的一个 重要研究分支，参数化技术的应用主导了c a d 发展史上的第三次技术变革。 第四次技术变革一一变量化技术 早在上世纪9 0 年代以前，s d r c 公司就己经进行了参数化技术的研究，通过经验总 结以及对工程设计过程的深刻理解，该公司的开发人员发现了参数化技术尚有许多不 足之处。在此基础之上，s d r c 的开发人员以参数化技术为基础，提出了一种比参数化 技术更为先进的实体造型技术一一变量化技术。这种技术是指设计对象的修改需要更 大的自由度，通过求解一组约束方程来确定产品的尺寸和形状0 1 。众所周知，已知全参 数的方程组去顺序求解比较容易。但在欠约束的情况下，其方程联立求解的数学处理 和在软件实现上的难度是可想而知的。s d r c 攻克了这些难题，并就此形成了一整套独 特的变量化造型理论及软件开发方法。由于变量化设计是在参数化技术基础上产生的， 所以它们之间的概念容易被混淆。它与参数化设计的差别主要体现在约束的定义和求 解方式上。在参数化设计中约束的建立和求解依赖于创建的顺序，每个几何元素根据 先前的己知的几何元素定位。参数求解采用顺序求解策略，后面元素的求解依赖于生 成它的几何元素和约束条件，求解过程不能逆向进行，即求解是过程式的。在变量化 设计中约束的指定是陈述式的，即约束的指定没有先后顺序之分，约束依赖关系可以 根据设计意图随意更改。它通常采用并行求解策略，通过同时求解一组约束方程来确 定设计对象的形状和尺寸。并且变量化设计具有同时处理几何约束和工程约束的能力， 它的应用范围也比参数化设计的应用范围广泛的多。变量化技术既保持了参数化技术 的原有的优点，同时又克服了它的许多不利之处，也驱动了c a d 发展的第四次技术变 革。 1 4 几何约束求解技术 现在被广泛应用的成熟的c a d 技术中，无论是参数化技术还是变量化技术，它们 都是以几何约束求解这一技术为核心的。 几何约束问题是指给定一些几何元素，并根据这些几何元素之间指定的约束关系 来确定几何元素的具体位置。几何约束求解技术就是通过计算确定同时满足约束关系 的几何元素的实际坐标。 几何约束求解技术被广泛的应用于各个领域，如计算机辅助设计、机器人动力学 分析、化学分子建模、误差分析、几何定理证明“”等等。尤其在机械设计中，因为大 部分的机械殴计来源于草图或现有的图形，在草图设计过程中，客户并不关心图形的 长春工业大学硕士学位论文 精确尺寸，而是粗略的画出零件的大致图形“；而且，客户也可能在现有图形基础上 进行尺寸改进和调整，这是非常普遍的现象，因为尺寸可以决定零件的几何形状，尺 寸的改变可以生成各种不同的图形。然而传统的交互作图的方法，虽然能够较充分的 发挥设计师的能力，但是一旦图形生成就很难进行尺寸上的调整。基于以上需求，l i n 和g o s s a r d 等人提出了参数化设计“”。参数化设计的基本原理就是系统在设计过程中 自动地捕获客户的设计信息，从而将客户设计中的各个设计对象以及对象之问的关系 记录下来，而当客户进行修改图纸中尺寸标注和参数时，系统能够自动对图纸进行必 要的修改，使图纸中反映客户设计思想的设计对象之间的关系依旧维持不变。这种技 术以其强大的草图设计和图纸尺寸驱动能力已成为实现产品的初步设计、系列设计以 及变异式设计的核心技术。参数化设计是一种基于约束的设计方法，用约束确定和描 述某一零件的几何形状。在该方法中，使用一系列与几何和工程参数有关的约束函数 来描述图形的特征。 基于几何约束满足的设计系统，是在设计对象的整个生命周期中，采用全部或部 分的几何约束方法，描述设计对象及其环境的功能性、结构性、可加工性等方面的约 束，方便灵活的操作这些约束。基于几何约束的系统设计，至今己经有很漫长的历史 了，自从1 9 6 3 年s u t h e r l a n d 提出了第一个基于约束的交互设计系统- - s k e t c h p a d 以来， 经过3 0 多年的发展，如今已经成为计算机技术中比较成熟的重要领域。 几何约束求解是基于约束求解的参数化设计方法的核心内容“3 】，几何约束求解在 工程绘图或c a d 开发上是指在输入一个草图以后，用户可以随时在需要的时候，以任 意的顺序重新输入几何约束，然后由计算机自动导出精确的满足客户需求的几何图形 的一种基于约束参数化设计方法。几何约束求解技术己经成为衡量一个基于约束的参 数化设计系统是否优良的重要标准。 1 5 本文的工作和组织 本文介绍了当前国内外学者处理几何约束求解问题的主要方法，对其中的个别热 点方法进行了较为详细的阐述，并且对粒子群优化算法这一新兴的群智能优化算法进 行了介绍。本文主要研究的是基于群智能的几何约束求解技术研究，它实际属于基于 代数计算方法的几何约束求解方法中的一种。通过对基本的粒子群优化算法的深入研 究，分析它的优缺点，特别是通过函数的测试，对其中具有平衡算法搜索范围与搜索 精度作用的参数惯性权重的研究分析，得出了一些具有积极作用的结论。由于群智能 算法具有的群体多样性和全局寻优能力，其在解空间极为庞大的几何约束求解问题上 表现得尤其突出。在将几何约束问题的约束方程组转化为优化模型的时候，我们需要 找到一种方法来跳出局部最优解，进而找到全局最优解。这罩包括用复合粒子群优化 算法来求解。由于群智能算法本身具有很多优点：很强的计算鲁棒性、隐含的内在并行 性、全局搜索与局部快速收敛能力，因此将群智能算法与约束求解相结合将大大提高 长春工业大学硕士学位论文 约束求解的效率。 本文具体章节安排如下： 第一章绪论。介绍了c a d 技术的发展历程、国内外研究现状，以及c a d 技术经历 的几次技术变革。介绍了几何约束求解技术的发展和研究现状，之处了几 何约束求解技术在参数化约束设计中占有重要地位。 第二章几何约束求解研究概述。主要是对几何约束问题进行了研究。详细的介绍 了几何约束相关的概念，基本的二维几何体的约束方程表示形式，约束的 分类情况以及现有的求解几何约束的主要方法。其中着重阐述了几何约束 求解的主要方法，通过详细讨论约束求解的几种典型方法，指出了各种方 法的优缺点。 第三章粒子群优化算法研究与发展。介绍了p s o 算法的基本原理、数学描述形式。 本文提出了一种建立记忆表的方法，详尽的描述了粒子的搜寻求解过程。 同时，本文对固定惯性权重和时变权重在粒子搜寻求解的不同阶段的影响 和作用进行了评估和总结。最后总结了近年来p s o 的研究现状，并简介了 一些混合p s o 算法。 第四章基于群智能算法的几何约束求解技术研究。本文将p s o 算法中控制参数的 选取作为一个优化问题，引入常规遗传算法中的选择、交叉的思想，用常 规遗传算法来控制p s o 算法中的启发式参数，形成复合粒子群优化算法， 并对基本p s o 和复合p s o 的性能进行实验分析。 第五章总结与展望。对全文所研究的主要内容、工作、创新性的理论和实际意义 做一个总结，并展望今后的研究工作。 长春工业大学硕士学位论文 第二章几何约束求解研究概述 几何约束求解( g e o m e t r i cc o n s t r a i n ts o l v i n g ) 技术是参数化特征造型系统的核 心技术之一，是研究在满足设计者给定的各种几何约束条件下，自动生成符合设计要 求的设计对象的技术，其实质就是一个约束满足问题。”。几何约束求解问题由一组几 何元素和对元素间约束关系的描述组成。其目标是找出一个满足约束条件的几何元素 布置方案。几何约束问题也是目前基于约束设计研究中的热点问题。 2 1 基本概念 在介绍几何约束求解问题之前，先来了解一些基本概念： 定义2 1 几何体：是指一个几何图形中具有最基本特征的几何元素“”，即二维空问中 的点、直线、圆、圆弧以及三维空间中的平面、球面、曲面等等。 定义2 2 几何约束：是指两个或多个几何体之间所具有的约束关系，即点与点之间的 距离、直线与直线之间的角度、两条直线垂直和直线与圆相交、相切等等。 定义2 3 几何约束问题：给定一个几何体的集合0 和一个关于集合0 中的几何体之间 的几何约束的集合c ，则我们将二元组( 0 ，c ) 称为几何约束问题。有时，我们也将几 何约束问题称为几何约束满足问题或者是几何自动作图。 我们举例来说明几何体与几何约束，如图2 1 所示： d b c 图2 1 基本几何体与几何约束 0 ( 几何体) ：点a ，b ，c ，d ；直线a b ，b c ，c d ，d a ，a c c ( 几何约束) ：距离i a b l ，i b c l ，i c d i ，i d a l ：角度a d c 定义2 4 几何约束问题求解：对于给定的一个几何约束问题( o ，c ) ，根据一定的算法 做出一个或所有几何图形。其中，这个几何图形是由集合0 中的所有的几何体构成， 并且这些几何体之间要同时满足集合c 中的所有几何约束。 定义2 5 几何体的自由度( d e g r e eo ff r e e d o m ) ：指要确定这个几何体的位置所需要 长春工业大学硕士学位论文 的独立参数的个数，记为d o f 。例如，二维空间中的点的自由度是2 ，圆的自由度是3 ， 线段的自由度是4 ；三维空间中的点的自由度是3 ，直线的自由度是4 。 表2 1 中列出了点、直线和圆等三种基本几何元素的参数和表达方法“”。 表2 1 三种基本几何元素的参数和表达方式 几何元素 参数 方程 点p ( x o ，y o ) ，其中】【o ，y o 分别是笛卡尔坐标x = x 0 7 d o f ( p ) = 2 y 2 y o 直线l ( d ，e ) ，其中d 是原点到有向直线的距离，x s i n ( o ) 一y c o s ( o ) + d = 0 d o f ( l ) = 2o 是x 轴正向和直线的夹角 圆 c ( x o ，y o ，r ) ，其中( 】【0 ，y o ) 是圆心，r 是半径( x - x o ) 2 + ( y y o ) 2 = y 2 d ( ) f ( c ) = 3 定义2 6 几何约束的约束度( d e g r e eo fc o n s t r a i n t ) ：指为了描述一个几何约束所 需要的代数方程的个数，记为d o c 。 表2 2 列出了一些典型几何约束关系的约束度“”。 表2 2 经典几何约束关系的约束度 几何约束关系约束度 点与点之间的距离 1 点到直线之间的距离 1 直线与直线之间的距离 2 直线与直线之间的夹角 1 水平直线 1 垂直直线 1 两直线平行 1 点在直线上 1 点在圆( 弧) 上 1 直线与圆( 弧) 相切 1 两圆( 弧) 相切 1 根据几何约束问题解的个数，我们将几何约束问题分为三类： 定义2 7 完整约束的几何约束问题：如果几何约束问题有有限个解。 定义2 8 欠约束的几何约束问题：如果几何约束问题有无限个解。 定义2 9 过约束的几何约束问题：如果几何约束问题没有解，但去掉一个约束条件后， 长春工业大学硕士学位论文 就有无限个解。 根据以上的分类，我们很难在求解一个几何约束问题之前就能判断出这个几何约 束问题是属于哪一类的。因此，我们从几何约束问题本身所具有的性质触发对几何约 束问题进行分类。 由以上定义，我们称一个几何约束问题( 0 ，c ) 是“”： 定义2 ，1 0 结构上完整约束的：如果集合0 中的任何一个子集晚中所包含的几何体的 自由度的总和等于集合c 中所有关于子集0 。中几何体的几何约束的约束度的总和减去 3 ( 二维) 或6 ( 三维) ； 定义2 1 1 结构上欠约束的：如果集合0 中存在一个子集0 。中所包含的几何体的自由 度总和大于集合c 中所有关于子集0 ，中几何体的几何约束的约束度的总和减去3 ( 二 维) 或6 ( 三维) ； 定义2 1 2 结构上过约束的：如果集合0 中存在一个子集o j 中所包含的几何体的自由 度总和小于集合c 中所有关于子集0 。中几何体的几何约束的约束度的总和减去3 ( 二 维) 或6 ( 三维) ； 注意到一个几何约束问题可能同时是结构上欠约束的和结构上过约束的，即在某 一部分是结构上欠约束的而在另一部分是结构上过约束的。 注：上述分类中出现的数字3 和6 是指一个刚体在二维和三维空间中所具有的自由度。 当我们求解一个几何约束问题的时候，我们只考虑几何图形的相对位置而不是绝对位 置。也就是说，当一个几何图形经过刚体变换( 二维中的两个平移变换和一个旋转变换； 三维中的三个平移变换和三个旋转变换) 以后可以变成另一个几何图形时，我们称这两 个几何图形是等价的，即我们认为这两个几何图形是相同的。因此在求解一个几何约 束问题的时候，我们要从集合0 中的所有几何体的自由度的总和中减去3 ( 二维) 或6 ( 三 维) 个自由度。因为这三个自由度是在一开始求解的时候由系统自动加上的。在求解的 最后，再将得到的几何约束问题的解经过剐体变换变成用户所需要的解。 2 2 二维几何体的约束方程 假设己知几何体o l ，根据这个几何体以及与其相关联的几何体0 l ，一，o i 一的不同情 况来分别讨论一下几何体n 的构造的具体实现“。 我们先来定义二维几何体的表示形式如下： 点p 。：( my 。) ，其中x ：，y ；分别是笛卡尔坐标。表示点的方程为： x = x i ， y = y l 直线l ：( a ，b ，c 。) ，a 。，b 不能同时为0 。表示直线的方程为： 口1 工+ 6 l y + c 1 暑0 圆0 ：( x ，y ，r ，) ，其中( x 。，y ) 是圆心坐标，r 是半径。表示圆的方程为： 1 0 长春工业大学硕士学位论文 ( x 一茗，) 2 + o ，一) ，。) 2 ；f 晚( a ，b ，c ) 是直线( 自由度为2 ) ，相关联的几何体为： ( 1 ) p o ：0 ，是过p 0 的一条直线( 少一个自由度) 。( a ，b ，c ) 满足如下约束方程： a x o + 砂o + c 一0 ( 2 ) l o ：o i 和直线k 成a 角( 平行、垂直、夹角) ( 少一个自由度) 。( a ，b ，c ) 满足 如下约束方程： 施。一a b o