Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2008年 第45卷 第9期    出版日期:2008-09-15
论文
基于路径匹配的在线分层强化学习方法
石 川, 史忠植, 王茂光,
2008, 45(9):  . 
摘要 ( 588 )   PDF (1197KB) ( 475 )  
相关文章 | 计量指标
如何在线找到正确的子目标是基于option的分层强化学习的关键问题.通过分析学习主体在子目标处的动作,发现了子目标的有效动作受限的特性,进而将寻找子目标的问题转化为寻找路径中最匹配的动作受限状态.针对网格学习环境,提出了单向值方法表示子目标的有效动作受限特性和基于此方法的option自动发现算法.实验表明,基于单向值方法产生的option能够显著加快Q学习算法,也进一步分析了option产生的时机和大小对Q学习算法性能的影响.
一种基于规划理论的密码协议形式模型
赵 宇 王亚弟 韩继红 范钰丹 张 超
2008, 45(9):  . 
摘要 ( 322 )   PDF (1553KB) ( 376 )  
相关文章 | 计量指标
将规划理论引入到密码协议形式化分析领域,结合密码协议在实际网络环境中的运行特点和规律,提出了密码协议攻击规划理论;建立了一种对密码协议进行安全性验证的形式化模型,即密码协议攻击规划问题模型;给出了模型的一阶语法、形式定义及相关运算语义.同时,分析了Dolev-Yao模型的不足之处,基于基本消息元素策略对其进行了改进;并通过增强应用语义来保证改进模型的可行性,从而避免了“状态空间爆炸”问题的发生,提高了密码协议攻击规划问题模型的完备性;并给出了基于该模型的NS公钥协议分析实例.提出的密码协议形式模型是证伪的,目的在于对密码协议进行验证,并查找协议中可能存在的漏洞,既可以方便地进行手工推导证明,也非常易于自动化实现.
基于偏向信息学习的双层强化学习算法
林 芬, 石 川, 罗杰文, 史忠植,
2008, 45(9):  1455-1462. 
摘要 ( 659 )   HTML ( 0)   PDF (1435KB) ( 475 )  
相关文章 | 计量指标
传统的强化学习存在收敛速度慢等问题,结合先验知识预置某些偏向可以加快学习速度.但是当先验知识不正确时又可能导致学习过程不收敛.对此,提出基于偏向信息学习的双层强化学习模型.该模型将强化学习过程和偏向信息学习过程结合起来:偏向信息指导强化学习的行为选择策略,同时强化学习指导偏向信息学习过程.该方法在有效利用先验知识的同时能够消除不正确先验知识的影响.针对迷宫问题的实验表明,该方法能够稳定收敛到最优策略;并且能够有效利用先验知识提高学习效率,加快学习过程的收敛.
结合似然关系模型和用户等级的协同过滤推荐算法
高 滢 齐 红 刘 杰 刘大有
2008, 45(9):  1463-1469. 
摘要 ( 489 )   HTML ( 2)   PDF (1103KB) ( 605 )  
相关文章 | 计量指标
针对传统协同过滤推荐算法的稀疏性、扩展性问题,提出了结合似然关系模型和用户等级的协同过滤推荐算法.首先,定义了用户等级函数,采用基于用户等级的协同过滤方法,在不影响推荐质量的前提下有效提高了推荐效率,从而解决扩展性问题;然后,将其与似然关系模型相结合,使之能够综合利用用户信息、项目信息、用户对项目的评分数据,对不同用户给出不同的推荐策略,从而解决稀疏性问题,提高推荐质量.在MovieLens数据集上的实验结果表明,该算法比单纯使用基于似然关系模型或传统协同过滤技术的推荐算法,不仅推荐质量有所提高,推荐速度比传统协同过滤算法明显加快.
一种基于模态逻辑的聚类结果评价方法
吕宗磊 王建东 李 莹 宰云峰
2008, 45(9):  1477-1485. 
摘要 ( 519 )   HTML ( 0)   PDF (1437KB) ( 496 )  
相关文章 | 计量指标
聚类评价指标对衡量一个聚类的优劣有着重要作用.现有的聚类评价指标通常都基于统计理论或模糊理论.收到基础理论的限制,在一些特殊场合,这些指标不能对聚类进行正确的评估.提出了一种基于模态逻辑的新的聚类评价指标.通过把相似性定义成数据集上的二元关系聚类被描述成Kripke结构.用原子公式表示每个簇后,聚类的结果可以用一组逻辑公式来表示.根据最小描述长度原则,聚类评价指标由这种表示方式的准确性和复杂性构成.由于这种新的评价指标对相似性没有任何附加的限制,它较之现有的评价指标更为通用,而那些指标往往都默认了某种相似性度量方式.列举了用于对比新旧指标的实验.实验结果表明,这种新的评价指标在一般情况下与大多数评价指标一致,而在一些类似“双环”的特殊情况下比现有评价方式更有效.
一种隶属关系不确定的可能性模糊聚类方法
陈健美, 陆 虎, 宋余庆, 宋顺林, 徐 景, 谢从华, 倪巍伟,
2008, 45(9):  1486-1492. 
摘要 ( 486 )   HTML ( 1)   PDF (1110KB) ( 478 )  
相关文章 | 计量指标
模糊聚类是聚类分析的一个重要分支,模糊C-均值聚类算法及其改进算法都是一种基于概率约束的聚类方法,所采用隶属度的取值形式体现了数据集的绝对隶属程度,常常出现不理想的聚类结果.对此,提出了不确定隶属的概念,在此基础上,通过提出两个基于相对隶属程度的判断准则参数,设计出一种新的基于隶属关系不确定的可能性模糊聚类新算法, 并给出了具体算法实现. 新算法将迭代过程中数据集对聚类簇隶属的可能性与不确定性关系引入目标函数中,达到明显的优化聚类结果的功效.理论分析和实验结果表明,相对其他聚类算法,新算法具有更高的聚类正确率.
多获胜节点SOM及其在股票分析中的应用
王丽敏, , 梁艳春, 韩旭明, , 时小虎, 李 明,
2008, 45(9):  1493-1500. 
摘要 ( 590 )   HTML ( 0)   PDF (1455KB) ( 472 )  
相关文章 | 计量指标
为了增强自组织映射(self-organizing map, SOM)网络的动态竞争和聚类能力,提高解的精度,在无监督的SOM神经网络的基础上,通过拓广获胜节点的数量,改进网络中的邻域函数和连接权函数等方法,提出具有多获胜节点的SOM模型.为了避免多个输入样本映射到同一个输出节点,还提出了禁忌映射的方法.为了验证所提出的方法的有效性,以股票的聚类分析为实例,对该方法进行了检验.通过对每股收益、每股净资产、净资产收益率、每股经营性现金流量及净利润等5项反映上市公司综合盈利能力的财务指标进行了模拟实验,所得的数值结果表明,在标准SOM及所提出的几种多获胜节点SOM网络模型中,具有双获胜节点(SOM with 2 winners, SOM2W)的网络模型获得了最好的聚类效果.结合实验结果对网络模型的进一步分析也表明,SOM2W的聚类能力优于标准SOM及其他网络模型.该模型为股票的分析和选择提供了一种可行的途径,在金融领域具有潜在的应用价值.
量子退火算法研究进展
杜卫林 李 斌 田 宇
2008, 45(9):  1501-1508. 
摘要 ( 1633 )   HTML ( 4)   PDF (1382KB) ( 4218 )  
相关文章 | 计量指标
在数学和应用领域,量子退火算法是一类新的量子优化算法.不同于经典模拟退火算法利用热波动来搜寻问题的最优解,量子退火算法利用量子波动产生的量子隧穿效应来使算法摆脱局部最优,而实现全局优化.在已有的研究中,量子退火算法在某些问题上展现出良好的优化效果.系统地综述了量子退火算法的基本原理和近年来的主要研究进展,较为详细地介绍了几个主要的量子退火算法,对量子退火算法的优点和可能的不足进行了分析评述,并对今后的研究方向进行了展望.
论文
一种基于链暗示技术的Min-CVCB问题的精确算法
王建新, 许小双, 冯启龙, 李 敏,
2008, 45(9):  1509-1516. 
摘要 ( 512 )   HTML ( 1)   PDF (1230KB) ( 438 )  
相关文章 | 计量指标
随着VLSI(超大规模集成电路)技术的发展,关于可重构阵列二分图的受约束最小点覆盖(Min-CVCB)问题受到了很多文献的关注.作为点覆盖问题的子问题,该问题已被证明是NP-完全问题.人们利用核心化和分支即使给出了时间复杂度为O((k\-u+k\-l)|G|+1.26\+\{k\-u+k\-l\})的目前最好算法,然而仍不能满足实际工程的需要.通过进一步深入分析二分图的结构,对含有权值大于或等于3的块的连通子图分析其可能连接情况后充分利用“链暗示”技术和分枝搜索技术来建立起新的搜索递推关系;对于分枝后的块提出了一种动态规划算法,其可在多项式时间内完成处理.整个参数算法的运行时间为O((k\-u+k\-l)|G|+1.1892\+\{k\-u+k\-l\}),极大地改进了目前的最好结果.
一种基于目录的软件事务性内存实现算法
张小强 彭 林 彭元喜 谢伦国
2008, 45(9):  1517-1523. 
摘要 ( 566 )   HTML ( 0)   PDF (1280KB) ( 463 )  
相关文章 | 计量指标
软件事务性内存(STM)提供同步手段,让多线程程序高效并发执行.STM算法中一般包含记录所访问的共享数据、缓冲投机修改的数据以及处理事务冲突.STM中的主要开销在于维护共享数据访问记录和一致性验证.维护共享数据访问记录主要目的是便于进行验证.冲突检测(conflict detection)判断两个事务能否同时提交,而验证(validation)确保每个线程看到的数据状态是一致的.给出了关于STM一个简单模型,证明在STM中对共享数据的修改是线性的.提出的LDSTM算法通过在目录中维护版本信息,可以在读取各个共享对象时快速确定事务的内存视图是否处于一致状态,可以极大减少冲突检测和验证的开销.该算法可以实现早期发现写-写冲突,减少无效计算.在单线程情况下该算法开销很小.实验数据表明,LDSTM简单高效,冲突检测和验证开销减少明显.
一种大规模网络上的服务组合流程搜索方法
虎嵩林, 梁 英, 姜 伟, 李 伟,
2008, 45(9):  1524-1531. 
摘要 ( 412 )   HTML ( 0)   PDF (1434KB) ( 456 )  
相关文章 | 计量指标
集中式的自动服务组合和非平凡服务发现能够根据给定的、具有特定输入输出的请求搜索出一系列满足要求的服务组合,是当前服务计算领域的研究热点.针对集中式结构带来的性能瓶颈和单点故障问题,提出了一种利用基于内容的分布式发布订阅技术实现大规模网络环境下的无中心自动服务组合方法,称之为流程搜索.基于内容的分布式发布订阅系统能够根据发布消息和订阅消息之间的内容匹配关系,将发布者提供的消息通过一系列中介节点转发给感兴趣的订阅者. 它可以为服务接口之间的可互操作性判定以及查询路由提供支持.将服务模型映射为发布订阅的消息模型,并利用基于内容的路由设计形成分布式环境下的搜索算法,并基于PADRES系统开发了一个PreSee原型系统.模拟实验显示,无中心控制的方法相对于集中式的架构而言,可以有效降低系统延迟,提高整个系统的效率.
基于领域最近邻的协同过滤推荐算法
李 聪, 梁昌勇, 马 丽,
2008, 45(9):  1532-1538. 
摘要 ( 909 )   HTML ( 8)   PDF (1132KB) ( 1198 )  
相关文章 | 计量指标
协同过滤是目前电子商务推荐系统中广泛应用的最成功的推荐技术,但面临严峻的用户评分数据稀疏性和推荐实时性挑战. 针对上述问题,提出了基于领域最近邻的协同过滤推荐算法,以用户评分项并集作为用户相似性计算基础,将并集中的非目标用户区分为无推荐能力和有推荐能力两种类型;对于前一类用户不再计算用户相似性以改善推荐实时性,对于后一类用户则提出“领域最近邻”方法对并集中的未评分项进行评分预测,从而降低数据稀疏性和提高最近邻寻找准确性. 实验结果表明,该算法能有效提高推荐质量.
空间数据库平面线段近邻查询问题研究
郝忠孝, 王玉东, 何云斌,
2008, 45(9):  1539-1545. 
摘要 ( 604 )   HTML ( 0)   PDF (933KB) ( 573 )  
相关文章 | 计量指标
空间数据库的近邻查询近几年受到人们越来越多的关注.近邻查询根据程度不同可分为点与点的近邻查询、点与线段、线段与线段的近邻查询.目前,前两者研究的较多,后者没有查到相关文献.提出平面线段与线段的近邻查询问题.有针对性地解决一些空间物体无法抽象为点的情况.平面线段的近邻查询在现实中有着广泛的应用价值.根据平面线段与线段是否相交分为两类;不相交的平面线段再根据位置关系分成9种情况.分别对上述各种情况进行讨论研究.给出了线段近邻查询的筛选规则、定理和查询算法,进行了实验分析和比较,新方法实现了平面线段与线段的近邻查询,具有较高的查询效率.
自治异构数据源聚集模型与算法研究
王 博 郭 波
2008, 45(9):  1546-1553. 
摘要 ( 438 )   HTML ( 0)   PDF (1431KB) ( 563 )  
相关文章 | 计量指标
自治异构数据源信息共享的主要问题是如何在P2P环境下对自治数据节点的信息进行统一访问.采用分层结构组织数据源节点能够提高查询效率,减小计算开销,但需要节点根据彼此相似度实现局部的聚类.给出了数据源节点信息发布的形式化描述,提出了基于模式元素匹配的自治异构数据源多重聚集模型以及聚类组织构建过程,采用TA算法解决top-K聚类节点搜索问题,并在此基础上提出TAL算法.实验结果表明,TA和TAL算法能够高效地解决节点聚类排序的问题,特别是TAL算法在聚类节点范围较大时计算性能优于TA.
Active XML文档有效性检验
马海涛, 郝忠孝, , 朱 燕,
2008, 45(9):  1554-1560. 
摘要 ( 467 )   HTML ( 0)   PDF (989KB) ( 417 )  
相关文章 | 计量指标
文档有效性检验是XML领域的一个基本问题.Active XML(AXML)文档在XML文档中引入Web服务,传统用于解决XML文档有效性的检验方法并不适用于AXML文档,为文档有效性检验提出了新的挑战.研究了AXML文档有效性检验问题,在原始树自动机的基础上,定义了AXML模式树自动机—ASTA机,该树自动机能够有效地描述满足AXML模式约束的文档集合.基于ASTA机,提出了一种多项式时间的AXML文档有效性检验算法.实验数据表明,基于提出的算法能够有效的完成对AXML文档的有效性检验.
基于Frobenius映射的快速标量乘算法
殷新春, 侯红祥, 谢 立,
2008, 45(9):  1561-1566. 
摘要 ( 508 )   HTML ( 0)   PDF (801KB) ( 461 )  
相关文章 | 计量指标
标量乘法的效率决定着椭圆曲线密码体制的性能,而Koblitz曲线上的快速标量乘算法是标量乘法研究的重要课题,在标量k的TNAF约简基础上,给出了一种基于Frobenius映射的上层运算:Comb算法.在预计算阶段,该算法利用Frobenius映射对宽度为r的序列计算其对应椭圆曲线上的点,从而建立预计算表,在累加赋值阶段结合约简后的TNAF(k)和预计算表来提高效率.Comb算法基于高效的Frobenius映射无须进行倍点运算,经过Comb矩阵的组合,其所需点加量是传统算法的1/5~1/4,当行数r任意时,其效率在任意坐标下比传统Comb算法提高至少67%.
路由器中拥塞数据流浪费带宽问题及其解决方法
曹继军 苏金树 吴纯青 时向泉
2008, 45(9):  1578-1588. 
摘要 ( 520 )   HTML ( 0)   PDF (1765KB) ( 394 )  
相关文章 | 计量指标
传统的路由器拥塞控制算法主要依据本级队列资源的拥塞状态信息进行报文丢弃决策,这将导致产生拥塞数据流浪费带宽问题BW-CDF.从理论上分析了BW-CDF问题产生的原因,为解决该问题提出了一种新的路由器拥塞控制算法CC-AMR,该算法综合考虑多级资源的拥塞状态而实施更加合理的报文丢弃决策.同时,阐述了该算法在基于网络处理器的核心路由器上的实现方法.实际的测试验证结果表明该算法能够缓解BW-CDF问题,从而较大幅度地提高了拥塞发生时路由器的总吞吐率.
度量和分析BitTorrent
雷迎春, 阳立堂, 姜 琦, 龚奕利, 张 军,
2008, 45(9):  1589-1600. 
摘要 ( 412 )   HTML ( 2)   PDF (1954KB) ( 448 )  
相关文章 | 计量指标
BitTorrent是一个用于内容分发的P2P协议,现在已经发展成为互联网的一项重要的应用.从性能的角度度量BitTorrent的行为,解释BitTorrent协议的关键元素,分析BitTorrent是否是高效的.1)提出一种有效度量BitTorrent式的P2P内容分发协议的仿真实验方法; 2)确认BitTorrent协议的Neighbor Selection,Choking/Unchoking和Piece Selection机制存在诸多影响系统性能的缺陷;3)设计ShareStorm协议,作为参照对象,证明BitTorrent的缺陷在协议层可以避免.经仿真实验验证,在下载完成时间这个最主要的性能指标上,ShareStorm比BitTorrent至少减少50%.
2次有理Bézier曲线的最优参数化
陈 军 王国瑾
2008, 45(9):  1601-1604. 
摘要 ( 409 )   HTML ( 0)   PDF (656KB) ( 506 )  
相关文章 | 计量指标
把Bézier曲线的最优参数化技术成功地推广到外形设计系统中更为常用的2次有理Bézier曲线场合.新方法能够事先对曲线进行重新参数化,而不需要在计算过程中对非均匀的参数速率采用动态的补偿算法.其关键是巧妙地化简需要求解的高次有理函数积分公式,使得Mbius参数变换公式并不是基于数值解法来得到近似解,而是简单明了地具有解析形式的精确解. Mbius变换能够保持有理Bézier曲线的控制顶点和形状不变,仅仅改变曲线的参数分布情况.优化后的参数速率保持C\+1连续.新参数速率关于单位速率的偏离量在L\-2范数下达到最小,即实现了最优参数化,所得到的参数最为接近弧长参数.新方法简单直接,数值实例验证了算法的正确与有效.
基于水平集的扫描点云简化算法及在人体模型上的应用
卫维恕 罗笑南 李 峥
2008, 45(9):  1605-1611. 
摘要 ( 535 )   HTML ( 0)   PDF (1159KB) ( 498 )  
相关文章 | 计量指标
简化是计算机图形学的一个重要课题.针对真实性建模技术在图形领域的迅速发展和三维扫描设备的广泛应用,提出一种基于水平集的扫描点简化算法,对高密度的扫描点模型作简化处理,并能解决扫描点模型中普遍存在的重影与空洞问题.该方法具有自动排序特点,并且使简化结果保留原扫描点模型按层划分的特性.通过指定不同的简化半径,该算法自动生成多分辨率的层次细节模型.实验结果显示,新方法在高简化精度下具有好的保形性,所得模型的误差优于角度简化结果.该方法对于高曲率细节显示的特殊需求可作自适应拓展.简化所得的点模型可通过多边形或曲线、曲面重建.三维人体模型重建工作是服装仿真、计算机动画等方面研究的基础性工作.经简化方法处理所得不同精度的人体模型能作为后续应用的基础.
从局部分类精度到分类置信度的变换
刘 明, 袁保宗, 苗振江, 唐晓芳, 李昆仑,
2008, 45(9):  1612-1619. 
摘要 ( 748 )   HTML ( 0)   PDF (1221KB) ( 442 )  
相关文章 | 计量指标
基于局部分类精度设计多分类器系统能够有效地提高分类正确率.目前流行的动态分类器选择方法不能充分利用各个基本分类器的信息.在动态分类器选择方法中,局部分类精度最高的基本分类器决定最终的分类结果,其他基本分类器的信息被忽略.提出了一种将局部分类精度变换为分类置信度的方法,从而可以利用度量层分类器融合方法对得到的置信度进行融合.与动态分类器选择方法相比,度量层分类器融合方法能够利用更多的信息,从而能够取得更高的分类正确率.ELENA数据库、UCI数据库和DELVE数据库上的大量实验表明,新方法在分类正确率方面超过动态分类器选择方法大约0.2%~13.6%.
多处理器片上系统任务调度研究进展评述
李仁发 刘 彦 徐 成
2008, 45(9):  1620-1629. 
摘要 ( 503 )   HTML ( 1)   PDF (1757KB) ( 1288 )  
相关文章 | 计量指标
多处理器片上系统在单芯片上集成了多种指令集处理器,可完成复杂完整的功能,在图像处理、网络多媒体和嵌入式系统等应用领域前景广阔.任务映射与调度是多处理器片上系统设计的关键问题之一.介绍了多处理器片上系统的基本结构和面临的挑战,从调度算法分析和实现框架两个方面着重探讨了近年来多处理器片上系统任务调度的国内外研究进展情况,分析了当前亟待解决的问题与下一步主要的研究方向,可为多处理器片上系统相关研究提供参考.