计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2008年第06期杂志 文档列表

计算机学报杂志综论

面向涌现的多Agent系统研究及其进展881-895

摘要：在多Agent系统研究领域，涌现现象越来越引起人们的注意，面向涌现的多Agent系统研究正成为多Agent系统研究中值得注意的一个新方向，它关注的是多Agent系统宏观层面的涌现性问题以及系统涌现的宏观与微观层面的联系机制，并最终希望发展出一套面向涌现的多Agent系统的设计和控制方法，该文在介绍涌现的概念和特征之后，考察了多Agent系统宏观特征的面向涌现描述方法；然后对多Agent系统涌现的微一宏观机制进行了总结，比较分析了面向涌现的多Agent系统设计方法和设计模式；最后分析讨论了该领域研究存在的问题和进一步的研究方向。

计算机学报杂志研究论文与技术报告

动态描述逻辑的Tableau判定算法896-909

摘要：动态描述逻辑在描述逻辑的基础上引入了动态维，用于描述和推理动态领域的知识，但目前缺少有效的判定算法作为支撑。文中以描述逻辑ALCO的动态扩展为例，构建出动态描述逻辑D-ALCO。以D-ALCO的构建过程为基础，将ALCO的Tableau算法、命题动态逻辑的Tableau算法以及对可能模型途径的处理有机地结合起来，给出了D-ALCO的Tableau判定算法，证明了算法的可终止性、可靠性和完备性．应用该算法，可以在采用开世界假设的情况下对D-ALCO中公式的可满足性进行判定。对于D-ALCQO、D-ALCQIO等具有更强描述能力的动态描述逻辑，可以对该算法扩展后得到相应的Tableau判定算法。

一个基于插值的解非线性双层规划的遗传算法910-918

摘要：非线性双层规划问题是一类递阶优化问题，相关的算法往往需要对每一个上层变量值求一个下层优化问题才能得到一个可行点，这使得算法的计算量很大。目前文献中的算法通常都是基于对每个确定的上层变量，下层最优解唯一的条件，这就意味着每个下层变量的分量都可以看成是上层变量的函数。基于这个思想，同时为了避免频繁计算下层优化问题，文中提出了一种新的方法。这种方法与已有方法的主要不同之处在于，它不需频繁求解下层规划，而是用插值函数近似下层最优解函数。其主要思想如下：首先，取一些上层变量值作为插值节点，计算它们对应的下层问题的最优解，这些最优解的第i个分量作为第i个插值函数的函数值，利用这些节点和函数值计算插值函数；其次，将插值函数代入上层问题，得到一个近似原问题的单层规划；最后用一个新的遗传算法求解该单层规划。由于插值节点和相应的插值函数在进化过程中自适应修正和更新，这样可使得该单层规划问题的最优解逐步逼近原问题的最优解，并且可减少计算量。对25个测试问题的仿真结果表明，该文所提出的算法能以较少的计算量找到这些问题的最好解。

一种基于预处理技术的约束满足问题求解算法919-926

摘要：相容性技术作为约束满足问题的一种有效求解技术，不论是在求解前的预处理过程中，还是在搜索过程中，都扮演着极为重要的角色。文中对预处理阶段的相容性技术进行改进和信息抽取，提出两种应用于搜索过程中的新算法Pre-AC和Pre-AC^＊，并嵌入到BT框架中，形成新的搜索算法BT＋MPAC和BT＋MPAC^＊，给出了其正确性证明，通过复杂性分析得到Pre-AC和Pre-AC”的时间复杂度分别是O（nd）和O（ed^2），明显低于目前最流行的弧相容技术的时间复杂度O（ed^3）．实验测试结果表明：对于不同类别的用例，新算法的执行效率是弧相容维护算法的2～50倍。

人类基因PolyA位点预测927-933

摘要：mRNA3’端的多聚腺苷酸化是真核细胞内mRNA转录后处理的三个最主要步骤之一。对DNA序列上发生多聚腺苷酸化的位置即PolyA位点的识别，对于理解mRNA的形成机制以及进行基因结构预测具有重要作用。本研究利用机器学习方法对PolyA位点进行预测，其实现过程分为以下三个步骤：特征的生成、特征的筛选、特征的综合分析聚类。首先，我们采取统计k阶核苷酸频率的方法来生成初始的特征；然后，通过信息学知识来对特征进行筛选；最后，使用SVM（Support Vector Machines，支持向量机）的方法进行特征的综合分析，确定参数，建立预测模型。在独立的测试数据集上进行测试，当敏感度（Sn）固定为60％时，在内含子水平和外显子水平上的特异性（sP）分别为71．67％和80．77％，在内含子水平上的预测精度明显优于国际上的同类软件。

基于模糊区域分布的分类规则提取及推理算法934-941

摘要：基于不同分类的样本在各规则对应模糊区域的隶属度分布，定义了一种规则相对匹配度，比分类匹配度更能体现样本在不同模糊区域的分布对比。设计了模糊区域分布矩阵，由该矩阵可以算得规则相对匹配度和分类匹配度，并提出了基于规则相对匹配度的分类规则提取算法，同分类匹配度算法相比，该算法充分考虑了每条规则之间的隶属度分布对比，同时以各分类样本的相对数量作为加权系数，从而兼顾了学习空间的全局密度优势和局部数量优势。通过解模糊器实现了基于规则的分类推理，其推理过程比以往算法具有更好的解释性和简洁性。最后，由Iris数据和Wine数据的分类实验证明：无论样本数量均衡与否，由规则相对匹配度提取规则都具有更好的分类效果。

应用统计方法综合评估核函数分类能力的研究942-952

摘要：应用统计方法对支持向量机方法中核函数选择问题进行了研究。文中将“纠正重复取样t测试”引入到核函数选择中，通过其与k-折交叉验证、配对t测试等多种统计方法的综合应用，对9个常用核函数的分类能力进行了定量研究。同时，文中还提出了基于信息增益的评估核函数模式识别能力的定量评估准则，证明了该准则是传统评估准则的非线性函数。数值实验表明，不同模型评估准则之间存在差异，但应用统计方法可以从这些差异中发现一些规律。同时，不同统计方法之间也存在显著差异，且这种差异对模型评估的影响要大于由于评估准则的不同而产生的影响。因此，只有应用综合的评估方法和准则才能对不同核函数的分类能力进行客观评估。

利用无私节点改善基于支付机制P2P应用的性能953-959

摘要：P2P应用中引入支付机制能够激励用户共享自己的资源来换取他人的服务，但缺点是用户获取货币能力不均衡会导致一些用户难以获得服务。文中提出加入一定的无私节点来提供基本服务保障时间来改善网络可用性的思路，并采用排队论理论对加入无私节点的网络性能进行了建模分析，得出系统请求平均等待时间、请求分配比例、服务保障时间和无私节点比例之间的函数关系，对于评估和优化系统性能有一定的指导意义。

面向Web网页的区域用户行为实证研究960-967

摘要：用户对web网页的访问是由用户需求行为确定的一个随着时间演化的复杂双模式二分网络。通过对网站聚类生成的二分网络的实证研究表明，其入度分布呈现出典型的无标度特征和集聚现象，幂指数介于1．7到1．8之间。将这种双模式二分网络映射为两种含权单模式网络：用户群体兴趣广义关联网络和网站资源广义关联网络，从而深入研究用户群体行为的关联性和从用户行为角度网站资源的关联性。实证分析其统计特性表明，两者的边权分布是幂律的，网络节点关联紧密且呈现簇聚特征。用户行为的无标度特征和集聚特点对优化Internet网络拓扑结构，改善其网络性能具有重要意义。

无线传感器网络的链路稳定成簇与功率控制算法968-978

摘要：在能量有限条件下通过降低能耗来延长网络生存时问是无线传感器网络面临的重要挑战之一。在层次体系结构中，MAC层和网络层的能耗是影响系统能量有效性的关键，因此可以将这两层结合起来考虑，从网络跨层优化的角度来分析其能耗。针对现有典型成簇算法理论前提条件多、无法适应网络动态变化、不易在实际环境中实现的不足，结合功率控制理论及算法，基于跨层优化的策略提出了一种易于实现、能动态适应网络变化、能量有效的链路稳定成簇算法。该算法能在降低能耗的同时扩大网络的吞吐量。实验仿真结果表明，与现有的几种典型方案相比，新算法在保证网络稳定性的同时使网络具有了更大的有效吞吐量及更长的生存时间。

基于SCC空性检测中状态空间的缩减方法979-988

摘要：对Couvreur提出的基于强连通图的空性检测算法进行改进，使基于嵌套的深度优先搜索与基于强连通图搜索算法的优势结合起来，在对基于迁移的扩展（具有多个可接受条件）Büchi自动机进行空性检测过程中，使用一个布尔变量标识一个状态，不仅节省了内存消耗，而且一般情况下的性能明显优于已有的算法，最坏情况等同于Couvreur的算法．同时反例寻找过程等同于基于强连通图的检测算法。

滑动窗口应用循环展开及其数据通路生成989-997

摘要：滑动窗口广泛应用于图像处理、模式识别和数字信号处理中，它具有数据量大、计算密集等特点。可重构硬件为滑动窗口应用提供了一个灵活高效的实现平台。文中基于一种存储、数据调度模型及其相应的数据通路生成技术，研究循环展开对滑动窗口应用的面积、时钟频率和吞吐率的影响。实验结果表明内层循环展开相对于外层循环展开将带来更大的控制复杂度，增加了对芯片面积的需求，然而外层循环展开需要更多的存储资源保存重用数据；当片内存储模块个数增加到一定规模时，时钟频率将随着循环展开不断降低；不同维度的应用，吞吐率随循环展开提升程度不同。

基于网格索引的连续Skyline计算方法998-1012

摘要：考虑按任意顺序随机增删的数据流场景下连续Skyline计算问题，首先基于已有工作提出了一个基本算法BCSC；然后基于“影响区域”的观察，提出了一个基于网格索引数据结构的算法GICSC，其基本思想为：（1）将数据空间划分为若干大小相等的网格，采用网格索引方法对数据点进行组织和管理；（2）用网格将数据空间表示为自由区域和影响区域两部分，发生在自由区域中的数据变化可以从理论上保证不影响计算结果，因此仅需对落于影响区域的数据增删进行运算，从而降低数据规模；（3）算法的计算模块通过逐步扩展的方法，无需遍历全部数据便可获得初始的Skyline集合及影响区域，维护模块通过类似方法计算数据变化对Skyline集合的影响，同时动态更新影响区域的大小。由于没有对数据流特性进行假设限制，因此BCSC和GICSC算法具有更广泛的适应性。理论分析和实验结果均验证了上述方法的有效性。

面向不同数据分布的多维直方图算法COCA-Hist1013-1024

摘要：基于代价的RDBMS优化器需要对含有范围查询的合取谓词的结果集基数进行准确的估计，多维直方图对多维数据分布进行模拟，避免在估计结果集基数时采用数据独立性假设，造成估计误差过大，进而导致选择非优化的查询执行计划。在不同的数据分布情况下，传统的多维直方图（如MHist-2）效果有很大不同。数据相关系数和值域密度、值域参数是准确刻画多维数据分布的有效指标，文中提出了根据不同的指标采用不同的动态优化的多维直方图算法COCA-Hist，可以大大改善传统多维直方图在平均情况下的准确性。通过分析传统的多维直方图的最坏情况，COCA-Hist的改进算法可以改进传统的多维直方图在最坏情况下的准确性。实验比较了COCA-Hist和传统的多维直方图MHist-2以及GENHist和STHoles的准确性和时间效率．实验显示无论在平均情况下还是在最坏情况下COCA-Hist的改进算法均优于传统的MHist-2直方图，并且COCA-Hist的准确性和创建时间均比GENHist有极大的改善，在准确性方面COCA-Hist较优于STHoles，而在空间预算有限时STHoles的创建时间比COCA-Hist高两个数量级。

一种新的变异测试数据自动生成方法1025-1034

摘要：变异测试是一种行之有效的软件测试方法，通过使用变异算子产生变异体系统地模拟软件中的各种缺陷，然后构造能够杀死这些变异体的测试数据集。自动生成能够杀死变异体的测试数据将提高变异测试的效率和有效性。当前的研究工作只考虑生成杀死单个变异体的测试数据。文中根据杀死同一位置的多个变异体的条件相近的特点，提出一种对杀死这些变异体的条件进行组合，然后生成同时杀死该位置多个变异体的测试数据的方法；给出相应的支持工具，并且通过实验验证方法的有效性。

SET证书申请协议在SPV下的自动化验证及改进1035-1045

摘要：基于实例化空间逻辑理论，使用知识推理方法，在SPV（Security Protocol Verifier）下对完整SET证书申请协议的秘密性、认证性等安全性质进行了完全自动化证明，并对协议进行了改进。SPV调用工业级SAT求解器，能够高效验证安全协议是否满足CAPSL（Common Authentication Protocol Specification Language）协议规范及单层、多层认知规范。应用一个逻辑或工具对协议进行验证首先必须对该协议进行简化，而SET协议作为当前最复杂的工业级协议，其原始文档有上千页，因此简化过程相当困难，相关研究较少，已有的一些简化模型也不够完整。因此，文章针对SET证书申请协议，给出了比以往更贴近原协议的简化模型，并详细阐述了该模型在SPV下的形式化描述及验证过程、验证结果，分析了由于协议不满足某些认知规范所带来的安全隐患，从而对协议进行改进，最后证明了改进后协议的有效性。该工作也充分说明了SPV足以处理复杂的工业级协议。

数字键汉字编码技术的研究和应用1046-1055

摘要：按照国家标准（GB／T18031-2000）的《通用要求》，对数字键汉字输入的键位设计和编码设计进行了理论探讨，并以数字王码为例，提出了键位、码元和取码规则的匹配策略，介绍了基础、初级、中级和高级等4套方案实例，以期作为我国数字键汉字输入技术研究应用及其实现标准化的参考。

基于双阶样条的代数双曲B样条升阶及割角算法1056-1062

摘要：考虑代数双曲B样条曲线的升阶问题，从理论上证明了曲线的升阶可以理解为控制顶点的割角过程。为了实现代数双曲B样条曲线的升阶，文中构造了一组基函数——双阶代数双曲B样条基函数，这组基函数并不具有统一的阶数，而具有“双阶”性质。代数双曲B样条基函数与双阶样条基函数之间的变换公式可以导出曲线升阶的割角算法。