蚁群算法融合粗糙集理论的属性约简算法  

A Algorithm for Reduction of Attributes Based on Ant Colony Algorithm and Rough Set Theory

作　　者：何明[1] 马国亮[2] 孙立峰[2] 

机构地区：[1]北京工业大学计算机学院,北京100124 [2]清华大学计算机系,北京100084

出　　处：《北京工业大学学报》2010年第9期1292-1296,共5页Journal of Beijing University of Technology

基　　金：国家'九七三'资助项目(2006CB303103);北京市自然基金资助项目(4063037);北京工业大学博士科研启动基金资助项目(52007011200701)

摘　　要：为了克服属性约简过程中寻找最小属性集算法存在时间复杂度高搜索空间大等不足,把属性抽象为节点,通过蚁群算法搜索得到节点的最少组合,使得其能代替原有的属性节点并保持决策系统的粗糙分类能力.针对蚁群算法初期信息素匮乏,收敛速度慢的问题,将蚁群算法和粗糙集理论融合,采用粗糙集理论的相关算法确定属性核,并将其作为蚁群算法的初始节点.利用蚁群算法的搜索能力,用于最小属性集的搜索.理论分析和实验结果表明,该算法可行有效.In order to overcome the defect of high time complexity and wide search space for finding the minimal attribute set during attribute reduction. In this paper, the reduction of attributes is considered as a special optimization process by ant colony algorithm displayed good performance in solving complex problem of combinational optimization. First,an attribute is abstracted as a node and the lease combination of these nodes is found which can take place in all attribute node s but not change the degree of classified roughness. Base on these points, rough set theory and ant colony algorithm are combined according to the problem of ant colony algorithm with little information pheromone and slow convergence rate. The attribute core is determined through the correlative algorithms of rough set theory, which can be used as initial node of ant colony algorithm. Finally, the least attribute set is scanned by means of the search capacity of ant colony algorithm. Theory analysis and experimental results show that the algorithm proposed in this paper is feasible and effective.

关 键 词：蚁群算法 粗糙集 属性约简 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]