首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 160 毫秒
1.
基于模型诊断中的极小碰集问题是人工智能领域的一个重要课题,现实中很多实际问题都可以转化为极小碰集问题,如老师与课程问题,极小覆盖集问题等.通过对极小碰集问题特征的研究,本文结合粒子群优化求解极小碰集的算法提出了一个新的算法,来指导极小碰集的求解:引入学习机制,减少极小碰集求解中对无解空间的搜索;加入翻转策略,来加速极小碰集有解空间中的求解.实验结果表明本文提出的算法在求解极小碰集问题上的效率有明显提高.  相似文献   

2.
使用SAT求解器产生所有极小冲突部件集   总被引:4,自引:0,他引:4       下载免费PDF全文
 产生所有的极小冲突部件集为基于模型诊断中的一个重要步骤.本文将待诊断系统的行为模型及观测分别使用合取范式(CNF)形式的文件描述,从而提出将判定系统组件子集是否为冲突集的问题转化为:首先提取相关组件的CNF模型及观测,然后调用成熟的SAT求解器判定可满足性.随后,通过有效地结合CSISE-tree等方法来产生所有的极小冲突集.为进一步提高效率,给出了充分利用系统输入/输出结构信息的启发式策略.实验结果表明,使用结合SAT求解器及CSISE-tree等方法能够较快产生所有极小冲突集,并且启发式策略使得求解效率进一步提高(平均提高约21%,最高者甚至达到约48%).  相似文献   

3.
基于模型的诊断为人工智能领域中一个重要的研究分支,极小碰集即候选诊断的求解过程极大影响最终的诊断效率.本文关注当前主要的极小碰集求解算法,简要介绍了它们的基本思想,从算法描述和实例比较了它们的异同和复杂性,并设计实现了一个统一的实验平台,测试并比较了它们的实际执行效率,为实际选择合适的算法提供了重要参考依据.  相似文献   

4.
基于模型的诊断问题在人工智能领域内一直备受关注,将诊断问题转换成SAT (Satisfiable)问题成为解决基于模型诊断问题的一个重要方法.基于目前高效诊断方法LLBRS-Tree (Last-Level Based on Reverse Search-Tree)的研究,本文提出电路分块诊断方法ACDIAG (Abstract Circuit Diagnosis)方法,对电路进行分块来缩减电路规模,利用LLBRS-Tree方法对分块后抽象电路求得极小块诊断解;提出诊断解拓展方法,结合分块后电路结构特征对每个极小块诊断解进行直接扩展得到极小诊断解,避免对抽象电路还原后才能得到所有解的问题.  相似文献   

5.
肖锋  周杰 《电子学报》2013,41(4):757-762
切平面法作为求解非光滑凸优化问题的典型方法,在支持向量机问题的求解中得到了广泛的应用.但是该算法在求解过程中往往会出现不稳定的情况.针对这一不稳定性,前人提出了优化切平面法,通过在切平面法中加入线搜索环节来确保目标函数单调下降.但是优化切平面法的运算复杂度比较高,不适合训练数据量大、对训练速度要求高的应用.本文提出了一种基于活跃集的优化切平面法,在计算目标函数和进行线搜索时,只单独处理活跃集内的样本,将其它样本当作一个整体来进行处理.相对于传统的优化切平面法,本文方法只需在一部分样本上计算目标函数和进行线搜索,从而可以在不损失求解精度的前提下节省求解时间.  相似文献   

6.
邵鹏  吴志健  周炫余  邓长寿 《电子学报》2015,43(11):2137-2144
对于粒子群优化算法易陷入局部最优的缺陷,反向学习策略对其的改进取得了较好的效果.然而,反向学习策略需要结合其它策略来提高算法后期的全局搜索能力,针对此缺陷,根据光的折射原理对反向学习策略的反向过程进行改进,提出反向学习的统一算法模型及基于折射原理反向学习模型的改进粒子群算法.实验与分析表明,与其它基于反向学习的粒子群算法相比,该模型更有效地改进了所提算法的全局搜索能力,提高了种群的多样性,从而提高了算法的收敛速度以及优化精度.  相似文献   

7.
针对现有神经网络剪枝方法未全面评估滤波器的重要性以及跨层滤波器的重要性间存在一定差异的问题,提出了一种基于多源信息的全局滤波器剪枝算法,建立了特征和权重信息间的连接.首先,根据特征信息较为丰富和权重信息受数据噪音影响低的特点,分别以特征间相关性和权重熵来评估滤波器的相对和绝对重要性.然后,将每层中不同压缩比例的滤波器看作一个整体,评估其对模型的全局重要性,按照压缩需求跨层剪掉模型中最不重要的部分.最后,采用知识蒸馏的方式来恢复剪枝后模型的精度,不依赖其他数据集就能完成模型的压缩与微调.为了验证所提方法的适用性,针对DeepLabV3、DABNet和U-Net网络在三个语义分割数据集上进行了大量的实验.也针对多种深度的ResNet网络在图像分类数据集上进行了验证.实验结果表明,通过多源信息可以更精确的评估单层中滤波器的重要性,通过全局重要性来指导跨层剪枝可以使模型的关键信息损失降到最低.  相似文献   

8.
魏潇 《电子科技》2015,28(2):7-10
随机线性互补是一类特殊的互补问题。常用的求解方法是先将其转化为约束极小化模型,然后用优化算法求解该模型。文中针对随机线性互补问题的期望残差极小化模型,通过使用Barzilai-Borwein步和有效集策略,提出了求解该模型的Barzilai-Borwein算法。实验结果表明,该算法与光滑投影梯度法相比,能在更短的时间内得到相应的数值结果。  相似文献   

9.
基于统计模型的变分水平集SAR图像分割方法   总被引:7,自引:3,他引:4  
针对SAR图像感兴趣区域分割问题,提出了一种基于统计模型的变分水平集分割方法.该方法在分析SAR图像特征的基础上,利用相干斑噪声的统计模型直接定义了关于水平集函数的能量泛函,不同于一般水平集方法中关于参数化曲线的能量泛函.通过极小化能量泛函,建立了水平集函数演化的偏微分方程.对水平集演化方程的数值求解,实现了对SAR图像感兴趣区域的分割.分别采用模拟和真实SAR图像对提出的方法进行了验证,试验结果表明该方法充分利用了SAR图像的特征信息,不需要相干斑噪声预处理,能够准确实现对SAR图像感兴趣区域的分割.  相似文献   

10.
针对预警机引导信息下相控阵雷达的最优搜索问题进行了研究。从预警机引导战斗机雷达搜索的角度出发,将搜索目标进行分类,根据实际作战需求加入搜索约束条件,完善现有的雷达最优搜索模型,提出两步优化策略来解决不同搜索阶段的优化问题;采用凸优化的手段对搜索模型进行求解,提出拉格朗日结合障碍法的方法来实现搜索数据率的快速优化,解决了雷达最优搜索多约束、多目标优化实时求解的问题,具有较高的工程应用价值;最后通过仿真验证了拉格朗日结合障碍法进行优化模型求解的有效性以及最优搜索模型的合理性。  相似文献   

11.
潘理  郑红  刘显明  杨勃 《电子学报》2016,44(8):1858-1863
冲突是Petri网研究的重要主题.目前Petri网冲突研究主要集中于冲突建模和冲突消解策略,而对冲突问题本身的计算复杂性却很少关注.提出Petri网的冲突集问题,并证明冲突集问题是NP(Non-deterministic Polynomial)完全的.提出极大冲突集动态枚举算法,该算法基于当前标识的所有极大冲突集,利用Petri网实施局部性,仅计算下一标识中受局部性影响的极大冲突集,从而避免重新枚举所有极大冲突集.该算法时间复杂度为Om2n),m是当前标识的极大冲突集数目,n是变迁数.最后证明自由选择网、非对称选择网的极大冲突集枚举算法复杂度可降至On2).极大冲突集枚举算法研究将为Petri网冲突问题的算法求解提供理论参考.  相似文献   

12.
Bitmap Algorithms for Counting Active Flows on High-Speed Links   总被引:2,自引:0,他引:2  
This paper presents a family of bitmap algorithms that address the problem of counting the number of distinct header patterns (flows) seen on a high-speed link. Such counting can be used to detect DoS attacks and port scans and to solve measurement problems. Counting is especially hard when processing must be done within a packet arrival time (8 ns at OC-768 speeds) and, hence, may perform only a small number of accesses to limited, fast memory. A naive solution that maintains a hash table requires several megabytes because the number of flows can be above a million. By contrast, our new probabilistic algorithms use little memory and are fast. The reduction in memory is particularly important for applications that run multiple concurrent counting instances. For example, we replaced the port-scan detection component of the popular intrusion detection system Snort with one of our new algorithms. This reduced memory usage on a ten minute trace from 50 to 5.6 MB while maintaining a 99.77% probability of alarming on a scan within 6 s of when the large-memory algorithm would. The best known prior algorithm (probabilistic counting) takes four times more memory on port scan detection and eight times more on a measurement application. This is possible because our algorithms can be customized to take advantage of special features such as a large number of instances that have very small counts or prior knowledge of the likely range of the count.  相似文献   

13.
Multiple constant multiplications (MCM) have been a core operation in many digital signal processing applications. In this paper, an efficient generalized contention resolution algorithm (CRA) is proposed to eliminate three broad categories of reusable common subexpressions in MCM. The idea is to revert a precedential decision of suboptimal common subexpressions by a localized cost function evaluation when there is a conflict between two competitive subexpressions. The proposed derivatives of the basic CRA are versatile in that they are capable of satisfying search for both intra- and intercoefficient subexpressions, in any legitimate composition of horizontal, vertical and oblique subexpressions. As the algorithms expand the common subexpressions to higher-weight only when there is cost saving, the logic depth can be controlled by constraining the weights of the subexpressions. The variants of CRA follow an important tenet of good heuristic that significant improvement in the solution quality is attained with increased problem size but the computational time remains well bounded. Experimental results with both benchmark filters and randomly generated coefficient sets are analyzed and compared with a number of well known common subexpression elimination methods to demonstrate the effectiveness and efficiency of our proposed approach.  相似文献   

14.
Biomolecular filtering, as a computing paradigm, consists essentially of two steps: (1) the codification of candidate solutions in DNA and (2) the removal of non-valid solutions by means of biochemical procedures. The sticker model makes use of this notion, defining simple bitwise operations over large sets of DNA-coded binary strings. A sticker machine is conceived as a robotic station automatizing sticker operations and thus, can be seen as an SIMD computer with a densely populated pool of data. In this paper, the maximum clique problem is tackled by harnessing the massive threading of the CUDA SIMT architecture to replicate the parallel strand filtering. The proposed heuristic relies on the sequential-and-progressive generation of partial search spaces for subsequent parallel filtering in GPU. Computational results over DIMACS benchmark set show that our approach is competitive, compared to a preceding similar work and to state-of-the-art branch-and-bound algorithms. Moreover, our approach is scalable and produces more than one solution for some instances. As far as we know, the number of found cliques has not been previously used as a reference point for this problem.  相似文献   

15.
曹政才  林诚然  黄冉 《电子学报》2017,45(12):2949-2956
本文针对一类带等待时间约束的不相关并行机调度问题,提出了一种基于Copula函数的分布估计算法.该算法以同类订单工件数与总工件数的比值为变量,对每台机器构造了一个Copula函数,进而建立了优势种群的概率模型.基于概率模型通过采样生成子代个体编码向量组,保留了父代种群的相对位置信息.从理论上分析了所提出算法的时间复杂度,其随工件个数的增加呈对数增长.通过基于实例的数值仿真以及与已有算法的比较验证了所提算法的有效性和鲁棒性.  相似文献   

16.
基于压缩NH表的高速IP路由查找算法的研究   总被引:4,自引:2,他引:2       下载免费PDF全文
由于因特网速度不断提高、网络流量不断增加和路由表规模不断扩大,IP路由查找已经成为制约核心路由器性能的主要原因,因而受到了广泛重视.目前人们已经提出几种高速IP路由查找算法,但没有一种是理想的.本文提出一种使用压缩NH表进行IP路由查找的方法,它具有查找速率高、更新时间快、存储代价低、易于实现等特点,能满足10Gbps速率核心路由器环境的要求.  相似文献   

17.
图着色问题是在满足相邻顶点不能分配相同颜色且颜色数最少的约束条件下,将图的顶点划分为不相交的集合,且每个集合中的顶点分配相同的颜色。由于图着色问题属于NP-完全问题,求解图着色问题的算法复杂度会随顶点个数的增加呈指数级增长。当顶点个数非常大时,通用处理器求解图着色问题的性能将会显著下降。因此,该文基于现场可编程逻辑门阵列(FPGA)实现求解图着色算法的专用硬件加速器。首先依据FPGA模块化的设计思路提出并实现了基于回溯法的图着色问题求解的硬件架构;其次分析了FPGA内部消耗资源与图着色顶点数之间的关系;最后利用通用异步收发传输器协议实现了通用处理器与FPGA的通信。实验结果表明,相比于在通用处理器上利用软件实现图着色算法,基于FPGA所实现的图着色算法运行时间减少了一个数量级。除此之外,FPGA内部消耗资源数与顶点个数呈线性关系,且每次迭代时FPGA运算所消耗的时间与顶点个数无关。  相似文献   

18.
We study the problem of dividing the /spl Zopf//sup 2/ lattice into partitions so that minimal intra-partition distance between the points is maximized. We show that this problem is analogous to the problem of sphere packing. An upper bound on the achievable intra-partition distances for a given number of partitions follows naturally from this observation, since the optimal sphere packing in two dimensions is achieved by the hexagonal lattice. Specific instances of this problem, when the number of partitions is 2/sup m/, were treated in trellis-coded modulation (TCM) code design by Ungerboeck (1982) and others. It is seen that methods previously used for set partitioning in TCM code design are asymptotically suboptimal as the number of partitions increases. We propose an algorithm for solving the /spl Zopf//sup 2/ lattice partitioning problem for an arbitrary number of partitions.  相似文献   

19.
In this paper, we propose an iterative area/delay tradeoff algorithm to solve the circuit clustering problem under the capacity constraint. It first finds an initial delay-considered area-optimized clustering solution by a delay-oriented depth first-search procedure. Then, an iterative procedure consisting of several reclustering techniques is applied to gradually trade the area for the performance. We then show that this algorithm can be easily extended to solve the clustering problem subject to both capacity and pin constraints. Experimental results show that our algorithm can provide a complete set of clustering solutions from the area-optimized one to the delay-optimized one for a given circuit. Furthermore, compared to the existing delay-optimized algorithms, this algorithm achieves almost the same performance but with much less area overhead. Therefore, this algorithm is very useful for solving the timing-driven circuit clustering problem  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号