基于数值计算的布尔表达式约简工具

运用数论理论中素数的性质和特点,将符号计算问题转化为数值计算问题,设计了一个布尔表达式化简工具。在理论上根据素数的性质重新定义了布尔函数的合取、析取以及非运算,并提供了相应的推理规则;提出基于素数性质的布尔函数约简算法。用VC++实现了布尔表达式约简工具,并为该工具在底层构建了大数据计算模块,以确保对变量个数没有局限性。该工具既可独立使用,也可以提供DLL作为其它软件、工具、算法的一部分。在移动通信用户流失分析中应用了该工具,取得较好的效果。     

基于改进的遗传算法的多目标优化问题研究

研究多目标优化算法问题,针对传统的多目标优化算法由于计算复杂度非常高,难以获得令人满意的解等问题,在图论和遗传算法基础上,提出了一种改进的遗传算法求解多目标优化方法。首先采用二进制编码表示最小树问题,然后采用深度优先搜索算法进行图的连通性判断,给出了一种新的适应度函数,以提高算法执行速度和进化效率。最后仿真结果表明,与经典的Prim算法和Kruskal算法相比,新算法复杂度较低,并能在第一次遗传进化过程中获得一批最小生成树,适合于解决不同类型的多目标最小树问题。     

柔集理论在MAS合作机制中应用研究

文章提出了一种多智能体系统的合作模式,并给出了如何应用该合作模式的详细描述。将系统中智能体的语义属性采用实系数来定义,并将其以表格的形式采用一种新的处理不确定性问题通用的数学工具—柔集合理论来表示。由此,在一系列的建议候选合作的智能体中就可以在经过约简的柔集合表里直接计算进行选择,系统中采用自适应学习算法来体现多智能体系统运行历史记录和干预用户选择状态。     

基于粗集理论复杂系统神经网络模型构建

设计了一个基于粗集理论复杂系统神经网络模型,详细地阐述了该模型的实现算法。运用分辨矩阵特性以及粗集理论得到一些结论,提出知识约简算法,避开NP-HARD问题,实现巨量数据知识库、多维指标体系参数和多类决策指标参数知识属性有效约简,降低构建神经网络系统复杂性,为神经网络系统构建提供了一种模型和方法。实例表明该算法在保持知识库系统不失真的情况下能够有效地对复杂系统知识约简,从而降低构建神经网络模型的复杂性。     

关系数据库中面向属性的泛化和约简

文中讨论了关系数据库中的知识发现,以RS理论为数学工具,将面向属性的归纳方法与实例学习相结合,用来关系数据库中知识发现的属性泛化和约简。引入了属性泛化的算法。用信息论的观点来解释属性约简的含义,提出了用信息增益作为属性的重要度量,并给出了基于这种重要度量的属性约简算法。     

On approximation algorithms for the terminal Steiner tree problem

The terminal Steiner tree problem is a special version of the Steiner tree problem, where a Steiner minimum tree has to be found in which all terminals are leaves. We prove that no polynomial time approximation algorithm for the terminal Steiner tree problem can achieve an approximation ratio less than (1−o(1))lnn unless NP has slightly superpolynomial time algorithms. Moreover, we present a polynomial time approximation algorithm for the metric version of this problem with a performance ratio of 2ρ, where ρ denotes the best known approximation ratio for the Steiner tree problem. This improves the previously best known approximation ratio for the metric terminal Steiner tree problem of ρ+2.     

A highly asynchronous minimum spanning tree protocol

Summary In this paper, we present an efficient distributed protocol for constructing a minimum-weight spanning tree (MST). Gallager, Humblet and Spira [5] proposed a protocol for this problem with time and message complexitiesO(N logN) andO(E+NlogN) respectively. A protocol withO(N) time complexity was proposed by Awerbuch [1]. We show that the time complexity of the protocol in [5] can also be expressed asO((D+d) logN), whereD is the maximum degree of a node andd is a diameter of the MST and therefore this protocol performs better than the protocol in [1] wheneverD+d<N/logN. We give a protocol which requiresO(min(N, (D+d)logN)) time andO(E+NlogNlogN/loglogN) messages. The protocol constructs a minimum spanning tree by growing disjoint subtrees of the MST (which are referred to asfragments). Fragments having the same minimum-weight outgoing edge are combined until a single fragment which spans the entire network remains. The protocols in [5] and [1] enforce a balanced growth of fragments. We relax the requirement of balanced growth and obtain a highly asynchronous protocol. In this protocol, fast growing fragments combine more often and there-fore speed up the execution. Gurdip Singh received the B. Tech degree in Computer Science from Indian Institute of Technology, New Delhi in 1986 and the M.S. and Ph.D. degrees in Computer Science from State University of New York at Stony Brook in 1989 and 1991 respectively. Since 1991, he has been an Assistant Professor in the Department of Computing and Information Sciences at Kansas State University. His research interest include design and verification of distributed algorithms, communication networks and distributed shared memories. Arthur Bernstein received his PhD in Electrical Engineering from Columbia University. He is currently a professor in the Computer Science Department at the State University of New York at Stony Brook. His research interests center around concurrency in programming and data-base systems.This work was supported by NSF under grants CCR8701671, CCR8901966 and CCR9211621     

基于粗糙集的决策树ID3算法

针对传统ID3算法计算过程复杂以及存在信息冗余的问题,提出了一种改进算法——基于粗糙集属性约简的简化ID3算法.该算法利用粗糙集中属性约简的性质删掉了系统中多余的知识,在保证同样的分类能力下使得分类系统更简洁,同时借助了泰勒公式对熵公式进行化简,使得计算更简便,然后把改进的算法用到实例中去,并用相关数据库上的大量数据编...     

属性约简算法CARRDG的改进及其实现技术研究

属性约简算法CARRDG是近来提出的能计算大型信息系统中所有属性约简的高效算法。针对属性约简算法CARRDG在实现技术层面上的可改进之处,在原有的三种约简分辨图深度优先搜索原则（成员独占原则、友人劝阻原则、陌生人吸纳原则）的基础上,增加新的深度优先搜索原则——阻挡层阻挡原则。由于采用了恰当的数据结构和实现技术,使得增加阻挡层阻挡原则不会增加原算法的程序实现的复杂性,也几乎不会增加程序的运行时间。相反,UCI数据实验结果表明,阻挡层阻挡原则对于某些大型信息系统的约简分辨图的剪枝效率超过了成员独占原则与友人劝阻原则。     

最优约简在分类问题中的应用

在机器学习和人工智能中,粗糙集是进行属性维约简的重要理论与方法。但是,对于给定的信息系统,可能存在多个不同的约简,而不同的约简将会导致产生不同的知识。因此,选择最适合的约简成为一个关键的问题。以此为研究目标,通过在信息系统上增加额外的信息-偏序关系,利用此关系指导属性约简的过程,求出该偏序关系下的最优约简,并运用该最优约简对原信息系统进行维约简。通过对相关工作进行比较分析,详细设计并证明了求取该最优约简的算法,并将最优约简运用于分类问题,得到了良好的效果。     

决策树算法的系统实现与修剪优化

决策树是对分类问题进行深入分析的一种方法,在实际问题中,按算法生成的决策树往往复杂而庞大,令用户难以理解,这就告诉我们在重分类精确性的同时,也要加强对树修剪的研究,以一个决策树算法的程序实现为例,进一步讨论了对树进行修剪优化时可能涉及的问题,目的在于给决策树研究人员提供一个深入和清晰的简化技术视图。     

On the terminal Steiner tree problem

We investigate a practical variant of the well-known graph Steiner tree problem. In this variant, every target vertex is required to be a leaf vertex in the solution Steiner tree. We present hardness results for this variant as well as a polynomial time approximation algorithm with performance ratio ρ+2, where ρ is the best-known approximation ratio for the graph Steiner tree problem.     

A note on the terminal Steiner tree problem

In 2002, Lin and Xue [Inform. Process. Lett. 84 (2002) 103-107] introduced a variant of the graph Steiner tree problem, in which each terminal vertex is required to be a leaf in the solution Steiner tree. They presented a ρ+2 approximation algorithm, where ρ is the approximation ratio of the best known efficient algorithm for the regular graph Steiner tree problem. In this note, we derive a simplified algorithm with an improved approximation ratio of 2ρ (currently ρ≈1.550, see [SODA 2000, 2000, pp. 770-790]).     

基于蚁群算法的QoS多播路由优化策略

对QoS多播路由和约束最小Steiner多播树进行了分析,提出了基于蚁群算法搜索约束最小Steiner多播树的ACMC算法,并与DDMC算法进行了实验比较.结果表明,在同样环境和多播组规模的条件下,ACMC算法花费的网络代价小于DDMC算法,从而验证了ACMC算法的有效性和可行性.     

基于粗糙集理论的条件属性动态约简算法

粗糙集理论是一种新的处理含糊和不确定性问题的数学工具,可以有效地分析和处理不完备信息。条件属性约简是粗糙集理论算法研究的重点。在启发式条件属性约简算法的基础上提出了动态条件属性约简算法,算法以一个信息大的属性作为基础,不断添加条件属性,并对新增加的条件属性进行修正,找到约简条件属性,目的为了进行遥感数据的动态分类做基础。文中在VC＋＋6．0开发环境下实现了两种算法,用HSV和Iris数据验证了算法的有效性,并分析了算法的时间和空间复杂度。     

一种基于粗糙集属性频度约简算法的改进

为了获得有效的属性最小相对约简,在基于属性频度的启发式约简算法的基础上,提出了一种同时满足属性重要性和频度改进的启发式约简算法。该算法的基本思想是：以属性的核为基础,以频度作为选择属性的启发信息,即把属性频度最大的属性添加到核属性中,这样就把分类能力较强的属性添加到约简集合中,从而能够获得较优的约简。     

Reoptimization of Steiner trees: Changing the terminal set

Given an instance of the Steiner tree problem together with an optimal solution, we consider the scenario where this instance is modified locally by adding one of the vertices to the terminal set or removing one vertex from it. In this paper, we investigate the problem of whether the knowledge of an optimal solution to the unaltered instance can help in solving the locally modified instance. Our results are as follows: (i) We prove that these reoptimization variants of the Steiner tree problem are NP-hard, even if edge costs are restricted to values from {1,2}$\{1,2\}$. (ii) We design 1.5-approximation algorithms for both variants of local modifications. This is an improvement over the currently best known approximation algorithm for the classical Steiner tree problem which achieves an approximation ratio of 1+ln(3)/2≈1.55$1+ln\left(3\right)/2\approx 1.55$. (iii) We present a PTAS for the subproblem in which the edge costs are natural numbers {1,…,k}$\{1,\dots ,k\}$ for some constant k$k$.     

Induction of multiple fuzzy decision trees based on rough set technique

The integration of fuzzy sets and rough sets can lead to a hybrid soft-computing technique which has been applied successfully to many fields such as machine learning, pattern recognition and image processing. The key to this soft-computing technique is how to set up and make use of the fuzzy attribute reduct in fuzzy rough set theory. Given a fuzzy information system, we may find many fuzzy attribute reducts and each of them can have different contributions to decision-making. If only one of the fuzzy attribute reducts, which may be the most important one, is selected to induce decision rules, some useful information hidden in the other reducts for the decision-making will be losing unavoidably. To sufficiently make use of the information provided by every individual fuzzy attribute reduct in a fuzzy information system, this paper presents a novel induction of multiple fuzzy decision trees based on rough set technique. The induction consists of three stages. First several fuzzy attribute reducts are found by a similarity based approach, and then a fuzzy decision tree for each fuzzy attribute reduct is generated according to the fuzzy ID3 algorithm. The fuzzy integral is finally considered as a fusion tool to integrate the generated decision trees, which combines together all outputs of the multiple fuzzy decision trees and forms the final decision result. An illustration is given to show the proposed fusion scheme. A numerical experiment on real data indicates that the proposed multiple tree induction is superior to the single tree induction based on the individual reduct or on the entire feature set for learning problems with many attributes.