一个解决集合覆盖问题的二阶段遗传算法

针对集合覆盖问题,提出一个高效的可解决大规模数据的二阶段遗传算法.二阶段遗传算法可以分为数据约简阶段和启发式求解阶段,论文形式化地描述了数据约简阶段的相关定义、定理和算法,证明了该约简方法的有效性;并给出了启发式求解阶段中针对集合覆盖问题的遗传算法中选择、交叉、变异算子的设计方法.对Beasley提出的45个测试用例的测试结果验证了二阶段遗传算法的求解效率和求解质量高于其它遗传算法.     

一种求解集合覆盖问题的启发式算法

集合覆盖问题是运筹学研究中的一个基本的组合优化问题,它通常描述成如下的一个覆盖问题:从一个m行、n列的0-1矩阵(aij)m×n中选出若干列盖住所有的行,使得付出的代价最小.集合覆盖问题被广泛应用到航空人员行程安排、电路设计、运输的车辆路线安排等领域.对这一问题,国内外学者提出了诸如遗传算法、模拟退火算法、蚁群算法、人工神经网络算法等求解算法.本文以贪心算法为基础,利用人类的智慧和经验,提出了一种求解集合覆盖问题的启发式算法.算法的主要思想为:从某个解出发,随机移除一定比例的列,再用贪心策略加入若干列.用本文提出的算法,对Beasley提出的45个测试实例进行了实算测试,所得结果和最优解的平均相对差值为0.44%,并且得到了其中33个实例的最优解,实算结果表明,本文提出的算法对求解集合覆盖问题是行之有效的.     

基于集合覆盖的不完备信息系统属性约简方法

深入分析了不完备信息系统的特点以及相似关系的定义,通过构造不完备信息系统的相关矩阵,把不完备信息系统的最小属性约简问题与最小集合覆盖问题联系起来,将不完备信息系统的最小属性约简问题转化为最小集合覆盖问题,给出了基于集合覆盖的不完备信息系统最小属性约简算法。实例分析证明该算法可行,高效。     

测试集问题的集合覆盖贪心算法的深入近似

测试集问题是一个有着广泛应用的NP难问题.集合覆盖贪心算法是测试集问题的一个常用近似算法,其由集合覆盖问题得到的近似比21nn+1能否改进是一个公开的问题.集合覆盖贪心算法的推广被用来求解生物信息学中出现的冗余测试集问题.通过分析条目对被区分次数的分布情况,用去随机方法证明了集合覆盖贪心算法对测试集问题的近似比可以为1.51nn+0.5lnlnn+2,从而缩小了这种算法近似比分析的间隙.另外,给出了集合覆盖贪心算法对冗余度为n-1的加权冗余测试集问题的近似比的紧密下界(2-o(1))lnn-Θ 1).     

集合多覆盖问题的乘性权重更新分析

集合多覆盖问题的简单贪心算法的近似比是lnn＋1。本文提出简单贪心算法的一个变形,宽度优先贪心算法,并且证明其有近似比（lnn）／r＋lnlnn＋O（1）,其中r是覆盖要求。这个结果比由随机取整方法得到的近似比O（（lnn）/r＋√（lnn）＋1为优。宽度优先贪心算法的设计可以归入Arora等最近提出的乘性权重更新方法的框架。关键词集合多覆盖,宽度优先贪心算法,乘性权重更新方法     

关于属性约简和集合覆盖问题的探讨

论文探讨了粗糙集的属性约简和集合覆盖问题之间的联系。通过构造信息系统的相关矩阵将粗糙集的属性约简问题与集合覆盖问题联系起来,从而将粗糙集的属性约简问题简化为集合覆盖问题。然后用几个定理及其证明说明了这种联系是存在的。基于这种联系,推断出求最小属性约简问题算法的近似度的上下界为ln(｜U'｜)-lnln(｜U'｜)+O(1)和(1-o(1))ln(｜U'｜)。最后,利用两个范例分别演示了如何具体地构造相关矩阵以及如何将解决集合覆盖问题的思想和方法应用到解决属性约简问题中来,由此推理如果将文献5中的解决集合覆盖问题的启发式方法应用到解决最小属性约简中,属性约简的复杂度为o(r2m3+m2),并且能以78%的“概率”得到最小属性约简。     

基于最小集合覆盖的属性约简算法

在粗糙集理论的各种应用中,属性约简算法具有重要的意义,因而对属性约简算法的研究一直是粗糙集理论研究中的重点问题之一。在对属性约简算法充分研究的基础上提出一种基于最小覆盖集的粗糙集属性约简算法,即通过构造知识系统的一种改进的相关矩阵将属性约简简化为最小覆盖问题。将该算法与文献[7]中的算法进行实验比较并对结果进行分析,实验结果表明,当随着数据量增大时该算法具有更小的时间复杂度。     

基于蚁群算法的集合覆盖问题

蚁群算法是一种基于群体智能原理的优化模型,用于解决组合优化问题。集合覆盖问题是NP完全问题中应用面最广的问题之一,它在模式识别、机器学习等领域中具有重要的应用。以SCHF[1]启发函数作为启发信息,用蚁群算法求得集合覆盖问题的优化解。通过几种算法的仿真结果对照表明,用蚁群算法求解集合覆盖问题是有效的,蚁群算法得到的解是比较理想的。     

基于绝对信息量的覆盖增量约简算法

在保持覆盖上下近似算子不变的情况下,探讨覆盖约简算法。通过定义绝对信息量和信息量,引入相邻矩阵等概念,提出基于绝对信息量的覆盖增量约简算法。实例表明,该方法是一种能够去除覆盖中绝对冗余知识的有效方法。     

基因学习算法及其在集合覆盖问题中的应用

在用传统方法解决一些复杂而规模较大的组合优化问题,尤其是NP难题,出现困难时,一些近似算法相继推出。启发式搜索法、模拟退火算法及进化算法等的出现,为解决这些优化问题提供了非常好的手段。近年来,出现了一种概率学习的进化计算模型,如Baluja的PBIL算法与Corno的自私基因算法。概率学习的进化计算模型通过不断地学习每一代的最优个体,最终收敛于最优或较优的解的等位基因概率,其过程描述如下:     

基于覆盖算法的条件信息熵表示及属性约简

利用覆盖算法对数据进行处理,得到论域U的一个划分,定义一种基于覆盖的条件信息熵,由新的条件信息熵定义新的属性重要性,并证明了对于一致决策表,它与代数定义下的重要性是等价的。以新的属性重要性为启发信息设计约简算法,并给出计算新的条件信息熵的算法。实验结果表明该约简算法能快速搜索到最优或次优约简。     

基于粗糙集和遗传约简算法的入侵检测方法

采用改进的贪心算法和遗传算法结合的混合遗传算法进行属性约简,并利用值约简后生成的入侵检测规则,提出一种基于粗糙集理论和遗传约简算法的入侵检测方法。基于KDDCUP99数据集的实验表明该方法取得了良好的入侵检测效果,并且改进的混合遗传算法生成约简的速度更快。     

Rule learning for classification based on neighborhood covering reduction

Rough set theory has been extensively discussed in the domain of machine learning and data mining. Pawlak’s rough set theory offers a formal theoretical framework for attribute reduction and rule learning from nominal data. However, this model is not applicable to numerical data, which widely exist in real-world applications. In this work, we extend this framework to numerical feature spaces by replacing partition of universe with neighborhood covering and derive a neighborhood covering reduction based approach to extracting rules from numerical data. We first analyze the definition of covering reduction and point out its advantages and disadvantages. Then we introduce the definition of relative covering reduction and develop an algorithm to compute it. Given a feature space, we compute the neighborhood of each sample and form a neighborhood covering of the universe, and then employ the algorithm of relative covering reduction to the neighborhood covering, thus derive a minimal covering rule set. Some numerical experiments are presented to show the effectiveness of the proposed technique.     

MSC问题的一类表面DNA解法

利用基于表面的DNA粘贴模型求解最小集合覆盖问题。改进体现在计算模版表面穷举了所有可能的结果,同一时间验证结果是否满足条件,真正实现了DNA的强大并行性。同时在互补的寡聚核苷酸片段发生退火反应时,利用特殊的化学反应,通过催化剂来决定是否杂交,减少了人工参与,提高了计算效率。通过计算机仿真模拟验证了模型的可行性。     

Using an interval graph approach to efficiently solve the housing benefit data retrieval problem

Rappos and Thompson use a set covering formulation and a commercial software package to solve the problem of trying to minimize the number of data sets that have to be read in retrieving all new housing benefit (HB) data entries for a fixed period of time. In this paper, we show that determining the minimum number of data sets that have to be read in retrieving all new HB data entries for a fixed period of time can be solved by finding a minimum size clique cover for an interval graph. Since it is well‐known that a greedy algorithm finds a guaranteed minimum size clique cover for an interval graph, this approach will be more efficient than a set covering approach. Finally, it is obvious that this interval graph formulation and greedy algorithm solution approach is applicable to other data retrieval problems.     

基于面上DNA计算求解最小集合覆盖问题*

利用DNA分子结构推得DNA计算机理及实现方式,提出用面上DNA计算模型求解最小集合覆盖问题,给出了具体应用和算法评价;在计算模板表面穷举了所有可能的结果,同一时间验证结果是否满足条件,实现DNA计算的强大并行性;同时在互补的寡聚核苷酸片段发生退火反应时,通过催化剂来决定是否杂交,减少人工参与、提高计算效率。最后,通过计算机仿真模拟验证了本模型的可行性。     

粗糙集属性约简方法及其在医疗中的应用研究

针对基于可辨识矩阵核求取属性约简存在的空间与时间都不理想的问题,提出一种新的基于粗糙集的属性约简启发式算法。该方法不直接构造及存储可辨识矩阵,而且在核不存在的情况下,也能取得较好的起点核心集,将获取矩阵元素及得到核心元素同步进行,并加入了对属性集频率的综合考虑。同时,将此方法应用于医疗诊断决策,并对属性约简前后的决策性能进行了分析。实验结果表明,利用约简后的属性集,计算复杂性降低,同时保持高的决策准确率,算法是有效的。     

基于变精度覆盖粗糙集的入侵检测方法

精准且快速地识别异常用户行为是入侵检测系统（IDS）的重要任务。针对入侵检测数据维度高、样本量大的问题，提出了基于变精度覆盖粗糙集的相关族属性约简方法，并将其运用至入侵检测数据中。首先，基于覆盖决策表生成条件属性的变精度相关族；然后，在所有条件属性变精度相关族的基础上利用启发式算法求得决策表的属性约简；最后，在上述的基础上结合分类器对入侵检测数据进行检测。实验结果表明，所提方法具有计算属性约简时间短的优点，在大样本数据集上，基于模糊粗糙集依赖度的属性约简算法NFRS运行所需时长为该算法的96倍。在入侵检测数据集NSL-KDD上，该方法可快速识别关键属性，剔除无效信息，其整体准确率可达到90.53%，且对Normal的识别准确率可达到97%。     

Homomorphisms-based attribute reduction of dynamic fuzzy covering information systems

Information system homomorphisms have made a substantial contribution to attribute reduction of covering information systems. However, the efforts made on homomorphisms are far from sufficient. This paper further studies homomorphisms for attribute reduction of dynamic fuzzy covering information systems. First, the concepts of neighbourhood and induced fuzzy covering are proposed and their properties are discussed in detail. Then, we introduce the concepts of consistent functions and fuzzy covering mappings providing a basic theoretical foundation for compressing fuzzy covering information systems. Afterwards, the notion of homomorphisms is presented to reveal the relationship between fuzzy covering information systems. We show how large-scale fuzzy covering information systems and dynamic fuzzy covering information systems can be compressed into smaller ones by means of homomorphisms. Finally, illustrative examples are employed to show that attribute reduction can be simplified significantly by our proposed approach.