2010, 21(5):875-885.
摘要:为了分析差分演化(differential evolution,简称DE)的收敛性并改善其算法性能,首先将差分算子 (differential operator,简称DO)定义为解空间到解空间的笛卡尔积的一种随机映射,利用随机泛函理论中的随机压缩 映射原理证明了DE 的渐近收敛性;然后,在“拟物拟人算法”的启发下,通过对DE 各进化模式的共性特征与性能差 异的分析,提出了一种具有多进化模式协作的差分演化算法(differential evolution with multi-strategy cooperatingevolution,简称MEDE),分析了它所具有的隐含特性,并在多模式差分算子(multi-strategy differential operator,简称 MDO)定义的基础上证明了它的渐进收敛性.对5 个经典测试函数的仿真计算结果表明,与原始的DE,DEfirDE 和 DEfirSPX 等算法相比,MEDE 算法在求解质量、适应性和鲁棒性方面均具有较明显的优势,非常适于求解复杂高维 函数的数值最优化问题.
2010, 21(5):886-898.
摘要:Packing 问题构成了一类重要的NP 难问题.对于加权3-Set Packing 问题,把问题转化成加权3-Set Packing Augmentation 问题进行求解,即主要讨论如何从一个已知的最大加权k-packing 求得一个权值最大的(k+1)-packing. 通过对问题结构的分析,结合Color-Coding 技术,首先给出了一种时间复杂度为O*(10.63k)的参数算法,极大地改进了目前文献中的最好结果O*(12.83k).通过对(k+1)-packing 结构的进一步分析,利用集合划分技术将上述结果降到O*(7.563k).
2010, 21(5):899-915.
摘要:首先归纳了AADL(architecture analysis and design language)的发展历程及其主要建模元素.其次,从模型 驱动设计与实现的角度综述了AADL 在不同阶段的研究与应用,总结了研究热点,分析了现有研究的不足,并对 AADL 的建模与分析工具、应用实践进行了概述.最后,探讨了AADL 的发展与研究方向.
2010, 21(5):916-929.
摘要:重复数据删除技术主要分为两类:相同数据的检测技术和相似数据的检测与编码技术,系统地总结了 这两类技术,并分析了其优缺点.此外,由于重复数据删除技术会影响存储系统的可靠性和性能,又总结了针对这 两方面的问题提出的各种技术.通过对重复数据删除技术当前研究现状的分析,得出如下结论:a) 重复数据删除 中的数据特性挖掘问题还未得到完全解决,如何利用数据特征信息有效地消除重复数据还需要更深入的研 究;b) 从存储系统设计的角度,如何引入恰当的机制打破重复数据删除技术的可靠性局限并减少重复数据删除技术带来的额外系统开销也是一个需要深入研究的方面.
2010, 21(5):930-941.
摘要:基于形式化的构件语义定义了健壮性,并提出一种基于状态机的构件健壮性测试方法.基于该方法实现 了原型工具RoTesCo.首先遍历状态机生成一组覆盖所有转换的路径,基于这些路径的测试用例驱动构件发生状态 转换;然后用无效输入和不当调用在构件的不同状态来测试其健壮性.通过区分测试中捕获异常的类别,自动报告健 壮性错误.以通用的开源项目构件组成评测平台,实验数据显示,RoTesCo 的测试效率比已有的算法表现得更优越.
2010, 21(5):942-949.
摘要:针对现有NHPP 类软件可靠性增长模型对故障排错过程中不完美排错情况考虑不完全的现状,提出了一 种新的软件可靠性增长模型.该模型全面考虑了不完美排错的两种情况:既考虑了排错过程中引入新错误的可能性, 又考虑了不完全排错的情况,并且引入了一种故障排除率随时间变化的故障排除率函数,使模型更符合实际情况.利 用公开发表的两组不同的软件失效数据对该模型进行验证的结果表明,与现有的对不完美排错情况考虑不完全的 模型相比,该模型能够取得更好的拟合结果和预测效果.
2010, 21(5):950-967.
摘要:将正交试验设计引入到克隆选择操作中,设计出基于正交试验的克隆选择操作(clonal selection operation based on orthogonal experiment design,简称CSO-OED),并将其加入到典型的克隆选择算法中,设计出并联式的 CSO+CSO-OED(I)算法和串联式的CSO+CSO-OED(II)算法.将新设计的算法用于9 个经典的测试函数和6 个复杂 的测试函数进行对比测试,实验结果表明,CSO-OED 能够有效地保持种群的多样性,避免算法不成熟收 敛.CSO+CSO-OED(I)和CSO+CSO-OED(II)将全局搜索和局部搜索分开进行优化,对比实验表明,这种搜索策略不 但能够保证算法的收敛性,还能有效地提高搜索解的精度,增强算法的鲁棒性.
2010, 21(5):968-977.
摘要:粗糙集扩展模型的研究是粗糙集理论研究的一个重要问题.其中,基于覆盖的粗糙集模型扩展是粗糙集 扩展模型中的重要一类.覆盖近似空间中的概念近似是从覆盖近似空间中获取知识的关键.目前,研究者对覆盖近似空间中经典集合的近似进行了较多的研究.针对覆盖近似空间中模糊集合的近似,虽然不同的覆盖粗糙模糊集模型 被提了出来,但它们都存在不合理性.从规则的置信度出发,提出了一种新的覆盖粗糙模糊集模型.该模型修正了已 有模型中存在对象在下近似中不确定可分和上近似中不近似可分的问题.分析了具有偏序关系的两个覆盖近似空 间中上、下近似之间的关系,发现两个不同覆盖生成相同覆盖粗糙模糊集的充要条件是这两个覆盖的约简恒等.分 析了新模型与Wei 模型、Xu 模型之间的关系,发现这两种模型是新模型的两种极端情况,且其应用前提是覆盖为一 元覆盖.这些结论将为覆盖粗糙模糊集模型应用于决策为模糊的情形提供理论基础.
2010, 21(5):978-990.
摘要:借鉴人类学研究中族群的概念以及以族群为视角来分析群体的结构及其演变趋势的方法,提出了一种简 单、有效的群体结构调控技术——族群机制.设计了针对二进制编码方式的族群分类方法,并基于该族群结构形成 了具有双轨协同进化特征的族群进化算法以及相应的族群算子.针对高维函数和复杂混合函数的数值优化实验表 明,族群进化机制可以显著提高群体的抗早熟能力和搜索效率,与其他典型算法的对比也表明,族群进化算法是一种 具有竞争力的函数优化算法.
2010, 21(5):991-1006.
摘要:主要从数据的机密性、数据的完整性、数据的完备性、查询隐私保护以及访问控制策略这5 个关键技 术,综述国际上在数据库服务——安全与隐私保护方面的研究进展.数据的机密性主要从基于加密和基于数据分布 展开分析;数据的完整性和完备性主要从基于签名、基于挑战-响应和基于概率的方法展开分析;查询隐私保护和访 问控制策略主要从目前存在的问题展开分析.最后展望了数据库服务——安全与隐私保护领域未来的研究方向、存 在的问题及面临的挑战.
2010, 21(5):1007-1019.
摘要:探讨演变图(即随时间变化的图)的挖掘,重点研究在演变图中挖掘连接子图的演变模式集合.提出一种连 接子图的相似度函数及其快速计算算法.基于该相似度函数,提出一种发现演变模式集合的多项式时间复杂度的动 态规划算法.模拟数据集上的实验结果表明,该算法具有较低的误差率和较高的效率.真实数据集上的实验结果表 明,挖掘结果在真实应用中具有实际意义.
2010, 21(5):1020-1030.
摘要:由于无线传感器网络的能源有限,且在许多应用中Skyline 查询的部分结果即可满足用户需求,提出了一 种近似Skyline 查询处理算法,在满足用户查询需求的前提下最大化地节省能量.该算法仅需无线传感器网络中的部 分传感器节点回传其感知数据即可计算出Skyline 查询的一个近似结果集.由于该算法在处理查询时,每个传感器节 点只需考察自身数据信息即可决定是否回传其感知数据,而无须与其他传感器节点的感知数据进行比较,因此可以 避免大量的网内通信开销,从而节省网络能源.模拟环境下的大量实验结果表明,该算法可以根据用户的应用需求, 节能地处理传感器网络中的近似skyline 查询.
2010, 21(5):1031-1041.
摘要:为解决倾斜分布的数据流聚类这一难题,提出了时态密度概念,给出其度量,揭示了其包括可增量计算在 内的一系列数学性质;设计了时态密度树结构,提高了聚类时的存储和检索效率;设计了能够以实时或异步方式捕捉 数据倾斜分布的数据流时态特征的聚类算法TDCA(temporal density based clustering algorithm),其时间复杂度为 O(c×m×lgm).实验结果表明,该算法不仅有较强的功能,而且具有较好的规模可伸缩性.
2010, 21(5):1042-1054.
摘要:提出一种两阶段评分预测方法.该方法基于一种新的联合聚类算法(BlockClust)和加权非负矩阵分解算 法.首先对原始矩阵中的评分模式进行用户和物品两个维度的联合聚类,然后在这些类别的内部通过加权非负矩阵 分解方法进行未知评分预测.这种方法的优势在于,首阶段聚类后的矩阵规模远远小于原始评分矩阵,并且同一类别 内部的评分具有相似的模式,这样,在大幅度降低预测阶段计算量的同时又提高了非负矩阵分解算法在面对稀疏矩 阵预测上的准确度.进一步给出了推荐系统的3 种更新模式下如何高效更新预测模型的增量学习方法.在MovieLens数据集上比较了新算法及其他7种相关方法的性能,从而验证了该方法的有效性及其在大型实时推荐系 统中的应用价值.
2010, 21(5):1067-1082.
摘要:分析了广域网分布式Web 爬虫相对于局域网爬虫的诸多优势,提出了广域网分布式Web 爬虫的3 个核心 问题:Web 划分、Agent 协同和Agent 部署.围绕这3 个问题,对目前学术界和商业界出现的多种实现方案和策略进 行了全面的综述,深入讨论了研究中遇到的问题与挑战,并论述了广域网分布式Web 爬虫的评价模型.最后,对未来 的研究方向进行了总结.
2010, 21(5):1083-1097.
摘要:基于目前对用户搜索意图的分类,进一步分析了每种用户意图的信息需求,提出了基于用户搜索意图的 Web 网页动态泛化模型,为搜索的Web 网页动态地建立文档片段、关键词、导航类型、文档格式之间的概念层次, 通过网页内容、类型和格式的泛化为不同的访问意图提供进一步的搜索导航,从而返回与搜索意图更相关的结果. 与相关工作对比,重点并非获取用户意图,也不是对用户意图分类,而是基于用户搜索意图的Web 网页动态泛化模型 的建立及Web 网页泛化过程的实现.实验结果表明,该泛化模型不仅能够通过导航自动获取用户搜索意图,而且能够 基于该意图提供相关搜索结果以及进一步的搜索导航.
2010, 21(5):1098-1114.
摘要:对3 种已有的计数型Bloom filter——Na?ve Counting Bloom Filter(NCBF),Space-Code Bloom Filter (SCBF)和d-left Counting Bloom Filter(dlCBF)——的查询错误概率进行了分析,得出了NCBF 的计数器防溢出条件 以及SCBF 和dlCBF 的参数最优设置准则.提出了一种衡量计数型Bloom filter 性能的指标:负载适应性.针对dlCBF 负载适应性差的问题,对dlCBF 进行了改进,提出了一种计数型Bloom filter:Binary Shrinking d-left Counting Bloom Filter(BSdlCBF).通过仿真实验,以计数误差、空间复杂度以及负载适应性为性能指标,对上述4 种CBF 进行了比较. 实验结果表明,BSdlCBF 具有最低的空间复杂度、最小的计数误差以及最佳的负载适应性. BSdlCBF 赢得上述性能 优势的代价在于其计算复杂度比其他3 种计数型Bloom filter 略高.
2010, 21(5):1115-1126.
摘要:提出了一种基于双层Counter Bloom Filter 的长流识别算法(algorithm based on double counter bloom filter for long flows identification,简称CCBF).该算法使用两层Counter Bloom Filter 结构,将长流过滤和长流存在分开处 理.分析了该算法的误判率,通过模拟数据分析了算法错误率和内存资源限制的关系,并在相同内存资源限制的条件 下,将该算法与类似算法的准确性进行了比较.结果表明,在数据量较大的情况下,该算法具有比现有算法更小的平 均错误率;对算法的时间效率分析表明,该算法可以达到1 500kpps 的处理速度.各项指标反映出,该算法可以应用于 大规模主干网的长流监测.
2010, 21(5):1127-1137.
摘要:提出了一种基于分簇的无线传感器网络数据汇聚传送协议CDAT(a cluster-based data aggregation and transmission protocol for wireless sensor networks).CDAT 通过均衡能耗的分簇方法及数据预测传送机制,可以有效 延长网络的生命期.在簇头选取阶段,利用应用期望的无缝覆盖率与所需簇头数的数学关系,限制节点竞选簇头的初 始概率,并联合节点的度和剩余能量来选取簇头;在数据聚合阶段,簇头广播消息,接收所有加入该簇的成员节点,然后对簇内数据进行聚合;在数据传送阶段,利用数据在时间上的相关性,簇头在满足传送精度的要求下,采用预测传 送机制将数据传送给基站,通过该机制,网络有效地减少了数据传送的次数.理论分析和模拟实验结果表明,CDAT 协 议在满足应用期望的服务质量要求下,通过均衡能耗、减少数据传送次数,使得网络生命期优于LEACH(low-energy adaptive clustering hierarchy),PEGASIS(power-efficient gathering in sensor information systems)等协议.
陈建忠 , 徐天音 , 李文中 , 陆桑璐 , 陈道蓄 , Edward CHAN
2010, 21(5):1138-1152.
摘要:提出了一种基于衍生树的P2P 系统框架,以支持交互式流媒体应用.该系统利用分布式发现服务来进 行资源定位,并通过基于衍生树的缓存结构来维护数据传输拓扑.使用基于衍生树的系统管理策略可以显著地降低 节点动态加入和退出等交互操作的开销.另外,通过使用分布式散列表(distributed hash table,简称DHT)来维护会话, 可以较低的代价实现资源查找、服务重构和拓扑维护等任务.仿真实验结果表明,与现有的P2P 流媒体系统相比,该 系统具有良好的性能,其用户交互操作的开销可以降低超过50%.
2010, 21(5):1153-1170.
摘要:根据手势手语的特点,提出了手语语言学和人体运动学相结合的非特定人手语数据的生成和检测方法. 首先,Mean-Shift 算法有控制生成强度的优点,将改进的Mean-Shift 算法应用于手形数据通道的生成,以保持手势手 语的语言学特性,并应用关键手形的音韵标记进行数据有效性的检测;其次,为了丰富手语手势动作的运动特性,将 改进的遗传算法应用于与运动相关的数据通道进行数据生成,并应用拉班舞谱对其进行数据有效性检测;最后,提出 了基于原始样本的检测实验框架,使得所提出的检测方法适用于语言类的多类别数据检测问题.实验结果表明,所提 出的非特定人手语数据的生成和检测方法是有效的.
2010, 21(5):1171-1180.
摘要:提出了一种基于反馈控制的自主虚拟人感知模型.该模型首先使用感知过滤器模拟人类器官感知限制, 然后设计了环形队列存储感知对象的相关信息来模拟人类的记忆功能,进而利用感知和记忆的结果,对感知过滤器 的各项参数进行反馈控制,从而体现感知结果对感知过程的影响.实验结果表明,基于反馈控制的感知模型不仅能够 较好地体现人类感知系统的特性,而且能够为自主虚拟人行为控制和决策提供更为真实的环境信息.