（计算机软件与理论专业论文）基于蚁群算法的异构数据集成动态调度优化研究.pdf

太原理工大学工学硕士研究生学位论文 基于蚁群算法的异构数据集成动态调度优化研究 摘要 随着计算机和网络技术的加速发展，各种数据以不同的形式存储在不 同的系统中，呈分布异构状态。而越来越多的用户希望能够透明地获取和 处理这些海量信息源中有用的数据，这也是数据集成系统研究一直是相关 领域一个非常热门话题的主要原因。异构信息集成系统的目的是通过集成 各种可用资源建立一个复杂的信息系统，屏蔽现在已有的各种异构数据管 理系统不同的访问方法和用户界面，给用户提供一个访问多种异构数据源 的公共接口，建立一个集成处理多种数据源、整合多个数据查询结果的信 息交互处理平台。 本文重点研究的异构数据集成系统动态调度优化机制是在数据源的自 主性以及数据量不断增加而严重影响系统性能下提出的。以往提出的调度 优化机制大多受数据源自主性以及网络的传输速度的影响，所以对系统中 大量返回结果提供一种快速而有效的调度机制是当务之急。 蚁群算法是一种基于启发式的仿生进化算法。已经在若干领域，特别 是组合优化问题中获得了成功的应用。如：t s p 、q a p ( q u a d r a t i ca s s i g n m e n t p r o b l e m ) 、j o b s h o p 调度等，易于与其它方法结合，其有较强的鲁棒性和自 组织性。本文在阅读了大量相关论文基础上提出了一种基于蚁群算法的异 构数据集成动态调度优化机制，同时引入了物化策略和分域求解策略。这 三者的结合有效地解决了初始化延迟、数据的突发性以及慢传输速率问题， 可以独立于系统的其它模块和数据源而自行调度。 太原蘧工大学工攀硕士磺究生学位谂文 最嚣，通过与本文介绍的静态调度优化算法( m s t - s o ) 矛d - - 种基于统计 推? i 受( s t a t i s t i c a lr e a s o n i n g ) 的动态调度优化算法( s r - d o ) 进行算法性能比较 得出，基于蚁群算法的异构数据集成动态调度优化算法a c d s a 性能上优异 前两者奄 关键字：异构，数据集成系统，动态调度优化，蚁群算法 h 太原理工大学工学硕士研究生学位论文 r e s e a r c ho fh e t e r o g e n e o u sd a t a i n t e g r a t i o nd y n a m i cs c h e d u l i n g o p t i m i z a t i o nb a s e d0 na n tc o l o n y a l g o r i t h m a bs t r a c t a c c e l e r a t e sa l o n gw i t ht h ec o m p u t e ra n dt h en e t w o r k i n gt od e v e l o p ，e a c h k i n do fd a t as a v e sb yt h ed i f f e r e n tf o r mi nt h ed i f f e r e n ts y s t e m ，a s s u m e st h e d i s t r i b u t e dh e t e r o g e n e o u ss t a t e m o r ea n dm o r ep e o p l ew a n tt og a i na n dp r o c e s s t h eu s e f u li n f o r m a t i o na m o n ge a c hm a s s i v ei n f o r m a t i o ns o u r c e sa n dd i f f e r e n t i n f o r m a t i o ns o u r c e si nt r a n s p a r e n t l y , i ti sa l s ot h er e s e a r c ho nd a t ai n t e g r a t i o n s y s t e mw a sa l w a y st h ep r i m a r yc a u s eo fv e r yh o tt o p i co fd i s c u s s i o ni nr e l a t e d d o m a i n t h ea i mo fh i i s ( h e t e r o g e n e o u si n f o r m a t i o ni n t e g r a t i v es y s t e m ) i s e s t a b l i s hac o m p l e xi n f o r m a t i o ns y s t e mb ym a k i n gu s eo fa v a i l a b l ei n f o r m a t i o n s o u r c e s ，s h i e l dm o s to ft h ed i f f e r e n c e so fe x i s t i n ga c c e s sm e t h o d sa n du s e r i n t e r f a c e so f e a c hh e t e r o g e n e o u sd a t am a n a g e m e n ts y s t e m s i ta l s op r o v i d e st o t h eu s e ra ni n f o r m a t i o ni n t e r o p e r a t i n gp l a t f o r ma sac o m m o ni n t e r f a c et oa c c e s s m u l t i p l eh e t e r o g e n e o u sd a t as o u r c e s ，i n t e g r a t em a n a g i n ga n dc o m b i n et h e i n t e r m e d i a t eq u e r yr e s u l t sf r o mt h e s es o u r c e s h e t e r o g e n e o u s d a t a i n t e g r a t i o nd y n a m i cs c h e d u l i n go p t i m i z a t i o n m e c h a n i s mi st h e i m p o r t a n t o ft h i s p a p e rr e s e a r c h ，i t i s p r o p o s e s t h a t i i i 太原理工大学工学硕士毳器究釜学位论文 a u t o n o m o u sd a t as o u r c e sa sw e l la st h ed a t aq u a n t i t yi n c r e a s eu n c e a s i n g l yh a d s e r i o u si n f l u e n c es y s t e mp e r f o r m a n c e t h es c h e d u l i n go p t i m i z a t i o nm e c h a n i s m b e i n gp u to u tb e f o r ew a sa f f e c tb ya u t o n o m o u sd a t as o u r c e sa n dt h er a t eo ft h e n e t w o r kt r a n s m i s s i o n + d e s i g naf a s ta n de f f e c t i v es c h e d u l i n gm e c h a n i s mf o rt h e r e t u r nr e s u l t so ft h es y s t e mi su r g e n ta f f a i r s 。 a n tc o l o n ya l g o r i t h mi sak i n do fb i o l o g i c a le v o l u t i o na l g o r i t h mb a s e do n t h eh e u r i s t i c i tw a sg e tt h es u c c e s s f u la p p l i c a t i o ni ns o m ed o m a i n s ，s p e c i a l l yi n t h eq u e s t i o no ft h ec o m b i n a t o r i a lo p t i m i z a t i o n ，f o re x a m p l e ，t s p 、q a pa n d j o b s h o pa n ds oo n ，a n da l s ob ee a s yt ou n i t et h eo t h e rm e t h o d s ，h a v i n gs t r o n g r o b u s t 。a f t e rr e a d i n gl o t so ft h er e l a t e dp a p e ro fd a t as c h e d u l i n g ，t h i sp a p e r p r o p o s eam e c h a n i s mo fh e t e r o g e n e o u sd a t ai n t e g r a t i o nd y n a m i cs c h e d u l i n g o p t i m i z a t i o nb a s e do na n tc o l o n ya l g o r i t h m ，a tt h es a m et i m ei m p o r tm sa n dd s 。t h et h r e ea s p e c tc o m b i n ee f f e c t i v e l yt h a ts o l v et h ei s s u eo fi n i t i a l i z ed e l a y 、 o u t b u r s to ft h ed a t aa n ds l o w l yt r a n s m i s s i o nr a t e ，a n ds c h e d u l i n gb yi t s e l f i n d e p e n d e n c et h eo t h e rm o d ea n dd a t as o u r c e so ft h es y s t e m 。 f i n a l l y , c o m p a r e dw i t ham s t - t oa n ds r d o ，w ea r eo b t a i nt h er e s u l tt h a t t h e a l g o r i t h mp e r f o r m a n c eo ft h eh e t e r o g e n e o u sd a t ai n t e g r a t i o nd y n a m i c s c h e d u l i n go p t i m i z a t i o nb a s e do na n tc o l o n ya l g o r i t h mm o r et h a nf r o n tt w o 。 k e yw o r d s ：h e t e r o g e n e o u s ，d a t a i n t e g r a t i o ns y s t e m ，d y n a m i cs c h e d u l i n g o p t i m i z a t i o n ，a n tc o l o n ya l g o r i t h m i v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：日期：迸：! 三 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；。学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签名砸哈二一 导师签名：蕴邀 太原理工大学工学硕士研究生学位论文 1 1 研究课题目的与意义 第一章绪论 近年来，通讯技术和硬件技术的发展呈加速态势，但各种应用的核心数据，仍 以不同的形式存储在不同的系统中，呈分布异构状态。随着应用需求的不断增加，越来 越多的用户希望能够透明地获取和处理来自这些海量信息源中的有用数据，实现多个软 硬件系统以及不同信息源之间的互操作。然而，这些信息源物理上可能分布在异构环境 的多个自治域( a u t o n o m o u sd o m a i n ) 中，有着不同的数据格式、存储方式、访问控制策 略，逻辑上则可能在数据模型、操纵语言和数据语义等方面存在着很大差异。同时，这 些信息源的可共享性、共享方式、共享内容等也可能随时发生变化。 数据集成【l 】的研究一直是数据管理研究领域及其它相关领域一个非常热门的课题， 如对多数据库系统m u l t i d a t a b a s e 的研究。近年来随着w e b 平台逐渐成为信息服务的主 导平台，对w e b 环境下的数据集成【2 】的研究也越来越成蓬勃发展的趋势。数据集成系 统也被称为信息集成系统( i n f o r m a t i o ni n t e g r a t i o ns y s t e m ) 、中介系统( m e d i a t i o ns y s t e m ) 或 信息搜集代t 里( i n f o r m a t i o ng a t h e r i n ga g e n t ) 等。数据集成系统为多个自治异构数据源的 查询提供一个统一界面方便用户进行集成查询【3 j 。它自动地将用户的查询请求分解为针 对各个数据源的查询请求，然后将各个查询结果合并成最终的结果呈现给用户。多个数 据源的存在对用户来说是透明的，用户好像只对一个单一数据源进行操作。 数据源自治指集成系统对数据源的组成和提供的服务没有任何发言权，数据源是事 先存在的。数据源异构指数据源可以是传统的结构化很强的关系型数据库系统也可以是 结构化文件系统，或者是彼此间查询接口各不相同w e b 数据源。在数据集成系统中， 系统所面向的数据源是自治的，系统所要访问的是“已经存在”的数据源，数据源的建 立是独立于数据集成系统的。 信息技术的应用正在从传统的事务处理( 如企业生产管理、办公自动化等) 逐步走 向i n t e m e t 环境下的数据集成、共享与互操作。企业的竞争优势更加依赖于信息系统的 可用性、可靠性和及时性，信息本身已成为企业最宝贵的财富。随着网络环境下数据资 源的迅速增加，以及持续性、高效性数据访问要求的不断提高，多种异构数据源之间的 信息交互和集成策略己成为企业充分利用信息资源、牢牢把握竞争优势的关键因素。然 1 太原理工大学工学硕士研究生学位论文 而，在今天许多重要的信息分散在各个地方，状态各异，结构不同。人们要想通过网络 和信息系统在允许的时间内获取所需要的信息，进而作出正确的决策，成为一件极为困 难的任务【4 1 。 电子政务是以计算枫技术和网络技术为基础，超越时闯、空间鞠部f 1 分隔的制约， 将大量频繁的行政管理和日常事务按照设定的程序在网上实施的一种工作方式。电子政 务的基础设施和赖以运行的基本环境是一个安全性赢、可用性强、跨地区、跨部门、跨 平台的协同工作通用信息集成平台，其中包含数据通信、电子支付、电子记录、电子文 件以及电子签名诸要素。在此信息集成平台中，既要保证各个不同的职能部门之间数据 的相对独立性，又要实现所有职能部门之间数据的共享性，能够极大的满足多层次、多 级别的查询、控制和核算。这要求集成平台能实现数据的平滑交换和透明互操作，而且 篱单易用、开放性好。 在现代战争中，对信息的全蘧掌控是致胜的关键，这些信息来叁于指挥( c o m m a n d ) 、 控镑l j ( c o n t r 0 1 ) 、通信( c o m m u n i c a t i o n s ) 、计算机( c o m p u t e r s ) 、情报( i n t e l l i g e n c e ) 、监视 ( s u r v e i l l a n c e ) 、侦察( r e c o n n a i s s a n c e ) 署d 电子战( e l e c t r o n i cw a r f a r e ) 等不同系统，即所谓的 “c 4 i s r e w 系统【5 】。只有实现这些异构信息系统间的互操作，综合集成各种数据，才 可能实现诸如战场实时指挥控制和高可用协同联络等军事应用。不难看出，异构信息集 成平台对关键应用的架构不可或缺，而且，这种应用的需求己是随处可见。这些应用绝 大部分都要求能处理分布在不同地域的数据源，能够提供一个集成的信息交互和处理平 台，在其上可实现用户定制的查询，募可支持远程事务处理，这就给我们设计异构信息 集成处理平台带来了如下的问题： 1 ) 地域的分布性。各数据源分布在不同的地域，属于分布式系统，因此，需要用 到许多分布式系统的处理技术，如分布式数据库系统、分布式对象技术等 6 1 。 2 ) 数据源的异构性。数据源的异构问题分为三个层次：平台层、数据模型层和语 义层f 霸。平台层异构是指数据源所处的硬件环境、操作系统、网络协议不同；数据模型 层异构是指各数据管理系统所使用的数据模型和数据语言的不同，语义层异构是指由于 各数据源设计上的独立性导致的语义冲突。 3 ) 数据源的自治性。被集成的每个数据源都有自己的管理系统，运行着各自已有 的应用程序。这些系统是预先已经存在的，称为遗留系统( l e g a c ys y s t e m ) t 8 1 。这就要求 这些数据源在被集成之后仍然保持定程度的独立性。 2 太原理工大学工学硕士研究生学位论文 4 ) 对用户的透明性。对于集成系统的全局用户，集成的复杂性应该是不可见的， 用户应能选择最适合的用户接口和查询语言，不需知道数据究竟是来自于哪个局部子系 统。 5 ) 查询处理。集成系统用户所需的数据物理上分散存储于各局部数据源中，用户 只是根据集成系统的全局逻辑视图进行查询，因此查询处理的关键是如何将全局查询分 解成不同数据源的子查询，并分发到各数据源，产生的子查询结果最后重新组成个回 答提交给用户【9 1 。 6 ) 事务处理。在集成系统中存在全局事务、全局子事务和局部事务三种类型的事 务，传统的单一串行化标准不再适用，事务模型中的a c i d 特性必须作适当的放松，基 于可串行化的一致性标准也应进行修改【10 1 。 7 ) 模型化问题。在异构信息集成系统中，同一个概念可能按不同的方式模型化， 相似的应用也可能选择不同的模型化技术。在多种模型化技术中，采用公共数据模型 ( c d m ) 表达的全局集成模式是一种较理想的方法【l l 】。这也提出了另外一个问题，即如何 在公共数据模型与局部数据模型之间进行转换。 岛 8 ) 数据抽取、整合和统一。目前，i n t e m e t i n t r a n e t 上已经积累了庞大的数据资源， 这些数据的构成方式各不相同。一种极端是来自传统的数据库数据，它们具有厚谨的结 构；另一极端是来自于一些文件系统中的无结构数据，如图像、声音和未加工的纯文本。 贪于两种极端中间的是所谓的半结构化数据，如h t m 删l 。由于没有预设的模式结 构，集成系统必须从中抽取出关键的、用户感兴趣的数据，然后加以整合，再与其它数 据源的数据一起集【12 1 。 ， 上述问题的圆满解决，是构建一个合理高效的异构数据集成系统的关键。同时，如 何找到解决这些问题的理想丽通用的方法，也构成了本论文研究的最初出发点。本文将 针对异构信息集成系统的分布性、异构性和自治性特点，结合蚁群算法的自组织性、鲁 棒性、易与其它方法相结合等特性，着力研究一种基于蚁群算法的异构数据集成动态调 度优化问题，从而使得异构数据集成系统中的调度模块可以独立于系统的其它模块和数 据源而自行调度。 1 2 调度优化的研究现状 异构多数据源的集成及其查询处理是一个很有研究价值，但也是非常复杂的研究课 3 太原理工大学工学硕士研究生学位论文 题。近2 0 年来，国内外学者从各个不同层面、采用不同的方法和技术对这个领域的相 关课题进行了研究，并得出了不少有益的结论，也建立了一些原型系统1 1 3 】 1 4 1 。但是一 方面由于各数据源的分布性、囱治性和异构性等特点带来的困难，另一方面也由于技术 条件的限制，嚣前并不存在一个“通用”的解决方案，现有的集成系统也都处在研究阶 段，离实用的商业化水平还相距甚远。调度优化是异构数据源查询处理中的一个核心模 块，对查询处理及系统性能起到举足轻重的作用。 调度优化主要分为两类：静态调度优化和动态调度优化，也可能是静态和动态相结 的调度优化方法。静态调度优化是在调度之前就先生成执行计划，然后按照执行计划调 度运行；动态调度优化并不事先生成执行计划，而是在结果合并过程中依照实际执行的 不同情况，采用一定的调度优化策略，确定下一步的动作。当然也有一些做法是动静态 相结合的方法，他首先是用静态调度优化算法来对查询结果进行优化，如果出现数据不 稳定的情况，那么再使震动态调度优化算法或是对静态调度优化算法不断地修改以便生 成更适合的调度计划。 一般来说，现有的静态调度优化和动态调度优化都要通过对数据源查询数据的时 间、查询结果转换时间与及查询结果的传输时间等进行代价评估来确定执行顺序，从而 找到最优或近似最优的执行计划。目前为止并没有一个通用的调度优化方法，所以本文 主要通过结合蚁群算法提池一种比较通用的动态调度优化方法【1 5 】。南于蚁群算法很容易 与一些启发式算法相结合以及它的鲁捧性和自维织性，所以在些特定的领域中可以结 合一些相适应的窟发式方法对本文提出的方法进行改进。在下文中我们将会介绍秘静 态调度方法和一种动态调度方法，并把这两种方法和基于蚁群算法的调度优化方法进行 比较。 13 蚁群算法的研究动态 1 3 i 蚁群算法的发展过程 在2 0 世纪9 0 年代意大利学者d o r i g o 1 6 1 等人从生物进化的机理中受到启发，通过 模拟自然界蚂蚁觅食时寻径的行为，提出了一种全新的模拟进化算法一蚂蚁系统( a n t s y s t e m ) ，该算法首先用于求解旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) ，试验结果 表明蚂蚁系统具有较强的鲁棒性和搜索较好解的能力，但是，这种算法也存在一些缺陷， 如：与其它方法相比，该算法一般需要较长的搜索时间，蚁群算法的复杂度可以反映这 4 太原理工大学工学硕士研究生学位论文 一点；而且该方法容易出现停滞现象( s t a g n a t i o nb e h a v i o u r ) ，即搜索进行到一定程度后， 所有个体所发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。 对于这两个问题，己经引起了许多研究者的注意，并提出了若干改善方法。蚂蚁系统的 出现引起了许多学者的关注，针对算法的不足，提出了许多新的蚂蚁算法如蚁群系统 ( a n tc o l o n ys y s t e m ，a c s ) 、最大一最小蚂蚁系统( m a x m i na n ts y s t e m ，m m a s ) 和基于 排序的蚂蚁系统( r a n k - b a s e dv e r s i o no f a n ts y s t e m ，a s r a n k ) 等。这些算法在性能上有了 很大的提高，很大程度上消除了搜索中的停滞现象，更适合求解高维的n p h a r d 问题； 除此之外，许多学者利用蚂蚁算法求解其它组合优化问题，如指派问题i l 列( q u a d r a t i c a s s i g n m e n tp r o b l e m ) 、j o b s h o p 调度问题【1 8 】【1 9 ( j o b s h o ps c h e d u l i n gp r o b l e m ) 、车辆路由 问题【2 0 】【2 1 ( v e h i c l er o u t i n gp r o b l e m ) 、图着色问题【2 2 ( g r a p hc o l o r i n gp r o b l e m ) 和网络路由 【2 3 】【2 4 ( n e t w o r kr o u t i n gp r o b l e m ) 等。 近年来，一些学者提出了蚁群优化【2 5 ( a n tc o l o n yo p t i m i z a t i o n ) 这一新概念，为蚂 蚁算法提供了一个统一的框架，为蚂蚁系统的理论研究打下了坚实的基础。 目前该算法理论研究正进一步加强，同时被迸_ 步应用到其它组合优化领域。 1 3 2 蚁群算法的基本特性 蚁群算法近年之所以得到人们的重视和认可，主要是由于它有着许多其它算法无可 比拟的优越性，主要表现在以下几方面： 1 )智能式搜索。蚁群算法的搜索策略既不是盲目式的乱搜索，也不是穷举式的全 面搜索，它是有指导的搜索，其执行依据是路径上的信息素多少，利用路径上的信息素 的指导，使蚁群算法逐步逼近目标值。 2 )较强鲁棒性。对蚁群算法稍加修改，便可应用于其它问题，没有中心控制与数 据，不会由于某一个或某几个个体故障而影响整个问题的求解。 3 )易于与其它方法结合。该方法可以与多种启发式算法结合，以改善算法的性能。 4 )并行性。每次迭代计算都是针对一组个体同时进行，而非对某一个体进行，因 此，尽管蚁群算法是一种搜索算法，但由于采用这种并行计算机理，搜索速度很快。 5 )通用性。适合解决能转换成为连通图结构的问题，包括许多n p 难题，此外还 能解决图结构属性在计算过程中发生变化的问题。 6 )正反馈。使用局部解来构造全局解，通常是加强局部的较优解。 5 太原理工大学工学硕士研究生学位论文 7 ) 负反馈。通过信息素挥发避免算法陷入局部收敛。 8 ) 间接通讯。蚂蚁之间没有直接的联系，信息的传递是通过路径上的信息素。 9 ) 自组织。依靠群体的力量解决问题。 1 3 - 3 蚁群算法的研究现状及未来研究 针对一般蚁群算法的不足，一些学者提出了许多新的蚁群算法，如蚁群系统( a n t c o l o n ys y s t e m ，a c s ) 、最大一最小蚂蚁系统( m a x m l na n ts y s t e m ，m m a s ) f f i 基于撵序 的蚂蚁系统( r a n k b a s e dv e r s i o no f a n ts y s t e m ，a s r a n k ) 等，下面分别介绍这几个算法。 ( 1 ) 蚁群系统( a c s ) a c s 算法对a s 算法的选路和信息更新策略作了相应的改进，即： 采用伪随机比率选择规则( p s e u d o 。r a n d o m - p r o p o r t i o n a la c t i o nc h o i c er u l e ) 的选路 方式，即对予在城市i 的蚂蚁，按公式( 1 一1 ) 选择下一个城市歹： | a r gm a x r ( i ，豁) r p ( i ，狂) i fq q o ，= u e a l l o w e d k 【0 o t h e r w i s e ( 1 1 1 其中q 。( o ，1 ) 为常数，q ( o ，1 ) 为随机生成数。r ( i ，“) 表示城市f 与城市甜之间的信息量， 刁( f ，“) 表示城市f 与城市u 之间的启发式因子，表示启发式因子的相对强弱。在选择 下一个城市之前随机生成q ，如果q 值小于常数q o ，则从城市i 到所有可行的城市中找 出忙( f ，“) 7 7 芦( f ，“) 最大的城市，即为下一个要选择的城市；如果随机数q 大于q o ，则按 公式( 1 2 ) 来选择下个成市。 p k ( i ，j ) =警龋卵鲫跏e 吱 ： 【f ( f ，s ) 】【帮( i ，s ) 。 0o t h e r w i s e 0 - 2 ) 局部信息更新。蚂蚁从城市f 转移到城市，后，路径( 瓦) 上的信息量按公式( 1 3 ) 进行更新： f ( f ，歹) = ( 1 一譬) 宰r ( i ，歹) + s 粕 占( o ，1 ) ( 1 3 ) 其中r 。为常数，暑( o ，1 ) 为可调参数。 全局信息更薪。针对全局最优解所属的边，按公式( 1 4 ) 进行信惠量更新： 6 太原理工大学工学硕士研究生学何论文 r e ( t + 1 ) = ( 1 一p ) 木o ) + p 守，p ( o ，1 ) t彗=、f(1-4) 其中为当前最优解的长度，p 为外激素的蒸发系数，r ，( f + 1 ) 表示什l 时刻( f ，j ) 边上的信息素。 在文献 2 6 中，m d o r i g o 将a c s 算法与模拟退火、进化计算和遗传算法进行了比 较，发现a c s 算法在大多数清况下要优于其它算法，至少性能相当。在解决非对称t s p 问题时，a c s 算法更具优势。 ( 2 ) 最大最小蚁群系统( m m a s ) m m a s 直接来源于a s 系统，主要作了如下改进： 1 ) 每次循环结束后，只有最优解路径上的信息被更新； 2 ) 为了避免搜索时出现的停滞现象，各路径上的信息量被限制在范围k 。，f 一】 内。 3 ) 初始时刻，各路径上的信息量取最大值。所有蚂蚁完成一次循环后，按公式( 1 5 ) 对路径上的信息量作全局更新： 勺o + 1 ) = ( 1 - p ) 木乃o ) + 呓积，p e ( o ，1 ) 呓倒= 17 产 ( 1 5 ) 允许更新的路径可以是全局最优解，或本次循环的最优解。实践证明逐渐增加全局 最优解的使用频率，会使该算法获得较好的性能。 ( 3 ) 基于排序的蚂蚁系统( a s r a n k ) a s r a n k 也是a s 系统的改进版本。在完成一次循环后，将蚂蚁所经路径按从小至大 的顺序排列，即_ 9 ) r o ) f ( f ) ，并根据路径长度赋予不同的权重，路径较短的权 重较大。全局最优解的权重为w ，第，个最优解的权重为m a x 0 ，w ，) ，按公式( 1 6 ) 更新 各路径上的信息： 乃p + 1 = 1 一力奉巧+ 荟纠m 巧 协彻( 0 ，1 ) 0 , 1 ( 1 - 6 ) 其中，a r o ( t ) = i l ，( f ) ，a r y ( t ) = l l 驴 同a s 算法相比，以上算法的共同之处在于加强了对最优解的利用。如在a c s 和m m a s 算法中，只有最优解( 全局最优或本次最优) 所属路径上的信息允许更新。在a s r a n k 中， 7 太潦理4 ：大学工学硕士研究生学侮论文 根据每次循环路径的长短赋予不同的权重，即对较短的路径赋予较大的权重。这样最优 解包含的路径将会有更多的机会被下一次选中。僵是加强对最优麓酌利用将会导致搜索 中的停滞现象。在a c s 算法中通过增加局部信息更新来减少路径上的信息量，从而使 后面的蚂蚁选择该路径的可能性减少；在m m a s 算法中，通过限制信息量的范围，使路 径上的信患量不会小于菜一最小值，从蓊避免了所有蚂蚁选择周一条路经的可能胜，即 避免了搜索中的停滞现象。蚁群算法未来的研究主要有以下几个方藤： 从m d o r i g o 第一次提出蚂蚁算法到现在只有十几年的时间，许多文献已经证明该 算法是一个非常有效麴解决组合优化问题的工具。目前该算法还毒许多值得研究熬地 方，主要是： 1 ) 进步研究真实蚁群的行为特征，包括其它的群居动物。因为蚂蚁算法是受蚁 群行为特征熬襄发露发展莛亲静一种模攒进纯算法，通过对真实蚁群行为的深入磷突有 利于进一步改进蚁群算法，从箍提嵩其性能。 2 ) 对该算法的收敛胜、收敛速度和参数设置的研究。算法的许多特性，如算法的 收敛性，参数熬设定都来自子大量试验统诗结果，譬前对该算法的理论研究有待进一步 加强。 3 ) 对算法的并行性研究的文献也较少，而并行性正好是提高算法收敛速度的有效 途径。 1 3 4 蚁群算法的应用 m ，d o r i g o 酋先髑a s 算法求解o l i v e r 3 0 t s p 阐题，在选择适当瓣参数匿，算法总麓 收敛到阀题的最优解。继m d o r i g o 之后，v m a n i e z z o 等人将a s 算法应用予指派问题 ( q a p ) 。最近几年，a m b a r d e l l a , t a i l l a r d 和s t u t z l e 发表了一些用a c o 算法求解o a p 闽 题的文章。目前，蚂蚁算法己经是求解q 艘| 瓣题最有效熊算法之一。 在文献【2 7 】中，a c o l o m i 等人首先将a s 算法应用于j o p s h o p 调度问题( j s p ) ，计算 结果表骥，该算法虽然麓解决j s p 闷题，但同s t a t e o f - t h e - a r t 算法相毖较，并没有任何 优势。后来，用m m a s 算法来求解流式j o b 。s h o p 调度润题( f l o ws h o p s c h e d u l i n g p r o b l e mu ，实验结果表明m m a s 优于模拟退火算法和禁愚搜豢算法。 c o s t e 和h e r z 提如增强的a s 算法，著将其应用于分配类型的瓣题。利用该算法在 求解图的着色问题时，得到了酉以完全和其它扇发式算法相媲美的结果。 8 太原理工大学工学硕士研究生学位论文 b u l l n h e i m e r , h a r t l 和s t r a u s s 用算法a s r a n k 来求解车辆路由问题( v e h i c l er o u t i n g p r o b l e m s ，v r p ) ，取得了和最优解非常相近的结果。近几年，g a m h a r d e l l a , t a i l l a r d 和 a g a z z i 对v r p 问题的研究，对一些标准基问题的最优解有所提高。 最近几年，许多学者将蚁群算法应用于通讯网络领域，特别是用它来解决网络路由 问题。因为网络信息的分布性、动态性、随机性和异步性与蚁群算法非常相似，如利用 局部信息发现解，非直接的通讯方式和随机状态的转换。d o r i g o ，d i c a r o 和g a m b a r d e l l a 已在相关的文献中将蚁群算法应用于网络路由问题，并称这种算法为a n t n e t 蚁群算法的应用研究是蚁群算法的很大一部分，算法主要用来求解组合优化问题， 虽然该算法的出现才十几年的时间，大量的实验结果证明，该算法具有很好的解决复杂 问题的能力。 1 4 本文的研究内容和章节安排 本文结合异构数据集成调度优化的特征对蚁群算法理论进行深入研究。针对异构数 拧 据集成调度问题复杂性，不确定性等特点，设计新的算法，合理选择调度次序，”降低系 统运行时间开销，提高系统的运行速度。 本文主要从以下几方面开展工作： ( 1 ) 提出问题 通过阅读大量论文得出：在异构数据集成系统中，在调度优化过程中主要会出现初 始化延迟、数据的突发性【2 8 】【2 9 1 、数据的慢传输速率以及调度优化算法过分依赖于数据 源、数据到达时间评估等异构数据集成系统的其它模块，导致调度优化算法缺乏自主性。 ( 2 ) 设计蚁群算法相关函数 从算法的基本思想入手，研究算法原理、特征及性能，在基本蚂蚁算法的模型上提 出相应解决问题的改进方法，设计与问题相适应的启发式方法使其适用于问题，以优化 其调度性能，解决异构数据集成调度优化问题。 ( 3 ) 设计异构数据集成动态调度优化算法 设计基于蚁群算法的异构数据集成调度优化算法只能说让算法有了自主性了，不再 依赖系统的其它模块而独立调度运行了。但对于数据返回结果的延迟、传输速率慢等问 题并没有解决。由于基于蚁群算法的鲁棒性以及易与启发式方法相结合等特点，本文给 出了两种重要的策略：物化策略和分域求解策略。物化策略主要解决数据返回的慢传输 9 太原理工大学工学硕士磷究垒学德论文 速率问题，而分域求解策略解决数据返回延迟的问题，如果把结果求解分成n 个域的话， 那么它允许最少据1 个结果返霾出现延迟，同瓣也提高了算法的并行性。 ( 4 ) 比较算法性畿 最感，逶过实验曲线定量地分耩并与静态调度算法和基于统计推理策略算法相眈 较；说明基于蚁群算法的异构数据集成动态调度傀纯算法鲍优异性。 论文按如下方式组织： 第章 本章主要介绍了选题的背景、目的和意义，并分析了该问题的研究现状； 同时，避过查阅大量资料，对蚁群算法的发展、特性、研究现状以及应用 乍了个大概 的介绍。最后提出了论文的主要开展工作以及设定论文的组织结构。 第二章 对髯构数据集成系统进行了基本介绍，设计了一种异构数据集成的查询 处理流程。定义了套谗灞度的一些基本操箨，最慝重点奔绍了二释调度优化算法：基予 p r i m 算法的静态调度优化算法和基于统计推理的动态调度优化算法，通过设计实例， 更清晰地表述算法思想和流程和更清晰地、具体地认识异构数据集成调度优化的具体问 题麟在。 第三章 介绍蚁群算法的基本原理和模裂，通过t s p 问题详细阐述蚁群算法模 型串的各个要素以及三种不同模型中信息素增量的不同定义，最后给出了蚁群算法的伪 代码擒述和算法流程圈。 第靼章 设计基于蚁群算法的异构数据集成谪度优化算法，对不定性返回的予查 询结果绘出了一辩分域策赂，对解决慢传输速率问题绘出了物化策略。根据异构数据集 成中的调度阍题提出了蚁群算法中的启发式函数犟( f ) ，并对信息素更新规则作了一些改 进，加快算法的收敛速度。 第五章实验及结果分析。通过实验得出算法的性能曲线分析算法性 能，分析物化策略和分域求解策略对算法性能的影响。 第六章最后对本文的研究工作进行了总结，并提出了今后进一步工作的方向。 太原理工大学工学硕士研究生学位论文 第二章异构数据集成与相关技术 本文主要介绍异构数据集成的基础理论知识，讨论异构数据集成的架构、主要思想 和关键技术。 2 1 异构数据集成 异构数据集成【3 0 】是数据库应用领域的经典问题，随着x m l 技术的兴起和成熟，它 再次成为一个研究热点。 2 1 1 异构数据和数据集成 异构数据【3 1 】是一个含义丰富的概念，不仅指不同的数据库系统之间的数据是异构 的，如o r a c l e 和s q ls e r v e r 数据库；还包括不同结构的数据之间的异构，如结构化的 s q ls e r v e r 数据库数据和半结构化的x m l 数据；更重要的是数据表示语义上的差异。 数据集成是指屏蔽各种异构数据间的差异，对各种异构数据提供统一的操作，使集 成后的异构数据对用户来说是统一的和无差异的。 对于目前的数据集成系统，绝大部分数据源的数据是属于异构数据，因此，通常人 们所说的数据集成就指异构数据集成。 2 1 2 现实环境中数据集成面临的问题 在现实环境中，数据集成通常面临以下几个问题： ( 1 ) 环境异构 系统异构：数据所依赖的应用系统、数据库管理系统乃至操作系统之间的不同。 模式异构：数据在存储模式上的不同，一般的存储模式包括关系模式、对象模式、 对象关系模式和文档嵌套模式等几种，其中关系模式为主流存储模式。需要注意的是， 即便是同一类存储模式，它们的模式结构可能也存在着差异。例如o r a c l e 所采用的数 据类型与s q ls e r v e r 所采用的数据类型并不是完全一致的。 ( 2 ) 完整性 太缀理互夫攀工攀硕士研究生学谴论文 异构数据集成的目的是为应用提供统一的访问支持，因此集成后的数据必须保证一 定的完整性，包括数据完整性和约束完整性两方面。数据完整性是指数攥的正确性，一 致性和相容性。约束完整性，约束是指数据与数据之间的关联关系，是唯一表征数据问 逻辑的特征。保证约束完整性是良好的数据发布和数据交换的前提，可以方便数据处理 过程，提高效率。 ( 3 ) 集成内容限定 多个数据源之间的数据集成，并不是要将所有的数据进行集成，那么如何定义要集 成的范圈和极限，就构成了集成内容的限定问题。 ( 4 ) 语义冲突 信息资源之间存在着语义上的送别，这些语义上的不同可能引起各种冲突。 ( 5 ) 较陵冲突 由于需要集成的数据可能癌属不嗣的单位或部门，因此如何在访闻异构数据基础上 保证原有数据的权限不被侵犯，就成为集成异构数据必须面对的现实问题。 以上这些阔题是糨互联系、相互制约的，不廒该简单地孤立对待。 2 。1 。3 仓艨法和虚拟法 仓库法( t h ew a r e h o u s i n ga p p r o a c h ) 和虚拟法( t h ev i r t u a la p p r o a c h ) 是数据集成系统中 的两种实现方法。 l 、仓库法 仓库法是指建立一个数据仓库，将参加集成煞各数据源的数据副本，按照一个集中、 统一的视图要求，转换成符合数据仓库的模式并存入数据仓库，同时，系统将提供对该 数据仓库的查询机制。这种方式的优点是既可雳于数据集成，又可用于决策支持；缺点 是数据更新不及时、数据重