（计算数学专业论文）基于自适应变搜索区间的遗传算法的点云曲线重建.pdf

摹 露 i j 基于自适应变搜索区间的遗传算法的点云曲线重建 摘要 曲线重建问题在反求工程和计算机视觉中都有着广泛的应用。反 求工程( r e v e r s ee n g i n e e r i n g ) 的一个重要任务是由物理模型重建 出几何表示模型，这其中包括数据采集、预处理、曲面拟合和建立 c a d 模型4 个步骤，其核心问题是如何从采样点集出发重建出曲线、 曲面的模型。在计算机视觉中通常要考察如何从图像或扫描获得的离 散数据点重建几何模型，以利于形状分析和识别。上述二者都要求由 已知的无序、带噪音的采样点集拟合出一条或多条曲线，反映出该点 集的形状和走向。曲线拟合在逼近论和几何造型中都是一个重要的研 究课题。随着三维扫描技术的成熟，点云问题成为了一个倍受关注的 热门问题。有序散乱点曲线重建已经有了许多成熟的方法。对无序数 据点的曲线重建，近年来已逐步受到人们的重视。另一方面，遗传算 法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型， 是一种新的全局优化搜索算法，具有简单通用，稳定性强，适于并行 处理以及高效、实用等显著特点，在很多领域得到了广泛应用。基于 这些理论可行性的大前提，本文在吸取前人实践经验的基础上，提出 了改进了的自适应的遗传算法，深入研究了自适应遗传算法在反求工 程中点云曲线重建的问题中的应用策略，并得到了比较满意的结果。 全文共分四章，在第一章，首先介绍了曲线曲面重建的研究背景， 实际意义以及当前国内外研究的大致情况。 硕士学位论文 在第二章，简单介绍了遗传算法的研究历史，生物背景，继而简 述了遗传算法的基本实现步骤和基本遗传算子的实现方案以及遗传 算法的基本特点和目前的基本应用情况以及作者在应用遗传算法处 理问题中的一点心得。 在第三章，我们提出了基于自适应遗传算法的无序点云的曲线重 构算法。根据无序点云的分布特点和待重建曲线的光滑，光顺假设条 件并模仿连续曲线的采样与逼近过程，我们把点云分布空间网格化， 在每个网格中搜索出最能代表该网格中点集的特征点，然后利用改进 的自适应的s i g ( s p h e r e o f i n f l u e n c e ) 图，对每个特征点作进一 步调整，从而得到能待重建曲线的型值点。我们利用测地距离函数 d g e o 来确定型值点的拓扑结构，利用b 样条函数来重建光滑曲线。 第四章，给出大量实例证明本文提出的方法简单可行，特别是对 于存在自交的情况以及点云具有明显角点的情况亦可以获得满意的 结果，并且算法的时间，空间复杂度均较小。 关键词：曲线重建，点云，白适应变搜索区间遗传算法 基于自适应变搜索区间的遗传算法的点云曲线重建 a b s t r a c t t h ec u r v er e c o n s t r u c t i o nh a ss t r o n ga p p li c a t i o n si nr e v e r s e e n g i n e e r i n ga n dc o m p u t e rv i e w a ni m p o r t a n tt a s ko ft h er e v e r s e e n g i n e e r i n gi sr e c o n s t r u c t i n gt h eg e o m e t r ym o d e l s f r o mt h e p h y s i c a lm o d e l sa n di tc o n t a i n sf o u rs t e p s ：t h ed a t ac 0 1 1 e c t i o n ， p r e t r e a t m e n t ， t h es u r f a c er e c o n s t r u c t i o na n dt h ec o n s t r u c t i o n o fc a dm o d e l s i nc o m p u t e rv i e w ，w eo f t e nw a n tt oc o n s i d e rh o w t og e tt h ed a t u mf r o mt h eg e o m e t r ym o d e l ss ot h a tw ec a na n a l y s i s a n di d e n t i f yt h es h a p eo fm o d e l se a s i l y a 1 lo ft h e s er e q u i r e d t of i g u r eo u tc u r v e sb a s eo nt h eu n o r g a n i z e dp o i n t sw i t ht h e n o i s e t h ec u r v er e c o n s t r u c ti sa ni r n p o r t a n tt o p i ci ng e o m e t r y c o n s t r u c ti o n a st h et e c h n o l o g yo f3 ds c a nb e c o m e sm a t u r e ，t h e t o p i co fp o i n tc l o u db e c o m e sh o t t e ra n d h o t t e r t h e r e c o n s t r u c t i o nf r o mt h eo r g a n i z e dp o i n t sh a v em a n ym a t u r e m e t h o d s ， s op e o p l ep a ym o r ea t t e n t i o nt ot h er e c o n s t r u c t i o n f r o mu n o r g a n i z e dp o i n t s 0 nt h eo t h e rh a n d ，g e n e t i ca l g o r i t h m ， a sac o m p u t a t i o n a l l o d e ls i m u l a t i n gt h eb i 0 1 0 9 i c a le v 0 1 u t i o n p r o c e s so fg e n e t i cs e l e c t i o nt h e o r yo fd a r w i n ， i saw h o l en e w 9 1 0 b a lo p t i m i z a t i o na l g o r i t h ma n di sw i d e l yu s e di nm a n yf i e l d s w i t hi t sr e m a r k a b l ec h a r a c t e r i s t i co fs i m p l i c i t y ，c o m m o n a l i t y ， s t a b i l i t y ，p r a c t i c a b i l i t y ，s u i t a b i l i t yf o rp a r a l l e lp r o c e s s a n dh i g h e f f i c i e n c y 0 nt h em a j o rp r e m i s eo ff e a s i b i l i t yo f t h i st h e o r y ，t h i sa r t i c l eb a s e do nt h ep r a c t i c eo ff o r e r u n n e r s ， h a sd o n es o m ef u r t h e rr e s e a r c hw o r ka b o u tt h es e l f a d a d t e do f g e n e t i ca l g o r i t h mf o rc u r v er e c o n s t r u c t i o nf r o mp o i n tc l o u d w i t has a t i s f a c t o r yr e s u l t t h i sa r t i c l ei sd i v i d e di n t of o u rp a r t s t h ef i r s tc h a p t e r i n t r o d u c e st h eb a c k g r o u n da n da p p l i c a t i o no ft h ec u r v ea n d s u r f a c er e c o n s t r u c ti o na n dt h el a t e s tr e s e a r c hi nt h ew o r l d t h es e c o n dc h a p t e rb r i e f l yi n t r o d u c e st h er e s e a r c hh i s t o r y o fg e n e t i ca l g o r i t h ma n db i 0 1 0 9 i c a lb a c k g r o u n da tt h eb e g i n n i n g t弋 1 f 卜 硕士学位论文 t h e nd i s c u s st h eb a s i cr e a l i z a t i o nm e t h o do ft h ea l g o r i t h m ， i t s o p e r a t o r s ， i t sb a s i cc h a r a c t e r i s t i c s ， i t sa p p l i c a t i o n sa n d s e v e r a l t h o u g h tso f t h ea u t h o ra b o u th o wt ou s eg e n e tic a l g o r i t h mt os 0 1 v ep r o b l e m s i nf o r t h c h a p t e r ， a n a d a p t i v eg e n e t i ca l g o r i t h m i s p r e s e n t e df o r c u r v er e c o n s t r u c t i o nb a s e do nt h er e g u l a r d i s t r i b u t i o np r o p e r t yo ft h ep o i n ts e t w ed i v i d et h er e g i o n o fp o i n ts e ti n t om a n yg r i d sa n di ne a c hg r i dw ee l e c tap o i n t b yt h ea d a p t i v eg e n e t i ca l g o r i t h m b e c a u s eo ft h ea s y m m e t r yo f t h ed a t e p o i n t s i ne a c h g r i d ， h e r ew ei n v e s t i g a t et h e s p h e r e o f i n f l u e n c eg r a p h ( s i g ) w i t hs e v e r a le x t e n s i o n s ，w h i c h p r o v i d e san a t u r a ln o t i o no fp r o x i m i t yi no u rc o n t e x t ，t oa d j u s t e a c hd a t ad o i n tt h a tw eh a v ee l e c t e d w em a k et h e s ea d j u s t e d d a t ad o i n t si no r d e ra n dt h e nw ec a nr e c o n s t r u c tt h ec u r v eu s i n g b s p li n ec u r v eb a s e do nt h e s eo r d e r e dd a t ap o i n t s t h ef o r t hc h a p t e rg i v e sal o t so fe x a m p l e s ，w h i c hp r o v et h a t t h ea l g o r i t h mw ep r e s e n ti sf e a s i b l ea n ds i m p l e ， s p e c i a l l y ，a s t ot h es e l f i n t e r s e c tp o i n ts e ta n dt h ep o i n ts e th a v i n gc o r n e r d o i n ti tc a na l s ow o r ko u tas a t i s f i e dr e s u l t k e yw o r d s ：c u r v er e c o n s t r u c t i o n ：p o i n tc l o u d ：a d a p t i v eg e n e t i c a l g o r it h m 一，| p、 ， 基于自适应变搜索区间的遗传算法的点云曲线重建三 1 绪论 1 1 反求工程及曲线曲面造型 近年来，随着计算机视觉、数字图像处理以及c a d 建摸技术的发 展，反求工程 1 已经成为包括形状反求、工艺反求和材料反求等诸 多方面的复杂的系统工程。反求工程基于一个实物模型来构造出它的 设计模型，然后通过对重构模型特征参数的调整和修改达到对实物模 型的逼近和修改，从而满足新产品的各种需求。反求工程广泛应用于 新零件的设计、已有零件的复制、磨损零件的还原、模型精度的提高 以及数字化模型检测等。 反向工程技术的本质是对实物件进行测量，得到其原始数据( 扫 描线或点云) ，再对原始数据进行一定的处理来生成c a d 模型的相关 数字化技术和几何模型重建技术。由此可以看出，如何迅速高效地获 取高精度的实体表面几何数据是一切讨论的前提。到目前为止，主要 的数据获取方法有激光三角法，断层扫描法，接触式坐标测量仪法， 结构光摄影测量法等，这些方法在测量的速度，精度，适用范围，灵 活性等方面各有所长。 反求工程有两个重要的研究内容：一是如何快速、准确地获取产 品表面的原始数据，即产品表面数字化；二是如何完成高质量的曲面 重构技术。曲面模型主要用于描述被测物体的表面形状，而物体表面 经常由大量初等解析曲面( 如平面、圆柱面、圆锥面、球面等) 和自 由曲面经过延伸、过渡、裁剪等混合而成。因此，在构造模型前需要 硕士学位论文 根据曲面的不同特征进行区域分割，以保证局部细节的拟合精度。目 前常用的有三种分割算法 2 ：( 1 ) 四叉数法。该方法首先将整个曲面 看成一个整体，拟合一个单一曲面；然后检验误差是否满足要求，若 不满足则将曲面分为4 个；最后对一部分重复上述过程，直至每个子 曲面都能满足精度要求。( 2 ) 基于特征线方法。该方法通过寻找曲面 的尖锐过渡，曲率极值点以及曲面对称中心等特征作为曲面片之间的 边界，利用这些特征线将曲面分割，在每个子曲面上进行拟合。( 3 ) 基于面的方法。该方法首先给某个区域的点集赋予一个曲面表达形 式；然后按由近及远的顺序向外扩展，同时不断地检验曲面的拟合程 度，至误差超出预定要求时停止。四叉树法比较简单，对于曲率变化 缓慢的物体轮廓进行拟合容易实现。但是，对于复杂曲面特征网格能 够合理地反映复杂曲面的结构特征。 产品开发和制造过程中，许多产品的设计最初是通过实物模型来 描述的，这种模型可以是实验模型，也可以是已有产品的局部。把这 种模型转化为c a d 模型的过程称为实物反求。它是反求工程的一个重 要分支。实物反求的过程如下图1 所示。其中概念模型( 新设计) ， 也可是已有产品的零部件或其局部；三维数据采集可以有多种方式， 有接触式扫描( 如c 埘) ，和非接触扫描( 如激光扫描，光学扫描) ； 三维数据预处理主要是对数据点云去除大误差点和进行均匀化处理， 并转化成点云拟合系统可识别的格式( 例如s t l ，a s c i i 格式等) ；点 云拟合后再经适当处理就形成产品的三维c a d 模型。本文对实物反求 关键技术之点云拟合技术进行研究。 基于白适应变搜索区间的遗传算法的点云曲线重建 三 图卜1实物反求过程框图 点云拟合重建几何模型的方法有b e z i e r 曲线曲面与n u r b s 法， 偏微分方程法和能量优化法，散乱数据插值曲面法，自由型变技术法 等方法。如果在这些方法中选择适当的方法对自由表面的点云进行拟 合。是完全可行的。有许多学者对此进行了研究和探讨 3 5 。但由 于反求实物的具体形态是复杂多样的，有些并不是有单纯的自由曲面 构成，其中还有许多基本形体表面，如直线，圆弧，自由曲线，平面， 球面，圆柱面，圆环面等，而且有许多情况下，点云的数据量非常之 大。如果单纯用这些方法进行曲面拟合。不仅耗时多，对计算机硬件 的要求高，而且也不能最准确地反映原设计意图。因此在进行点云拟 合时，采用适当曲面拟合方法与特征识别技术相结合的策略，不仅使 数据处理大大简化，而且提高拟合的精度，使所得c a d 模型更准确地 反映设计意图。 要进行点云中的特征识别，首先要对点云进行分块。如果三维数 据点云已进行了适当预处理，滤去了扫描中的粗大误差点，并进行了 均匀化处理，那么三维点之间的排列并不是杂乱无章的，而是有一定 规律。不管以何种扫描手段获取的数据，经预处理后，相邻行之间的 硕士学位论文 点，其数据也是相邻的。那么用点云中相邻点组成的三角片的变化可 以搜索和划分表面及其边界。具体做法是每一数据点可与相邻两点组 成一个三角面片，而每个三角面片都有一个法向。这个法向与其所在 表面的法向变化相一致 6 ，7 。对于平面，圆柱，球面，环形体面， 锥面等基本表面。相邻三角片法向的变化具有一定的规律，如平面上 相邻三角片法向变化为零；圆柱面上沿坐标轴的相邻三角片法向的变 化应为恒定值，其他特征也都有响应的规律。 三维几何造型技术己在产品的开发、设计及制造过程中得到了广 泛的应用，但是仍有许多产品的设计并不完全源于设计运算，不能完 全由c a d 模型来进行表述，这种模型可能是已有产品的局部模型，也 可能是产品实验求解实物模型( 如飞机部件的风洞吹风试验模型) ， 还可能是根据概念设计效果图所制作的雕塑模型( 如汽车前脸方案的 油泥模型) 。 点云数据采集，实际上就是利用相应的测量或扫描设备对被测对 象进行测量或扫描，以形成产品三维实体模型的点云数据的过程。 1 2 点云拟合技术的定义 基于特征生长的点云拟合技术是根据已有的实物样件固有的几 何特征，构造具有一组约束变量的特征库，如平面、旋转面( 如圆柱、 圆锥、圆台、球) 、长方体、棱柱、棱锥、多面体、锥台、自由曲线 曲面、自定义的各种特征面( 如扫描面和放样面) ，实行变量驱动， 特征的变量通过追踪点云拓扑结构而自由生长，从而实现点云拟合的 基于自适应变搜索区间的遗传算法的点云曲线重建三 一种新的曲面重构技术。 该处定义的特征包括如下四个部分： ( 1 ) 由解析式所表示的图形，如直线、平面、圆、椭圆、抛物线、 双曲线、螺旋线、球、椭球、圆柱等； ( 2 ) 由几何定义所表示的图形，如圆锥、圆台、多面体、棱锥、锥 台，以及解析式所表示的曲线、曲面绕旋转轴或向导线运动所 形成的各种旋转面、扫描面、和放样面，以及各种特征经过布 尔运算得到的新的特征； ( 3 ) 自由曲线曲面特征 ( 4 ) 用户自定义特征 1 3 曲线重构 曲线重建问题在反求工程和计算机视觉中都有着广泛的应用。反 求工程( r e v e r s ee n g i n e e r i n g ) 的一个重要任务是由物理模型重建 出几何表示模型，这其中包括数据采集、预处理、曲面拟合和建立 c a d 模型4 个步骤 8 ，其核心问题是如何从采样点集出发重建出曲 线、曲面的模型。在计算机视觉中通常要考察如何从图像或扫描获得 的离散数据点重建几何模型，以利于形状分析和识别 9 。上述二者 都要求由已知的无序、带噪音的采样点集拟合出一条或多条曲线，反 映出该点集的形状和走向。 曲线拟合在逼近论和几何造型中都是一个重要的研究课题。随着 三维扫描技术的成熟，点云问题成为了一个倍受关注的热门问题。有 硕士学位论文 序散乱点曲线重建已经有了许多成熟的方法 1 0 一1 2 。对无序数据点 的曲线重建，近年来己逐步受到人们的重视。到目前为止，现有的工 作大致可分为3 类，第1 类方法采用回归或最小二乘拟合的方法。如 l e v i n ，l e e 等人利用m o v i n gl e a s t s q u a r e 方法，对原始点集进行 两次局部最小二乘回归，细化点云，重建出曲线 1 3 1 5 ，但这种方 法最大的缺点是所需计算量太大。第2 类方法主要采用图像细化的方 法来实现曲线重建。如p o t t m a n n 等人将原始的数据点集投影到平面 网格上，以生成二值图像，g o s h t a s b y 先由离散点构造势函数并生成 灰度图像，最后利用图像细化算法来得到重建曲线 1 6 ，1 7 ，但该方 法获得的重建曲线并不能很好地反映点云端点的形状，并且重建曲线 的准确性甚至正确性受到网格分辨率的影响。第3 类方法是由相应的 曲线模型出发，直接进行重建。如f a n g ，t a u b i n 等人分别利用弹力 模型与隐式曲线模型，把已知数据点作为约束条件，直接求解曲线参 数，得到重建曲线 1 8 ，1 9 。这种方法常需要优化或迭代求解，对于 噪音过多的数据点集，该方法也不够理想。n i n aa m e n t am a r s h a l l b e r n 等人提出的重建平滑曲线的c r u s t 方法，能很好的重建出平滑 曲线，但这种方法要求曲线形状上没有角点，分支，没有自交的情况。 e d e l s b r u n n e r h e 和m c k e 在1 9 9 4 年提出的q s h a p e 算法是一种分段 线性重建算法，该方法仅仅是针对无躁声采样点。近年来，也有学者 提出平面无序点集曲线重建的跟踪算法 2 0 以及基于场表示的平面 无序点集曲线重建算法 2 1 ，能够在某些方面克服前三类方法的弊 端，但是文献仅针对简单光滑曲线的重建问题，对于存在自交的情况 基于自适应变搜索区间的遗传算法的点云曲线重建 z 以及点云具有明显角点的情况还不能很好地解决；而文献当点云较为 复杂时，存在如何根据点云的自身性质自适应地选择一个合适的初始 曲线和加速迭代速度是较难克服的问题。 硕士学位论文 2 遗传算法 2 1 遗传算法的基本步骤 遗传算法的基本描述：算法开始于一个用染色体形式表达的初始 解集，总是用前一代解集的解来生成后一代解集的解，整个过程有一 个进化的思想，那就是新的一代总是要比旧的一代要好。因此在选择 产生新一代的父体时总是参照他们的适应值，适应值越大，再生的机 会越大。进化的过程不断进化，直到满足终止条件，比如进化的代数 或者适应值的改进趋势。 2 2 遗传算法的基本理论 遗传算法的基本步骤： s t e p l ：随机产生代表问题的n 个可行解的n 个染色体x 构成的初 始种群。 s t e p 2 ：计算种群中每一个染色体x 的适应值f ( x ) 。 s t e p 3 ：重复以下的步骤s t e p 4 至6 直到产生新的种群。 s t e p 4 ：按适应值越大，概率越大的原则从种群中选择两个父辈染 色体。 s t e p 5 ：以一定的交叉概率交叉父辈染色体来形成新的后代染色 体。 s t e p 6 ：以一定的变异概率变异新产生的后代染色体。 基于白适应变搜索区间的遗传算法的点云曲线重建竺 s t e p 7 ：检验终止条件是否满足，如果满足停止进化并返回当前种 群中的最优解，不满足则返回s t e p 2 。 2 3 遗传算法的基本操作 遗传算法包括三个基本操作：选择，交叉和变异。这些基本操作 又有许多不同方法，我们逐一介绍。 1 选择( s e l e c t i o n ) 选择是用来确定重组或交叉个体，以及被选个体将产生多少个子 代个体。首先计算适应度： ( 1 ) 按比例的适应度的计算( p r o p o r t i o n a lf i t n e s s a s s ig n m e n t ) ： ( 2 ) 基于排序的适应度计算( r a n k - b a s e df i t n e s s a s s i g n m e n t ) 适应度计算之后是实际的选择，按照适应度进行父代个体的选择。 可以挑选以下算法。 ( 1 ) 轮盘赌选择( r o u l e t t ew h e e ls e l e c t i o n ) ( 2 ) 随机遍历抽样( s t o c h a s t i cu n i v e r s a ls 锄p l i n g ) ： ( 3 ) 局部选择( 1 0 c a ls e l c e c t i o n ) ： ( 4 ) 截断选择( t r u c a t i o ns e l e c t i o n ) ： ( 5 ) 锦标赛选择( t o u r n a m e n ts e l e c t i o n ) 。 2 交叉概率( c r o ss o v e r ) 交叉是结合来自父代交配种群中的信息产生新的个体。依据个体 硕士学位论文 编码表示方法的不同，可以有以下的算法： ( 1 ) 实值交叉( r e a lv a lu e dc r o s s o v e r ) 离散交叉( d e s c r e t ec r o s s o v e r ) 中间交叉( i n t e r m e d i a t ec r o s s o v e r ) 算术交叉( a r it h m e t icc r o s s o v e r ) ( 2 ) 二进制交叉( b i n a r yv a l u e dc r o s s o v e r ) 单点交叉( si n g l e p o i n tc r o s s o v e r ) 多点交叉( m u l t i p l e p o i n tc r o s s o v e r ) 均匀交叉( u n if o r mc r o s s o v e r ) 3 变异( m u t a ti o n ) 交叉之后的子代经历的变异是子代基因按小概率扰动产生的变 化。依据个体编码的表示方法的不同，可以有以下的算法： ( 1 ) 实值变异 ( 2 ) 二进制变异 2 4 遗传算法的特点 遗传算法作为一种快捷、简单、容错性强的算法，在各类结构对 象的优化过程中显示出明显的优势。与传统的搜索方法相比，遗传算 法具有如下特点：搜索过程不直接作用在变量上，而是在参数集进行 了编码的个体。此编码操作，使得遗传算法可直接对结构对象( 集合、 序列、树、图、链和表) 进行操作。搜索过程是从一组解迭代到另一 组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解 基于自适应变搜索区间的遗传算法的点云曲线重建旦 的可能性，并易于并行化。采用概率的变迁规则来指导搜索方向，而 不才采用确定性搜索规则。对搜索空间没有任何特殊要求( 如连通性、 凸性等) ，只利用适应性信息，不需要导数等其他辅助信息，适应范 围更广。 遗传算法的优点是它的并行性，在解空间的多个点同时进行搜 索，因而很少陷入局部最优解。遗传算法比较容易实现，一旦你编了 一个遗传算法程序，解决不同的问题时，往往你只需要修改编码方案 和适应值函数就可以了，当然这个容易只是相对的，因为编码方案和 适应值函数的选择有时候会变得很难。 遗传算法的缺点是计算时间，比某些方法要稍微长一些，但是对 于今天的高速计算机而言这并不是一个很大的问题。 2 5 遗传算法的应用情况 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依 赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛用于 很多学科领域，经常被用来解决复杂问题，像n p 难题，机器学习， 程序进化，甚至在艺术方面被用来生成图片和音乐。它的一些主要应 用领域有： 非线性动力系统数据预测和分析 神经网络设计 l i s p 程序设计 策略计划 硕士学位论文 蛋白质分子形状研究 t s p 和计划表 图像创建 2 6 遗传算法应用中的几个关键问题 基于文献 2 2 2 5 以及具体的实践经验，我们总结了遗传算法应 用中的几个关键问题。当我们打算应用遗传算法来解决某个问题，面 临的第一个问题是当前问题适不适合用遗传算法来处理? 我们解决 某些问题，经常是在很多解中搜索，可行解构成的空间称为搜索空间， 该空间中每一个点代表一个解，每一个可行解由问题的本身的函数值 或适应值评估优劣，我们寻找的解只是搜索空间中的一个点而已。求 解过程经常等同与在搜索空间寻找极值( 最大值或最小值) ，通过统 计搜索时间可以预知搜索空间的大小，但是经常是我们只知道当中的 一些点，而随着搜索的进行自动生成其他点。已经发展了很多搜索方 法，比如枚举法，爬山法，随机法，处理一些问题特别是局部最优非 常少时这些方法非常有效。但是有些问题的解的搜索有时非常复杂， 它有很多的局部最优解，而先前的算法一旦陷入了某个局部最优解， 就很难在跳出来，这个时候我们就应该考虑使用遗传算法来解决问 题。但是必须记住，用遗传算法找到的解经常只是被认为是一个好的 解，因为很可能没有办法证明它是真正的最优解。 处理各种各样的问题时，总的基本步骤都查不多，但是各个步骤 具体实现往往差异很大，这就需要创造性思维。我们面临的第二个问 基于自适应变搜索区间的遗传算法的点云曲线重建旦 题是选择怎样的编码来实现染色体。 这个首先与其解决的问题本身的特点密切相关，其次要使得交叉 和变异这两个基本的遗传算子的易于实现。解决实际问题的实践中产 生很多编码方案： ( 1 ) 二进制编码 ( 2 ) 实值编码 基于历史原因过去人们常常使用的是二进制编码，现在绝大部分 相关研究使用的是性能相对较好的实值编码。 第三个问题：选择什么样的交叉和变异算子? 整个遗传算法的实现过程中，可以说交叉和变异是相当重要的两 个环节，算法的性能主要由这两个算子影响，在具体应用中，要求具 体问题具体分析，这里是一个要求见多识广和充分发挥主动能动性的 地方。 第四个问题：遗传算法的参数选择 在运行遗传算法程序时，需要对一些参数作事先选择，它们包括 种群规模，交叉率，最大进化代数，这些参数对遗传算法的性能都有 很重要的影响。对这些参数有以下建议： ( 1 ) 种群规模： 一般来说，较大数目的初始种群可以同时处理更多的解，因而更 加容易找到全局最优解，但是实践表明，巨大的种群规模并不能提高 算法的性能，因为每次再生的迭代时间会加长，好的种群规模大约为 2 0 1 0 0 ，好的种群与编码方案也有关系。 硕士学位论文 ( 2 ) 交叉概率 交叉概率的选择决定了交叉操作的频率，频率越高，可以越快地 收敛到最有希望的最优解区域，因此通常选择较大的交叉率，一般为 6 0 9 0 ，不要设为1 0 0 ，因为太高的交叉概率会导致过早收敛。 ( 3 ) 变异概率 变异概率相反通常应当很小，一般设为5 2 5 。若设为1 0 0 退化成随机搜索，这样极其不稳定，设为o 容易陷入局部最优点而 导致早熟现象。 ( 4 ) 最大进化代数 最大进化代数作为一种模拟终止条件，一般视具体情况而定，计 算量小的问题取1 0 0 5 0 0 即可，而计算量大的问题，可能取到l o o o o 等值。 对于具体问题而言，衡量参数设置恰当与否，要依据多次运行的 收敛情况和解的质量来判断。如果调整参数难以有效地提高遗传算法 的性能，则往往需要借助对基本遗传算法的改进，改进的手段可以是 多方面的，如适应度比例的调整，引入自适应交叉率和变异率，尝试 其他的遗传操作，甚至采用混合方法。 基于自适应变搜索区间的遗传算法的点云曲线重建堕 3 基于自适应遗传算法的点云曲线重建 3 1 多种参数的动态自适应确定 一般遗传算法有三个关键的进化参数：( 1 ) 适应度函数f ( x ) ( 通过 线性定标，o 截断或是乘幂标等方法确定) ( 2 ) 选择概率p m ( 3 ) 杂交概 率p c ( 完全由算法设计者根据其经验设定) 。即以上关键的进化参数 都是算法使用者在算法运行之前确定，在算法进行过程中无法对其进 行动态修改。因此，算法缺乏动态的生命力，导致算法的在线性能与 离线性能降低。本文在遗传算法执行过程中，三个关键参数都动态地 根据染色体个体当时的情况确定，因此算法具有自适应性，从而能够 以概率为1 搜索到全局最优解。 1 适应度函数f ( x ) 的动态确定 f ( x ) = w o r s t + ( 缈1 铀e s 。w o r s 。) 卡( 取) 。w o 贼) ( b 6 。w 0 政)坟x ) k 1 a v g ( 3 一1 ) 1w o r s t + ( 砚铀e s t w o r s t ) 木( 坟x ) 一w o r s t ) ( b 6 t - w o r s t )f i x ) k 1 冰a v g 时，算 法将动态地将其适应值降低( 缈1 越小，适应值降低的程度就越大) ， 从而很好地抑制了局部最优解的出现。但f ( x ) k 2 水a v g 时，算法将动 态地将即将死亡的个体的适应值相对提高( 国2 越大，适应值提高的 程度就越大) ，从而在一定程度上延缓了这些个体的死亡，保证了群 硕士学位论文 体个体的多样性。 k 1 ，k 2 两常数需根据具体函数，具体情况动态确定。根据( 1 ) 式，若某个染色体的适应值大于平均适应值的k 1 倍，算法则自动的 调节将其适应值减少；若某个染色体的适应值小于平均适应值的k 2 倍，则算法自动调节将其适应值增大。因此，当b e s t ，w o r s t ，a v g 均为正值时，k 1 ，k 2 越小则动态确定的适应度函数使群体中各个个 体的适应度差距变小，增加了多个个体进入下一代的概率，保证群体 的多样性k 1 ，k 2 越大则动态确定的适应度函数将拉大群体中各个个 体的适应度，是适应度高的个体很快占绝对优势，迅速收敛到全局最 优解。 因此，我们提出在进化初期采用较小的k 1 ，k 2 值，较小的国1 值， 较大的功2 值；在进化后期采用较大的k 1 ，k 2 值，较大的纠值，较小 的彩2 值。 2 杂交概率和变异概率的动态确定 杂岑岂概率p c = k 2 ( g e n e r a t i o n “r a n d ( 1 n v a r s ，1 p o p s i z e ) ) 。 ( 3 2 ) 选择概率p m _ k l ( g e n e r a t i o n “( 1 n v a r s ) ) 。 ( 3 3 ) 其中k 1 ，k 2 为常数，由实验动态确定。g e n e r a t i o n 为进化代数，n v a r s 为染色体的长度，p o p s i z e 为每代群体的规模。 这样确定的p c ，p m 值随着进化代数而随机进行自适应的更新。 总体来说，p c ，p m 在进化初期较大，随着进化的发展，p c ，p m 值逐 基于自适应变搜索区间的遗传算法的点云曲线重建 旦 渐变小。从而完全符合进化发展规律。 定义： 尸：( f ，) ：p ，( 1 一p 。) 叫川，e ：如，lr，其中 d ( f ，) = k ，f 。，l 七蹦船j 表示的是个体f 和之间的h a m m i n g 距 离，z = 刀p 阳砌船p ：( j ，) 表示由种群x ”到种群y ”的转移概率，即 p ：( f ，) = p 】厂”= ，x ”= ， 。 ( 3 4 ) 6 。= m a x 尸：t ( f ，nf ，f _ ，ej 2 ( 彳。胛( 1 一彳咖船) ( 删船川) 一 3 5 d 。= m i n 伽：( f ，歹) ，f 歹，f ，ej 2 ( 彳l 喇胚) ( 1 一彳l 瑚船) 。3 6 nn 显然，只要满足p o p s i z e 2 木n v a r s + l ，则有 ( 1 ) 妻 ( b n ) 脚妇】 o o ( 3 7 ) ( 2 ) d 。= ( 3 8 ) 根据参考文献 2 6 2 7 能够从理论上保证对于仅带选择( 杰出者 选择以及最佳值选择) 和变异的遗传算法几乎必然强收敛到全局最优 解。 为了进一步加强算法的收敛性，本文提出对遗传算法个体的变异 位个数也采用自适应方法确定。 n ( i ) = c e i1 ( n 术( b e s t f ( i ) ) ( b e s t w o r s t )( 3 9 ) 其中n 为常数，一般为染色体长度的1 4 到1 3 。f ( i ) 为染色体 个体的适应值，b e s t ，w o r s t 为群体中最大和最小的适应值。可以看 出，适应值大的个体发生变异的位数少，从而保证其稳定性：适应值 硕士学位论文 差的个体发生变异位数多，在一定程度上增加了群体个体的多样性。 3 2 搜索区间的动态自适应确定 用一般的遗传算法求解非线性方程，无须考虑求根区间( 即使在 选取的区间无根或有多个根) 和初始值选择问题，但存在如下两个缺 点： ( 1 ) 很难收敛到精度要求很高的最优解，如果盲目地通过扩大群 体规模来提高精度，将很大程度地增加算法的时间复杂度。 ( 2 ) 当任意给定的求根区间中存在多个解时，一般的遗传算法只 能收敛到其中一个解。 本文提出了g a n e 算法克服了此两缺点，它能够保证在有限步内 进行很有效的判断并搜索到最优解( 有解存在的情况) ，对f ( x ) 本 身性质不作任何要求( 如不要求f ( x ) 连续) ，也无须考虑奇点存在 的情况，而且在初始区间有多个解存在的情况下也能有效地同时搜索 到各个解。 在g a n e 进化过程中，自适应地根据在上个世纪( 若干年代的总 和) 中产生的最优解b e s t x 将搜索区间划分成 d o w n ，b e s t x 和 b e s t x ，u p 两个区间，分别在这两个小区间中进一步搜索，如果在 某个小区间中经过若干世纪进化未搜索有比b e s t x 更优的染色体则 将该区间舍去，如果在某个区间中经过若干世纪的进化搜索出比 b e s t x 更好的染色体b e s t x ，则使b e s t x 成为新的区间分界点， 将其所在的原区间进一步分为两个更小的区间，这样不断在各个新的 ， 基于自适应变搜索区间的遗传算法的点云曲线重建 小搜索区间递归地调用动态自适应的遗传算法，直止达到精度要求或 小区间宽度为零为止。以下以含两个根的初始区间为例来说明一下具 体的算法： 适应值函数：f ( x ) = c “：“x ) i f f ( x ) 精度要求) o r ( d o w n l = = u p l ) g e n e r a ti o n ( d o w n l ，u p l ) ： i f ( ( u p l 一b e s t x ) ( d o w n l 一b e s t x ) )a n d ( f ( d o w n l ) 精度要求) o r ( d o w n 2 = = u p 2 ) g e n e r a t io n ( d o w n 2 ， u p 2 ) ： if( ( u p 2 一b e s t x ) ( d o w n 2 一b e s t x ) )a n d( f ( d o w n 2 ) f ( u p 2 ) ) u p 2 = b e s t x ： e l s e d o w n 2 = b e 乩一x ： e n d e n d b e s t x 2 = b e s t x ： 3 3 曲线重建算法 3 3 1 相关定义 数据点集：s ： 、，。：。，y ) j ：1 为已知平面上一组离散的带误差 的无序采样数据点。 点的邻域：p 为点集s 中的任一点，定义点p 的p 一邻域为 m 。( p ) = qd ( p ，q ) p ，q r2 。 点集的邻域：点集s 的p 一邻域定义为j ( s ) ：um ，( p ) 。 采样密度：s 为一组采样数据点，若存在一个最小的正数p ，s 中任意一点的p 一领域内都含有s 中的其它数据点，则称s 的采样密 度为p 。 基于自适应变搜索区间的遗传算法的点云曲线重建型 p 一道路连通：a ，b 为点集s 中的任意两点，如果存在s 中的一 组点列 p 0 ，p 。，p 。) 满足d ( p ；，p ) p ，( i = 0 ，n 一1 ) ， 且p 0 - a ，p 。= b ，则称a ，b 两点p 一道路连通。若点集s 中任意两点都 是p 一道路连通的，则称点集s 为p 一连通的。 p 一连通子集：p 为点集s 中的任意一点，称s 的包含p 点的p 一 连通子集为q = q lp ，q 两点p 一道路连通，q s ) ，也称之为p 一连 通分支。可知，但s 只有一个p 一连通子集时，s 是p 一连通的。 根据上述定义，可以得到点集s 具有如下性质。 性质1若点集s 是p 一连通的，则它的p 一领域是一个连通区域。 3 3 2 点云区域分割 t 锄a sv a r a d y 等人将基于实物的反求工程c a d 建模