计算机研究与发展杂志 北大期刊 CSCD期刊 统计源期刊

计算机研究与发展 2011年第04期杂志 文档列表

计算机研究与发展杂志人工智能

基于自适应划分的进化多目标优化非支配个体选择策略545-557

摘要：进化多目标优化主要研究如何利用进化计算方法求解多目标优化问题,已经成为进化计算领域的研究热点之一.多目标优化问题解的多样性主要体现在两个方面,即分布的广度和均匀程度.在分析了已有多目标进化算法保持解的多样性策略的基础上,提出了一种基于自适应划分的非支配个体选取策略.新策略根据非支配个体在目标空间的相似性程度对由当前非支配个体构成的前沿面进行自适应划分,在划分出的各区域选择最具代表性的个体,实现对非支配个体的修剪操作.为了验证新策略的有效性,将此策略应用于两类典型的多目标进化算法中,基于13个标准测试问题的仿真结果表明,自适应划分策略使最优解的均匀性和广度得到了很好的提升.

多查询相关的排序支持向量机融合算法558-566

摘要：排序学习是目前信息检索与机器学习领域研究的热点问题.现有排序学习算法在学习时把训练样本集中的所有查询及其相关文档等同对待,忽视了查询之间的差异,影响了排序模型的性能.对查询之间的差异进行描述,并在训练过程中考虑这种差异,提出一种基于有监督学习的融合多个与查询相关排序子模型的方法.该方法为每一个查询及其相关文档建立一个子排序模型,并将子排序模型的输出进行向量化表示,将多个查询相关的排序模型转化为体现查询差异的特征数据,实现多排序模型的集成.以排序支持向量机为例,在查询级和样本级建立新的损失函数作为优化目标,并利用此损失函数调节不同查询产生损失之间的权重,提出多查询相关的排序支持向量机融合算法.在文档检索和网页检索中的实验结果表明,使用多查询相关的排序支持向量机融合算法可以取得比传统排序学习模型更好的性能.

一种基于多目标进化算法的模糊关联分类方法567-575

摘要：准确率和解释性是模糊关联分类模型的两个相互制约的优化目标.目前已有的研究方法中,有的只考虑了分类模型的准确率,有的把模型两个目标转化为单目标问题求解,在模型解释性目标上的优化策略较简单.为此提出一种基于Apriori和NSGA-II多目标进化算法的模糊关联分类模型（MOEA-FACM）,采用基于概率独立性的模糊确认指标筛选生成高质量的模糊关联规则集,以Pittsburgh式的编码方式构建准确率和解释性折中的模糊关联分类模型.标准数据集上的实验表明,该方法所建模型分类准确率比同类模型高,分类模型具有较好的泛化能力,而其所含模糊关联规则的数目和规则前件总的模糊项的个数却较少,模型的解释性较好.

流形学习中基于局部线性结构的自适应邻域选择576-583

摘要：近年来,流形学习成为包括机器学习、模式识别和计算机视觉等相关领域的研究热点.流形学习算法中,邻域选择直接关系到算法的性能,而传统的邻域选择算法如k近邻和ε邻域算法存在参数难以确定,所构建邻域不能反映流形学习算法对邻域要求等缺点.提出了一种基于流形局部线性结构的自适应邻域选择算法（ANSLL）.首先通过分析现有流形学习算法,总结出构建邻域的两个基本原则：1）同一邻域的所有点都近似地位于某一d维线性子空间内（d为流形维数）;2）每个邻域包含尽可能多的点.基于这两个基本原则,ANSLL算法采用主成分分析技术（PCA）度量有限点集的线性程度,通过邻域压缩或扩张方式自适应地构建邻域.针对邻域线性结构的特点,还提出了一种改进的邻域图构建方法,以提高等度映射（Isomap）算法中测地线距离估计的准确性.最后大量系统的实验表明,ANSLL算法能够依据流形的局部曲率自适应地构建邻域,从而提高大多数流形学习算法（如Isomap和LLE）的性能.

多Agent动态影响图的一种混合近似推理算法584-591

摘要：多Agent动态影响图模型适合于对动态环境中多Agent问题进行建模,Agent之间结构关系被表示成局部的概率因式形式.概率图模型推理所面临的一个主要问题是难以实现近似推理的精度和复杂性之间的均衡.近似推理方法可提高推理精度,但同时也会带来推理精度的损失.BK和粒子滤波（PF）是动态概率模型两种重要的近似推理算法,BK算法有较高的计算效率但会引入较大的误差,PF可以近似任意分布但存在计算的高维问题.结合BK和PF的优点,提出多Agent动态影响图（MADIDs）的一种混合近似推理算法.根据概率图模型的可分解性,将MADIDs分解生成用于推理的原型联合树,混合近似推理算法在规模复杂度较小的团上执行PF推理以达到局部最佳估计,而在其他的团上执行BK推理,为了减小推理误差引入了分割团.仿真实验表明混合近似推理算法是MADIDs模型的一种有效推理方法,与BK和PF算法相比,该算法显著提高了推理精度,且可以实现推理精度和时间复杂性之间的均衡.

IKnnM-DHecoc：一种解决概念漂移问题的方法592-601

摘要：随着数据流挖掘的应用日趋广泛,带概念漂移的数据流分类问题已成为一项重要且充满挑战的工作.根据带概念漂移的数据流的特点,一个有效的学习器必须能跟踪并快速适应这种变化.一种基于增量KnnModel的动态层次编码算法被提出用于解决数据流的概念漂移问题.在将数据流划分为数据块后,根据增量KnnModel算法对每块的预学习结果构建并更新类别层次树、层次编码,用可增量学习的分类算法对照编码划分进行学习,并生成备选分类器集.最后依据活跃度对结点进行剪枝处理以减少计算代价.在预测阶段,利用增量KnnModel算法和动态层次纠错输出编码算法的各自优势进行联合预测.实验结果表明：基于增量KnnModel算法的动态层次纠错输出编码算法不但能够提高模型学习的动态性和分类的正确性,而且还能够快速适应概念漂移的情况.

联盟结构图的性质及应用602-609

摘要：形成有效的联盟是多Agent系统的一个重大课题.然而联盟结构的数目很大,对于包含n个Agent系统来说,其可能构成的联盟结构是O（nn）,以至于通过穷举搜索最优联盟结构是不可能的.另外联盟结构空间是一个什么样的形态,这是目前为止很少有人系统研究的课题,尤其是其图性质的研究.从图的视点讨论多Agent系统中的最优联盟结构生成问题.首先将联盟结构空间抽象为一个联盟结构图,其中顶点代表联盟结构,有向边代表联盟结构的分解.随后总结和形式化该联盟结构图所具有的两个性质：最优子结构、重复子结构问题;推广了一个性质：关键搜索集;给出了一个新性质：较少冗余路径的图的连通性.为了理解联盟结构图的这些性质,将这些性质用到了有效动态规划法（effectivedynamic programming,EDP）中,分析得到其时间复杂度的下界是Ω（2.1n）,上界是O（3n）.实验分析表明,EDP算法比DP算法的搜索次数更少,在含有21个Agent的系统中,EDP比DP减少42%的搜索次数.

基于图的同义词集自动获取方法610-616

摘要：同义词集是重要的语言基础知识,基于大规模语料库的同义词集自动获取是自然语言处理领域的一项基础性研究课题.从大规模语料中自动获取有并列结构关联的词语对,据此形成图,采用Newman算法对图进行划分而自动聚类相似词语.着重研究在Newman算法的基础上,充分挖掘和利用并列结构的特性和汉语的构词特点,采用6种方法对图中边的权值加以改进从而提升效果：分割语料、去除低频边、加重双向边、加重团、加重相同后字、惩罚音节不等.同义词集自动获取的准确率从初始的23.28%提升至53.12%,准确率提高了约30个百分点.

计算机研究与发展杂志软件工程

一种基于约束的变异测试数据生成方法617-626

摘要：作为衡量测试用例集完备性的测试策略,变异测试是一种＂面向缺陷＂的单元测试技术,主要用来生成完备的测试用例集.其中面向路径测试数据生成技术通过约束系统构造和求解过程实现用例集生成,是一种高效的测试用例生成技术.但目前大部分面向路径测试用例生成技术只考虑了程序语句间的控制依赖,即通过对控制流图的分析来构建约束系统,而忽略了语句间的数据依赖对约束系统的影响.充分考虑两种依赖关系,针对域削减的测试数据生成技术进行了改进,提出了一种考虑数据依赖的域削减方法.实验表明,这种方法在变异测试数据生成的成功率和执行效率上都有较大程度的提高.

一种基于格式化标签的可扩展控制流检测方法638-646

摘要：硬件瞬态故障是运行于高辐照宇宙环境下的航天计算机面临的最主要挑战之一.其中,控制流错误是这种故障影响系统可靠性的重要体现.首先在程序控制流图的基础上,利用图着色算法对基本块进行分类,然后基于基本块的格式化标签提出一种有效的控制流检测方法ECCFS,并针对基本块内部和过程间两个控制流检测问题分别给出其扩展解决方法.检测效能分析和故障注入实验的结果都表明,除了伪分支和几个边界检测盲点之外,ECCFS能够检测出绝大部分的控制流错误.与两个有代表性的控制流检测方法相比较,ECCFS在错误检测率和性能开销等方面都具有一定的优势.

一种需求驱动的软件可信性评估及演化模型647-655

摘要：软件可信性评估模型的构建依赖于对特定应用领域中可信需求的准确提取和指标系统的合理建立.对于体系结构庞大、非功能性需求复杂的软件而言,可信需求往往随着软件运行状态的转移而不断发生变化.由于可信需求的动态演化将直接影响指标系统的稳定性,因此引起了可信软件研究领域专家的广泛关注.针对该问题,给出一种需求驱动的软件可信性评估及演化模型.首先,剖析和总结软件可信性评估过程中涉及的关键技术,如需求分析与指标提取、可信证据采集与转换、可信性评估推理等,讨论了可信性需求演化背景下的可信性评估自主求解问题.其次,为了分析可信属性间的内在联系及可信属性相对权重的变化规律,给出关联矩阵的概念,并在此基础上提出应用于软件可信性评估指标系统自主配置的自适应重构器.最后,给出软件可信性评估及演化模型的整体框架.实验结果证明了该模型的合理性和正确性.

计算机研究与发展杂志计算机网络与信息安全

一种离线TTP公平非否认协议的安全性分析方法656-665

摘要：给出了一种离线TTP公平非否认协议的分析方法,离线TTP公平非否认协议得到了广泛的研究,针对离线TTP公平非否认协议的分析并不是那么广泛.针对离线TTP公平非否认协议具有协议簇的特点,将协议实例化,实例化后可以对单个协议实例的非否认性和有效性进行分析;通过扩展Kailar逻辑,增加时间相关限定词来表述协议的执行序列,用协议执行序列来表达和分析协议的公平性和时效性.利用该方法,对两种公平非否认协议进行分析,分析的结果表明CCD不符合公平性,而ZG的时效性不能够得到满足.

计算机研究与发展杂志读者专栏

iThings 2011 The 2nd IEEE International Conference on Internet of Things665-665

有界区域流场拓扑Voronoi图可视化666-674

摘要：特征可视化能揭示流场的拓扑结构,是流场可视化的重要手段之一.传统特征可视化侧重于描述流场中各临界点间的拓扑关系,而较少重视各特征的区域范围.作为特征的重要属性,合理定义描述特征的有效影响范围,对于研究流场特征性质及其变化非常重要.为此,分析了平面流场拓扑特征,定义了流场典型特征的有效区域范围,提出了一种描述流场性质及变化的新方法——拓扑Voronoi图.该方法借鉴了传统Voronoi图区域分割的思想,针对流场矢量性特点引入了流线距离概念.然后在此基础上,与临界点方法相结合,量化给出了流场内各临界点的特征区域范围.设计了有效的拓扑Voronoi图生成算法.实验数据与合成数据测试表明：该方法能有效描述流场特征结构,对分析流场性质变化具有重要的意义.

计算机研究与发展杂志计算机网络与信息安全

Bézier曲线合并的区间逼近675-682

摘要：从区域逼近的全新角度来研究几何逼近的核心问题之一：曲线的近似合并.给出了将两条或多条平面Bézier曲线合并为一条尽量细窄的区间Bézier曲线的两种方法：一是基于求已知Bézier样条曲线的上下边界直接得到区间控制顶点的值,从而诱导出一条区间合并Bézier曲线;二是基于最小二乘法求出原多段Bézier曲线合并结果的最佳一致逼近曲线作为区间Bézier曲线的中心曲线,再取区间Bézier点为常值域或变值域来得出两种误差曲线.给出大量实例来展示上述算法的逼近效果,并进行分析与比较.结果表明,算法在实现外形信息的几何逼近及数据转换方面有明显的应用前景,并可推广于空间Bézier曲线、圆域Bézier曲线、有理Bézier曲线的合并.

计算机研究与发展杂志计算机辅助设计

AFMC：一种新的异步电路设计自动化流程683-690

摘要：随着VLSI面临的功耗及时钟问题越来越突出,异步电路及其设计方法得到了广泛关注.基于宏单元的异步电路设计流程能够采用现有的同步EDA工具和设计流程将同步电路转变成相应的异步电路.在基于宏单元的异步电路设计流程的基础上提出了一种新的异步电路设计自动化流程,并与解同步异步电路设计自动化流程进行了比较.在UMC 0.18μm工艺下采用提出的自动化流程设计实现了一款DLX异步微处理器,实验结果表明该流程能够快速地进行异步电路设计,并且在异步电路的数据通路性能优化方面具有一定的优势.相对于解同步DLX微处理器,采用基于宏单元的异步设计自动化流程实现的异步DLX微处理器能够获得6%左右的性能提高.

计算机研究与发展杂志操作系统

硬实时系统中基于软件容错模型的容错调度算法691-698

摘要：在硬实时系统中,由于任务超时完成将会导致灾难性后果,因此硬实时系统必须具有实时性和可靠性保障.软件容错模型是提高硬实时系统容错能力的一种有效方法.针对硬实时系统中容错优先级两种分配策略存在的不足,基于软件容错模型提出了一种容错优先级可提升的双重优先级分配策略.该方法通过为替代版本分配双重优先级,不仅能够提高硬实时系统的容错能力,同时还能够显著减少任务间的抢占次数.为了获得双重优先级分配的最佳策略,基于任务最坏响应时间的可调度性分析,首先提出了一种最大的双重优先级配置搜索算法（MDPCSA）.然后结合MDPCSA算法,提出了一种最优的双重优先级配置搜索算法（ODPCSA）.仿真实验表明,与两种分配策略相比,在提高系统容错能力和降低抢占开销方面更为有效.

计算机研究与发展杂志高性能计算

一种采用边界表进行可重构资源管理及硬件任务调度的算法699-708

摘要：可重构计算兼具硬件的高效性和软件的灵活性,发挥可重构计算的高性能,对可重构资源及硬件任务进行有效管理和科学调度是关键.针对一维可重构器件中硬件任务调度问题,提出一种基于边界表的可重构资源管理方法,该方法用＂边界表＂数据结构记录R-T坐标系中的区域边界及其位置关系,实现对可重构资源的管理.以此为基础,提出了R-T坐标系下的任务调度及布局算法：BT-P算法,实现硬件任务的调度和布局.算法采用加权边界重叠长度作为任务调度的估值函数,与采用边界表的资源管理方法相结合,以较小的运行时开销实现调度的优化.实验表明,与Stuffing算法相比,BT-P算法下的可重构硬件的器件利用率随负载率的变化提高5%~11%,任务拒绝率随负载率和松弛因子的变化降低9%~11%,每个任务的平均调度布局时间开销在2~4μs之间.