SENSITIVITY ANALYSIS OF THE KNAPSACK PROBLEM： TIGHTER LOWER AND UPPER BOUND LIMITS

In this paper, we study the sensitivity of the optimum of the knapsack problem to the perturbation of the profit of a subset of items. We propose a polynomial heuristic in order to establish both lower and upper bound limits of the sensitivity interval. The aim is to stabilize any given optimal solution obtained by applying any exact algorithm. We then evaluate the effectiveness of the proposed solution procedure on an example and a set of randomly generated problem instances.     

基于软件历史仓库和抽象语法树的相似缺陷识别方法

软件开发过程中,软件开发人员常常通过搜索软件历史仓库(historical software repository, HSR),再经复制/粘贴以实现软件复用。HSR中会保存被复用的代码的缺陷及修复信息,辅助处理相似缺陷。基于此,提出一种基于HSR挖掘的相似缺陷识别方法。首先,基于变更日志的分析,从HSR中提取出已知缺陷的模块,建立bug模块库。然后,采用基于抽象语法树(abstract syntax tree, AST)的相似代码检测方法,识别待测试软件与bug模块库中相似的代码,并借助HSR中保存的相应缺陷及修复信息,完成待测试软件中可能包含潜在缺陷的模块的识别。同时,为提高相似代码的识别精度,优化基于AST的代码特征度量。在18个C程序、164对克隆代码上进行实验,结果表明所提方法能够识别出全部相似代码且性能优于已有工具。在人工构建的bug模块库上验证了代码相似性对相似缺陷识别的作用。最后,在8个真实的大型C项目上进行验证,平均缺陷召回率达到94%,表明挖掘HSR可以有效地为跨项目传播的相似代码提供缺陷理解支持。     

组织人才培养的超网络模型

从知识和知识管理的角度出发,提出基于定量化方法的组织人才培养超网络模型.研究根据不同类型的数据建立人员网络、物质载体网络和知识网络,再根据不同网络之间的相互映射关系建立超网络. 在超网络中,依据知识网络和人员网络之间的关系确定易流失知识和易流失领域,然后确定组织需要的知识.提出计算组织需要知识与人员知识相似度的算法,根据算法计算的相似度大者被确定为培养人选,然后依据组织需要的知识对培养人选进行培养. 最后,给出了一个实例进行验证.     

基于排队论的一个物流模型

利用排队论研究了一个物流模型. 货物到达货运站形成一复合泊松过程.每辆货车每次装载货物数量必须刚好为$N$.求得了系统稳态存在的充分必要条件,利用补充变量法求得了任意时刻货运站内的平均货物量以及货车刚到达货运站时货运站内待运的平均货物量.最后给出了一个数值实例.     

卫星应用产业效益估计的相似系统方法

为了估计缺乏统计数据的中国卫星应用产业的效益,运用相似系统方法,把美国卫星应用产业系统变换成中国卫星应用产业的相似系统,由美国卫星应用产业的数据估算得到中国卫星应用产业的效益,通过主成分分析等方法对估算结果进行验证.研究表明,相似系统方法是一种合理可行的预测模型方法,不仅能解决数据不足的问题,还可以推广应用到难以直接建立数学模型的实际预测、决策和规划问题中.     

逆向系统工程引论

基于科学、技术、工程"三元论"的理论,对系统工程的基本定位及思维方式进行了反思,提出了创建逆向系统工程(results-oriented system engineering,ROSE)的必要性和可行性.指出ROSE构建的新的存在物以系统形式存在,构建过程表现为要素集成和整体涌现.阐述了ROSE的成效性原理、精益性原理、集成性原理和实践性原理,并从系统认知和系统实践两个层面阐述了ROSE方法论的逻辑过程.最后对ROSE的应用进行了实证分析.     

系统、仿真系统及其理论

主要从基本理论、基本概念、基本方法、演变规律的角度,回顾、分析论述了系统、系统理论、原始系统、仿真系统、相似理论与系统仿真组合理论的基本内容、相互关联和发展概况,从而引出相应结论.     

无迹粒子滤波在基于色彩的视频目标跟踪中的应用

在视频目标跟踪中把视频象素点的色彩值(RGB值)作为跟踪系统的观测量,用无迹粒子滤波算法估计活动目标在每一帧视频画面中的位置.在粒子滤波的重要性采样步骤中以色彩相似度作为更新粒子权值的标准.采用一种判断是否需要进行重采样的方法.在MATLAB环境下仿真时采取调用预先编译得到的DLL文件的方式减少仿真时间.实验结果表明,取300个粒子时,能以每秒24帧的速率跟踪随机运动的视频目标.     

基于广义梯形模糊数相似度的交叉效率集结

在不确定环境下,针对模糊数据的多样性和复杂性,本文结合广义梯形模糊数相似度理论将广义梯形模糊数的交叉效率矩阵转换为交叉互评相似度矩阵,并根据模糊信息检索系统中的布尔模型,以能最大程度还原信息本身为准则,构建满足"正相容性"的有序几何平均集结函数对交叉互评相似度矩阵进行集结,从而得到关于每个决策单元的同行评价综合相似度.根据决策单元的同行评价综合相似度,建立反映决策者偏好的模糊一致性偏好矩阵,并对决策单元进行集结权重的分配,根据分配结果计算决策单元的全局交叉效率值.本文的集结方法可以解决不确定环境下,交叉效率矩阵数据多样性的问题,有较高的适用性;并且其集结结果具有较高的一致性和稳定性.最后本文以梯形模糊数的交叉效率矩阵为算例,来说明该方法的合理性和适用性.     

通信辐射源运动轨迹相似性分析

针对传统运动轨迹相似性分析利用时空信息效率不高问题,结合通信辐射源主体特点,提出基于时空和语义信息的辐射源轨迹相似性分析算法。在该算法中,对相似运动轨迹距离测度进行改进,提出基于马氏距离的轨迹时空相似度算法,将轨迹分割后计算相似度,克服了时间不匹配轨迹和不同采样间隔对轨迹相似性判断的影响;同时,结合基于高效K近邻(K-nearest neighbor, KNN)相似搜索的语义相似数据搜索算法,实现对辐射源相似轨迹的准确判断。该算法能够准确判断相似轨迹,优于现有的相似轨迹判断方法,且适应噪声环境。仿真实验结果验证了该算法的性能。