（作物遗传育种专业论文）曲线和曲面拟合的改良缩张算法.pdf

万林生：曲线和曲面拟合的改良缩张算法 三 曲线和曲面拟合的改良缩张算法 研究生：万林生 导师：顾世梁教授 中文摘要 回归分析是描述交数之间数量化关系的统计分析方法，相比其它统计方法而 言，有更悠久的应用历史，由于其应用的假定条件大多能够得到满足，统计推断 的基础牢固，故结论也较为可信。线性( 一元或多元) 回归分析求算过程比较简 单，也有许多软件可供选用，易为大多数使用者掌握，因而线性回归分析得到了 极大程度的应用。然而，绝大多数农学、生物学、经济学或者其它许多领域中的 变数间的量化关系并非线性，线性仅是非线性关系中的一个特例。相比于线性回 归分析的广泛应用，以非线性方程描叙变数问数量关系的非线性分析研究、应用 进展比较缓慢。究其原因主要是曲线和曲面拟合即非线性方程的最优参数估计非 常复杂，由于缺乏普遍适用的算法，一般难以得到最优参数估计。纵观业已存在 的曲线、曲面拟合即参数估计的算法，主要有解析法和直接法两大类。 本文对这两大类方法中出现的一些比较常用的方法迸行总结介绍，分析各种 方法的优点及其局限性。解析法是以解q 的偏导方程为特征的，其最大的优点就 是能够利用偏导函数指导搜索寻优方向，搜索效率比较高，在较适合的初始值条 件下，可以较快实现目标函数的优化。但该类方法以非线性方程的偏导函数为基 础，而有些非线性方程很复杂，不易获得其所有偏导数；并且对于大多数拟合方 程而言都必须提供合适的初始值，否则很容易陷入局部最优的陷辨，所估参数并 非最优。直接法是以将参数点代入目标函数直接迭代估计为主要特征的，其最大 的优点就是省去了提供偏导数的麻烦，可适用于各种类型的非线性关系，通用性 较强。但其缺点是搜索效率比较低，在参数较多且非线性关系复杂时，实现全局 最优的能力较低。顾世梁等多年前提出的一种以步点为主要特征的直接法缩 张算法，在曲线和曲面拟合中有较好的效果，对绝大多数问题均能实现大范围初 值的全局最优拟合，此外该算法对大多数较复杂的约束和非约束非线性规划问题 全局最优解也有突出表现，但是该算法也存在直接法所普遍存在的拟合效率不高 的问题。 为了能更加有效地实现各类非线性回归分析，促进非线性回归的广泛应用， 本文对曲线和曲面最优拟合方法进行重点研究，对原有的性能较好的缩张算法作 扬州大学硕士学位论文 2 了步长、中心点调整等若干改进，其中最主要改进之处在于以此算法为基础，结 合数值微分技术及解析法中改良高斯。牛顿法，建立了曲线和曲面拟合的新算法 改良缩张算法。新算法主要利用缩张算法对各种类型非线性模型的通用性以 及跳出局部最优陷阱的能力，实现目标函数的全局最优；利用结合改良高斯牛顿 法，加速回归统计数迭代逼近，其中曲线和曲面方程对各回归统计数的偏导函效 将采用数值微分技术，既免去提供偏导函数的麻烦，又能以近似偏导函数指导寻 优进程，提高非线性统计数估计的效率。以上述两个关键技术有机结合构建的新 算法可将各步骤的优点充分发挥，而又能克服它们单独运用时的缺陷，极大程度 地提高实现曲线和曲面拟合的能力，为非线性回归分析建立坚实的基础。本文对 于新算法以m a t l a b 为平台编制了算法软件，以各种模拟和实例验证其功效。模 拟和实例验证表明，新算法具有较高的拟合效率和唯一准确的拟合结果。 关键词，非线性方程；缩张算法；参数估计；最优化；数值微分；程序 万林生：曲线和曲面拟合的改良缩张算法 c u r v ea n ds u r f a c ef i t t i n gw i t hi m p r o v e d c o n t r a c t i o n - e x p a n s i o na l g o r i t h m s u p e r v i s o r ：p r o f s h i l i a n gg u a b s t r a c t 3 r e g r e s s i o na n a l y s i si sas t a t i s t i c a lm e t h o dw h i c hq u a n t i f i e st h er e l a t i o n s h i p b e t w e e nv a r i a b l e s l i n e a rr e g r e s s i o na n a l y s i sh a sal o n g e ra p p l i e dh i s t o r yt h a nm o s t o t h e rs t a t i s t i c a lm e t h o d s f o rm o s t a p p l y i n ga s s u m p t i o n sc o u l db es a t i s f i e d ，i t s s t a t i s t i c a li n f e r e n c ei sv a l i do nt h ew h o l e t h er e s u l t sf r o mr e g r e s s i o na n a l y s e sa r e r e l i a b l eo nm o s to a s e s b e s i d e s ，t h ep r o c e d u r eo fl i n e a rr e g r e s s i o na n a l y s i si sr e l a t i v e s i m p l ea n dc a nr u no nm o s ts t a t i s t i c a ls o f t w a r e m o s tu s e f s 锄e a s i l yh a n d l et h e m e t h o d , s oi th a sb e e nw i d e l yu s e di nm a n yf i e l d s h o w e v e r , t h er e l a t i o n s h i pb c t w c a l v a r i a b l ea r er a r e l yl i n e a r , m o s ta c c u r a t ef u n c t i o n sb e t w e e nc a u s a lt r a i t sa n de f f e c to n e s a r en o n l i n e a r ，l i n e 翘rr e l a t i o ni sj u s ta s p e c i a lc a s eo fn o n l i n e a rr e l a t i o n s h i p c o m p a r e d w i t he x t e n s i v ea p p l i c a t i o no fl i n e a rr e g r e s s i o n , n o n l i n e a re q u a t i o n sw e r er a r e l yu s e dt o d e s c r i b er e l a t i o n s h i pb t 出a 啪nc o n c e r n i n gv a r i a b l e si nm o s tr e s e a r c h i n g 丘e l d s 。如b a p p l i c a t i o no f n o n l i n e a rr e g r e s s i o na n a l y s e sa f ef a rm o r el a g g e db e h i n do t h e rs t a t i s t i c a l m e t h o d s 髓她r e a s o ni st h a tc i l r v ea n ds u r f a c ef i t t i n g 。a l s or e f e r r i n g 鹊o p t i m a l p a r a m e t e r se s t i m a t i n go fn o n l i n e a re q u a t i o n s ，i sm u c hm o r ec o m p l i c a t e dt h a nl i n e a r r e g r e s s i o n l a c k i n gp r o p e ra l g o r i t h ma n ds o f t w a r e ，t h eo p t i m a la a i n gi s u s u a y d i t t i e u l tt or e a c h t h e r eh a sb e e nt w oe x i s t i n gc u r v ea n ds u r f a c ef i t t i n g a l g o r i t h m s ： n a m e l y , a n a l y t i ca n dd i r e c tm e t h o d s t n 圮t h e s i si n t r o d u c e ds o m ec o n t l l l o nm e t h o d so f a b o v et w oc l a s s e sa n da n a l y z e d t h ea d v a n t a g ea n dd i s a d v a n t a g eo ft h e m t 1 1 ea n a l y t i cm e t h o di sd 吣噬a d e f i z e db y s o l v i n gt h ep a r t i a ld e r i v a t i v e se q u a t i o n so fo b j e c t i v ef u n c t i o nq ma d v a n t a g eo ft h i s k i n d o fm e t h o d si st h a tt h e yc a l lu s ep a r t i a ld e r i v a t i o nf u n c t i o n st og u i d et h es e a r c h i n g d i r e c t i o na n dt h es e a r c h i n ge f f i c i e n c yi su s u a l l yh i g l ls ot h a ti tc a na c h i e v eo p t i m i z e d o b j e c t i v ef u n c t i o nw i t hl e s st i m ep r o v i d e dp r o p e rg i v e ni n i t i a l s h o w e v e r , t h ea n a l y t i c m e t h o d ，w i t hp r e c o n d i t i o no ft h ep a r t i a ld e r i v a t i o nf u n c t i o n , w a sh a r dt oo b t a i na l l p a r t i a ld e r i v a t i v ef u n c t i o n sf o r t h ec o m p l e x i t yo fs o m en o n l i n e a rf u n c t i o n s f u r t h e r m o r e ， a p p r o p r i a t ei n i t i a lv a l u e sw e r ed i f f i c u l t yt os e ti np r i o r , o t h e r w i s ei tc o u l de a s i l yb e t r a p p e di nl o c a lo p t i m a l ，a n dt h e 西o b a lo p t i m i z i n gn o n l i n e a rp a r a m e t e r sc o u l dn o tb e e a s i l yo b t a i n e d t h ed i r e c tm e t h o di sc h a r a c t e r i z e db yd i r e c ti t e r a t i v ee s t i m a t i o no fp a r a m e t e r so f 扬州大学硕士学位论文 。4 n o n l i n e a rf u n c t i o n t h ea d v s n t a g eo ft h i sm e t h o di sn o tn e e d e dt oo b t a i l lt h ep a r t i a l d e r i v a t i v e sa n ds u i t a b l ef o ra l lk i n d sn o n l i n e a re q u a t i o n s 。h o w e v e r , l o w 鼹甜幽 e f f i c i e n c ya n dp o o rg l o b a lr e a c h i n ga b i l i t ye s p e c i a l l yf o rt h o s eb i gp a r a m e t e rn u m b e r s i t u a t i o n sa t h em a j o rd i s a d v a n t a g e s t h ec o n t r a c t i o n - e x p a n s i o na l g o r i t h m , ad i r e c tm e t h o dp u tf o r w a r db ys h i l i a n g g ue ta 1 缸1 9 9 8 ，c h a r a c t e r i z e db ys e a r c h i n gf o rt h eo p t i m a lp a r a m e t e rv e c t o ri nt h e u n i f o r md i s t r i b u t e dp o i n t si n pd i m e n s i o n a ls p a c e ，h a dg o o de f f e c ti nc u r v ea n ds 触 f i t t i n ga n dc o u l da c h i e v et h eg l o b a lo p t i m a lf i t t i n gi naw i d er a n g eo fi n i t i a lv a l u e s i t c o u l da l s os o l v es o m ec o m p l e x “m s t 陷i n c dn l p s i m i l a rt ot h o s ed i r e c tm e t h o d s ，i ta l s o h a dt h el o we f f i c i e n tp r o b l e m i no r d e rt op r o m o t ee x t e n s i v ea p p l i c a t i o no fn o n l i n e a rr e g r e s s i o n , t h i st h e s i s f o c u s e do nt h em e t h o do fc u r v ea n d 研f h c ef i t t i n ga n dm a d es o m ei m p r o v e m e n t0 1 1c - e a l g o r i t h mb ys t e pl e n g t ha n dc e n t r a lp o i n t 硼l l s n n e 眈1 kf e e d b a c ks y s m m , u s i n g 蝴s p f c a do fs p r i n gp o i n t st o 嘶u s ts e a r c hs t e pk n g i h w 勰v a o r es e n s i t i v et h a n p r e v i o u so n e 砸壕m o s ti m p o r t 砸ti m p r o v e m e n ti st oc o m b i n ec - ea l g o r i t h m 谢t h 缸l a m cm e t h o d , l c v e n b e r g - m a r q u a r d tm e t h o d 田地n 钾m e t h o dc o u l du t i t i z eg e a l g o r i t h mt oj u m po f fl o c a ln l i n 嘞a n d i a p tt h en u m e r i c a ld e r i v a t i v e st og u i d e a r c h i n gd k e c l i o n , i tc o u l dr e 斌i z eg l o b a lo p 蝴o no fo b j e c t i v er u n d o nf o r m o s tp r a c t i c a lo u r v oa n ds u r f a c ef i t t i n gp r o b l e m s 1 1 砖n 鲫c - ea l g o r i t h m , c o m b i n i n g t h ea d v a n t a g e sa n do v e r c o m i n gt h ed i s a d v a n t a g e so ft w ok i n d so fm e t h o d ，g r e a t l y e n h a n c e da b i u t yt or e a c ht h eg j o b a lo p t i m a le s t i m a t i o no fn o n l i n e a rp a r a m e t e r sa n d e s t a b l i s h e das o l i df o u n d a t i o nf o rn o n l i n e a rr e g r e s s i o na n a l y s i s t h en 哪m a t l a b p r o g r a mw a sc o m p i l e db a s e do nt h ei m p r o v e da l g o r i t h l n a n dv a r i o u sk i n d so fm o d e l s a n de x a m p l e sw e f eu s e dt od e m o r 曲a t ei t sf u n c t i o n k e yw o r d s ：n o n l i n e a re q u a t i o n ；c o n t r a c t i o n - e x p a n s i o na l g o r i t h m ；p a r a m e t e r e s t i m a t i o n ；o p t i m i z a t i o n ；n u m e r i c a ld i f f e r e n t i a t i o n ；p r o g r a m 万林生：曲线和曲面拟合的改良缩张算法 l 引言 1 1 论文背景 回归分析是描述变数之间数量化关系的统计分析方法，主要是利用最小平方法 确定自变数与依交数量化关系，并对目标变数作出数值分析和预测自 k g o l t o n l 8 8 6 年首次将其应用于身高的遗传分析以来已有t 0 0 多年的历史，这是比 f 测验、方差分析等应用更早的统计分析方法。相比于其它统计方法而言，回归分 析应用的假定条件大多能够满足，统计推断的基础牢固，结论也较为可信。在回 归分析中一元线性和多元线性回归相对应用比较广泛，其求算过程相对比较简单， 一般采取最小二乘法即可精确计算各回归统计数并且能根据求算的一些中问量对 各统计数进行正确的演i 验与参数区间估计【l 刁。目前，一元或多元线性回归方法被 几乎所有的统计软件所包含，也为广大使用者提供了极大的方便，这也是该方法 被广为应用的最主要的原因之一。纵观业已发表的有关回归分析的文献，一元或 多元线性回归仍然占有相当大的比例，并且涉及到的研究领域也较为广泛【3 d 3 1 然而线性回归被广泛的运用并不代表其普遍适用，在绝大多数农学、生物学、 经济学或者其它许多研究领域中变数问的量化关系并非线性，如作物生产中产量 依肥料使用量的关系、禾谷类作物茎蘖动态变化过程、生物干物重随生长过程的 累积、叶面积指数与作物产量的关系等都是非线性关系，线性仅是非线性关系的 一个特例对于诸如此类非线性问题的解决如果仅仅停留在线性回归上将极有可 能会得到与实际情况相差较远甚至完全不同的结论，给研究本身带来了比较大的 影响。虽非线性关系普遍存在，但以非线性方程描述变数间数量关系的非线性回 归分析的研究与应用进展却较为缓慢，近年来曲线或曲面拟合的应用文献虽有所 增秒1 4 - 2 5 l ，但非线性回归分析的应用仍然稀少且过于简单，这也是与普遍存在的 非线性关系很不相称。 非线性回归之所以应用比较少，究其主要的原因是该回归分析方法的研究相对 比较复杂，难以被大多数使用者所掌握和接受，这种复杂性主要集中体现在以下 三个方面：1 、非线性关系的可能模型数量众多，对于研究的变数之间选择合适的 模型比较困难；2 、曲线或曲面拟合即非线性方程的最优参数估计非常复杂，由于 缺乏普遍适用的算法，即使模型是适合的，一般方法也是较难得到最优参数估计； 3 、非线性模型及回归统计数的测验相对不成熟，未能如线性回归那样准确地测验 扬州大学硕士学位论文 其显著性，从而进行稳健的统计推断。应该说，若想对非线性回归方法有所突破， 就必须要解决以上三个问题，只有有效地解决好这些问题，非线性回归方法才能 更加广泛的应用 相对而言，上述第二点曲线和曲面拟合即非线性回归统计数的估计难度最大 除了极少部分简单的二参数非线性及多项式方程可用变量转换的方式将其转化为 线性关系【2 9 】，采用线性回归方法近似求解外，绝大多数非线性统计数估计需直接 以离回归平方和( 置嚣，o rq ) 作为目标函数，在一定初值条件下迭代逼近，使目 标函数趋于最小，从而得到最优估计的非线性回归统计数。由于在非线性方程参 数的求解过程中不存在解析解，因此也只能通过算法和软件迭代逼近。因此，非 线性方程的参数估计就成为大多数应用工作者最大的难题，这也是一些相关网站 热问0 除q ) 的话题。 为了验证和改善非线性拟合算法和软件的可靠性和精确性，美国国家标准和技 术研究院( n i s d 统计参考数据集( s t r d ) 公示了用于各类型的非线性方程的2 7 组 袁、中、低难度的数据及业已验证i & 固的结果【3 0 ，3 u 。， 堑型奎兰堡主鲎垡笙奎 里 则屯在此处的增加将使脚变大；若a i r _ s $ 。时，喜( y 一八x ，6 ) ) 筹= 厶屯= 为负，它的方向是朝着使脚减小 的方向若筹 。时，喜( y f ( x ，坳著= 屿= 色为正对，它的方向是朝着便 g s s 减 、的方向所以，只要在原( 6 ) 的基础上加上，均是朝着使置豁减小 的方向，因此，梯度法回归参数的迭代公式为： b ! = 0 - r e a o j妒= b 。j + k a j ( s ) 这是，是迭代的轮次，七是一个常数，七的选择还应取决于： 麟g 呜+ k a ) s 魅s ) ( 6 ) 逐步迭代后，将使屯趋于最优。 2 3 1 2 高斯牛顿法 在某一优化参数点6 ( o ) 处，将夕= ，何，6 ) 按多元t a y i o r 级数展开，略去二次及 二次以上各项得： 露= f ( x i 泖2 和+ 警五+ 警兄+ + 考乃+ + 薏彩c 7 ， 乃= 乃一垆 ( 8 其中厶，等，分别为初始参数点6 ( o ) 处依西的非线性回归值及偏导函数值，乃 为第，参数在吩与垆问之差值因而，方程( 2 ) 可以转化为； q 2 著n 嘶以彤) ) 2 = 荟n ( 】；一十鲁西+ 薏晚+ + 警炉( 9 ) ，- l f ；1 叻哟功n 对方程( 9 ) 求偏导数，即： 万林生：曲线和曲面拟合的改良缩张算法 虿a o = 酗至警考+ 而砉卺考+ + 哆薹孥孥一耋考t 五一乃n 从而得到p 个偏导方程令嘶= 争堑a 。j 塑o t , k ，啊= 薹秘嘶测可以觚 i a l l 8 1 + a 1 2 a 2 + ”+ a l p 昂2 a l y j a 2 1 8 1 + a 2 z a z + + a 2 p 哆2 a 2 y用矩阵表示即为：a a ( 1 1 ) r l a p l i 3 1 + a p 2 8 2 + + 口彤= 勺7 其中= ( 8 1 ，屯，艿f ，) 是在6 ( 处能使目标函数减小的回归参数增量可由 a = 4 1 k 解出a 并由公式( 5 ) 得到新的优化点6 ：b = 6 ( o ) + a 。当6 与6 ( o ) 有差 异时，应令6 替代6 ( o ) 重新计算出新的反复迭代直至a 趋于0 或q 在前后轮的 差异小于某一定值为止 2 3 1 3 改良高斯一牛顿法( m a r q u a r d t 法) m a r q u a r d t i s l 捌法是结合梯度法和高斯牛顿法附3 1 爿1 而产生的一种方法由 方程组( 1 1 ) 求解a 的过程中，由4 社 孟= l ，2 , - ，p ) 所组成的p 。p 阶2 a c c o b i 矩阵彳 很可能是奇异的，无法求其逆阵。因此需对4 阵作适当调整。通常可将一小正数 a ( o a o ，则计算新点的接受概率：p ( 们= e x p ( - y 忙9 ) ，产生【o ，1 】 区间上均匀分布的伪随机数，【o ，l 】。着ps ，则接受新点作为下一次模拟的 初始点；否则仍取原来的点作为下一次模拟退火的初始点。 以上步骤称为m e t r o p o l i s 过程，按照一定的退火方案逐渐降低控制温度，重 复m e t r o p o l i s 过程，直至达到结束准则，就构成了模拟退火算法，算法能收敛到全 局最优点或近似全局最优点。在同一温度下，重复m e t r o p o l i s 过程的次数称为马尔 可夫链长 对于理想的模型，经典模拟退火算法在下述条件下收敛于全局最优解：初始 温度足够高，降温速度足够後，终止温度足够低。在理论上模拟退火算法要对每 个温度通过多次迭代达到平衡，当温度从足够高降到足够低时，就可以求出目标 函数的最小值，即全局最优解。但是，在每一温度下达到目标函数的平衡，需要 的迭代次数是非常多的，而且理想的退火过程要求温度连续下降，这也是难以达 到的，这些都是模拟退火法效率不高的重要原因。由此，初始温度的确定、解的 万林生：曲线和曲面拟合的改良缩张算法 产生机制、结束准则的确定、计算效率和计算精度的平衡，都是构造模拟退火算 法的重要问题。作为一种随机性搜索方法，模拟退火算法还有如下缺点：没有充 分利用当前领域知识，搜索序列不单调，在低温下很难跳出局部极小点。 2 3 2 2 三次设计结合模矢法 三次设计是针对大体已知范围的参数进行优化，而模矢法是针对未知范围的 参数进行优化，通过计算机编程上两者的紧密融合，同时对参数进行优化，以下 对两种方法的原理及它们相结合的步骤作详细介绍。 三次设计指的是系统设计、参数设计和容差设计。目前该设计方法在质量管 理、工程技术、科研实验等管理设计中广泛应用，其中参数设计是十分重要的质 量管理对策。曲线或曲面可以看作是系统设计阶段所布列的使用性能指标同各有 关元器件( 参数) 之间的函数关系”，利用模型的可计算性，通过正交表进行选优， 尤其是对给定范围的参数，缩小步长，反复计算，最后使给参数达到最佳组合 这就是该方法的基本原理。 模矢法是胡克( h o o k e ) 和基尔斯( j e e v e s ) 于1 9 6 1 年提出的，其迭代步骤简 单，变量较小时尤为适用，易编制计算机程序，具有追循谷线( 脊线) 加速移向 最优点的性质。其原理如下；假定欲求某实值删的极小点，为此，任选一基点 b i ( 初始近似点) ，算出该点的目标函数值，然后沿第f 个坐标方向以某个步长a 。进 行探索，即在丑一a i 和置+ 色中选能使目标函数值下降的点，并把它作为临时矢点， 再由此点出发沿坐标另一方向进行同样的探索，如能得到更好的点，则以该点作 为临时矢点。如此沿各个坐标方向轮流探查一遍，并选这一轮探索最好的点( 最 后的临时矢点) 作为第二个基点岛。由基点岛、恳构成第一个模矢，就岛而言， 沿这一方向前进目标函数值下降最快，即为最有利改善方向，显然这一方向近似 子目标函数的负剃度方向。现假定在第二个基点附近进行类似的探索，并把模矢 口猡i 加长一倍，同样，对每个坐标方向进行探索和摄动，得出第三个基点岛，并 得到第二个模矢岛岛，其后，再把模矢岛历加长一倍，如此继续进行探索和加速 以及摄动，即可得到越来越好的目标函数下降点，如果探索进行到某一步时，得 不出新的下降，则应缩小步长以进行更精细的探索，当步长已缩小到某精度要 求但仍得不到新的下降点，即可将这基点作为所求的近似极小点，就此停止迭代 扬州大学硕士学位论文 对于比较复杂的目标函数，为了防止把局部极值误认为全局最优值，应分区探查， 或从任意选取的不同点开始，至少引入两个独立的搜索，如果它们都收敛于一点， 则这个点作为最优点的把握就会增加 根据三次设计法和模矢法的原理，将其结合形成三次设计结合模矢法，该方 法可以分为以下几个步骤进行： s t e p l 对模型中的参数进行分析，可分为可定范围、大体可定范围、不可定范 围三类。 s t e p 2 根据可定范围和大体可定范围参数的数目选择合用的正交表，合适的位 级及初始比例公差。 s t e p 3 据现有材料确定s t e p 2 中参数的初始值及参数位级表 s t e p 4 对不可定范围的参数，可随机初选四个点( 一般要求能代表不同的区域 范围) s t e p 5 对于大体可定范围参数，在某一个位级点时，与不可定范围参数起构 成独立变量，其组合即为初始基点马，对每个独立变量在每个初始基点分别选定 比例系数矗 s t e p 6 在可定范围参数为某一位级时，分别计算各个初始基点下的目标函数值 ，翟f ) 、贝b o - j 3 ) 、朋式1 勘，不断的摄动变化，直到这些初始基点收敛到一点或选 择最小目标函数值的基点作为收敛点，定出某一位级下各个最优参数解 s t e p 7 通过位级的变化可得出第一轮三次设计的参数聚焦点，以此作为初始位 级点，变化比例公差，调整正交表，进行下一级的循环 s t e p 8 在上述运算过程中，由于三次设计不断地把可定范围参数聚焦，而使其 收敛到某几点，由于模矢法在每一次运算过程中都可找到某一位级点是的近似最 优点，因此，结合三次设计的收敛，便可得出几个近似收敛点，选择其中目标函 数值最小的参数组合，作为最终参数解( 有时几个都是) 2 3 2 3 邈传算法 遗传算法( 又称g a ) 是一种仿生物系统基因进化的迭代搜索算法，被广泛应用 于机器学习、模式识别、图像处理、软件技术等领域。由于遗传算法的整体优化 歹林生些线和曲面拟合的改良缩张算法旦 策略以及优化时不依赖于梯度信息，所以具有较强的全局搜索能力，对解空阃的 全局最优具有较强的逼近能力。般遗传算法可分为以下几个步骤： s t 印l 编码 遗传算法在进行搜索之前先将解空间的可性解数据表示成遗传空间的基因型 串结构数据，这些串结构数据的不同组合便成了不同的可行解。对目标解空间编 码效率的高低将直接影响遗传算法的效率 s t e n 生成初始群体 随机产生n 个初始串结构数据，每个串结构数据成为一个个体，n 个组成一 个群体，遗传算法以该群体作为初始迭代点 s t e p 3 适应度评估检测 根据实际标准计算个体的适应度，评价个体的优劣，即该个体代表的可行解的 优劣。适应度函数的选择是实现算法最关键的一步，因为它是g a 寻求最优解的 基础 s t c p 4 选择 从当前群体中选择m 个优良( 适应度高) 的个体，使它们有机会被选中进入 下一次迭代过程，舍弃适应度低的个体。 s t e p 5 交叉 对选择产生的m 个个体，按照事先设定的杂交概率任意选取两个进行杂交运 算，或者称为交叉运算，产生新一代群体的两个新个体。杂交是两个个体交换一 部分基因链的运算，是个体之间随机交换信息的一种手段，重复这一过程直到产 生新一代的群体。 。 8 t e p 6 变异 在杂交运算产生的新的群体中，按照一定的概率从中选取若干个体，按一定的 策略进行变异操作，即改变码值的某一位的值。变异运算增加了群体的多样性， 避免了算法过早的陷入局部最优解。 s t e p 7 检验停机条件是否满足 扬州大学硕士学位论文 若满足则停机，否则转到( 3 ) 继续进行进化过程 相对于其它的寻优算法而言，遗传算法优点在于它对目标问题的求解完全的依 赖于解空间的个体及其适应度，而不需要其他的知识，故它对于解决复杂的非线 性拟合、非结构性问题有很强的求解能力。但将遗传算法应用与复杂函数的寻优 时，也存在着收敛速度慢，且存在陷入过早收敛而使寻优结果与最优解相差较大 的缺陷。其原因主要有两个方面：l 、遗传算法采用固定的交叉概率和变异概率， 这样容易造成适应度高的个体过度早熟，使算法陷入局部最优；2 、若算法陷入局 部最优，算法无法通过其它方法跳过局部最优点，向全局最优收敛 2 3 2 4 极大似然法 在统计学中，如果我们已经知道了总体的分布函数形式，但它的若干参数未 知，那么就可用极大似然法来估计这些未知参数下面将其基本思想和步骤介绍 如下： 设在疗维基本空间中有一个固定点d ( x b x 2 ，j 吣，那么随机点皤，磊，磊) 落在a 点附近的概率为： 只= ，“一她 磊 五十她，毛一蝇 ( 磊 毛+ 蝇， 一瓴 磊 + 瓴 = p 一缸 磊 毛+ 缸) ，一厶b 磊 毛+ 蝇) p 一瓴 磊 毛+ 蝇 = n ，“；m t - ! 其q ，f ( x , ；e x i = 1 , 2 , ，面为概率密度，口为未知参数 设辅助函数三瓴，屯，；刃= n b ；力 ( 1 3 ) 柚 以下利用式( 1 3 ) 求算随机点皤磊，磊) 落在固定点4 附近的最大概率值。即 令兰= 0 ，求出驻点口。由于我们是在极小范围五一她 d当前点不可成为下一轮的中心点 ( 1 7 ) 在本轮搜索点的试算比较中，当a o 时，说明该点的日标函数优于以往的优 化点，可成为下一轮搜索的中心点；当0 a d 时，该点 不被用作下一轮的中心点其中满足a d 的试算点统称为度点( s p r i n gp o i n t ) 以 度点为新的中心点一方面可直接跳出局部最优陷j i ，向可能的全局最优点靠近， 另一方面是这些点提供了后续重点搜索区域的信息这些点应在搜索过程中予以 记录( 记录其总和n 二阶原点距( 平方和) s 以及点数地) 2 3 2 5 3 下一c - e 循环中新的中心点、步长和临界值的确定 上述收缩步和扩张步构成一个c - e 循环最初的搜索区域，可以是经验或随 机的当完成一个循环后，应利用上述循环的信息确定下一个循环的中心点、步 长和临界值。 2 325 3 1 下一c - e 循环新的初始中心点和步长的确定 目标函数全局优的实现和效率很大程度上取决于步长由初始值确定的步长 难于满足要求，必须由寻优过程的信息反馈调整设上一个循环所有度点数为， 其总和为r ，原点二阶矩( 平方和) 为s ，则平均数i 和标准差j 及步长为： 扬州大学硬士学位论文 丑 p 莘2 兹 ，蚺叩 ( 1 8 ) l j = 遗岱r t i n c ) i n c t j = 蠹l 平均数i 提供了下一循环搜索起始中心的信息，标准差一则提供了搜索步长的信 息，= 声，即定为下个循环c 步第，个参数的搜索步长标准差体现了优化点( 包 括度点) 的散布程度，如果上一循环优化点( 包括度点) 在第，维参数上散布程度 比较大，下一循环的步长就应较大，否则就应较小。搜索步长根据优化点的散布 程度自动调整，避免了人为确定的偏差，使搜索寻优的效果更好当确定了新一 轮中心点和步长后，进行新的5 ，个步点组合进行c 步第一轮迭代计算后续c - e 循环中心点和步长的确定都照以上类推 2 3 2 5 3 2 下一c - e 循环临界值的确定 度点的数量取决于i 晦界值d 的大小，若d 很小，产生的度点数量必然太少， 不足以跳出局优陷阱，也难于提供参数点散布程度和目标函数趋向的信息d 很 大，产生的度点数量太多，降低搜索效率适当的度点数最易跳出局部最优陷阱， 且获得后续搜索的合适步长和新的重点搜索区域的信息这重要的临界值需在搜 索过程中自动反馈调节至最恰当的程度。经对各类曲线和曲面拟合实例的反复试 验研究，下一循环l 临界值d 的计算由下列公式给出： k = l ( n + n c + ) ( 1 9 ) n c 、地分别为上一循环收缩步和扩张步的度点数，口。为上一轮的临界值后续 c - e 循环中临晃值的确定都照上式确定 2 3 2 5 4 缩张算法的优缺点 缩张算法是一种直接法参数估计算法，它省去了提供偏导数的麻烦，对初始 值依赖性较小，能跳出局部最优陷阱，在较大程度上实现目标函数的全局优但 该方法在参数较多且非线性关系较复杂时，搜索寻优的效率较低，尤其在初始值 很不恰当时，从初始点到最优点的搜索进程相对较慢 万秫生：曲线和曲面拟合的改良缩张算法 3 实现全局最优化的改良缩张算法 为了能高速正确地对曲线和曲面全局最优化拟合，现对原有缩张算法进行若干 改进，改进之处主要涉及步点、中心点、临界值等方面，其中最主要也是最关键 的改进是结合数值微分( 珈姗两c a ld e r i v a t i v e ) 技术及解析法中改良高斯牛顿法 脚b e 学m 龇q 嘲略形成一个结合直接法与解析法优点的新算法一改良缎张 算法现对主要改进要点作一详细介绍并将其优点进行说明 3 1 步点数的改i 莲- _ 5 步点改成3 步点或者2 步点 在以5 步点试算对，若有p 个参数，每轮次的试算点数有穸个如p 暑5 时， 每一轮盼试算点共有5 s f f i 3 1 2 5 个；p = 1 0 时，则为5 t o = 9 , 7 6 5 ，6 2 5 个每一试算点均 需计算目标函数且进行比较，复杂的曲线、曲面拟合往往衙多个循环的许多轮次， 计算量之大显而易见因此需对步点数进行改进：在参数相对多对，将5 步点改 成3 步点，每一轮试算点数为矿个；在参数相当多( 一般p l o ) 时，将5 步点 改成2 步点，每一轮试算点数为2 p 个如p = 5 时，试算点数3 s - - - 2 4 3 仅为5 步点时 的7 8 ；p = l o 对，试算点数2 1 0 ；5 9 ，0 4 9 仅为5 步点时的0 0 1 ，计算重大为减少， 这就使一些多参数较复杂非线性问题的全局参数估计成为可能但试验也表明， 在参数少( p 4 ) 时，3 步点法或2 步点法获得的有效参数点偏少，将会对步长和 临界值的确定有一定的负面影响，仍以采用5 步点为宜 3 2 临界值d 反馈调节的改进 影响缩张算法功能和效率的关键因素之一是临界值d 的大小d 值太小，度 点数太少，不足于跳出局部最优陷阱；d 值太大，度点数太多且参数点的跳跃程 度过大，影响搜索效率因此，应由度点数反馈调节临界值d 经验证，原有的 调节公式d o = d _ ( n + + ) 存在调节力度不足的缺点经对各类曲线和曲面 拟合实例的反复试验，得到新一轮循环临界值d o 由负指数式确定： i d k e x p ( 一1 3 x ( 飞一1 3 x 5 ) 5 ) p s 4 d o = d o x e x p ( - i 3 x ( 一1 3 x 3 ) ，3 ) 4 p 9( 2 0 ) l 钆e x p ( - 2 x 魄- 1 3 x 2 ) 2 7 ) ，p 1 0 扬州大学硕士学位论文 用式( 2 0 ) 进行临界值调节，其敏感度有了大大的加强，