（计算机系统结构专业论文）利用神经网络求解组合优化问题.pdfVIP

山东大学硕士学位论文 摘要 由于神经网络具有强大的自学习、自适应、自组织能力，有较好的容错和并 行处理能力，对非线性函数有较强的逼近能力，而得到了越来越广泛的研究和应 用的推广。组合优化问题的求解是神经网络的重要应用之一。作为一个具有代表 性的组合优化问题，旅行推销商问题( t s p ) 一直是众多学者的研究对象。近十年来， 神经网络模型开始用来求解t s p 并取得较满意的结果。本文的研究主要着眼于以下 几个方面： 首先，提出了一种能够得到旅行商问题( t s p ) 的近似最优解的拉格朗日对象 松弛算法。这种算法主要包括两个阶段。首先求得一个可行解，在此基础上再用 h o p f i e l d 神经网络( i - i n n ) 求得一个近似最优解。拉格朗日对象松弛技术能够通 过调节拉格朗日因子帮助h n n 脱离目前的局部极小值。通过对t s p 的理论分析和 对一些t s p l i b 问题的仿真，实验结果表明本文所提出的方法能够得到1 0 0 有效 的近似最优解。 其次，还提出了两种导引式局部搜索( g l s ) 的改进算法：类g l s 算法和目 标函数调整算法，用来改善局部搜索的局部极小值。在类g l s 算法中，本文提出 了一种新的惩罚规则来进一步改善g l s 的有效性。此外，目标函数调整算法( 0 a ) 是对类g l s 算法的改进，通过在搜索过程中引入可调因子有效的改善了类g l s 算 法的性能。基于对一些t s p l i b 标准问题的仿真测试结果表明，o a 算法能够得到 比局部搜索、( 乱s 、禁忌搜索以及类g l s 更好的解。 虽然神经网络在很多领域都得到了很好的应用和推广，但是有两个亟待解决 的问题! 一是其网络收敛速度比较慢，二是有可能收敛到局部极小值，无法全局收 敛。为了解决这两个问题，人们做了大量的研究工作，其中小波神经网络可以有 效地提高收敛速度，并使局部极小值有所改善。鉴于局部线性小波神经网络是对 小波神经网络( w n n ) 的一种改进，通常采用梯度下降方法作为学习规则。本文 试着用一种局部线性小波神经网络来预测太阳黑子数，在权干扰( w p ) 技术中引 入模拟退火的思想，并用此规则来训练网络。仿真结果表明这种方法非常有效。 关键词：组和优化；对象松弛神经网络：目标函数调整算法；太阳黑子预测 山东大学硕士学位论文 a b s t r a c t r e c e n t l y ，t h ea r t i f i c i a ln e u r a ln e t w o r k ( a n n ) h a sb e e nw i d e l yr e s e a r c h e da n d a p p l i e dd u e t oi t ss t r o n gs a l e - s t u d y 、s e l f - a d a p t a t i o na n d s e l f - o r g a n i z a t i o nc a p a b i l i t i e s i n a d d i t i o n , i ta l s oh a sb e t t e re r r o rt o l e r a t i o n 、p a r a l l e lp r o c e s sc a p a b i l i t i e sa n dn o n l i n e a r f u n c t i o n a p p r o a c hc a p a b i l i t y t h ec o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sa r eo n e i m p o r t a n ta p p l i c a t i o nf i e l do fa n n t h et r a v e l i n gs a l e s m a np r o b l e mf r s p ) i sa r e p r e s e n t a t i v e c o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e ma n dh a sb e e nr e s e a r c h e db y n u m e r o u sr e s e a r c h e r s d u r i n gt h ep a s tt e ny e a r s ，t h en e u r a ln e t w o r km o d e ls t a r t st ob e u s e dt oc a l c u l a t et h et s pa n dh a sg a i n e ds o m ef a m o u sr e s u l t s t h i sp a p e rf o c u s e so n t h ef o l l o w i n ga s p e c t s ： f i r s t l y ，ip r o p o s eal a g r a n g eo b j e c tr e l a x a t i o nt e c h n i q u et h a tc a no b t a i nam o r e n e a r - o p t i m a ls o l u t i o nf o rt h et s p i tc o n s i s t so ft w os t a g e s f i r s t ，af e a s i b l es o l u t i o ni s c a l c u l a t e da n ds e c o n d , am o r en e a r - o p t i m a ls o l u t i o ni sc a l c u l a t e db ya h o p f i e l dn e u r a l n e t w o r k 饵n n ) t h el a g r a n g eo b j e e tr e l a x a t i o nt e c h n i q u ec a l lh e l pt h eh n ne s c a p e f r o mt h el o c a lm i n i m u mb yc o r r e c t i n gl a g r a n g em u l t i p l i e r s t h el a g r a n g eo b j e c t r e l a x a t i o nn e u r a ln e t w o r ki s a n a l y z e dt h e o r e t i c a l l ya n de v a l u a t e de x p e r i m e n t a l l y t h r o u g hs i m u l a t i n g1 l i et s et h es i m u l a f i o nr e s u l t sb a s e d0 1 1s o m et s p l i bb e n c h m a r k p r o b l e m ss h o wt h a tt h ep r o p o s e dm e t h o dc a nf i n d1 0 0 v a l i ds o l u t i o n sw h i c ha r e n e a r - o p t i m a ls o l u t i o n s s e c o n d l y ，ig i v et w oi m p r o v e da l g o r i t h m so fg u i d e dl o c a ls e a r c h ( g l s ) ，g l s l i k e a l g o r i t h ma n do b j e c t i v ef u n c t i o na d j u s t m e n t ( 0 a ) a l g o r i t h m , t oi m p r o v et h el o c a l o p t i m ao fl o c a ls e a r c h i nt h eg l s l i k ea l g o r i t h m , an e wp e n a l t yp r i n c i p l ei sp r o p o s e d t of u _ t h e ri m p r o v et h ee f f e c t i v e n e s so fg l s t h eo b j e c t i v ef u n c t i o na d j u s t m e n t a l g o r i t h m i sa l li m p r o v e da l g o r i t h mo f g l s l i k eu s i n gm u l t i p l i e r sw h i c hc a nb ee d j u s t e d d u r i n gt h es e a r c hp r o c e s s t h es i m u l a t i o nr e s u l t sb a s e do ns o m et s p l i bb e n c h m a r k p r o b l e m ss h o w e dt h a tt h eo aa l g o r i t h mc o u l df i n db e t t e rs o l u t i o n st h a nt h el o c a ls e a r c h , g u i d e dl o c a ls e a r c h ，t a b us e a r c ha n dg l s 1 i k e 山东大学硕士学位论文 a l t h o u g ht h ea n n h a sb e e na p p l i e d 锄dp o p u l a r i z e d 、i d a l y t h e r es t i l le x i t ss o m e p r o b l e m s o n ep r o b l e mi st h es l o wc o n v o r g o n c es p e e d , a n dt h eo t h e ri st h el o c a l i i l i i l i n m mp r o b l e m t h ea n n ( ：a l ln o tg u a r a n t e et h ee 丑o b a lc o n v e r g e n c e t h e r e s e a r c h e r sh a v ed o n eq u i t eal o to fr e s e a r c hi no r d e rt os o l v et h e s et w o p r o b l e m s t h e w a v e l e tn e u r a ln e t w o r kc a ni n c r e a s et h es p e e do fc o n v e r g e n c ea n di m p r o v et h el o c a l m i l l i m b r l l t h el o c a ll i n e a rw a v e l e tn e u r a ln e t w o r ki sa ni m p r o v e m e n to ft h ew a v e l e t n e t w o r ka n dc o m m o n l yu s e dl e a r n i n ga l g o r i t h mi sg r a d i e n td e s c e n tm e t h o d i nt h i s p a p e r , 啪a t t e m p tt op r e d i c ts t m s p o t su s i n gal o c a ll i n e a rw a v e l e tn e u r a ln e t w o r ka n d w e i g h tp e r t u r b a t i o nt e c h n i q u el i k es i m u l a t e da n n e a l i n gt h es i m u l a t i o nr e s u l t ss h o w t h ee f f e c t i v e n e s so f t h ep r o p o s e dm e t h o d k e yw o r d s ：c o m b i n a t o r i a lo p t i m i z a t i o n ，o b j e c tr e l a x a t i o nn e u r a ln e t w o r k , o b j e e f i v e f u n c t i o na d j u s t m e n ta l g o r i t h m ，s u n s p o tp r e d i c t i o n m 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导炳的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作毒耋要贡献的个人察集体，蚜甚在文中戬绢确方式标弱。本声明 的法德责任由本人承掇。 论文作者签名：叁塞：楚譬期：塑：兰 关予学位论文使鼹授权越声讶 本人完全了解山东大学有关保留，使用学位论文的规定，婀意学校保留域向 罄家毒关繇门或氍梅送交论文静笈窜譬 _ 荸陲奄子黢，兔译论文鼓在褥帮撩露；零入 授权山东火学可以将本学位论文的全部或部分内容编入有关数据库进彳予检索，可 以采用影印、缩印或其他复割手段保存论文和汇绽本学缎论文。 ( 保密论文在解密聪应遵守此规定) 论文作者签名：熬塞旌导师签名；日期：纽& 。垒。 山东大学硕士学位论文 第1 章绪论 1 1 神经网络 i i 1 人工神经网络概述 人工神经网络的研究已经有较长历史，最早的研究是1 9 4 3 年心理学家 m c c u l l o c h 和数学家p i t s 提出的兴奋与抑制型神经元数学模型，以及1 9 4 9 年h e b b 提 出的改变神经元连接强度的h e b b 规则。他们的研究成果至今仍是许多神经网络研 究的基础。5 0 年代末，r o s e n b l a t 设计制作了“感知机”( p e r c e p a o n ) ，它是一种多 层神经网络，首次将人工神经网络的研究从理论探讨付诸工程实践。6 0 年代初， w i d r o w 提出了自适应线性元件网络( a d a l i n e - a d a p t i v el i n e a re l e m e n t ) ，它是一种连 续取值的线性加权求和权值网络，可用于自适应系统。然而从1 9 6 9 年以后，这一 研究方向转入低潮，主要原因在于传统的v o nn e u m a n n 型数字计算机正处于发展的 全盛时期，许多人误认为数字计算机可以解决人工智能、模式识别、专家系统等 方面的一切问题。其次是电子技术工艺水平比较落后，要制作在规模上与真实神 经系统相比拟的人工神经网络还非常困难。加之m i n s k y 和p a p e r t 于1 9 6 9 年出版了 ( p e r c e p t r o n ) 一书。论证了简单的线性感知机功能有限，不能解决如异或( x o r ) 这样的基本问题，且指出多层网络还未找到有效的计算方法。由于上述这些原因， 使不少神经网络研究人员失去了信心，神经网络的研究转入低潮。7 0 年代末期， 人工智能和数字计算机在若干应用领域遇到了困难，加之1 9 8 2 年美国物理学家 h o p f i e l d 采用全互联型神经网络模型利用所定义的计算能量函数成功地求解了计 算复杂且著名的“旅行商最优路径”( t s p - t r a v e l l i n gs a l e s m e np r o b l e m ) 问题，从 而使人们对神经网络的潜力有了新的认识，推动了神经网络的进一步研究。接着 1 9 8 6 年r u m e l h a r t 和m c c l e l l a n d 提出了多层网络的反向传播( b a c kp r o p a g a t i o n ) 学习 算法( 简称b p 算法) ，该算法从后向前修正各层之间的连接权，并有很强的运算能 力，否定t m i n s k y 等人的错误结论。基于神经网络的非线性系统多步预侧控制论， 成为当前应用最广泛的神经网络之一。目前提出的神经网络模型己有几十种，其 中应用最广泛且富有成果的有b p 网络、h o p f i e i d l 网络、自适应共振理论( j 撮t ) 网络、 自组织特征映射网络和小脑模型关节控制器( c m a c - c e r e b e l l a rm o d e la r t i c u l a t i o n c o n t r o l l e r ) 等。 山东大学硕士学位论文 当前人工神经网络的应用研究主要包括下列几个方面：信号处理与模式识别 ( 如手写体字符识别和图象识别) 、知识处理工程与专家系统( 如预测估计、医疗 诊断) 和运动过程控制( 如智能控制、自适应控制) 等。神经网络在非线性系统的 建模、辨识和控制中获得了很大的发展。将神经网络应用到预测问题中，对于任 意复杂的非线性系统不仅能快速有效地建模，还能够大大减少计算时间。因此， 神经网络成为实现非线性预测控制的关键技术之一。本文主要讨论人工神经网络 在预测方面的应用。 1 1 2h o o f i e i d 神经网络概述 人工神经网络的研究从2 0 世纪6 0 年代末开始进入十余年的沉寂时期，而从 2 0 世纪8 0 年代初又开始蓬勃发展起来，出现了持续的研究高潮，直至今日。其中 h o p f i e l d 的两篇经典论文提出了h o 曲e l d 神经网络的概念【1 一，他和t a n k 将其用于优 化问题时取得了令人瞩目的成果嘲，这成为这一研究领域的复兴和快速发展的最重 要动因之一。 i 玉0 p f i e l d * 经网络主要采用模拟生物神经网络的记忆机理。是一个非线性动力 学系统，可以用一组非线性分方程或微分方程描述。 1 0 p f i e l d 主要应用于联想记忆 或求解优化问题。一般分为离散型h n n ) 和连续型( c 删) 两种。 ( 1 ) 离散型h o p f i e l d 神经络结构 d h n n 是一种单层，输入输出为二值的全反馈网络，其特点是任意一个神经元 的输出均通过连接权w 。反馈至所有神经元的输入。每个神经元都通过连接权接受 所有神经元输出反馈回来的信息，其目的是为了让任一神经元的输出都受其它神 经元输出的控制，从而使各个神经元互相制约。d h n n 网络计算公式如下： n 拍( f + 1 ) = w g y ( t ) - e j = l 站( ，+ 1 ) = s g n u , ( t + 1 ) 】 其q 3 s g n ( x ) 为符号函数： 2 山东大学硕士学位论文 ，、f 1 x 0 唧( x 卜i - 1 x t 血舰训车狲酬+ 勰- 1 乃 其中，饿蛳。呼+ - 0 是两个城市间的距离，口是类g l s 算法的一个参数，在所有仿真 实验中取值均为1 1 。 当局部搜索陷入局部最优值时( 图3 - 2 ( a ) ) ，根据等式7 所列的新规则惩罚 烈娜x c 椰+ 1 0 ( 图3 - 2 ( b ) ) ，一旦搜索到比当前解好的解时将所有惩罚因子 烈钒嘎跚+ 1 0 重新初始化为0 。 3 3 3 目标函数调整算法 在目标函数调整算法中，为目标函数的每一项都乘以一个因子，表达式如下： e 2 善a 似, c x u + 1 ) ) d p x ( o , c m o + i ) ) + 以c ，( 帕，c x ( 1 ) ) - d ( c ，o x c ，o ) ) 当局部搜索陷入局部最优值时，o a 算法通过调整各个因子来帮助局部搜索脱离局 部最优值。本节采用与类g l s 相同的规则来调整因子烈钒。x c 砷+ 0 ，即 训# 训+ 篙矧 ( 3 9 ) 其中，a 是一个参数，在所有仿真实验中取值均为1 1 。正如类g l s 算法那样，当 局部搜索陷入局部最优值时( 图3 - 2 ( a ) ) ，通过调整因子砸删x 跚+ - ) ) ( 图3 - 2 ( b ) ) 来摆脱局部极值。一旦搜索到更好的解，便将坝啊0 ，觏一) ) 重新初始化为1 ( 图3 2 ( c ) ( d ) ) 。这一过程对目标函数调整算法非常关键。只有这样，才能确保搜索遍 整个目标函数。 山东大学硕士学位论文 3 4 仿真结果 为了证明提出的方法的有效性，本节将其基于几个标准问题的性能与局部搜 索、g l s 以及禁忌搜索进行了比较。在所有的方法当中，都采用2 - o p t 和o r - o p t 作为局部搜索机制。对于每种算法，都计算出1 0 0 个次优解。通过计算 a v e r a g e t o u r l e n _ g t h - o p t i m a l l e n g t h 1 0 0 和b e s t t o u rl e n g t h - o p t i m a ll e n g t hx 1 0 0 的值来 o p t t m a ll e n g t ho p t u n a ll e n g t h 对上述四种方法进行比较。 表3 1 列出了基于a t t 4 8 ( 4 8 一c i t y ) ，a l t 5 3 2 ( 5 3 2 c i t y ) a n d p r l 0 0 2 ( 1 0 0 2 一c i t y ) 问题的 仿真数据。由此可以看出，o a 算法能够得到比其他四种方法更好的解，并且各算 法的运行时间都基本相同，但o a 算法具有更小的平均错误值。由其他算法得不 到的值能够由o a 算法得到。 3 5 本章小结 表3 1 各种方法的仿真结果比较 上sg l s疆g l 岛脚kd 4 i t t 4 si 钟仉7 2o 4 6o 6 6悯 日- e n h u 岫口 ( o )( o0 0 )( 0 0 0 )( o o o ) ( o 0 0 ) m t f h 24 6 93 辨 4 0丑5 i3 5 8 ( h l r m s t )( 2 “)( 24 s )( 2 4 5 ) ( z 0 2 )i 馏) i _ r 1 0 0 2 6 0 65 7 55 ，8 2，5 45 廿 ( b a s t n _ m ( 3 9 9 )3 9 4 )( 3 6 4 )0 5 2 )q 5 0 ) 本章提出了g l s 的两种改进算法来改善局部搜索的局部最优值。为了证明所提 出算法的有效性，本人做了很多的仿真实验。基于对一些t s p l i b 标准问题的仿真 结果证明，o a 算法能够得到比局部搜索、g l s 、禁忌搜索和类g l s 要好的结果。 本人希望能在将来的研究工作中用l i n - k e m i g h a n 启发算法来测试o a 的性能。 o a 算法通过增加和调节因子而使g l s 算法得以改进，具有广泛的应用性。其 计算过程并不复杂，因此，希望上述算法能够为正从事于求解组合优化问题的研 究者们提供有用的参考数据。 山东大学硕士学位论文 第4 章应用局部线性小波神经网络预测太阳黑子数 4 1 背景介绍 预测理论经过长期的发展，在建立和使用定量模型和定性模型等方面，取得了 长足进步，但是当系统具有较强的非线性时，各种模型的适应能力都是有限的。一 般来说，对于非线性系统的建模研究，通常处理的方法是将非线性系统做一定的变 换，转化为线性系统，或对某些特殊的非线性系统做特殊的处理。因此，在实际的预 测环境中模型常常失去效用。同时，对于大量的实际预测问题，数据的采集通常是 不精确的，甚至可能是错误的，而且只有当预测模型参数的选取随着预测环境的不 同而变化，才会得出较好的预测结果，这些问题对于传统的预测方法是难以解决 的。而小波神经网络可以很好地解决这个问题。 太阳黑子数是一个表征太阳总的活动水平的指数，自1 9 4 9 年w o l f 提出后就一 直延用至今。在实际应用中，只有它的月均值、月滑值和年均值才有较大的实用意 义。在早期的研究工作中，人们试图通过各种建模的方法来描述它变化的规律，而 象月均值所具有的变化强烈而又缺乏规则性的数据，使得建模的方法遇到了巨大 的困难。这说明太阳黑子数的演化具有高度的复杂性。太阳黑子数预测是一种重 要的研究和应用问题。在长期的研究过程中，提出了很多改进类似太阳黑子预测 的时间序列预测问题的改进方法。但是，大部分研究都被证明是不成功的，因为 他们受数据集大小的限制，以及大量的噪声对数据的影响。 小波理论能够为数据分析、信号处理以及其他一些应用提供有效的算法，但是 其局限性在于，他只能应用于低维的问题。人工神经网络是处理高维问题的有效 工具，但是却没有很好的构造方法。而最早由张清华9 t3 5 1 提出的小波神经网络有 效地克服了小波理论应用和神经网络所存在的问题。小波神经网络( w n n w a v e l e t n e u r a ln e t w o r k ) 是将小波理论与人工神经网络的思想相结合而形成的一种新的神 经网络，它既能充分利用小波变换的局部化性质，又能结合神经网络的自学习能 力，从而具有较强的逼近和容错能力、较快的收敛速度和较好的预测效果。通常 小波神经网络是将常规单隐层神经网络中的s i g r n o i d 函数由小波函数来代替，相应 的输入层到隐层的权值及隐层闽值分别由小波函数的伸缩参数与平移参数所代 山东大学硕士学位论文 替，而输出层为线性神经元，它将隐层的小波伸缩系线性叠加形成输出，即一系 列小波函数的权值和。局部线性小波神经网络p 6 ，3 刀是对小波神经网络的改进，在 这种网络中隐含层神经元与输出神经元之间的连接权值用一种局部线性模型来替 代。 小波神经网络最常用的一种学习算法是梯度下降方法。权值干扰( w e i g h t p e r t u r b a t i o n ：w p ) 3 5 1 是基于梯度下降的神经网络训练技术之一，其主要思想是将 均方误差( m e a ns q u a r ee r r o r ：m s e ) 对权值的微分用一个小的干扰噪声来近似。 但是，这种技术却很难摆脱缓慢的收敛性和中止于局部最小值的缺点。模拟退火 ( s i m u l a t e da n n e a l i n g ：s a ) 3 9 1 是一种启发式算法，这种方法不仅接受降低目标函 数的变化过程，还以一定概率接受使目标函数增加的变化过程。尽管s a 不一定总 是能够得到最优解，甚至在某些情况下永远得不到最优解，但是，通常还是能够 得到较其他启发式算法要好的解。 4 2 局部线性小波神经网络 由小波变换理论可知，小波是一个由函数妒( x ) 经过伸缩、移位操作所得到的 一个函数集，如下所示： t = 啊= b 1 4 ”y - x - g 一- 加- ) 、：翻，籼r 4 ，z ) ( 4 1 ) x = ( n ，x 分，】知) ，a j # ( a a ，a i 2 , ，f i 折) ，6 i = ( b n ，b t 2 , ，6 m ) 其中，x 表示输入向量，国是伸缩参数，西是位移参数。妒( 功被称作母小波函数， 在频域空间和时域空间都具有局部特性，并垂直于由母小波函数经过伸缩或移位 得到的所有函数。小波神经网络可以被看作一个由小波作为隐含层活动函数，并 且只有一个隐含层的神经网络。由小波神经元构成的神经网络，其基本思想是将常 规神经网络隐层的节点函数用小波函数替代，相应的输入层的权值及隐层的阈值 分别由小波函数的尺度与平移参数代替。w n n 的输出可以表示为； 山东大学硕士学位论文 ( x ) = y 和w 咿* i 1 ”爿x - - o , t 甲o ) = w t b i 叫：一l 扛l i = l o ( 4 2 ) 其中，w 是隐含层第f 个神经元的小波活动函数。w t 是连接隐含层第1 个神经元 和输出层神经元之间的权值。对于h 维的输入空间，多维的小波墓函数可以由撑 个单- 4 , 波基函数通过下面的方法来计算。 t ( 功= 兀y ( 船) ( 4 3 ) 显然，隐含层第f 个神经元的位置取决于伸缩参数函和位移参数6 j 。根据前人 的研究可知，这两类参数都可以由小波变换理论或者训练算法预先求出。不难看 出，小波神经网络是一类特殊的径向基函数( r a d i a lb a s i sf u n c t i o n , r b f ) 神经网络 之一，其主要特点是由小波作为基函数。w n n 的特征之一是隐含层神经元具有局 部活动的特性。因此，神经元之间的连接权值可以被看作局部参数。这一特性提 供了很好的学习效率和结构透明性。但是其缺点是，对于高维的问题，、q n 的隐 含层需要很多的神经元。 为了能够利用隐含层神经元数不多的w i , 、i r n 具有局部性的优点，陈跃辉 3 6 , 3 7 1 提 出t w n n 的一个变种，叫做局部线性小波神经网络( l l w n n ) ，其结构图如图 4 1 所示。 图4 - 1 一个局部线性小波神经网络 山东大学硕士学位论文 输出层的输出按如下式子计算。 m j ，= ( 1 ，i o + w f l x l + + 1 | 幽) 啊( 力 j f f i l =兰cw一姊叫等x-ott=1 = ( m o + w n 舶+ + w m h ) b i “2 叫：_ l “o ( 4 4 ) 用一个局部线性模型 = w t o w i l x t + - 4 - w 幽来代替直接的权值w t 。 的值取决 于与其相关的局部活动小波函数妒( x ) ( f = l 一2 一彤) ，因此 具有局部重要性。 在w n n 中引入局部线性模型的目的在于( 1 ) 局部线性模型曾被应用在神经元一 模糊系统( n e m o - f u z z ys y s t e m ) 中，并显示出良好的性能。( 2 ) 局部线性模型在 处理高维问题时，特别是对稀疏( s p a r s e ) 的高维模型能够提供更有效的解决办 法。伸缩参数a t 、位移参数b e 以及局部线性模型的参数被随机地初始化，并用下 面章节介绍的训练算法进行训练。实践证明，这种l l w n n 比w n n 的性能好， 且能够为高维问题提供有效的解。 4 3 学习算法 4 3 1 用权值干扰进行局部搜索 权值干扰w p l 3 s ，删的基本思想是：将权值参数引入噪声，如果增加的噪声使能 量函数值得以降低，则接受噪声对权值的干扰，这也就意味着对未来的输入值会 有更小的能量值。相反，如果增加的噪声使能量函数值增加了，则采取相反的改 变来更新权值，这也将意味着对未来的输入会得到更小的能量值。 在l l w n n 中，将一个包含所有参数( 连接隐含层神经元和输出层神经元的 权值、小波函数的伸缩参数和位移参数) 的向量矿定义如下： 矿- - - = w 1 0 ，w l l ，w 口，a l l ，a 1 2 ，a f ，b l l ，b 1 2 ，6 9 r( 4 5 ) 所采用的具体能量函数可参考等式4 1 0 ，也可被简写成： e = 耳矿)( 4 6 ) 采用权值干扰作为邻居寻址方法的局部搜索，其基本思想是：不断地调整向 山东大学硕士学位论文 量n 使能量函数逐渐减小。首先，搜索从一个初始点开始，试着朝3 n 个方向移 动。3 打表示向量啪维数。例如，第h 个方向所对应的向量可以表示为： 2 ( 0 ，0 ：，o ，旦) 1 ( 4 7 ) 给定初始方向以及噪声干扰o 的大小，r “中的向量序列乃，的顺 序可以由如下方法得到：从第一轮循环开始，第k ( o 后s3 n ) 轮循环的搜索过程为 从v k r “开始，搜索的目标是寻找一个合适的方向，使满足e ( v k + a 峨) e ( r o 或e ( “一a ) 0 表示噪声干扰大小。如果找到 了这样的方向，则认为本轮搜索成功，且下一轮的搜索向量y “j 取v k + 1 - 阼+ a t e 。 o r 儿+ - = 赡一略。但是，如果找不到满足上述条件的方向，那么本论搜索就被 认为是不成功的，并模拟退火算法( s i m i i l a t e d a n n e a l i n g ) t 3 9 1 在求解组合优化问题时 引入了统计热力学的一些思想和概念，且下一轮搜索的向量值等于当前的向量值， 即v k + 1 声取。此时调整干扰噪声参数山+ z 的大小为如i ，其中，在整个过程中取 0 d l 之间的一个常数值。因此，如果梯度v e ( v k ) 不为0 ，步长血足够小，搜索 过程最终将找到一个局部最优解或全局最优解。 4 3 2 模拟退火 上节介绍的局部搜索存在的一个问题就是很容易陷入局部极小值而无法找到 全局最小值。为了能够帮助局部搜索脱离局部极小值，本文将模拟退火的算法思 想引入权值干扰技术当中。模拟退火是局部搜索算法的一个变种，在搜索过程中 允许以某种控制规则朝着“上坡”的方向移动。模拟退火借鉴了金属降温至具有 最低能量的晶体结构的过程( 退火过程) ，利用这种思想来解决求最小值的优化问 题。金属的结晶过程从很高的的初始温度开始，逐渐降低温度进行冷却，最终达 到一个稳定的状态，此时的能量最低。 本章所提出的方法从一个初始高温z 腑和一个初始解s 开始，然后，在温度保持不 变的条件下，按照上一节所介绍的局部搜索算法进行搜索。搜索过程即计算一个 新解s ，并以概率p 决定接受还是拒绝这个解。 山东大学硕士学位论文 p = e x p 一( e ( s ) 一e ( s ) ) b t 】( 4 8 ) 其中，e ( s 表示新解j 的能量，耶) 是当前解s 的能量。6 是b o l t z m a n n s 常量，r 是当前的温度。 当一个新的解被接受的时候，相应地改变温度值，并重复前述搜索过程。这 一算法基本是朝着“下坡”的方向移动，偶尔移向“上坡”方向。温度越高，s a 移向非最优状态的可能性就越大，而温度越低，s a 移向“上坡”方向的可能性越 小。图4 2 描述了采用模拟退火思想的权值干扰技术的流程图。 s t e p l ：i n i t i a l i z e t e m p e r a t u r e t t o a h i g h e r t e m p e r a t u r e t q i s e l e c t d i n i t i a l s o l u t i o n s a t r a n d o m ； s t e p2 ：u s e l o c a l s e a r c h t o s e l e c t a n e i g h b o r s o l u t i o ns o f s ： c a l c u l a t et h ec h a n g ei ne n e r g y f u n c t i o na e - e 秘_ e ( s ) ： i f a e o t h e n3 _ s ： e l s e g e n e r a t er a n d o mr 【o ，1 】； r ( 宅印( 醯，码t h e ns s ； r e p e a t t h i s s t e p at i m e s ； s t e p ，：r e d u c et e m p e r a t u r et a s ：r + 士r i f t e m p e r a t u r e t i s h i g h e r t h e n t h e m i n i m u m t e m p e r a t u r e p = t h e n g o t o s t e p 2 e l s e b e o v g r 图4 - 2 应用模拟退火的权值干扰技术的程序流程 在所有实验中，z 淼的值取5 0 0 0 0 0 ，m 的值取1 0 0 0 ，常量6 的值取0 9 9 9 。在 某一温度下，重复步数4 的值取5 。 山东大学硕士学位论文 4 4 预测太阳黑子数的仿真实验 4 4 1b i f 的太阳黑子活动数据集 太阳黑子的活动直接影响地球气候的变化，在太阳黑子最多的时候，太阳温度 会上升，太阳的火焰和磁场会十分活跃，直接影响地球的天气及通讯系统，也可能 损害地球上空的人造卫星。因此，准确预报未来时刻的太阳黑子数有十分重大的 意义。由于太阳黑子数变化的高度复杂性，使得人们通过建模的方法描述其变化规 律的尝试遇到了巨大的困难。 太阳黑子序列是从1 7 0 0 年开始记录的，记录每年太阳表面的可见黑子数。这 一数据集是非线性的且非高斯分布的，通常被用来测试一些非线性统计模型的性 能。近年来，人工神经网络被认为是一种预测太阳黑子数【4 1 1 的有效方法。本章采 用从1 7 4 9 年一月份到1 9 9 9 年1 2 月份的太阳黑子数的月记录作为实验数据集进行 测试。图4 3 描述了这一时间段( 3 0 0 0 个点) 的太阳黑子数变化的曲线图。 3 0 0 2 5 0 日2 0 0 娶1 5 0 a 1 0 0 5 0 0 5 0 11 0 0 1 1 5 0 1 2 0 0 12 5 0 1 d a t a 图4 - 3 从1 7 4 9 年到1 9 9 9 年的太阳黑子数月数据的变化曲线 4 4 2 仿真结果 采用具有5 个输入，一个具有1 5 个神经元的隐含层和一个输出单元的l l w n n 来预测太阳黑子数。伸缩参数、位移参数和权值参数被初始化为随机数，并用上 一节介绍的局部搜索算法对参数进行优化。在所有实验中，选取的母小波函数为： 山东大学硕士学位论文 妒= 吖e 坤( - x 2 ( 4 9 ) 将网络训练成能够根据5 个以前的太阳黑子活动数据( 图4 - 4 ( a ) ) 预测太阳 黑子活动规律的网络。本节采用另一种网络结构( 图4 - 4 ( b ) ) 来测试预测结果的 性能。 圆 d a t a f t + 5 ) i l l w n n tl + l t + 2 t + 3t + 4 m a ld a t a 回 d a t 鑫【t + 5 ) ( a ) ( b ) 图4 - 4l l w n n 的训练结构图( a ) 和测试结构图( b ) 设置一个延迟单元将前一次输出值作为下一个模式的输入，另设四个延迟单 元将上一次邻居的输入值设置为当前的输入值。例如，如果输入数据为d a t a ( 0 ，那 么除一个输入单元的输入值取上次的输出值外，其余四个输入单元的输入值都取 d a t a ( f + 1 ) 。训练过程的能量函数e 的表达式为： 12 5 f i e = 去( 2 0 0 y t 一2 0 0 t e a c h e n ) 2 ( 4 1 0 ) 其中，弘是i j 删的输出，教师信号t e a c h e r t 为s u n s p o t j d a t a ， 2 0 0 的输入数据。此外，测试过程的f i t n e s s 函数表达式如下： f：1登200200teachl 3 , , - 2 0 0t e a c h e r , ) 2 f = 五扛2 5 t 并作为下一个模式 ( 4 1 1 ) 为了证明权值干扰技术的有效性，本节将其应用到l l w n n 中。为了做一个 比较，还考虑了其他一些情况，如输入数据+ 噪声的情况，以及简单的局部搜索 山东大学硕士学位论文 ( 即没有退火过程) 。并且采用了两个实验数据集。 对于每种方法和每个数据集，在初始参数取不同随机值的情况下，进行了1 0 0 次训练，以避免参数的初始值对最终结果的影响。实验求得了每种方法的1 0 0 个 训练错误值，此外，当训练错误达到最小时，还记录了此时的测试错误值，虽然 这不一定是最小的。通过计算1 0 0 次实验所得数据的平均训练错误值和平均测试 错误值，比较了三种方法的性能( 如表4 ，l ，表4 2 所示) 。 本节将输入数据集中连续的每l o 个数求平均值( 图4 3 中从l 到2 5 0 0 ) 求得 的2 5 0 个值作为一个训练数据集d a t al 。此后，将这- - n 练模型用来预测接下来的 5 0 个数据，即从2 5 0 1 到3 0 0 0 的数每1 0 个求平均而得到的5 0 个值。结果如表4 1 所示。 表4 1 对数据集d a m1 的仿真测试结果 p r o p o s e dp r o p o s e d + n o i s e l e e a ls e a r c h t r a i n i n ge l t o r 回 2 1 9 7 3 2 2 1 6 2 0 63 2 8 8 5 9 t e s te l t o r ( t o 4 4 4 1 1 74 3 8 8 4 95 4 6 8 0 5 此外，本章运用相同的学习技术，但采用不同的数据集对网络进行训练。将 输入数据集中连续的每5 个数据求平均值( 图4 3 从1 到1 2 5 0 的数据) ，将得到的 2 5 0 个值作为训练集，然后用训练好的模型预测接下来的5 0 个数据( 从1 2 5 1 到 1 5 0 0 的数据每5 个求平均值得到的5 0 个值) ，实验结果如表4 2 所示。由表可以 看出，这种将求5 个数的平均值作为输入的