（光学工程专业论文）基于人工神经网络的时间序列预测与路由优化.pdf

中文摘要 中文摘要 本文主要研究了人工神经网络模型在通信网络路由优化和非线性时间序列 信号预测这两个领域中的应用。 在网络路由优化的部分，我们首先考察了单播路由的两类有代表性的基本问 题，即费用最小一延迟受限( d c l c ：d e l a y c o n s t r a i n e dl e a s t c o s t ) 问题和多限制 路由( m c p ：m u l t i c o n s t r a i n e dp a t h ) 问题，介绍了基于h o p f i e l d 神经网络的解 决方案，提出两种能量函数，并以此决定网络的互连权重，寻找最优的路由。 尤其是对于后者，以往的方法需要仔细选取的参数数目比较多，这是一个艰巨 的任务，尤其是限制条件达到一定数目后，这些参数的合理选取是极其困难的。 我们通过提出一种新的能量函数，将k 个参数( 限制条件数目) 减少为1 个， 降低了选取参数的复杂性和计算的复杂性。在计算机模拟中，h o p f i e l d 神经网 络可以在1 0 1 。5 量级的时间内收敛到正确结果，从而保证q o s 路由的实时选择。 最后，我们讨论了真实网络中存在的状态参数不确定( 非精确) 性的来源与数 学模型，并提出基于l t o p f f e d 神经网络模型的解决方案。同样，计算机模拟表 明神经网络可以迅速收敛到正确的结果。 在对股指进行时间序列预测部分，我们首先通过数学分析，给出价格的数学 表达式，从而指出对其进行预测是可能的。然后，我们利用e 支持向量机和v 一支持向量机模型对存在着虽然是作为极小概率事件发生但对经济有非常深远 之影响的崩溃过程的上证指数和道琼斯工业平均指数进行了成功的预测，其 相对误差仅为l o 。量级。最后我们在训练数据严重不足的情况下( 这一缺点对神 经网络来说往往是致命的) 对台湾股指进行了宏观变量的预测，相对误差为1 0 。 量级，也是令人满意的结果。 关键词：人工神经网络、q o s 路由、h o p f i e l d 神经网络、不确定性( 非精确性) 、 支持向量机、非线性时间序列预测 a b s t r a cj a b s t r a c t i nt h i sp a p e r , w ec o n c e n t r a t eo u ra t t e n t i o nt oa p p l y i n ga r t i f i c i a ln e u r a ln e t w o r k s i nb o t hq o sr o u t i n gp r o b l e mi nc o m m u n i c a t i o nn e t w o r ka n dt h ep r e d i c t i o no f n o n - 1 i n c a l t i m es e r i e s i nt h ef i r s tp a r t ，w eb e g i no u ra n a l y s i sw i t ht w op o p u l a ru n i c a s tr o u t i n g p r o b l e m s ，i e d e l a y - c o n s t r a i n e dl e a s t c o s tr o u t i n g ( d c l c ) a n dm u l t i c o n s t r a i n e d r o u t i n g ( m c p ) f o re a c ho n e ，w ep r e s e n tal y a p u n o ve n e r g y f u n c t i o nu s e di n h o p f i e l dn e u r a lm o d e lt of i n do u tt h eo p t i m a lr o u t e f o rm c p , t h e t r a d i t i o n a le n e r g y f u n c t i o ni n t r o d u c e sm u l t i t e r m sc o r r e s p o n d i n gt om u l t i c o n s t r a i n s ，w h i c hh e n c eb r i n g t o g e t h e rs o m ep a r a m e t e r sh a r da n de v e ni m p o s s i b l et od e t e r m i n e d ，e s p e c i a l l yw h e n t h en u m b e ro fc o n s t r a i n si sh u g e i no u rn e wf u n c t i o n ，j u s to n et e r mi se m p l o y e d t h e r e f o r e ，d i f f i c u l t i e so fc h o o s i n gal o tp a r a m e t e r sb r o u g h tb ym u l t i - c o n s t r a i n e dc o n d i t i o n s ， t o g e t h e rw i t hd i f f i c u l t i e si nc o m p u t i n g ，a r er e m o v e d t h e i rc o m p u t e rs i m u l a t i o n ss h o wt h a t h n nc a nc o n v e r g ei n 1 0 s ，w h i c hi n d i c a t e st h a th a r d w a r ei m p l e m e n t a t i o no f t h e m s e l v e si ss u i t a b l ef o rt h er e a lw o r l dd y n a m i c a lc o m m u n i c a t i o nn e t w o r k s f i n a l l y ， w ed i s c u s ss e v e r a lp o s s i b l eo r i g i n so fu n c e r t a i n t yi nn e t w o r kp a r a m e t e r sa n ds e tu pa m a t h e m a t i c a lm o d e lt od e s c r i b et h ep r o b l e mw ea r ef a c i n gi ns u c hs i t u a t i o n s t h e n ， a t lh n n b a s e dm e t h o di sp r o p o s e dt os o l v es u c ha j lo p m pp r o b l e m a l s o ，t h e d e m o n s t r a t i o ns h o w st h a ts u c ha nh n n b a s e dm e t h o dc a r lf i n dt h ec o r r e c tr e s u l t r a p i d l y a sf o rt h es e c o n dp a r t ，w ef i r s t l yi n t r o d u c et h ef o r m u l ao fp r i c ei n c l u d i n g b u b b l e si nt h ev i e wo f m a t h e m a t i c s ，t h e n c et h ef e a s i b i l i t yo f p r e d i c t i o n s e c o n d l y , w e a p p l yt h e 一s u p p o r tv e c t o rm a c h i n ea n dv s u p p o r tv e c t o rm a c h i n ei np r e d i c t i n g t h ep r i c e so fs h a n g h a ic o m p o s i t ea n dd e wj o n e sa v e r a g e se s p e c i a l l yd u r i n gt h e c o u r s ew h e nt h e ya r cc r a s h i n g ，r e s p e c t i v e l y t h er e s u l ti ss a t i s f y i n g ，w h i c hc a nb e v e r i f i e dw i t ht h ef a c tt h a tt h er o o t m e a n s s q n a r c e r r o ri sa b o u t10 a t1 a s t w i t h b a d l yi n s u f f i c i e n tt r a i n i n gs e t ，a l t h o u g hs u c haf a u l ti su s u a l l yf a t a lt on e u r a ln e t w o r k s h o w e v e r , w eg e tt h es a t i s f a c t o r yp r e d i c t i n gv a l u e ，a n dt h er m s e i sa b o u t10 k e yw o r d s ：a r t i f i c i a ln e u r a ln e t w o r k ，q o sr o u t i n g ，h o p f i e l d n e u r a ln e t w o r k ， i n a c c u r a c y ( u n c e r t a i n t y ) ，s u p p o r tv e c t o rm a c h i n e ，p r e d i c t i o no fn o n l i n e a r t i m es e r i e s 南开大学学位论文版权使用授权书 本人完全了解南开大学关丁i 收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的e p , f 6 u 本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：互互 曲o ；年；具3 。b 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 三主 解密时间：年 月 日 各密级的最长保密年限及书写格式规定如下 内部5 年( 最长5 年，可少于5 年) 秘密1 0 年( 最| 芰= 1 0 年，可少于1 0 年) 机密2 0 年( 最长2 0 年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导卜- ，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果1 i 包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 互互 护口f 年厂月如同 第一章引言 第一章引言 第一节人工神经网络 最困难的部分是引言。 一一西塞罗 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ：a n n ) 是一种根植于许多学科的 技术，其中涉及神经科学、数学、统计学、物理学、计算机科学与工程学，它 模拟人类大脑的记忆、识别和联想等功能，是由大量的简单单元神经元相 互连接而成的自适应非线性动态系统。神经网络在两个方面与人脑相似：( i ) 神 经网络获取的知识是从外界环境中学习得来的；( i i ) 互连神经元的连接强度， 即突触权值，用于储存获取的知识。因而人工神经网络具有的很多优点：( 1 ) 学习能力，即在有教师( 监督) 或无教师( 监督) 的情况下能够从输入数据巾 进行学习；( 2 ) 群并行性，全并行处理数据，速度快；( 3 ) 推广性好；( 4 ) 联 想、容错与鲁棒性等。这使它在不同领域中得到应用，如建模、时间序列分析、 模式识别、信号处理与控制等。 一个神经元的功能如图1 1 所示。而神经网络由大量这样的神经元相互连 接组成的。按照神经元构成神经网络的连接方式分类，其类别如图1 2 所示。“1 图1 1 生物神经元与人工神经元。 1 第一章引言 圜匿圜圈犀障 图1 2 人工神经网络的类别。 前馈型神经网络内的神经元分层排列，模型由输入层、中问层( 或称隐藏层) 和输出层组成。每一层内的神经元之间无连接，仅层间神经元有连接，且各神 经元的状态信息仅向前传递。即由输入层，顺序到各中间层，最后从输出层输 出。应用最广泛的前馈模型有背传( b p ：b a c kp r o p a g a t i o n ) 神经网络、支持向量 机( s v m ：s u p p o r t v e c t o r m a c h i n e ) 、径向基网络( r b f ：r a d i a lb a s i sf u n c t i o n ) 等。 其中b p 网络的学习算法是误差反传( b p ) 规则，也叫广义占规则，通过比较实 际输出与理想输出之间的差值，从后向前传递误差信息以逐层的修改权重从而 使实际输出逼近理想输出。1 而后两种模型的思想则是通过将输入映射到核空 间，从而将非线性问题尽量线性化。一个结构为一m 一工的前馈网络模型如图 1 3 所示。 输入层 中间层 图13 前馈嗍络结构模型 2 第一章引言 一些学者研究了多层神经网络的近似能力。但是它们对如何确定网络的规 模，即网络应该包含的隐层及隐节点数几乎没有理论指导。c y b e n k o 证明了具有 单隐层及任意固定的连续非线性s i g m o i d 函数的m l p ，可以一致逼近任何连续 函数。”即给定d 0 和连续函数厂：q - r ，q c r ”是r ”上的有界闭子集， 则存在一权重矩阵w r ，s 为权重系数的个数，使神经网络的输出 r n n ( x ，w + ) 满足 1 厂t w 一s ( x l 占 ( 1 1 ) 这一性质鼓励人们将前馈网络用于模式识别、聚类、函数拟合、预测、优化和 智能控制等领域。虽然从存在性的角度来看，具有单一隐层的两层神经网络己 能逼近任意连续函数，但是，这并不等于说从学习的收敛速度、网络结构的简 单性以及推广能力等性能来看，单一隐层神经刚络对给定的实际问题来说一。定 是最佳的选择。所以有很多的人对如何确定网络的规模，即网络应该包含的隐 层及隐节点数做了大量的研究”。此外，训练学习样本的选择在所有模型的应 用中都很重要，学习样本数目以及是否具有代表性都会影响到网络的预测、分 类识别以及推广、容错能力。“。根据研究对象的特点，本文采用s v m 模型，对 于这个模型，我们将在f 一章中作较为详细的介绍。 反馈型人工神经网络是一个全互连的网络结构，不仅层与层之间存在反馈互 连，而且层内的神经元之问也相互影响，存在反馈互连，这类神经网络的输出 都要通过某种途径反馈到它的输入端。反馈型网络的代表是l l o p f j e t d 网络，由 l _ i o p f i e l d 于1 9 8 2 年提出，其电路的实现见图1 4 。由于它准确地保留了生物神 经网络的动态和非线性特征，而且在优化控制方面展现了强人的能力，一度引 领了神经网络研究的新浪潮。”1 我们将在后而具体介绍它。 第一章引言 图1 4 h o p f i e l d 神经网络的电路结构图。 第二节神经网络与路由优化 本文的第一个研究对象是通信网络的q o s ( q u a i t yo fs e r v i c e ) 路由。传统 的i n t e r n e t 网络主要为数据业务提供尽力而为的服务，接入率与网络吞吐量是 其主要的优化对象。数字音视频等多媒体应用的出现对通信网络提出了更多样 化和更为严格的服务质量要求。为提供服务质量保证，网络必须进行合理的资 源预留并实现对网络的有效控制。过去几年中，大量新的网络体系结构( 如 i n t e r s e r v 、d i f f s e r v 、m p l s 等) 对资源预留、接纳控制、节点控制等提出了多 种改进措施，但在这些考虑q o s n 务质量保证的网络结构中还缺少一个关键技 术，即为满足q o s 要求进行最优化选路的q o s 路由技术”1 。除了上面提到的这一点 外，在现代通信网络中，服务质量研究的推动力还有：一，通过q o s 研究，有助 于提高网络效率，降低网络成本；_ ，运营商可以通过q o s 机制，按照不同用户 对服务质量的不同要求，提供多种有区别的服务，提高州户的满意度，i 司时提 高网络运营商的收益一，。 q o s 路由的主要目标足为接入的业务选择i 司时满足其各种服务质量要求的传 输路径，同时保证网络资源的有效利用。目前q o s 路由的研究可以分为三个方面： 单播路由( u n i c a s tr o u t i n g ) 、多播路南( m u l t 卜c a s tr o u tin g ) s d a dh o c 路 由。所谓单播路由，其目标是在一个源节点和一个目的节点间寻找一条满足服 务质量的传输路径。如果单播路由可以称为一对一路由的话，多播路由就是一 第一章引言 对多路由。而a dh o c 路由是指在是一种白组织、自适应、不需要基础设施的无 线网络上实现的路由技术。本文只针对单播路由。前面提n q o s 路由应该满足各 种服务质量的要求，而这些服务质量的度量参数则包括：费用、带宽、延时、 延时抖动、丢失率等等。这些度量参数又可以分为加性、乘性和凹性的“，比 如传输延迟、跳数、费用是加性的，丢失率是乘性的，而带宽是凹性的。尽管 存在这样的区分，但我们在考虑问题足指要讨沦加性参数即可，因为乘性参数 可以通过对数变换而转化成加性参数，而j 、l 凹性参数不满足要求的链路都可以 简单地认为其在物理上不存在。一卜述各种服务质量要求的组合有许多种，比如 费用最小一延迟受限( d e l a y c o n s t r a i n e dl , e a s tc o s t ) 这一组合要求在保证延 迟不超过一个阈值的情况下找到费用最小的传输路径，而延迟受限一延迟抖动受 限( d e l a yd e l a y j i t t e r c o n s t r a i n e d ) 的组合则要求找到的路径的延迟和延迟 抖动都不要超过相应的阈值。对于这些不同组合的问题及其可能的解决方案， 文献 1 1 给出了很好地总结和展望。 自从h o p f i e l d 和t a n k 开创性地将a n n 应用于优化计算后1 ，以h o p f i e l d 的名字命名的神经网络模型便成了解决组合优化问题强有力的工具之一，文献 1 3 对h o p f i e l d 网络模型这一领域应用的物理原理和实验性能进行了总结。而 由于大规模网络中的路由问题本质上就是一个组合优化问题，从而h o p f i e 】d 模 型在这一领域中的应用也是相当广泛的”“。文献 1 5 1 8 对利用h o p f i e l d $ 经网 络解决计算机网络中的最短路由问题进行了探索，提出了各种模型，在这中间， m u s t a f ak m a 1 i 和f a o u z ik a m o u n 提出的网络模型较具有实用性。这也成 为更复杂路由问题的基础网络模型。 本文将使用h o p f i e l d 网络解决三个问题：优化一受限( 以d e l a yc o n s t r a i n e d l e a s t c o s t 为例) 路由优化、多限制路由( m u l “一c o n s t r a i n e dp a t h ，以 d e l a y d e l a y j j t t e rc o n s t r a i n e dp a t h 为例) 优化以及在度量参数不精确的情 况下优化路由的问题。对j 二第一类问题( d c l c ) ，已经提出了许多算法“，对 于第二类问题( m c p ) ， 1 9 ，2 0 可能是迄今最有价值的文献，然而这些算法都依 赖于传统的数学思想，串行的工作方式很难适应及时性的要求，尤其n c p 问题 将是一个n p 问题，尽管s c h e n 和k n a h r s t e d t 提出的方法“”可以将n p 问 题转化成多项式时间的问题，但转化过程中需要的参数是需要精心考虑的。我 们在这里使用神经网络就是要利用其并行处理的能力，提高优化选择路由的速 度，同时减少所需参数的数目，避免了需要精心选择众多参数的困难。由_ 丁通 第一章引言 信刚络内在地使刚络状态信息旱现非精确的性质，所以我们在处理完前述两个 问题之后，将注意力转入当网络状态的度量参数是不精确的情况下如何处理q o s 路由优化的问题，a o r d a 等人 2 1 - 2 4 1 做出了开创性的并且也是全面性的研究，我 们的工作是把他们在数学上的思想引入到神经网络的实现中来。 第三节神经网络与时间序列预测 公式( 1 1 ) 从数学上保证了神经网络用于时问序列预测的可能性。预测足 根据事物以往的发展规律判断其未来的趋势。一般认为，在时问序列的过去值 和未来之之间是存在着关系的，于是通过将日寸间引入神经网络，可以使它跟踪 时间序列过程的统计规律及其变化，从而对下一个或以后几个时间点的状态进 行预测。预测方式可分为离线预测和在线预测，离线预测是指用时问序列的过 去值建立模型，并用这个固定模型执行接下来的预测工作，而在线预测则是在 前面得到的模型基础上，同时在预测过程中还要不断的调整模型参数。我们在 文中采用离线预测的方法，尽管它会给长期预测的精度造成影响，但我们却可 以从中发现一些有趣的特点。为了将记忆( 时间) 引入网络，可以有许多方法。 使用普通的时间延迟来执行时序处理的通用神经网络就是所谓的时延神经网 络，将输入的p 阶延迟共同作为网络的输入，即x ( n ) = 【x ( 月) ，x ( n 一1 ) ，x ( n p ) ， 而网络的输出即为预测值x ( n + 1 ) 。至于阶数p 的选择，它涉及了非线性时间序 列相空间重构的问题。【2 副 我们在本文中第二部分进行时间序列预测的对象是股市的股指。神经网络作 为一种有效的预测手段，很早便被应用于金融价格、外汇市场以及其他金融市 场价格的预测中+ 。尤其足最近1 0 年来的研究，显示出了其巨大的能力。1 9 9 1 年y o o n 和s w a l e s 采用一个9 2 4 结构的神经网络对标准普尔5 0 0 指数的价格进 行预测，结果表明预测效果优于传统的多元判别分析f 2 。w e i g e n d 等人应用神经 自1 9 世纪7 0 年代的洛桑学派至今，数学被越来越广泛的应用于绎济领域的研究之中，经济学已经 被认为很有可能超越物理学，成为最依赖数学技术的- r l 学科。尤其在当今智能计算的发展环境f ，举儿 新的技术、思想，比如神经计算、独立成分分析、支持向量分析、遗传与进化算法、小波计算等都被引入 到这个社会科学的研究领域中。美国电子电气工程师协会( i e e e ) 从1 9 9 5 年开始土办“金融t 程的计算 智能”国际会议，并版会议论文集p r o c e e d i n g so f t h ei f e e i a f e i n f o r m sc o n f e r e n c eo nc o m p u t a t i o n a l i n t e l l i g e n c ef o rf i n a n c i a le n g i n e e r i n g ( c i f e r ) 。 第一章引言 网络预测外汇汇率揭示出汇率的变化具有一定的非线性规律，并不是完全随机 的 2 7 】。后来，s h a z l ye l 利月j 一个4 1 0 1 结构的三层网络对外汇汇率的研究表 明神经网络的预测能力优于传统的经济讣量模型与随机游走模型 2 8 。z a r e m b a 利用2 0 一4 1 ，1 结构的三层前馈网络对美国圈债和黄金期货价格进行预测，结果表 明神经网络模型优于传统的线性模型1 2 9 】。些更新的模型也得到了应用，a n d r e w b a c k 首先使用独立成分分析( i c a ) 对日本东京股票市场股价的时间序列进行 了分析，表明该方法在揭发股价运动机制上优于传统的主成分分析口。c h e u n g y i u - m i n g 提出了在经济序列分析中确定独立成分顺序的方法p “，e r k k io j a 等人 则对1 c a 在经济上面的应用作了总结【3 。s w a m p w a n d a l 为公司经营的健康状态 建立了神经网络模型 3 引，y a n g 利用支持向量机的分类功能对英国2 4 0 8 家公司的 经营业绩进行了研究和预测【3 4 】。神经随着神经网络模型研究的不断深入，其在 经济领域中的应用必然会更加广泛。【j 副 我们把预测的重点放在股市泡沫崩溃过程。白二十世纪以来，世界经济经受 了多次金融危机的威胁。”1 。在重大的金融危机中，我们总能看到泡沫和泡沫经 济的影子。在我国，也同样受到过泡沫经济的困扰，股市的重创和海南等地房 地产市场泡沫的破灭，至今仍留有许多印迹。对泡沫现象的研究已有了相当长 的历史。但真正对泡沫现象进行系统分析足从理性泡沫开始的，这项工作大约 始于上世纪6 0 7 0 年代。理想泡沫概念的提出是人们针对资产价格中经常可以观 测到的过度波动现象寻求解释的一种尝试，它可以从理性预期和局部均衡的角 度解释为什么会出现背离经济基础条件的泡沫现象。h a h n ，s a m u e l s o n 和s t i g l i t z 等人分别从理性预期出发证明了在某些条件下经济系统中可能出现理性泡沫 3 8 4 0 】。到了8 0 年代，b l a n c h a r d 和w a t s o n 从理性预期出发，在套利均衡条件卜， 求解出了理性泡沫解，同时还构造出了一种被称为爆炸性泡沫的理性泡涮4 “。 到了9 0 年代，随着鞅的引入，泡沫研究脱离了笼统的研究阶段，开始了分门别 类的细致研究。人们清楚地把理性泡沫划分为马尔可夫泡沫、确定性泡沫、近 似随机游走泡沫、爆炸性泡沫、内蕴性泡沫和外来性泡沫等不同类型。这种分 类为泡沫不同类型的实证研究提供了函数设定准备。 有了上述( 数学上的、经济学上的、物理学上的) 理论成果，对于泡沫的事 前预测( 市场崩溃的预测) 的研究才是有意义的。s o r n e t t e 在2 0 0 3 年发表的综述 性报告【4 ”，对市场崩溃行为的数学( 物理) 基础进行了广泛详实的总结和精彩 深刻评论，堪称最重要的文献之一。黄明坤“”以其理工背景利用计量经济学模 第一章引言 型刘同本泡沫经济存定性与定量两个方面都进行了充分的分析。郑鑫2 9 1 利用改 进的r b f 神经网络对深圳股之进行预测，也得到了小错的结果。我们在本文中利 用一种适用于样本数较少的基于最小风险的神经【嘲络模型支持向量机 对( 主要是中国的) 股市股指泡沫崩溃过程进行预测，结果是令人满意的。 第四节本文的组织 在本文中，第_ 章利用h o p f i e l d 模型解决已知度量参数情况下以及度量参数 不准确的情况下q o s 路由优化问题。对于前者，我们分别解决两个有代表性的 问题，即优化一受限路由优化和多限制路由优化；对于后者，我们在探讨了不精 确性的根源以及数学模型之后，也提出自己的h o p f i e l d 神经元模型。 在接下来的第三章中，我们开始本文的第二部分，即利用支持向量机对股票 市场股指的时间序列信号进行分析与预测，由于我们的研究对象是具有实际意 义的经济变量，所以我们首先要从数学角度表明这种预测的可能性，并在简要 介绍预测工具支持向量机模型的原理之后，对具有崩溃特征的时间段内的 上证指数以及道琼斯工业平均指数进行时间序列预测。在该章的最后一节，我 们还要利用一些宏观变量对台湾股市泡沫崩溃时的股指进行预测。 在最后一章中，我们将进行总结和展望。 第二章基于人工神经嘲络的q o s 路由优化 第二章基于人工神经网络的q o s 路由优化 第一节h o p f i e l d 神经网络模型“叫 1 9 8 2 年，j j h o p f i e l d 发表了他的影响深远的论文【1 2 1 ，为神经网络的应用拓 展了片新天地。在这篇论文巾，h o p f i e l d 将l y a p u n o v 能量函数的概念引入递 归网络模型，随着递归计算过程，能量函数最小化( 至少在局域内) ，网络收敛 到能量函数所决定的与输入模式具有最小距离的吸引子( 平衡点) 上，这一过 程使我们可以更深刻的理解网络动态行为的物理含义。 许多组合优化问题，比如旅行商问题( t s p ) ，都可以通过构造适当的能量 函数而利用h o p f i e l d 神经网络模型加以快速解决。 对于一个包括n 个神经元的h o p f i e l d 网络，他的输出有两种形式，二值化 或连续值。也就是说，设k 表示第i 个神经元的输出( 状态) ，那么，二值化就 意味着k 或者是1 ，或者是一1 ；而连续值则表示k 可以取区间 o ，1 上的任意值。 令w 。表示连接神经元f 和j 的权重，在对称的模型中，w d = w ”v i ，且w 。= o ，v i 。 连续h o p f i e l d 神经网络模型( 用类似图1 - 4 的电路可实现) 的动态方程和能量函 数分别表示为 坐：争t i j b - 旦+ ：一竺一丝 ( 2 1 ) 廊智 fro v , e ：一i 1 u n一兰+figt,y,vj gi ( v ) d v( 2 2 ) e = 一i 一 + ( 2 2 镏( u ) 2 南 2 3 ) 其中u j 是第i 个神经i 的净输入，t 为电路的时间常数， 表征s i g m o i d 函数 的最大导数值。在平衡点， v i = g i ( w f 一，) ( 2 4 ) i 式( 2 1 ) 所表示的更新过程丌j 以同步和异步两种方式工作，所谓同步更新，是 指所有的神经兀在每一步都同时更新，这样，所有的神经元就必须共享一个时 第二章基于人 ：神经网络的q o s 路由优化 钟；而异步更新则在每一步随机选择一个神经元进行更新。一般情况下，两种 工作方式输出相同的结果。但是当输入的模式与不同的吸引子有相同的距离时， ( 即输入模式处于两吸引子所在吸引域的边界时) 两种更新方式可能输出不同 的结果，即网络状态被吸引到不同的吸引子上，涉及到组合优化，即使输出的 结果不同，其输出都是最优解。考虑到电路实现必然是同步模式，我们在这里 也选用同步模式。从式( 2 1 ) 中还可以看到，随着递归过程的进行，网络的能 量也在减小，直到达到它的局部最小值。这个局部最小值点就是网络状态空间 的吸引子，如图2 1 所示，网络初始化为状态空间中的一点，随即向其所在吸 引域中的吸引子运动，形成运动轨迹。如果能构造适当的能量函数，从而使网 络状态空间的吸引子就是能量函数的最小值点，这样，我们就可以利用h o p f i e l d 神经网络模型来解决组合优化问题了。 状态空间 图2 1 状态空间中吸引子、吸引域以及运动轨迹示意图 满足各种组合的q o s 服务的路由选择可以看成一个最小非线性优化问题， 我们将在本章接下来的部分依次处理在确定参数情况下路由优化中的优化一受限 问题。多条件约束问题，以及在不确定参数下的延迟约束问题。 第二节d c l c 问题的神经网络解决方案 首先考虑第一类问题，即优化一受限路由( d c l c ) 问题。 通常，一个给定的通信网络被定义为一个有向图g ( n ，a ) ，n 为n 个顶点 第一章基于人t 神经网络的q o s 路由优化 的集合，对于通信网络来讲，就是n 个终端( 节点) ；a 为m 条边的集合，对应 由点i 到点，的每一条边( f ，) ，对于通信网络来说，就是从节点i 到节点，的链 路。定义一个费用矩阵c = c d ，c d 表示点f 到点，的费用，如果点i 到点，没有 连接，则c 定义为。0 ，冈为g 为有向图，c 。不一定等于c 。一个有向路径p “ 表示从始点s 到终点r 的路径，即j 叫巧叫( 见图2 2 ) ，从始点s 到终点t 的 总费用为i 5 l c 。：+ c 矿c 。同理，我们定义一个延迟矩阵d = d ，】。d c l c 问题就 是寻找具有最小总费用l “的路径p ”，同时，该路径的总延迟还不能大于一个 阈值d 。 为了使h o p f l e l d 神经网络能应用于上述问题，我们把最小的费用 ( l e a s t c o s t ) 作为优化目标，而把d e l a y c o n s t r a i n e d 作为限制项。定义一个m x n ) 的矩阵v = k ， ，n 为顶点数( 与通信网络中的节点数相同) ，每一个非对角 线单元k f 就是一个神经元，行x 和列i 都表示结点数，因此共需n x m 一1 j 个神经 元，如果点x 到点i 的边在费用最小的路由中，则圪，= l ；否则为0 。另外，再定 义一个矩阵【pe c i ，如果点x 到点i 的边在物理链路上确实存在，则p ，= o ；否则， p ，产1 。注意到每个点不能被经过一次以上，所以矩阵v 的每行和每列中包含的 元素“l ”不应多于一个，并且主对角的元素均为0 。 图2 2 d c l c 问题。链路状态参量= ( 延迟，费用) 对于优化目标，即最小费用路径问题，m u s t a f ak m a l i 和f a o u z ik a m o u n 提出如下的能量方程1 7 1 ： e 倒：等宝宝c ，_ ，+ 等宝宝n 。屹，+ 争n n ，一n ) z x = li = l x = li = 1 x = lp 1i = 1 ( 。- ) 4 4 5 ( 。，5 ) “ 5 ) 。 5 。 ( 2 ，5 ) + 等主窆_ ；( 1 一圪，) 十等( 1 一) x = li = 1 j ( # ，1 ) ( d j ) 第二章基于人工神经网络的q o s 路由优化 其中第一项是优化项，用f 寻找费用最小的路由；第二项可以避免在结果 中出现并不存在的物理链路；对于解中的每一结点，若其输入链路数等于输出 链路数，第三项为零，否则，该项不等于零；第四项迫使神经网络的状态收敛 到超立方体的2 n ( n 。个顶点上。第五项保证结果能形成一个从s 到d 的环路。 由 式( 2 1 ) 、( 2 2 ) 可得 等= 一争一等c ( 1 - 8 x a ，瓦) 一譬几( 1 - 屯瓦) 一心喜眩一) + 段砉帆一) 等( 一z + 譬如氏 v ( x i 1 n n x i 实际上，我们还要考虑限制条件( 即d e l a y c o n s t r a i n e d 部分) ，这一限制条件可 以表示为： 巩屹， 1 ( c ，) 。 ，= 5 第二章基于人工神经网络的q o s 路由优化 “ 。，而在模拟中，这是不可能的，那么九 到底选取多人时就可以满足要求呢? 为此我们进行了研究。图2 5 是我们研究的 结果，为了图示方便，去约束条件个数k = 2 ，即式( 2 9 ) 中只包含前两项。图 中横座标表示对第一种度量参数计算得到的嘲剀和约束值之比，即w ( p ) c ，纵 座标则对应第二种度量参数，g 。( p ) 搜索范围为横坐标、纵座标和不同 时 g 。( p ) 曲线所围成的面积， 斗o o 时，g 。( p ) 搜索范围为图中四个娥标轴所围成 的面积，可见在只有两个约束条件的问题中，旯= 1 0 和九= 1 0 0 的搜索范围相当 接近，而且当五= 1 0 时，g ，( p ) 的搜索范围已经非常接近整个搜索范围。所以在 大部分情况下，令五= 1 0 可以达到令五一。的效果。同样对于多个约束条件的问 题，x 也没有必要取得太大。 取得太大除了使计算量变大以外，还会影响ul 的取值，比如凡由1 0 变成1 0 0 ，则u1 也要相应的从0 0 1 变成0 0 0 1 甚至更小。 图2 5 对于不同的 ，g 。( p ) 的搜索范围。 接下来，我们将通信网络的节点数扩充到2 ( ) 个，仍寻找从节点1 到节点2 0 的路由，每条链路上的延迟和延迟抖动都是在( 0 ，1 0 ) 之间随机取值，约束条 件为d e l a y 3 且j i t t e r o 时等于1 而在x ! d 时其值为零。对于链路b ，f ) ，如果它相应的神 经元的输出圪。为正值，也就是说，的确有延迟被分配到这条链路上，这时s i g n ( v 。d 就等于1 ，而这条链路就成为最优路由的一部分。式( 2 1 0 ) 中的第一项表示所 选路由的总代价，由于总的概率是相乘的关系，所以我们对其取对数从而变成 相加的关系，这与将乘性度量参数变换为加性度量参数的技巧足一样的；对于 最优路由中的任一节点，只有当进入该节点的链路数f 1 等于流出该节点的链路 数目时项才等于零；第4 项只有在全部延迟要求被充分分配到通信网络巾的情 况下才等于零；而g l k p 5 项的f 1 的是使得神经网络模型能够生成从源节点s 至l j t 的 一条通路。 到f 1 前为止我们还血临着一些实际计算上的困难，首先，冈为函数s i g n 似j 的微分是一个6 函数，这样一来，在我们计算之前必须用一个合适的函数来代替 s i g n 以j ，以便顺利的计算微分值。同时我们还希望存计算过程中，这个替代函 数能够逐渐逼近真正的s i g n 似j ，所以我们选择了下面的这个分段线性连续函数： 第二章基于人工神经网络的q o s 路由优化 吒，0 屹。1 c t 0 聊) ，至于链路4 7 和7 8 ，相应的值为1 9 5 8 2 、 6 2 4 4 和2 6 7 9 5 、5 5 6 3 。图2 9 中我们没有画山另外那些神经元的动态行为， 因为他们在计算一开始就迅速衰减到零了。我们在图2 9 中还可以看到，网络的 收敛速度非常快，在8 0 1 0 0 次迭代之后，网络的输出已经没有明显的变化了。 吃 也l 口 ，。l = 、， 儿 ，lg 第二章基丁人上神经网络的q o