一种基于决策表约简的集覆盖问题的近似解法

南京大学学报(自然科学版) ›› 2018, Vol. 54 ›› Issue (4): 821–.

一种基于决策表约简的集覆盖问题的近似解法

陶玉枝1，2，赵仕梅1，2，谭安辉1，2*

出版日期:2018-04-30
作者简介:1.浙江海洋大学数理与信息学院，舟山，316022；2.浙江省海洋大数据挖掘与应用重点实验室，舟山，316022
基金资助:
基金项目：国家自然科学基金(61602415，61573321，41631179，61773349)，浙江省自然科学基金(LY18F030017)，浙江省大学生科技创新活动计划暨新苗人才计划(2017R411036) 收稿日期：2018－05－16 *通讯联系人，E－mail：tananhui86@163.com

A decision table reduction－based approximate method for set covering problem

Tao Yuzhi1，2，Zhao Shimei1，2，Tan Anhui1，2*

Online:2018-04-30
About author:1.School of Mathematics，Physics and Information Science，Zhejiang Ocean University，Zhoushan，316022，China； 2．Key Laboratory of Oceanographic Big Data Mining & Application of Zhejiang Province，Zhoushan，316022，China

摘要/Abstract

摘要： 集覆盖问题和决策信息表的约简问题分别是优化领域和信息处理领域重要的研究课题，但目前的研究大都针对这两个问题分别独立展开. 通过分析集覆盖问题的解结构和决策信息表的布尔约简结构，将两者联系起来探讨. 首先，给出一个集覆盖问题的布尔矩阵表示，并通过添加决策属性，对集覆盖中的集合进行分类，进一步诱导出一个以该布尔矩阵为条件属性值的决策信息表. 其次，分析了决策表和集覆盖的辨识集之间的关系，证明了集覆盖问题的一个局部最优解恰好是该决策表的一个属性约简，即，求解集覆盖问题可等价地转化为求解决策表的属性约简问题. 然后，利用决策表中的条件熵来度量集覆盖中一个集合在集族中的相对重要度，并构造了基于条件熵的集覆盖问题的近似算法. 最后，运用实例验证了该算法的有效性和可行性，并将新算法与几个传统集覆盖算法进行了对比. 实验结果表明，新算法在求得满意解上具有一定的优势．

Abstract: The set covering problem and the decision table reduction problem are important research subjects in the fields of optimization and information processing，respectively. However，from the perspective of many research achievements，scholars are mostly studying them independently and have not connected them together. In this paper，by analyzing the solution structures of the set covering problem and the decision table reduction problem from the view point of Boolean operations，we study their connections and associate them together. First，we represent a set covering problem by using a Boolean matrix. Then，by classifying the sets in the set covering problem with a decision attribute，a decision information table is further induced，where the Boolean matrix constitutes the conditional attribute values. Second，by examining the relationship between the discernibility sets of a decision table and a set covering，we point out that the sub－optimal solution of the set covering problem is a reduct of the decision table，i.e.，solving the set covering problem is equivalent to solving the attribute reduction problem of the decision table. Then，the conditional entropy of decision tables is employed to measure the relative significance of a set with respect to a collection of sets in the set covering problem，and a conditional entropy－based reduction algorithm of decision tables is introduced to solve the set covering problem. A practical example is used to outline the efficiency and effectiveness of the proposed method. In the end，the new algorithm is compared with several traditional set covering algorithms. The experimental results show that the new algorithm has certain advantages in finding satisfactory solutions.

陶玉枝1，2，赵仕梅1，2，谭安辉1，2*. 一种基于决策表约简的集覆盖问题的近似解法[J]. 南京大学学报(自然科学版), 2018, 54(4): 821–.

Tao Yuzhi1，2，Zhao Shimei1，2，Tan Anhui1，2*. A decision table reduction－based approximate method for set covering problem[J]. Journal of Nanjing University(Natural Sciences), 2018, 54(4): 821–.

参考文献

[1]　Pawlak Z. Rough sets. International Journal of Computer & Information Sciences，1982，11(5)：341－356. [2] 张文修，吴伟志，梁吉业等. 粗糙集理论与方法. 北京：科学出版社，2001，224. [3] 顾沈明，万雅虹，吴伟志等. 多粒度决策系统的局部最优粒度选择. 南京大学学报(自然科学)，2016，52(2)：280－288.(Gu S M，Wan Y H，Wu W Z，et al. Local optimal granularity selections in multi－granular decision systems. Journal of Nanjing University(Natural Sciences)，2016，52(2)：280－288.) [4] 胡　谦，米据生，李磊军. 多粒度模糊粗糙近似算子的信任结构与属性约简. 山东大学学报(理学版)，2017，52(7)：30－36.(Hu Q，Mi J S，Li L J. The fuzzy belief structure and attribute reduction based on multi－granulation fuzzy rough operators. Journal of Shandong University(Natural Science)，2017，52(7)：30－36.) [5] Skowron A，Rauszer C. The discernibility matrices and functions in information systems ∥ Sowiński R. Intelligent Decision Support. Springer Berlin Heidelberg，1992：331－362. [6] Qian Y H，Liang J Y，Pedrycz W，et al. Positive approximation：An accelerator for attribute reduction in rough set theory. Artificial Intelligence，2010，174(9－10)：597－618. [7] Liang J Y，Shi Z Z. The information entropy，rough entropy and knowledge granulation in rough set theory. International Journal of Uncertainty，Fuzziness and Knowledge－Based System，2004，12(1)：37－46. [8] Yao Y Y，Zhao Y. Discernibility matrix simplification for constructing attribute reducts. Information Sciences，2009，179(7)：867－882. [9] Fomin F V，Kratsch D. Exact exponential algorithms. Berlin：Springer，2010. [10] Beasley J E，Chu P C. A genetic algorithm for the set covering problem. European Journal of Operational Research，1996，94(2)：392－404. [11] Aickelin U. An indirect genetic algorithm for set covering problems. Journal of the Operational Research Society，2002，53(10)：1118－1126. [12] S ＇lzak D. On generalized decision functions：reducts，networks and ensembles ∥ Yao Y Y，Hu Q H，Yu H，et al. Rough Sets，Fuzzy Sets，Data Mining，and Granular Computing. Springer Berlin Heidelberg，2015：13－23. [13] 胡琳琳，宁爱兵，黄　飞等. 加权集合覆盖问题的加权分治算法. 小型微型计算机系统，2016，37(5)：987－991.(Hu L L，Ning A B，Huang F，et al. Measure and conquer algorithm for minimum weighted set covering problem. Journal of Chinese Computer Systems，2016，37(5)：987－991.) [14] Aguilera N E，Katz R D，Tolomei P B. Vertex adjacencies in the set covering polyhedron. Discrete Applied Mathematics，2017，218：40－56. [15] 谭安辉，李进金，陈锦坤等. 图支配集问题的粗糙集属性约简方法. 模式识别与人工智能，2015，28(6)：507－512.(Tan A H，Li J J，Chen J K，et al. An attribute reduction method based on rough sets for dominating sets of graph. Pattern Recognition and Artificial Intelligence，2015，28(6)：507－512.) [16] 陈彩云，李治国. 关于属性约简和集合覆盖问题的探讨. 计算机工程与应用，2004(2)：44－46，84.(Chen C Y，Li Z G. A study of reduction of attributes and set covering problem. Computer Engineering and Applications，2004(2)：44－46，84.) [17] Chen J K，Lin Y J，Li J J，et al. A rough set method for the minimum vertex cover problem of graphs. Applied Soft Computing，2016，42：360－367. [18] 王国胤，于　洪，杨大春. 基于条件信息熵的决策表约简. 计算机学报，2002，25(7)：759－766.(Wang G Y，Yu H，Yang D C. Decision table reduction based on conditional information entropy. Chinese Journal of Computers，2002，25(7)：759－766.)

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed