（计算机软件与理论专业论文）在线货币交易问题中的竞争性决策算法研究.pdf

j i i b y z h a n g r u i y i n g b e ( n o r t h w e s tn o r m a lu n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o r t h ed e g r e eo f m a s t e ro f e n g i n e e r i n g c o m p u t e rs o f t w a r e t h e o r y i nt h e g r a d u a t es c h o o l o f l a n z h o uu n i v e r s i t yo f t e c h n o l o g y s u p e r v i s o r p r o f e s s o rz h a n g y i a a n p i n g m a y , 2 0 11 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：弧粥鞋 日期：b 1 1 年 月5 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同 时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据 库，并通过网络向社会公众提供信息服务。 日期：2 0 1 1 年易月5 日 日期：力，年厶月易日 1 1 3 在线决策算法研究框架及决策过程4 1 1 4 在线算法的应用领域5 1 2 课题背景及研究意义8 1 3 国内外研究现状9 1 4 本文的研究内容及结构l l 第2 章在线交易决策问题的基本模型及相关算法1 2 2 1 在线决策问题概述1 2 2 2 在线交易决策问题基本模型1 3 2 2 1 时间序列搜索1 4 2 2 2 单向交易1 4 2 2 3 随机性时间序列搜索和单向交易算法1 4 2 3 竞争性决策算法1 6 2 3 1 保留价格策略( r e s e r v a t i o n p r i c e p o l i c y r p p ) 1 6 2 3 2 指数限定策略( e x p o n e n t i a lt h r e s h o l dp o l i c y ) 1 6 2 3 3 竞争性数据对比1 7 2 4 其它模型及相应算法1 7 2 4 1 价格汇率随时间变化模型1 7 2 4 2k 一时间序列搜索模型1 8 2 5 本章小结1 8 第3 章时间序列搜索确定性决策算法1 9 3 1 时间序列搜索扩展模型1 9 3 2 基础定义及简单讨论2 0 3 3 在线确定性决策算法2 0 3 3 1 算法思想2 0 4 1 基础知识2 6 4 1 1 基本数学概念2 6 4 1 2 相关符号定义2 6 4 。2 随机性决策算法2 7 4 2 1 算法思想2 7 4 2 2 竞争分析2 7 4 2 3 实验对比3 1 4 3 改进的随机性算法3 2 4 4 本章小结3 4 结论与展望3 5 参考文献3 7 致谢4 l 附录a 攻读学位期间所发表的学术论文目录4 2 附录bj a v a 程序源代码4 3 在线问题及其竞争算法理论是近年来国内外一个热点研究方向。在线问题是 研究不完全信息下的决策问题，由于不能知道和预测未来的确切信息，因此往往 无法对问题做出最优决策，而只能尽量给出问题的满意决策。而竞争算法就是这 样一种决策，该决策算法在各种条件下给出的决策结果都在对应离线最优决策的 一定范围内。在线竞争算法以及竞争比概念的提出弥补了传统优化理论在处理在 线问题时的不足，已经在计算机科学方面取得很多研究成果并得到了广泛的应用。 近年来，随着贸易全球化和经济一体化进程的加快，并且由于金融和管理问 题中未来信息的缺乏和不确定性，如今它们也越来越多地受到众多在线问题和竞 争算法研究者的广泛关注。在线交易算法不但在经济领域有着极其重要的理论意 义，而且在经济管理及日常生活当中也有着广泛的应用，如搜索雇员和工作、股 票投资，库存和保险问题等等。现实中典型的在线交易决策问题，已有各种不同 的模型用确定性或随机性算法得到求解。本文介绍了在线交易问题基本模型及相 关确定性和随机性算法，并基于引入利润函数的时间序列搜索模型基础上提出了 随机性决策算法r a k d ( r a n d o ma l g o r i t h mw i t hk n o w nd u r a t i o n ) ，分析证明了算 法最坏情况下的竞争比，最后通过实验与确定性算法进行了性能比较，分析及实 验结果表明该算法可以在一定情况下降低算法竞争比，并且应用范围较为广泛。 另外，针对非最坏情况提出了改进的随机性算法。 最后，对本文的研究工作进行了总结，并指出了在线交易算法在该领域进一 步要研究的问题。 关键词：时间序列搜索；在线交易算法；确定性算法；随机性算法；竞争比 在线货币交易问题中的竞争性决策算法研究 a b s t r a c t o n l i n ep r o b l e ma n di t sc o m p e t i t i v ea l g o r i t h mt h e o r ya r eh o tr e s e a r c hd i r e c t i o n si n r e c e n ty e a r sa th o m ea n da b r o a d o n l i n ep r o b l e mi st h es t u d yo fd e c i s i o n m a k i n g u n d e rt h e i n c o m p l e t ei n f o r m a t i o nc o n d i t i o n s ，s i n c ei t i si m p o s s i b l et ok n o wa n d p r e d i c tt h ef u t u r ei n f o r m a t i o ne x a c t l y , p e o p l eo f t e nc a nn o tm a k et h eo p t i m a ld e c i s i o n o nt h eo n - l i n ep r o b l e mb u to n l yc a nm a k eas a t i s f i e dd e c i s i o na sm u c ha sp o s s i b l e t h e c o m p e t i t i v ea l g o r i t h mi s o n es u c hd e c i s i o ns t r a t e g y , t h ed e c i s i o nr e s u l t so ft h e c o m p e t i t i v ed e c i s i o na l g o r i t h mu n d e rv a r i o u sc o n d i t i o n sa r ew i t h i nac e r t a i nr a n g e c o r r e s p o n d i n gt ot h eo f f l i n eo p t i m a ld e c i s i o n t h es t a t e m e n to ft h eo n l i n ec o m p e t i t i o n a l g o r i t h m sa n dt h ec o n c e p to fc o m p e t i t i v er a t i om a k eu pf o rt h ei n s u f f i c i e n t so ft h e t r a d i t i o n a lo p t i m i z a t i o nt h e o r yi nd e a l i n gw i t ht h eo n l i n ep r o b l e m s m a n yr e s e a r c h a c h i e v e m e n t sh a v eb e e n a c q u i r e d i nt h ec o m p u t e rs c i e n c ea n di to b t a i n st h e w i d e s p r e a da p p l i c a t i o n s i nr e c e n ty e a r s ，a l o n gw i t ht h eg l o b a l i z a t i o no ft r a d ea n dt h ea c c e l e r a t i o no f e c o n o m i ci n t e g r a t i o np r o c e s s ，a n db e c a u s e o ft h el a c ko ff u t u r ei n f o r m a t i o na n d u n c e r t a i n t yi nf i n a n c i a la n dm a n a g e m e n tp r o b l e m s ，n o wt h e ya r ea l s oi n c r e a s i n g l y r e c e i v e dn u m e r o u so n l i n ep r o b l e m sa n dc o m p e t i t i v ea l g o r i t h mr e s e a r c h e r se x t e n s i v e a t t e n t i o n o n l i n et r a d i n ga l g o r i t h m sn o to n l yh a v et h ee x t r e m e l yi m p o r t a n tt h e o r e t i c a l s i g n i f i c a n c ei nt h ee c o n o m i cf i e l d ，b u ta l s oh a v et h ew i d er a n g eo fa p p l i c a t i o n si n e c o n o m i cm a n a g e m e n ta n dt h ed a i l yl i f e ，s u c ha ss e a r c he m p l o y e e sa n dw o r k ，s t o c k i n v e s t m e n t ，i n v e n t o r ya n di n s u r a n c ei s s u e sa n ds oo n i nr e a l i t y , t h e r ea r eav a r i e t yo f d if f e r e n tm o d e l so ft h et y p i c a lo n l i n et r a d i n gd e c i s i o n m a k i n gh a v eb e e ns o l v e db y d e t e r m i n i s t i ca l g o r i t h m sa n dr a n d o ma l g o r i t h m s t h i sa r t i c l ed e s c r i b e st h eb a s i cm o d e l o fo n l i n et r e a d i n gp r o b l e ma n dr e l a t e dd e t e r m i n i s t i ca n ds t o c h a s t i ca l g o r i t h m s ，a n d p r o p o s ea nr a n d o md e c i s i o na l g o r i t h mr a k d ( r a n d o ma l g o r i t h mw i t hk n o w n d u r a t i o n ) b a s e do nt h e t i m e - s e r ie ss e a r c hm o d e lt h a ti n t r o d u c e dp r o f i tf u n c t i o n ， a n a l y s i s a n d p r o v et h e w o r s tc a s ec o m p e t i t i v e r a t i o ，f i n a l l yc o m p a r e i tw i t h d e t e r m i n i s t i ca l g o r i t h mo n a l g o r i t h mp e r f c r m a n e et h r o u g h t h e e x p e r i m e n t s ，t h e a n a l y s i s a n dt h e e x p e r i m e n t a l r e s u l t ss h o wt h a tt h e a l g o r i t h m c a nr e d u c et h e c o m p e t i t i v er a t i ou n d e rc e r t a i nc i r c u m s t a n c e s ，a n da p p l i c a t i o ns c o p ea r em o r ew i d e l y i na d d i t i o n ，t h ea r t i c l eg i v e st h ei m p r o v e dr a n d o ma l g o r i t h mt ot h en o nw o r s tc a s e f i n a l l y , t h ep a p e rs u m m a r i z e st h er e s e a r c hw o r k ，a n dp o i n t so u tt h a tw h a tn e e dt o ! 1 1 插图索引 图1 1 在线问题及竞争性算法研究框架5 图2 1 在线交易问题基本模型图1 4 i v v 1 7 3 2 现实生活中的许多现象通常都具有非常强的动态特征，人们对于这些现象一 般是先进行数学方面的抽象，然后再通过静态或者统计的方法加以研究和处理。 从优化的理论和方法来看，传统的优化理论大多都是站在旁观者的立场上看待问 题的，即首先确定已知条件，然后在这些已知条件假设不变的情况下给出最优方 案( 即得到最优解) 。然而，随着社会经济的发展和信息时代的到来，各种现象越 来越呈现出在线特征，如计算机操作系统中的调页问题，页面的调入是随机的， 并且后续页面的信息( 如页面的大小，使用的频度等) 都是不可预知的，此时由 于变化的不确定性因素对所考虑的问题影响较大，传统的优化算法对问题的某一 特例可能会给出离实际最优解相距甚远的解，这就难以满足实际的要求。于是在 线问题( o n l i n ep r o b l e m ) 以及解决这些在线问题的竞争算法( c o m p e t i t i v ea l g o r i t h m s ) 就引起了人们的广泛关注。 1 1 1 在线问题 所谓最优化问题( o p t i m i z a t i o np r o b l e m ) 就是按照给定的标准在某些约束条件 下选取最优解集的问题，可以分为函数优化问题和组合优化问题两大类，其中函 数优化问题处理的是某一特定区间内的连续变量，而组合优化问题处理的则是解 空间中的离散状态。组合优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) i h - j 题是通过数学的方法 研究离散事件的最优编排、分组、次序及筛选等，是运筹学( o p e r a t i o n sr e s e a r c h ) 中一个经典且重要的分支，所研究的问题涉及经济管理、交通运输、工业工程、 通信网络等诸多领域。 组合优化问题的特点是可靠解的数量有限。虽然从理论上讲这种有限问题可 以通过简单的枚举法找到最优解，然而在实际情况中通常无法实现，特别当实际 问题的规模很大，可行解的数量非常多时更是如此。例如典型的组合优化问题旅 行商问题、0 1 背包问题、图着色问题、聚类问题等可行解的数量就非常庞大，通 过枚举法将难以实现。 如果一个优化问题的输入是以在线的方式接收，输出也以在线的方式产生时， 则称该优化问题为在线问题( o n l i n ep r o b l e m ) ，即所谓的在线问题就是指只知道局 部信息而需要对全局做出决策的那一类问题，它可以是费用最小化( c o s t m i n i m i z a t i o n ) 问题也可以是利润最大化( p r o f i tm a x i m i z a t i o n ) 问题。 通常可以将现实生活中遇到的问题分为三类：一类是如操作系统中的调页问 在线货币交易问题中的竞争性决策算法研究 题( p a g i n g ) ，电话线路交换( p h o n ec i r c u i ts w i t c h i n g ) 和投资规划( f i n a n c i a lp l a n n i n g ) 等这类问题，由于在处理过程中对问题的输入只有部分可知，其它后序相关数据 当前不可访问，随着处理的推进按序逐渐获得，对它们的处理本质上是在线的， 因而是在线问题。一类是如线性规划问题( l i n e a rp r o g r a m m i n g ) 等这一类问题，它 们的输出是在所有输入信息都已获知的情况下通过选择最佳算法方案得到的，它 们本质上是离线的，因此称为离线( o f f l i n e ) 最优化问题。还有一类是如任务分配 ( j o bs c h e d u l i n g ) 及装箱( b i np a c k i n g ) 等问题，离线和在线两种情况都有意义，仅根 据问题的条件和目标而定。 1 1 2 在线算法和竞争分析 在在线决策问题中，输入总是逐步被提供的。设p = ( i ，f ，o 是一个在线问题， 这里i 表示可能的输入集，对每一个输入i i ，f ( j ) 表示合理可行的输出集，c 是 一个效用函数，满足对于所有的输入，和0 f ( d ，c c x ，d ) r 。考虑问题p 的任 意算法a l g ，给定任意输入序列i ，a l g 计算出合理的输出0 ，( ，) ，我们用 a l g ( i ) = c ( i ，d ) 来表示算法a l g 在输入序列为，时的利润( 或费用) 。很典型的每 一个输入都可以表示为一个有限序列i = ，厶，并且每一个合理的输出d 也可以 表示为一个有限序列0 = o l ，0 2 ，o n 。 一个在线算法x l g 就是指在没有获得整个输入的情况下逐步处理输入的一种 算法，即对于每一个j = l ，1 1 ，算法a l g 必须在f ，+ 。给出之前计算出o l ，在线算 法属于不完全信息决策领域。相应的，如果一个算法在给出整个输入序列后产生 一个可行解，则称该算法为离线算法，我们用o p t 表示离线最优算法。 竞争分析是分析在线算法的一种方法，在这个方法中在线算法的性能与获得 整个输入序列的最优离线算法的性能进行比较，对于在线问题的最优离线算法是 假定的，因为它需要透视的能力因而是不能实现的。算法竞争比可以理解为在线 算法的性能( 由问题的一个特定值来衡量) 与最优离线算法的性能在最坏情况下 的比值，因为竞争分析属于最坏情况分析，所以竞争比是最坏情况的性能衡量。 由离线最优算法的定义可知，如果在线问题p 为费用最小化问题，则满足对 于所有合理的输入，等式o p t ( 1 ) = n f l nc ( i ，d ) 成立。对于费用最小化问题，存在 o e f ( i ) 一个算法a l g ，它的可行的输出为x t g f f 】，费用为a l g ( i ) = c u ，a l g 功。如果存 在一个常量口0 使得对于所有合理的输入，不等式a t g u ) 一c o p t ( i ) 口均成立 时，称算法a l g 是费用最小化问题的一个c 近似算法，更准确地称为渐近c 近似算 法( a s y m p t o t i cc a p p r o x i m a t i o na l g o r i t h m ) 。当口= 0 时称算法a l g 为严格的c 近似 算法。无论是渐近c 近似算法还是严格的c 近似算法，我们都称算法a l g 获得竞争 比c 。 2 硕士学位论文 相应的，如果在线问题p 为利润最大化问题，则满足对于所有合理的输入， 等式o p t ( i ) = m a xc ( i ，d ) 成立。对于利润最大化问题，存在一个算法a l g ，它的 o e f ( ，) 可行的输出为a i 。a i 】，利润为a l _ , a ( i ) = c ( i ，a l g i ) 。如果存在一个常量口0 使得 对于所有合理的输入，不等式o p t ( i ) 一c a z , g ( j ) 口均成立时，称算法a l g 是利 润最大化问题的一个c 近似算法，即算法a l g 获得竞争比c 。 由上述定义可知，无论后面的序列是怎样的不稳定或不好，对于费用最小化 问题，c 竞争性算法总是可以确保至多花费最优离线费用的c 倍，而对于利润最大 化问题，c 竞争性算法总是可以确保至少获得最优离线利润的1 c 。并且无论是费 用最小化问题，还是利润最大化问题，c 的取值是大于或等于l ，c 越接近于1 ， 则表示在线算法相对于离线最优算法的性能越好。 需要注意的是竞争比c 和常数口最多只是与描述这个决策问题本身的相关参 数有关，与输入序列，是相互独立，即无关的。并且离线最优算法和在线算法的解 不一定需要各自计算出，关键在于如何通过问题数学模型中的相关函数性质及不 等式性质进行相应的理论证明从而得出比值c 。 虽然普遍认为是由s l e a t o r 和t a r j a n 最早进行在线问题及其竞争分析算法研究 的【2 】，但实际上在1 9 6 6 年，g r a h a m 就已经首次运用竞争分析算法思想来分析并解 决了并行机器调度问题【3 j ，后来陆续有一些学者在自己的研究中运用并扩展了这一 思想。直至1 9 8 3 年，真正标志在线问题与竞争算法理论萌芽的是t a r j a n 在文献中 所讨论的a m o r t i z e d 方法【4 】，这也是真正标志着对在线问题的竞争分析系统研究的 开始。 从博弈论的角度来看，竞争分析可以被视为两人博弈的情形，其中一方为在 线决策者，另一方为离线的对手。在线决策者使用自己设计的算法来运行对手创 建的输入序列，目标是设计出尽可能好的在线算法，使得付出成本或所得收益尽 可能跟踪上离线最优算法的成本或收益。而对手则根据自己对在线参与者所采用 算法的有关知识，构建一个对于在线参与者来说尽可能坏的输入序列，以使得竞 争比尽可能最大。换言之，对手竭尽全力使得在线参与者付出尽可能昂贵的代价， 与此同时，要尽可能使离线最优算法付出尽可能小的代价。有时候把离线对手和最 优离线算法看成一个整体：离线参与者。 竞争分析方法与传统的分析方法不同，传统分析方法对在线算法的研究是在 概率( 或平均情况) 复杂性构架下进行的，即总是先对事件( 或事件序y 0 ) 的分布作某 种假设，然后求解这种假设下全部事件或个别事件的期望费用。但是传统的算法 理论在处理在线决策问题时有两个十分明显的缺陷，其一是事件未来发生的概率 分布往往是很难预测到，其二是一旦小概率情况发生，决策的结果就会与最优结 果相差较远。 3 在线货币交易问题中的竞争性决策算法研究 当然任意的分析方法都有其优点及缺点。竞争分析的缺点就是过于悲观，这 种方法假设输入是由对手选择的最坏输入，而在实际情况下，最坏输入很少发生。 优点就是无需假设输入的概率分布，并且在在线决策问题当中，面对不确定性决 策环境，在线决策者通常是希望获得某一个较少但相对确定的收益，而不是愿意 暴露于严重的风险之下获得相对较高的平均利润，实际上，这正是竞争分析所能 提供的；竞争分析的另外一个优点是在某种程度上，它提供了一般意义下任何两 种可供比较竞争算法的性能统一度量。 在竞争分析方法中，在线决策者的目的就是设计一个好的算法以应对离线对 手可能发出的不可控变化因素的最坏情形。竞争分析与以往的解决此类问题方法 的最大区别在于：它在变化因素的每一个特例中都能给出一个方案，使得这一方 案所得到的解离最优方案给出的解总在一定比例之中，从而使在线问题的解始终 保持在一个最优的状态。竞争分析方法最初只是用来分析n p 难问题近似最优解， 之后广泛应用于分析在线问题，已经越来越多的获得了认可。 不失一般性，在线算法也有确定性在线算法( d e t e r m i n i s t i co n l i n ea l g o r i t h m ) 和随机性在线算法( r a n d o m i z e do n l i n ea l g o r i t h m ) 之分。其中确定性算法在前面已 有所描述，即每一步的决策都是确定的，并且当输入相同时，不管什么时候执行 算法，其输出总是完全相同。而随机性算法在执行时根据输入随机选择做出决策 的一类算法，因此即使在输入完全相同时，其输出也会随着每次执行而不同。对 于随机性算法，对手的分类有很多种，本文只针对遗忘性对手研究随机性算法， 也就是表明随机性算法是基于确定性算法提出来的，它其实就是确定性算法集合 儿q 上的一个概率分布，对于某一特定序列i ，儿g u ) 是关于确定性算法集合 的随机变量，所以需要替换确定性算法定义中的舭g ( ，) 为e a l g ( i ) 】，其中研】表 示的是相对于随机选择的一个期望值。并且由于离线情况将不受在线算法随机化 的影响，所以o p t ( i ) 不是一个随机变量，不需要取期望值。通常由于随机算法完 成一个特定需求输入的决策是一个随机变量，因此随机性算法的性能通常用它的 期望值来衡量，其竞争比要好于确定性算法【5 6 】。另外，有些在线决策问题有可能 不存在确定性在线算法，而只能研究在线随机性算法。如g o l d b e r g 等人【。7 】研究的 网上电子产品在线拍卖问题，选取的基准算法是离线的k 级拍卖报价策略，他们从 理论上严格证明了此问题不存在确定性算法，并且给出了一些相应的随机性在线 拍卖算法。 1 1 3 在线决策算法研究框架及决策过程 面对复杂的环境和不可预知的变化，决策者常常需要在线做出决策。相对于 传统的离线决策，在线决策更强调决策的时效性和决策技巧，同时它也代表着决 策研究领域的一个重要研究方向。 4 硕士学位论文 传统对在线问题的研究是在概率( 或平均情况) 复杂性构架下进行的，即总是先 对事件( 或事件序列) 的分布作某种假设，而基于竞争分析的在线决策算法对未来情 况则不做任何的分布假设，只强调算法本身的设计。其研究框架如下图： 攀睦 决策ii 照学 问题r 1 。竺。! 的有il 里堡 效描il 述i 广l 两人博弈 对手控制 输入序列 最优离线 决策算法 决策问题 在线算法 广义预测 艄阂圈曝 确定性算法集li 随机性算法集 确定性在线 算法的竞争 分析及竞争 比求解 随机性在线 算法的竞争 分析及竞争 比求解 最优竞li 竞争比ll 竞争比 争比i 上界l 下界 图1 1 在线问题及竞争性算法研究框架 一个完整的决策过程( d e c i s i o np r o c e s s ) 通常包括下面几个步骤：描述问题、 确定目标、收集信息、制定方案、选择方案、执行方案并利用反馈信息进行控制。 目标应定的明确，尽可能做到目标能够计量。目标可能是求最大收益值，也可能 是求最小费用值。目标确定之后，决策者必须通过收集各种信息，提出多种可供 选择的行动方案。制定方案时既要对每种可能入选的方案作深入分析和精心设计， 也要考虑影响各种方案实施在自然因素以及每种方案在自然因素影响下所产生的 效果，还要对所有方案可能产生的结果进行估计根据决策目标和决策准则，对 制定的方案进行评论、比较，分清各方案的优劣、利弊和得失，并且对其进行综 合分析与全面考量，从中选择最优方案。问题是否准确，目标是否明确，方案是 否最优，这些都需要在方案的实施中加以验证，以便对所选择的方案进行补充与 修正。 图中竞争比的概念是在线决策算法的核心理念。在线问题的竞争分析是一个 很有意义的对在线算法的最坏情况的分析方法。 1 1 4 在线算法的应用领域 在线算法的应用领域非常广泛，最初在理论计算机科学领域，换页、k 服务器 和任务分配三个基本的在线问题被人们广泛的进行了研究。 1 、计算机科学领域 1 ) 换页( p a g i n g ) 换页问题是虚拟存储系统中一个基本的也是研究较为完善的在线问题。在计 算机中存在两类存储器：一类是辅助存储器( a u x i l i a r ys t o r a g e ) ，存储容量很小但 存储速度很快；另一类为主存储器( m a i ns t o r a g e ) ，存储容量很大但存储速度很慢。 s 在线货币交易问题中的竞争性决策算法研究 每一类存储器都可以存储一定数量的数据块( 或者指令块、指令数据块) 。存储在 高速缓存存储器中的所有数据块总是存储在主存储器中的数据块的一个子集。问 题的输入为一系列数据块的调用，当要调用一个数据块时，总是首先在高速缓冲 存储器中查找该数据块，如果找到则调用费用为0 ；否则需要从高速缓冲存储器中 取出去一个数据块，同时把把所需数据块从主存储器中调入高速缓冲存储器，此 时的调用费用为1 。换页问题就是决定把哪一个数据块从高速缓冲存储器中取出， 使后续一系列操作之后的总调用费用最小( 也就是提高系统的执行效率) 。关于换 页问题的离线算法有l f d ( l o n g e s tf o r w a r dd i s t a n c e ) ，b e l a d y 在文献【8 j 中证明了 离线算法l f d 为最优离线算法，具有最小的页面失效率。对在线换页问题的研究 最初是在概率分布假设基础上进行的【9 ，10 1 ，之后s e a t o r 和t a r j a n t 2 】运用竞争算法分 析了换页问题，证明了对于( j i l ，七) 换页问题，l r u 算法和f i f o 算法具有竞争比 纠( 七一h + 1 ) ，并证明了算法下限为k 。另外还有许多关于此问题的随机性算法研究 f 6 1 1 1 o 2 ) 舡服务器 矗服务器问题是在线问题及竞争算法理论处理的问题中比较早，也是比较经典 的问题之一，其优化的目标是服务器行驶的总里程数。m s m a n a s s e 等在文献【i 刁 中对矗服务器问题的在线概念和竞争算法进行了介绍，在国外，相关的研究成果 已经有很多，具体可以参见文献【1 纠7 1 。 在国内研究方面，基于国外学者对于肛服务器问题的研究成果，国内学者的 研究主要是集中在其推广模式七车服务问题上，将在线问题及其竞争算法应用 到决策领域。堵丁柱先生在文献【1 3 】中对k 车服务问题与竞争算法的研究是国内在 线问题研究的指路牌。在文献中，堵丁柱先生采用由特殊到一般的介绍方法，结 合严格的数学论证，给出了在线竞争算法解决k 车服务问题的数学模型。在后来 国内学者的研究过程中，都或多或少地从文献【1 3 】中获得了启示。近年来围绕这一 方向的文献层出不穷，更多改进的竞争算法的提出使得解决的问题更加地贴近现 实。 3 ) 任务分配( s c h e d u l i n g ) 任务分配问题是一类典型的组合优化问题。该问题的研究是有效利用系统资 源处理实际问题的热点课题。这方面的研究结果在大规模数值计算、v l s i ( v e r y l a r g es c a l ei n t e g r a t e de i r e u i t ) 和计算机网络技术等方面都有很好的应用背景。在 理论方面，由于任务分配问题是被公认的n p 难问题，所以如何构造有效的启发式 算法或近似算法是目前研究的热点领域。任务分配中的负载平衡问题( 1 0 a d b a l a n c i n g ) 1 8 , 1 9 1 和装箱问题( b i np a c k i n g ) 2 0 】分别是最早的在在线算法中隐式和 显式的使用了竞争分析。 负载平衡问题最简单的一种情形可描述为：有刀个任务需要分配给n 个机器去 6 硕士学位论文 完成，每一个任务就称为一个负载，每个任务只能分配给1 台机器处理，且每台 机器只能处理1 个任务，不同的分配花费不同的代价。负载平衡问题要求找到一 种分配方案使所花费的代价最小。而动态分配算法就是指在运行过程中，将任务 分配给各处理机，并对其上的任务数进行动态调整，尽可能使系统中各处理机上 的负载达到基本平衡。其主要特点是能充分发挥各处理机的能力，但实现起来复 杂程度高【2 1 2 2 1 。 著名的装箱( b i np a c k i n g ) i h - j 题是一个典型的分配问题。问题的目的在于将每个 货物一次性永久地分配到某个箱子里，使最后所用的箱子数最少。这一问题最早 被作为是离线问题考虑的，之后才逐渐考虑在线情况。u 1 l m a n 【2 3 】介绍了在线装箱 问题的竞争分析，提出并且证明了首次适应算法( f i r s tf i t ) 的竞争比为1 7 1 0 。1 9 8 6 年，y a o 2 0 】声明在在线装箱问题算法中显式使用竞争分析，并且证明了在线算法的 下界是大于等于1 5 ，提出改进的首次适应算法( r e f i n e df i r s tf i t ) ，其竞争比为5 3 。 之后b r o w n 2 4 】将在线装箱算法的下界精确到大于等于1 5 3 6 。当前关于在线装箱问 题算法的最优下界是1 5 4 0 2 5 1 。 另外，在线算法还广泛应用于计算机通信网络【2 6 。2 3 1 ，图论【2 9 训】，学习理论【3 2 1 ， 等计算机相关领域中。 2 、金融领域 随着在经济管理当中出现越来越多的在线问题，竞争研究算法在金融决策及 经济管理领域也引起了越来越多的关注，由于一方面在经济决策当中，面对在线 决策环境，投资者通常是期望获得某一较少但相对确定性的收益，而不是愿意暴 露在严重的风险之下期望获得比较高的平均利润，实质上，这正是竞争分析所能 提供的。另一方面竞争比的另外一个优点是：在某种程度上，它提供了一般意义 下任何两种可供比较算法的性能统一度量。因此竞争分析方法在经济领域已经越 来越多的获得了认可。 1 ) 在线拍卖问题 随着信息和网络技术的发展，网上动态拍卖机制已作为一种重要的电子商务 活动，得到了迅速发展。1 9 9 9 年，g o l d b e r g 7 】在计算机理论科学领域提出应用竞 争分析框架来研究无限供给下数字产品的在线拍卖问题。随后，许多学者应用在 线算法和竞争分析对在线拍卖问题进行了一系列广泛深入的研究。2 0 0 0 年，l a v i 和n i s a n 3 3 给出有限供给k 个物品在线拍卖的确定性算法，分析算法得出算法获得 竞争比m a x f o i k + l , o l o g f a ) ，这里缈表示拍卖物品估价的上下界的比值。2 0 0 3 年， a w e r b u c h 等【3 4 】在l a v i 和n i s a n 的研究模型基础上，研究了在激励相容条件下无限 供给物品的在线拍卖问题，设计了随机在线拍卖算法。2 0 0 4 年，h a j i a n g h a y i 等【3 5 】 在l a v i 和n i s a n 的研究基础上，引入竞买人的进入与离开时间，使竞争比达到 e + d ( 1 ) 。 7 在线货币交易问题中的竞争性决策算法研究 2 ) 在线租赁问题 在线租赁问题是在线问题及其竞争算法理论在决策领域和金融领域应用的一 个热点方向，也是在线不确定性决策理论研究的一个重要方向。关于在线租赁问 题，最初的模型是1 9 9 2 年k a r p 在理论计算机科学领域提出的“租雪橇 问题。 即在租赁活动当中，投资者每期必须做出是继续租用还是立即购买设备的决策。 若投资者知道未来使用期限，则为离线问题；若投资者不知道未来使用期限，则 为在线问题。对于在线租赁问题，k a r p 给出了最优的确定性算法，其竞争比为 2 1 s ，其中召为购买设备的费用。之后徐维军等在文献 3 6 】中结合输入结构的分 布信息研究了离散型的在线租赁问题，建立了最优的离散型在线租赁决策模型，并给出 了最优的竞争策略及其竞争比，将这一情形下的在线租赁问题的竞争比降低到了 1 4 3 9 5 9 ，并且通过事实证明，将在线竞争算法同未来信息预测分布特征结合起来 研究的方法是行之有效的。 在线租赁问题另外一个研究的热点方向是其推广模型的研究。徐寅峰等在文 献 3 7 】中将市场利率这一因素条件引入到在线租赁问题中去，相比早期的研究，文 献 3 7 1 给出的竞争比性能更好，竞争模型更加地接近现实情况。另外近年来辛春林 等在文献 3 8 1 、 3 9 】中讨论的特殊优惠卡问题也是在线租赁问题的一个推广。 3 ) 在线外汇兑换问题 在线外汇兑换问题是在线问题及其竞争算法理论在决策领域和金融领域应用 的另一个热点方向，同样也是在线不确定性决策理论研究的一个重要方向。在线 外汇兑换问题是指在线交易者观察按序展开的价格汇率序列，并选择一个价格汇 率，但在作选择决定时不清楚后续价格汇率，目的是选择的价格汇率使获得的在 线收益较接近于离线最优价格的收益。目前在线外汇兑换问题已经存在许多模型 及相应的确定性算法和随机性算法。 另外，在线算法还广泛应用于在线证券组合投资问题中 4 0 - 4 2 】。 1 2 课题背景及研究意义 近年来，随着社会经济的发展与信息时代的到来，网络已经逐渐成为人们生 活要素的一部分，许多网站看到了其中的商机，利用其资源和网络特点，为人们 提供不同的服务，给人们生活带来了极大的便捷。各种决策也越来越呈现出在线 特征，特别是在金融研究领域，如证券组合投资、融资租赁及在线拍卖等方面，存在 着很强的动态特征，需要在没有获得未来足够信息时就必须对当期需求做出决策。 并且随着经济贸易的全球化，各国之间的商贸往来也越来越频繁，企业之间进行进 出口业务时，不同货币之间的往来结算也变得越来越重要，同时人口的流动日益频 繁，出国旅游、移居国外的人们往往需要进行货币兑换，货币兑换也变得越来越重 要。 8 硕十学位论文 曼曼曼曼曼曼曼曼曼量曼曼曼曼i i ；i 一一i ii i 皇曼曼曼! 曼曼曼曼舅 在线交易问题同样是需要人们在未知以后信息的情况下做出一些决策，并且 希望获得最大利润。本文所关注的在线交易问题主要是在线时间序列搜索和单向 交易两种模型，其中单向交易问题模型是在线时间序列问题模型的一个扩展。传 统方法在处理此问题时，通常假设未来输入序列为一随机变量，服从某种概率分 布，然后寻求平均意义上的最优方案。当最坏情形发生时，这种概率意义上的最 优方案将失去任何意义。更重要的是，在决策分析中，有时变量之间的关系往往 非常复杂，很难构造出一个合适的概率分布。再者，传统决策优化方法实质上是 一种离线优化方法，在给定输入分布并假设条件不变的情况下进行事后优化的。 之后出现了一些在线算法研究此在线决策问题，弥补了传统方法的不足，并通过 竞争分析方法分析了在线算法。 在线交易问题已出现许多变变型和扩展，存在着普遍应用，例如搜索雇员和 工作，寻找商品的最低价格等等，因此对在线交易问题的竞争性算法进行改进以 降低竞争比，从而提高竞争性有着非常重要的理论和现实意义，是在线决策问题 中非常有前景的研究课题。 1 3 国内外研究现状 对于在线交易问题的研究最初主要基于b a y e s i a n 方法，基于