（通信与信息系统专业论文）基于坐标系统的ba网络可视化.pdf

北京交通大学硕士学位论文 y8 7 8 1 5 摘要 因特网的无尺度特性已得到广泛认知，具有幂律度分布的无足度网络 呈现出多星式弱层次结构。对这种网络拓扑的建模己取得很大进展，但现 有的可视化工具对这种层次结构的反应并不理想。能够反映这种结构特征 的网络可视化工具对网络研究具有一定的实际意义。 b a 模型以优选连接机制模拟无尺度网络的增长模式，能够形成具有 幂律度分布的网络拓扑，但是由于b a 模型中完全不考虑节点的空问位置 信息。因而简单地给节点赋予随机坐标所显示的b a 算法生成图不能反映 无尺度网络的结构特征。 本论文在这方面进行探索，提出一种8 a 网络可视化工具。本文基于 节点覆盖面积与节点度相关的概念进行b a 生成图节点空间位置的推断， 依据推断出的空间坐标对b a 生成图进行可视化，一定程度上反映出卧生 成图中弱层次结构。在坐标推断的具体实现上采用全局网络定位( g 1 0 b a l n e t w o f k p 0 s i t i o j i i n 岛g n p ) 坐标系统，这种坐标系统通过最优化算法依据 可测量的主机之间的时延距离推断计算每个主机在网络中的坐标。本文通 过仿真比较不同最优化算法在实现g n p 机制上的性能和复杂度，确定采用 单纯形算法实现了g n p 机制。论文给出采用g 肿机制实现b a 生成图的启 发式算法及仿真结果。 由于仿真得到的网络图层次并不是十分清晰，离预期结果有一定距 离，算法需要进一步的改进，寻找更加合理的坐标计算方案。 关键字：无尺度网络，b a 模型，0 n p ，最优化算法 北京交通大学硕士学位论文 t h ec h a f a c t e r i s 雠o fi n l e n l 毗t h a tv c n e x n e c t i v j t j e sf o l l a was c a l e f 记e p o w e r _ l a wd i s t 工i b u t i o nh 祁b c c nw e l lc o g i z c d a n ds c a k - f r e en e t w d r ks h a w s 8p o o rm u l 睡s t a rh i e m r c h i c a is l r u c t i l f e g r a t e 吖0 l u t i o nh a sb c ea o q u 沁di m o d e l j z a t i o no ft l l i sk i n do fn e t w o mt o p q l o g y b u te 地t e dv i s u a l i z a n o nt o l o l s c 叫ts h o wi h i sh i e f a r d 正c 矗ls t r u c l 呲i d e a n m s l i a l i z a i i o nl l sw h j c hs h o w t h i sh i e r a r c h i c a ls t 九l c t i l r ch a s p r a c t i c a ie f 缸“m f c s e a f c h0 fn e t w d k b am o d c ls i m u l a t 船t h e g r o w mo f s c a l e - f r e en 咖。出b a s e d 佃 p r e f 锹m d a l 甜a c h m e 此柚di tc a | lf o 皿an e 啪r k 叫) o l o g y0 fp o w e i - l a w d i s t r i b u t i o n b c 僻e os p a t 试p o s 铂o ni i i 如r m a t i o ni s n s i d c r e di nb a m o d 吐b am o d e l1 i t h 砌d o ms p a t 瑚p 0 s n i o nc a ns h o wt h ch j 删c a l s t n l c 眦eo fs c a l e - f t c en e n v o f l l t b j sp a p c rd o e ss o m ee x p i 面n gw o r k 柚d 脚o s e daa l g 。r i t h l l lt 0 v i s u a l i z eb an e t w l r kt h i sp a p e fc o m p u t 璐t h e 姗f d i n a t eo fn o d e si nb a m o d e lb a s c do n t h ec o n 。e 两仰t t i “t l l e v e ra 托ao f a n o d e 叫d t h ed c 蓼e e0 f t h i sn o d ea r ei n t e c i a t e d a n das h a w sb i e r 岫i c “s t r u c t u r eo fb a e t w o f k o ns o r n eb x t e n t t 蛐sp a p 盱d o e sal o to fs h u l a t i 叩s t o 明a l y z et h e p e d 咖c eo f t h ep r o p o s e da 埯嘶t l l 1 b u tt h ef c s u l to ft l l e p r 0 p o da l 鲫m mh a ss o m ed i s t 粕c ct o t l l e e x p e c t c dr c s u l t ，彻d t 1 1 eh i 翻1 f c h i c a ls t f l l d u r eo f e t w d r kg r a 曲g o tf r o m s 妇u l a t i 彻d o e s td e a re n o u g h 1 1 l ea l 酬瑚s h o u l db e 油p r o v e da n da m o r er e a s o n a b l cm e t h o dt og e t o r d i n a t es h o u l db ef o u d i 岫，w o r d s s c a l e f r e en e 押o r k ，b a m o d c l ，g n p ，o p t i m i z a 虹o nt k o i y 北京交通大学硕士学位论文 第一节前言 第一章绪论 网络有随机网络和无尺度网络，许多网络包括因特网、人类社会和人 体细胞代谢网络等，都是无尺度网络。研究无尺度网络，对于防备黑客攻 击、防治流行病和开发新药等，都具有重要的意义。 现实世界中许多系统都可以用复杂网络来描述 卜4 ，网络节点为系 统元素，边为元素间的互相作用和相互联系( 即关系) ，如社会网络中的 合作网、信息网络中的万维网、技术网络的k t e m e t 网和运输网、生物网络 的代谢网络，等等。由于现实网络的规模一般很大，节点间的相互作用多 而复杂，其拓扑结构基本上未知或未曾探索。两百多年来，人们对描述真 实系统拓扑结构的研究经历了三个阶段。在最初的一百多年里，科学家们 认为真实系统因素之间的关系可以用一些规则的结构表示，例如二维平面 上的欧几里德格网；从2 0 世纪5 0 年代末到9 0 年代末，无明确设计原则的大 规模网络主要用简单而易于被多数人接受随机网络来描述 5 ，随机图的 思想主宰复杂网络研究达四十年之久；直到最近几年，科学家们发现大量 的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同 的统计特征的网络，其中最有影响的是小世界网络 6 和无尺度网络 7 。 在过去4 0 多年里，科学家习惯于将所有复杂网络看作是随机网络， 随机网络的最大特点就是高度民主，绝大部分的节点拥有比较相似的连接 数量。连接数量比平均水平高许多或低许多的节点，都是很少见的。因此， 当a b a r a b a s i 【7 - 8 】和r 舢b c n 【7 8 】等人于1 9 9 8 年研究互联网当中网页 的相互指向结构时，本以为会得出一个随机网络。因为他们觉得人们会根 据自己的兴趣，来决定将网络文件连结到哪些网站，而个人兴趣是多种多 北京交通大学硕士学位论文 样的，可选择的网页数量也极其庞大，因而最终的连结模式将呈现出相当 随机的结果。但是，最终的统计结果出乎预料。他们发现，万维网实际上 是由少数高连结性的页面组织起来的，8 0 以上页面的连结数不到4 个。 然而只占节点总数不到万分之一的极少数节点，却有1 0 0 0 个以上的连结。 这种网页的连接分布遵循所谓的“幂次定律”：任何一个节点拥有k 条连 接的概率，与1 k 成正比。它不像钟形曲线那样具有一个集中度很高的峰 值，而是一条连续递减的曲线。如果取双对数坐标系来描述幂次定律，得 到的就是一条直线。 e r 随机网络模型有很大的不足，在该网络模型中，网络规模固定不 变并且所有节点都是平等的。而现实情况却并非如此，实际网络中网络规 模是不断扩展的( 成长性) ，并且新进入的节点在选择连接时具有偏向性 ( 择优连接) 。久b a r a b 勰i 【7 】和r 砧b e n 【7 】根据这两种特性，设计了一 个网络演化的计算机模拟程序，结果显示，具有择优连接特性并且持续成 长的网络，确实会发展成无尺度网络，并且节点的分布也遵循幂次定律， 虽然这个理论模型( b a 模型) 过于简化，且需要根据具体情况加以调整， 但还是对现实世界中无尺度网络的普遍存在提供了解释。 无尺度网络指节点度服从幂律分布的网络。b a 模型是第一个无尺度 f 网络演化模型，它捕捉到了无尺度网络形成的两个必不可少的机制增 长和择优连接 7 ，8 ，说明了大规模复杂网络自组织成为无尺度状态的原 因。b a 开创性论文的发表，掀起了无尺度网络和b a 模型研究的高潮，在 新世纪初的最近几年里，科学家们就提出了许多产生无尺度网络的模型 9 1 5 ，并对b a 模型的主要性质进行了深入研究 1 6 ，1 7 另一方面，分布式网络服务的兴起促进i m e m e t 坐标系统的发展与应 用。各种分布式网络服务要求知道主机间的网络距离，而如果按照需求进 行网络距离的测量则会增加网络的负担，不仅开销大，而且很花费时间， 北京交通大学硕士学位论文 所以可以通过预测网络距离避免大量的测量。利用h i t e r n e t 坐标系统可以 预测主机间的网络距离，因而这种坐标系统在p 2 p 网络中得到了广泛的应 用。 b a 模型及其扩展模型得到了广泛的应用与研究，然而我们通常根据 无尺度网络的两个特性得到的b a 网络图是杂乱无章的，并不便于人们观 察和研究。如果能有一种方法可以使b a 网络图更加清晰明了，那么对于 研究b a 网络是有重要意义的。在这篇论文中，我将i n t 咖e t 坐标系统应用 到b a 模型中，通过b a 网络中各个节点之间度的关系赋予每个节点个 坐标值，目的是使最后生成的b a 网络图更加清晰，具有可视性，从而实 现b a 网络的可视化。 第二节论文完成的工作 这篇论文对i n t e r n e t 坐标系统、无尺度网络及b a 模型进行了深入的 理论研究和仿真观察，并对研究过程中遇到的最优化问题进行了理论分析 和仿真比较。章节安排如下：第二章和第三章综合研究了本论文需要用到 的理论基础，包括i n t 唧e t 坐标系统之一g n p 、几种最优化算法的理论知 识，并通过仿真对其中的一些算法进行了比较；第四章是本论文的中心， 首先对无尺度网络进行了简单的介绍，接着描述了b a 模型的算法，提出 了将i n t 啪e t 坐标系统之一g n p 运用到b a 网络中的算法，并对新算法对 各种情况下的b a 网络的性能进行仿真分析；第五章总结整篇论文的工作， 指出将来可以进行的工作。 3 北京交通大学硕士学位论文 第二章i n t e r n e t 坐标系统的理论研究与仿真 第一节什么是i n t e r n e t 坐标系统 分布式网络服务的兴起促进h n e m e t 坐标系统的发展与应用。各种分 布式网络服务要求知道主机间的网络距离，而如果按照需求进行网络距离 的测量则会增加网络的负担，不仅开销大，而且很花费时间，所以可以通 过预测网络距离避免大量的测量。 如何找到离客户最近的服务器? 网络距离如何定义? 这是在建立 i n t e m e t 坐标系统时要首先考虑的问题。首先我们要明确，由于路由策略 及连接性等原因，地理距离与网络距离并不等价，即使把地理距离看作网 络距离，仍然要解决一个问题：客户如何从n 个距离中选择最近的服务 器? 如果我们把网络延时作为网络距离则更加合理，因为网络延时与路由 策略、各节点间的连接性密切相关，能够更加贴切地表征网络距离。但仍 然存在n 个距离的问题：需要n 次测量，更新网络距离表，如何解决这 些问题昵? 通过建立i n t e m e t 坐标系统可以解决上面提到的问题。在这种坐标系 统中，坐标间的距离作为网络距离，通过少量实际测量的距离计算出节点 坐标，从而通过节点间的坐标关系得到大量近似的网络距离。 建立i n t c m e t 坐标系统的常规方法： 1 如何将网络映射到坐标系中? 4 北京交通大学硕士学位论文 h 麓鸯 m s m a p p i n g y 图2 一卜l网络到坐标系统的映射 2 建立h t e m e t 坐标系统的一般步骤： l 、选择主机的一个子集作为参考点( r p ) ： 2 、测量r p 之间的距离； 3 、计算每个r p 的坐标； 4 、测量主机到每个r p 的距离； 5 、计算主机的坐标 针对l 、3 、5 条的不同实现方案出现了几种不同的坐标系统，如 g n p 【1 8 】、p 王c 【2 3 】、i j g h 也o u s e s f 2 4 】，咖a ll a n d m a r k f 2 5 】，以及v a l d i 4 6 】。 下面对g n p 坐标系统进行详细的理论研究。 第二节g 】 坐标系统 为了发掘因特网基础结构的巨大潜力，一种新的大规模的全球分布式 网络服务和应用已经形成：内容访问网络 1 9 2 0 ，以及p 2 p 文件共享如 n a p s t e r 和g n u t e l l a 。由于这些系统在选择通信路径上有很大的灵活性，它 们可以受益于基于网络性能的智能路径选择方案。例如在p 2 p 文件共享应 用中，客户端要知道自己和有所需文件的所有对等端之间的可用带宽。然 而，虽然诸如可用带宽和延时等动态网络性能特征是和应用紧密相关的， 5 北京交通大学硕士学位论文 并且可以按需求进行精确测量，但是这些在分布式系统中需要考虑大量的 大区域跨越的端到端路径，从而使得进行按需网络测量时由于其昂贵的开 销、时间花费及其带来的网络负担变得不实际。 为了协调性能优化和可扩展性之间的冲突，有前景的方法是要尝试预 测主机闻的距离( 如，往返时间和发送延时，这是相对稳定的特征) ，并 且将它作为减小或取消按需网络测量需求的优先辨别度量。因此，关键的 问题是设计出能够准确地、可扩展地、及时地预测网络距离的方法。 本节描述了在p 2 p 网络中如何使用基于坐标的机制来预测网络距离， 介绍了常用的是全局网络定位( g 1 0 b a ln c t w o r kp o s j t i i n g ，g n p ) 1 8 方 法。这种方法的主要特点是通过将因特网建模成一个几何空间来计算绝对 坐标并建立因特网坐标系统，再以绝对坐标为基础预测网络距离。由于终 端主机维护它们自己的坐标，这些方案允许终端主机一旦发现其它主机存 在就计算它与其它主机之间的距离。由于坐标在描述主机间距离时十分有 效，这使得该方法在网络测距方面具有很高的可扩展性。 2 2 1 网络距离预测方法 在f r a n 豳e t a l 的初期工作中 2 1 ，作者从拓扑的角度详细分析了网络 距离预测中的问题，并提出了第一个完整的解决方案，称为i d m a p s 。它 是一种基础设施服务，其中特殊的h o p s 服务器维护一个虚拟的因特网拓 扑图，其中包括终端主机和特殊主机( 被称为追踪器1 h c e 碍) 。主机a 和 b 之间的距离通过将追踪器虚拟拓扑上a 和距其最近的追踪器t l 之间的 距离，加上b 和距其最近的追踪器t 2 之间的距离，加上t 1 和t 2 之间最 短路径的距离来估算。随着追踪器数目的增加，i d m a p s 的预测准确性将 会提高。由于它被设计成客户一服务器结构的解决方案，终端主机可以通 6 北京交通大学硕士学位论文 过询问h o p s 服务器来得到网络距离预测。目前已经有部署的实验性的 i d m 印s 系统。 本节介绍另一种在p 2 p 网络中使用的网络距离预测的体系结构 1 8 。 与传统的基于客户一服务器的方案相比，p 2 p 系统在伸缩性上有潜在的优 势。由于没有共享服务器的需求，故潜在的性能瓶颈可被消除，尤其当系 统规模增大的时候，由于没有与远端服务器通信时的延时，性能也有可能 得到改善。另外，这种结构也与正在形成的p 2 p 应用相一致，这些应用如 媒体文件共享，内容访问网络等，可以很大程度地受益于网络距离信息。 这种用在p 2 p 网络结构中预测网络距离的方法是基于坐标的。它的主 要思想是让终端主机维护描述它们在因特网中位置的坐标( 如一组数字 集) ，这样网络距离可以通过对主机坐标进行距离函数的运算来估计。基 于坐标的方案很适合用于p 2 p 体系结构，因为在p 2 p 应用中，当一个终 端主机发现其他终端主机的身份时，预先计算的坐标会被捎带确认，所以 终端主机可以立即计算出网络距离。另一个基于坐标的方法的好处就是坐 标在总结大量距离信息时是非常有效的。例如，在一个多用户的应用中， k 个用户间所有路径的距离可以通过置组坐标、每个坐标d 个数字( 如 o ( 足d ) 个数据) 有效地通信；而单个距离有k ( 足一1 ) 2 个( d ( k 2 ) 个数 据) 。所以这种方法可以在大量减少通信开销的情况下交换本地的计算结 果。以达到更高的可扩展性。 用以距离预测的绝对坐标，可由全局网络定位( g n p ) 1 8 的方法得 到，如图2 2 1 所示。其关键思想在于将因特网建模成个几何空间( 如 三维欧氏空间) ，并将因特网中的任何主机的位置表征为这个空间中的一 点。因而任何两个主机间的网络距离可以由它们之间建模的几何距离来预 测。 7 “l ，y y 。 x oy z ，z 甜 t z 1 ) 髟k 毯、 】【 蓬 建 i 口 ( n ，3 z 3 ) 图2 2 1 网络中主机的几何空间模型 2 2 2 全局网络定位( g n p ) 为使因特网中的几何主机坐标的计算是可扩展的，首先将整个系统结 构分为两部分。第一部分包括少量被称为路标( 1 柚d m a r k ) 主机的分布式 集合首先在选定的几何空间中计算它们的坐标，将它们的坐标作为参考， 并散布到任何想参与定位的主机中。第二部分包括任何主机只要拥有路标 主机的坐标，就可以计算出自己与这些路标相关的坐标。 在下面的部分中，将详细描述这种两部分的结构。 假定将因特网建模成一个特殊的几何空间s 。那么在s 中的主机日的 坐标记为c 三，在这些坐标上求解距离的函数记为，s ( ) ，计算出的主机胃， 和h ：的距离，5 瞄。，四：) 记为露。，。 a 第一部分：路标主机坐标确定 北京交通大学硕士学位论文 。誊i 誊露誊；i ii + 篱j 瓣然j ；i j 曩。j 。1 | 繇i 骋n 秘| 董_ i j ；| j 。j ： ；1 ， 曩 x 2 v “1 苦7 嗲 瓷 曩? 蠛歌筑窑辆 【档y 渤 图2 2 2 路标主机坐标确定 这部分的目的是使用少量主机的分布式集合作为路标，提供一组参考 坐标，以便为s 中的其它主机确定各自的坐标。如何最优的选择路标的位 置和数量仍然是一个开放性问题。然而，可以看到，对于一个d 维的几何 空间，我们必须至少用d 十1 个路标。否则，不可能唯一地计算出主机地 址，这个问题在下一部分将会看的更加清楚。 假设有个路标：厶上。路标之间使用i c m p 的p i n g 消息简单地 测量路标间的往返时间( r 1 r r ) ，并且将每条路径的最小测量值作为x n 距离矩阵的一半基础值( 认为该矩阵是斜对角对称矩阵) 。将测到的主机 h 。和丑：的距离记为d 且马。接下来使用测量的距离吒厶( 1 j ) 的一个主 机( 有可能是个路标中的个) 来计算路标在s 中的坐标。目标是为 个路标找到一组坐标呓，c 乏，来使得测量的距离与s 中计算距离的整 体误差最小。用数学表达法就是最小化下面目标函数厶“) ： ，o w t 喊，c 乏卜q 善骆，动 2 。2 1 ) 其中( ) 是误差度量函数，可以用下面简单的平方误差 9 北京交通大学硕士学位论文 ( d h h ：，蠢置：) - ( d 马片：一孑主日，) 2 或一些其它的复杂的误差测量公式， 目标函数中误差测量的方式将严重影响最终的距离预测的准确性。用 以上这个公式，坐标的计算可被视为多维全局最小化问题，而这个问题可 由许多可用的方法如s i m p l e xd o w h i l l 2 2 来近似解决。图2 2 2 说明了 三个路标在二维欧氏空间中的路标主机操作。注意到由于一组坐标的任何 旋转和或附加平移将保留路标主机间的距离，因而路标主机的坐标有许 多解决方案。但是由于这些坐标在g n p 中仅仅被用于一组参考，所以重 要的是它们的相对位置，任何解决方案都是可以满足的。当由于时间推移 需要重新计算路标主机的坐标时，如果在最小化问题初始阶段简单地将旧 的坐标代替随机数字作为输入，那么就可以保证坐标不会有很大的改变。 一旦计算出路标主机的坐标c 三。，呓，它们连同采用的几何空间5 的标识、相应的距离函数，5 ( ) ( 可能隐式地) ，就被发送到任何想参与到 g n p 的普通主机。这里，我们不详细说明发送机制( 如单播还是多播，推 进还是牵引) 和所采用的协议。 b 第二部分：普通主机坐标确定 图2 2 3 普通主机坐标确定 1 0 川 北京交通大学硕士学位论文 在体系结构的第二部分，要求普通主机主动参与，使用几何空间s 中 已经确定的路标主机坐标，每个普通主机可以得到自己的坐标。为了达到 这一目的，普通主机日用l c m p 的p i n g 消息测量它到个路标的r t t 时 间，并且在每条路径上选择最小的测量值作为实际距离。在这个阶段，路 标主机完全是被动的，它们简单地应答到来的p i n g 消息。丽主机日可以 使用这个测量的主机到路标的距离d 凰计算出自己的坐标c ；，并使这 个坐标使得测量值和s 中坐标计算出的主机到路标距离的整体误差最小。 数学表达方式就是力求最小化以下目标函数，曲，：( ) ： 厶：( c 扣q 黜m ，磕) 2 3 ) 其中( ) 为前面讨论的误差测量函数。如同得到路标的坐标一样，这个计 算可被视为一般的多维全局最小化问题。图2 2 3 说明了一个普通主机在 有三个路标主机的二维欧式空间中的操作过程。 现在我们清楚了为什么路标主机的数目j v 一定要比几何空间s 的维 数d 大。如果比d 小，路标主机的坐标就取决于至少d l 维的超平面。 因此，目标函数不能区分d 维空间中的一点和它通过路标主机的超空间的 映射，导致主机坐标模糊，这样就不能保证主机坐标的唯一性。使用比路 标主机数目少的坐标维数可以简单地避免这种明显的问题。 2 2 3g n p 存在的问题 路标主机是g n p 方案中的重要设施，它的数目确定、超载和出现问 题时导致的网络测距的失败等等这些问题都是存在的，因此如何最优的选 择路标主机是一个研究点。另外，在g n p 中所使用的s i i i 叫e xd o w n l l i u 的算法，它并不能保证坐标的唯一性，而且如果算法的起始点选择不当将 北京交通大学硕士学位论文 导致目标函数得不到最小值，因而得不到坐标。 2 2 4 其它几种矾啊臻阐暇坐标系统 继g n p 之后，又出现了几种改进的i n t e m e t 坐标系统，如p i c ( p r a i ：t i c a l i n t c m e tc b o r d i n a t e s ) 2 3 、i j 曲t h o u s e s 2 4 等。其中p i c 相对于g n p 的 改进在于它的路标主机的数目是可以增加的，任何一个已经计算出自己坐 标的主机都可以作为整个坐标系统的路标主机。而u 曲t h o u s e s 中主机可 以自己选择参考点( 1 i g h t h o u s e s ) ，并且坐标的计算都是线性变换。另外， 还出现了一些基于p c a 的技术，如n l l a ll a n d m a r k s 2 5 等等。 利用因特网坐标系统来预测网络距离大大减小了终端主机的开销，并 具有很好的可扩展性。目前有很多应用都可以采用这种技术来改善性能， 如分布式网络游戏中最近服务器的选择、p 2 p 网络的构建、移动a d - h o c 网络中路由以及网络距离估计等。由此可见因特网坐标系统是很有发展前 景的，但还有很多开放性问题如路标主机的位置、几何空间的维数、路由 策略以及最小化误差函数等，这些问题需要更多的研究人员去探讨和解 决。 第三节g n p 坐标系统的仿真 采用上面所说的s i n l p l c xd ( 1 w n h j l l 算法解决误差总和最小化问题，我 们对路标主机使用m 棚a b 进行仿真，在程序中设路标主机的数量为n ， 并给定路标主机间的实测距离，实现以上描述的g n p 算法后，得到的仿 真结果如下，图中横坐标代表每两个节点之问存在的一个实测距离与预测 距离的误差点，总坐标代表误差。 当改变网络中路标主机的数量n 分别为5 、1 0 、2 0 时，误差图如下： 北京交通大学硕士学位论文 图2 - 3 1n = 5 时，f a v a l ：o 0 0 2 1 ；e x i t n a g = 1 o u t p u t = i t c 例吐s ：7 6 8 ，f i l n c t i o n c o u m ：1 1 0 1 图2 3 2n = 1 0 时，f 打a l = 3 8 7 8 7 ；e x i t n a g = l 0 u t p u t = i t e m t i o n s ：7 9 7 4 ； f u c t i o n c o u n t ：1 0 0 8 4 北京交通大学硕士学位论文 图2 3 2n = 2 0 时，f a v a l = 3 7 8 9 7 1 ；d u t p u t = n e r a t i o 越：4 7 1 4 6 ； f i m c c o u n t ：5 4 7 4 0 可见随着n 增大，要不断调整m 积1 t e r 和m a x f u n e v a l 参数的值，默认 值为2 0 0 未知数，但在求较多未知数时是远远不够的，调整不当可能使 函数不收敛。另外随着n 增大，运行时间也增大。 s i m p l c xd o w i l h i l l 算法是最优化算法的一种，最优化在航空航天、生 命科学、水利科学、地球科学、工程技术等自然科学领域和经济金融等社 会科学领域有着广泛和重要的应用，它的研究和发展一直得到广泛的关 注。最优化的研究包含理论、方法和应用。最优化理论主要研究问题解 的最优性条件、灵敏度分析、解的存在性和一般复杂性等。而最优化方法 研究包括构造新算法、证明解的收敛性、算法的比较和复杂性等。最优化 的应用研究则包括算法的实现、算法的程序、软件包及商业化、在实际问 题的应用。在下面一章里将简单介绍几种最优化算法。 1 4 第三章最优化算法 第一节单纯形( d o w n h ms i m p k l x ) 方法 d o w l l l l i us i m p k x 方法 2 2 是由n e l d e r 和m e a d 两位在1 9 6 5 年提出来 的，下面整理出d ( w n l l i l ls i m p l e x 方法的特点： 0 ，o s c 2 确定搜索方向以，按照一定的规则，构造，在点砟处的下降方向作为 搜索方向； 确定步长因子口。，使得目标函数在某种意义上取得下降： 令 2 r 托京交通大学硕士学位论文 吒+ 。一+ 吼以 ( 3 3 1 ) 若。满足某种终止条件，则停止选代，得到近似最优解坼+ 1 0 否则， 重复以上步骤。 3 3 2 牛顿算法 牛顿法是利用目标函数的二次t a y l o r 展开式并将其最小化的方式进 行最优化的优化算法。 设f ( x ) 是二次可微实函数，彤，h e s s e 矩阵v 2 ，( ) 正定a 在 附近将，扛) 二次t a y l o f 展开有 ，( 耳+ s ) 一q ( t ( s ) 一，( ) + w ( 以) 7 d + 三s w ( 黾) s ( 3 3 2 ) 其中，s 一并一 ，口( ( j ) 为，b ) 的二次近似。将式( 3 3 2 ) 右边极小化， 便得 矗。一一 v 2 厂( & ) 】w ( 毛) ( 3 3 3 ) 这就是牛顿算法迭代公式。在这个公式中，步长因子靠一1 ，令 qz v “( ) ，g v 2 ，( 磁) ，则( 3 3 3 ) 可写成 h + 1 ；x i g ；1 9 i ( 3 3 4 ) 对于正定二次函数，牛顿法一步即可达到最优解，对于非二次函数， 牛顿算法并不能保证经有限次迭代求得最优解。但由于目标函数在极小点 附近近似于二次函数，故当初始点靠近极小点时，牛顿法的收敛速度一般 是快的。但是应当注意的是当初始点远离最优解时，瓯不定是正定的， 迭代方向就不一定是下降的方向。这样就不能保证牛顿算法的收敛性，这 北京交通大学硕士学位论文 样也说明恒取步长因子为l 也是不合适的，应该在牛顿法中采用某种一维 搜索来确定步长因子。 下面给出带步长因子的牛顿法的步骤： 步1 选取初始数据：取初始点，终止误差5 ，0 ，令：置o ； 步2 计算。若恬。8 c ：，停止迭代，输出黾： 否则进入下一步； 步3 解方程组构造牛顿迭代方向。即求解q 或- 乳，求出喀； 步4 进行一步搜索，求吼使得 ，( t + q 矾) 一嘧，( 耳+ 睇噍) 令耳+ 1 一黾+ 破，七：一七+ 1 转第2 步。 3 3 3 拟牛顿算法 由于牛顿法需要利用h e s s e 矩阵提供的曲率信息。而计算h e s s e 矩阵的 工作是非常巨大的，对于复杂的问题，这个计算也是非常困难的，这样就 导致仅仅使用目标函数一阶导数信息的方法产生，拟牛顿算法就是利用目 标函数值，和一阶导数占的信息，构造出目标函数的曲率近似。而不需要 直接计算h e s s e 矩阵，同时又保