软件学报杂志 北大期刊 CSCD期刊 统计源期刊

软件学报 2007年第11期杂志 文档列表

软件学报杂志算法设计与分析

流量矩阵估算的研究2669-2682

摘要：流量矩阵是许多网络规划和流量工程任务的关键输入，精确的流量矩阵至关重要，但直接监控非常具有挑战性．因此，如何根据对有限链路的测量数据和路由信息等先验信息，通过合理建模来推断流量矩阵，成为重要的研究课题．首先给出了流量矩阵的基本概念和估算原理；然后对近年来提出的20多种不同的解决流量矩阵估算问题的方法进行分类剖析，总结了目前流量矩阵估算方法的最新研究进展，并讨论了部分方法的性能和估算误差；最后讨论了未来流量矩阵估算的研究趋势和应用前景．

PRAM和LARPBS模型上有向序列翻转距离并行算法2683-2690

摘要：分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法．基于Hannenhalli和Pevzner理论，分3个主要部分设计并行算法：构建断点图、计算断点图中圈数、计算断点图中障碍的数目．在CREW-PRAM模型上，算法使用O（n^2）处理器，时间复杂度为O（log^2n）；在基于流水光总线的可重构线性阵列系统（linear array with are configurable pipelined bus system，LARPBS）模型上，算法使用O（n^3）处理器，计算时间复杂度为O（logn）．

软件学报杂志模式识别与人工智能

覆盖算法的概率模型2691-2699

摘要：要从本质上提高覆盖算法的精度，必须在算法中引入全局的优化计算．为此，先将覆盖算法扩展成核覆盖算法（以高斯函数为核函数），再利用高斯函数的概率意义（高斯分布），为核覆盖算法建立一个有限混合概率模型，在此基础上，利用“最大似然原理”引入全局优化计算，并利用EM（expectation maximization）方法进行求解，完成对覆盖算法的全局优化计算，从而扩大覆盖方法的使用范围并提高算法的精度，且将它从确定的模型扩展成概率的模型，后者更具抗噪声干扰的能力．最后给出模拟实验，实验比较结果表明，经优化后的概率模型确实提高了算法的精度．

免疫克隆算法求解动态多目标优化问题2700-2711

摘要：求解动态多目标优化（dynamic multi—objective optimization，简称DMO）问题的主要困难在于目标函数、约束条件或者相关的问题参数是随时间不断变化的．基于免疫克隆选择学说，提出一种用于解决DMO问题的新算法——动态多目标免疫克隆优化（immune clonal algorithm for DMO，简称ICADMO）．该算法改进了现有的克隆策略，采用整体克隆的方式；在选择策略上l艮据Pareto-占优的概念，将抗体群中的个体分为支配个体和非支配个体，对非支配个体进行选择．采用3个特色算子，使其很好地保持了所得解的多样性、均匀性和收敛性．通过数值实验，与DBM（direction—based method）算法进行比较，结果表明，新算法在收敛性、多样性以及解分布的广度方面都体现了很好的性能.

基于支持度理论的广义Modus Ponens问题的最优解2712-2718

摘要：为了将模糊推理纳入逻辑的框架并从语构和语义两个方面为模糊推理奠定严格的逻辑基础，通过将模糊推理形式化的方法移植到经典命题逻辑系统中，把FMP（fuzzy modus ponens）问题转化为GMP（generalized modus ponens）问题，并基于公式的真度概念提出了公式之间的支持度，进一步利用支持度的思想引入了GMP问题以及CGMP（collective generalized modus ponens）问题的一种新型最优求解机制．证明了最优解的存在性，同时指出，在经典命题逻辑系统中存在着与模糊逻辑完全相似的推理机制．该方法是一种程度化的方法，这就使得求解过程从算法上实现成为可能，并对知识的程度化推理有所启示．

基于向量集约简的精简支持向量机2719-2727

摘要：目前的支持向量集约简法在寻找约简向量的过程中需要求解一个无约束的多参数优化问题，这样，像其他非线性优化问题一样，求解过程需要面对数值不稳定或局部最小值问题．为此，提出了一种基于核聚类的SVM（support vector machine）简化方法．此方法首先在特征空间中对支持向量进行聚类，然后寻找特征空间中的聚类中心在输入空间中的原像以形成约简向量集．该方法概念简单，在简化过程中只需求解线性代数问题，从而解决了现存方法存在的瓶颈问题．实验结果表明，该简化法能够在基本保持SVM泛化性能的情况下极大地约简支持向量，从而提高SVM的分类速度．

一种基于多类型偏好的偏好逻辑2728-2739

摘要：针对目前缺乏多类型偏好共存的偏好逻辑系统的现状，提出并构造了一个能够描述和推理多种类型偏好的逻辑系统MPL（logic of many kinds of preference）．在进一步提出MPL语言LMPL基于最粗糙／最细致描述原则的非单调语义基础上，通过分级知识库这种常用偏好表示方法的LMPL重写，初步考察了LMPL表示能力，最后进行总结并提出需要进一步研究解决的问题．

自适应扩散混合变异机制微粒群算法2740-2751

摘要：为了避免微粒群算法（particle swarm optimization，简称PSO）在全局优化中陷入局部极值，分析了标准PSO算法早熟收敛的原因，提出了自适应扩散混合变异机制微粒群算法（InformPSO）、结合生物群体信息扩散的习性，设计了一个考虑微粒分布和迭代次数的函数，自适应调整微粒的“社会认知”能力，提高种群的多样性；模拟了基因自组织和混沌进化规律，引入克隆选择使群体最佳微粒gBest实现遗传微变、局部增值，具有变异确定性；利用Logistic序列指导gBest随机漂移，进一步增强逃离局部极值能力、基于种群的随机状态转移过程，证明了新算法具有全局收敛性．一与其他几种PSO变种相比，复杂基准函数仿真优化结果表明，新算法收敛速度快，求解精度高，稳定性好，能够有效抑制早熟收敛.

中国科学院软件研究所筹建国内首家软件博物馆2751-2751

软件学报杂志数据库技术

挖掘多关系关联规则2752-2765

摘要：关联规则的挖掘是数据挖掘中的一项重要和基础的技术，已进行了多方面的深入研究，有着广泛的应用．传统数据挖掘算法是针对单表数据进行处理的，在应用于多关系数据挖掘时存在诸多问题．对多关系关联规则的挖掘问题进行了重新定义和总结．提出了多关系关联规则挖掘的一个框架，并对已有算法进行了分类．然后对各类代表性算法进行了描述、分析和对比，对尚存在的问题进行了分析和总结．最后，对该领域未来的研究工作提出了建议．

DNA序列数据挖掘技术2766-2781

摘要：DNA序列数据是一类重要的生物数据．研究DNA序列数据解读其含义是后基因组时代的主要研究任务．数据挖掘是目前最有效的数据分析手段之一，用于发现大量数据所隐含的各种规律，也是生物信息学采用的主要数据分析技术．将数据挖掘技术用于DNA序列数据分析，已得到了广泛关注和快速发展，并取得了许多研究成果．综述了DNA序列数据挖掘领域的研究状况和进展，提出了3个研究阶段：基于统计的挖掘方法应用阶段、一般化挖掘方法应用阶段和专门的DNA序列数据挖掘方法设计阶段．阐述了DNA序列数据挖掘的基础是序列相似性，评述了DNA序列数据挖掘领域所采用的关键技术，包括DNA序列模式、关联、聚类、分类和异常挖掘等，分析讨论了其相应的生物应用背景和意义．最后给出DNA序列数据挖掘进一步研究的热点问题，包括DNA序列数据新的存储和索引机制的设计、根据生物领域知识的数据挖掘新模型和算法的设计等．

数据库中的知识隐藏2782-2799

摘要：伴随着数据共享、隐私保护、知识发现等多重需求而产生的PPDM（privacy preserving data mining）．成为数据挖掘和信息安全领域近几年来的研究热点．PPDM中主要考虑两个层面的问题：一是敏感数据的隐藏与保护：二是数据中蕴涵的敏感知识的隐藏与保护（howledge hiding in database，简称KHD）．对目前的KHD技术进行分类和综述．首先介绍KHD产生的背景，然后着重讨论敏感关联规则隐藏技术和分类规则隐藏技术，接着探讨KHD方法的评估指标，最后归结出KHD后续研究的3个方向：数据修改技巧中基于目标距离的优化测度函数设计、数据重构技巧中的反向频繁项集挖掘以及基于数据抽样技巧的通用知识隐藏方法设计．

软件学报杂志计算机网络与信息安全

缓冲交叉开关交换结构性能分析2800-2809

摘要：分析了一种缓冲交叉开关交换结构在突发流量到达下的性能．通过建立分析模型，给出了每个输入端口拥有单个或多个输入队列的缓冲交叉开关结构的饱和吞吐．结果显示，对于单输入队列结构而言，随着突发平均长度的增加，饱和吞吐迅速从1下降，并收敛于0．5髓着每个输入端口输入队列数目的增加，饱和吞吐率逐渐接近1．仿真实验验证了分析模型的准确性．该结果可以用于指导基于缓冲交叉开关的路由交换设备的优化设计．

Web集群中基于控制论的分布式QoS量化控制2810-2818

摘要：基于控制理论提出一种分布式Web集群QoS量化控制机制，具有分布控制，灵活、有效的系统化设计，高可扩展，高可用及易于部署等特点．系统的实现及实验验证了该方案的可行性和有效性．

无结构P2P覆盖网络的拓扑优化2819-2829

摘要：研究了全分布无结构P2P（peer-to-peer）网络拓扑的最优化问题．通常认为，无结构P2P网络拓扑属于Power-Law结构．然而，Power-Law并非对所有应用都是最好的选择．首先研究了无结构P2P覆盖网络结构对无结构P2P搜索的影响，给出了结点度分布、访问频率模式和搜索成功率之间的关系．然后基于数据访问频率分布，给出了结点度的优化分布模型．实验结果表明，该无结构P2P拓扑优化结构在提高搜索成功率方面是有效的．该工作对构造合理的覆盖网络拓扑具有重要意义．同时将加深对无结构P2P环境下数据部署问题的认识．

一种基于路由器矢量边采样的IP追踪技术2830-2840

摘要：提出了一种新型的边采样方法“路由器矢量边采样”（RVES），使得概率包标记（probability packet marking，简称PPM）设备容易实现和部署．在图论模型上，RVES以网络接口替代路由器作为顶点，以路由器“矢量边”替代传统采样边．该方法实施简单，标记概率的策略配置灵活，可以有效解决分布式拒绝服务（router’s vector-edge-sampling，简称DDoS）攻击的重构问题．基于传统边采样的PPM相关技术依然适用于RVES方法．原理样机已经研制出并部署在Internet上．实验结果验证了该方法的有效性和可行性．

一种基于控制流的程序行为扩展模型2841-2850

摘要：提出一种基于控制流的程序行为扩展模型EMPDA（extended model based on push down automaton）．对控制流模型加入不变性约束扩展，该模型能够表达程序正常运行时所应保持的不变性质约束，增强了模型的监控能力；通过以实际应用区分系统调用重要性，将模型划分为核心模型和辅助模型，以降低模型整体消耗，提高模型学习效率．实验结果表明，该扩展模型较之原模型有更好的覆盖速度、误报率以及检测能力.

一种支持多维资源描述的高效P2P路由算法2851-2862

摘要：在分析现有P2P（peer to peer）路由算法的基础上，提出了一种基于二阶矩定位、支持多维资源数据描述的高效资源路由算法——FAN（flabellate addressable network）路由算法．FAN算法将节点映射到统一的多维笛卡尔空间，并以节点相对空间原点的二阶矩作为子空间管理和资源搜索的依据．FAN路由算法具有O（10g（N／k））的高路由效率．在节点加入和退出FAN网络时，更新路由信息的代价为O（klog（N／k））．实验结果表明，FAN路由算法具有路由效率高、维护代价小的优点，是一种P2P环境中支持多维资源数据描述的高效结构化资源路由算法．而且，目前部分基于CAN（content—addressable network）网络的改进算法也可以在FAN网络中适用，并获得更好的路由效率和更低的维护代价．