[1]马胜蓝,叶东毅.一种带禁忌搜索的粒子并行子群最小约简算法[J].智能系统学报,2011,6(02):132-140.
 MA Shenglan,YE Dongyi.A minimum reduction algorithm based on parallel particle subswarm optimization with tabu search capability[J].CAAI Transactions on Intelligent Systems,2011,6(02):132-140.
点击复制

一种带禁忌搜索的粒子并行子群最小约简算法(/HTML)
分享到:

《智能系统学报》[ISSN:1673-4785/CN:23-1538/TP]

卷:
第6卷
期数:
2011年02期
页码:
132-140
栏目:
出版日期:
2011-04-25

文章信息/Info

Title:
A minimum reduction algorithm based on parallel particle subswarm optimization with tabu search capability
文章编号:
1673-4785(2011)02-0132-09
作者:
马胜蓝叶东毅 
福州大学 数学与计算机科学学院, 福建 福州 350108
Author(s):
MA Shenglan YE Dongyi
College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China
关键词:
属性约简粗糙集禁忌搜索粒子群优化算法并行子群
Keywords:
attribute reduction rough set tabu search particle swarm optimization parallel particle subswarm
分类号:
TP18
文献标志码:
A
摘要:
为了提高基于群体智能的粗糙集最小属性约简算法的求解质量和计算效率,提出一个结合长期记忆禁忌搜索方法的粒子群并行子群优化算法.并行的各子群不仅具有禁忌约束,而且包含多样性和增强性策略.由于并行的子群共同陷入局部最优的概率小于一个粒子群陷入局部最优的概率,该算法可提高获得全局最优的可能性,并减少受初始粒子群体的影响.多个UCI数据集的实验计算表明,提出的算法相对于其他的属性约简算法具有更高的概率搜索到最小粗糙集约简.因此所提出的算法用于求解最小属性约简问题是可行和较为有效的.
Abstract:
In order to improve the solution quality and computing efficiency of rough set minimum attribute reduction algorithms based on swarm intelligence, a parallel particle subswarm optimization algorithm with longmemory Tabu search capability was proposed. In addition to the taboo restriction, some diversification and intensification schemes were employed. Since parallel subswarms have a lower probability of simultaneously getting trapped in a local optimum than a single particle swarm, the proposed algorithm enhances the probability of finding a global optimum and decreases the influence of initial particles. Experimental results on a number of UCI datasets show that the proposed algorithm has a higher probability of finding a minimum attribute reduction in rough sets compared with some existing swarm intelligence based attribute reduction algorithms. Therefore, the proposed algorithm is feasible and relatively effective for the minimum attribute reduction problem.

参考文献/References:

[1]SWINIARSKI R W, SKOWRON A. Rough set methods in feature selection and recognition[J]. Pattern Recognition Letters, 2003, 24: 833849.
[2]CHOUCHOULAS A, SHEN Q. Rough setaided keyword reduction for text categorization[J]. Applied Artificial Intelligence, 2001, 15(9): 843873.
[3]SKOWRON A, RAUSZER C. The discernibility matrices and functions in information systems[C]//Dordrech: Kluwer Academic Publishers, 1992: 311362.
[4]HU X. Knowledge discovery in databases: an attributeoriented rough set approach[D]. Regina, Saskatchewan: Canada, Computer Science Faculty of Graduate Studies, University of Regina, 1995: 1152.
[5]WROBLEWSKI, J. Finding minimal reducts using genetic algorithms[C]//Proc of the Second Annual Joint Conference on Information Sciences. Wrightsville Beach, USA, 1995: 186189.
[6]JENSEN R, SHEN Q. Finding rough set reducts with ant colony optimization[C]//Proceedings of the 2003 UK Workshop on Computational Intelligence. Bristol, UK, 2003: 1522.
[7]HEDAR A R, WANG J, FUKUSHIMA M. Tabu search for attribute reduction in rough set theory[J]. Soft Computing, 2008, 12(9): 909918.
[8]叶东毅, 廖建坤.基于二进制粒子群优化的最小属性约简算法[J].模式识别与人工智能, 2007, 20(3): 295300. YE Dongyi, LIAO Jiankun. Minimum attribute reduction algorithm based on binary particle swarm optimization[J]. Pattern Recognition and Artificial Intelligence, 2007, 20(3): 295300.
[9]叶东毅, 廖建坤.最小约简问题的一个离散免疫粒子群算法[J]. 小型微型计算机系统, 2008, 29(6): 550555. 
YE Dongyi, LIAO Jiankun. Immune discrete particle swarm optimization algorithm for minimum attribute reduction problems[J]. Journal of Chinese Computer Systems, 2008, 29(6): 550555.
 [10]王国胤.Rough集理论与知识获取[M].西安:西安交通大学出版社, 2001: 23145.
[11]张文修,梁怡,吴伟志.信息系统与知识发现[M].北京: 科学出版社, 2003: 5668.
 [12]GLOVER F. Tabu searchpart I, ORSA[J]. Journal on Computing 1989, 1(3): 190206.
[13]KENNEDY J, EBERHART R C.Particle swarm optimization[C]//Proc of the IEEE International Conference on Neural Networks.Perth, Australia, 1995: 19421948.
[14]WANG Xiangyang, YANG Jie, PENG Ningsong, et al. Finding minimal rough set reducts with particle swarm optimization[J]. Lecture Notes in Artificial Intelligence, 2005, 3641: 451460.
[15]MENDES R, KENNEDY J, NEVES J. The fully informed particle swarm:simpler, maybe better[J]. IEEE Transactions on Evolutionary Computation, 2004, 7(8): 204210.
[16]DENG Tingquan, YANG Chengdong. An improved ant colony optimization applied to attributes reduction[J]. Fuzzy Information and Engineering, 2009, 54: 16.
[17]MONTGOMERY D C, RUNGER G C.Applied statistics and probability for engineers[M]. 3rd ed. New York,USA:John Wiley & Sons Inc, 2003: 278326.

相似文献/References:

[1]尹林子,阳春华,桂卫华,等.规则分层约简算法[J].智能系统学报,2008,3(06):492.
 YIN Lin-zi,YANG Chun-hua,GUI Wei-hua,et al.Hierarchical reduction of rules[J].CAAI Transactions on Intelligent Systems,2008,3(02):492.
[2]毋 非,封化民,申晓晔.容错粗糙模型的事件检测研究[J].智能系统学报,2009,4(02):112.
 WU Fei,FENG Hua-min,SHEN Xiao-ye.Research on event detection based on the tolerance rough set model[J].CAAI Transactions on Intelligent Systems,2009,4(02):112.
[3]王国胤,张清华,胡 军.粒计算研究综述[J].智能系统学报,2007,2(06):8.
 WANG Guo-yin,ZHANG Qing-hua,HU Jun.An overview of granular computing[J].CAAI Transactions on Intelligent Systems,2007,2(02):8.
[4]裴小兵,吴 涛,陆永忠.最小化决策规则集的计算方法[J].智能系统学报,2007,2(06):65.
 PEI Xiao-bing,WU Tao,LU Yong-zhong.Calculating method for a minimal set of decision rules[J].CAAI Transactions on Intelligent Systems,2007,2(02):65.
[5]张志飞,苗夺谦.基于粗糙集的文本分类特征选择算法[J].智能系统学报,2009,4(05):453.[doi:10.3969/j.issn.1673-4785.2009.05.011]
 ZHANG Zhi-fei,MIAO Duo-qian.Feature selection for text categorization based on rough set[J].CAAI Transactions on Intelligent Systems,2009,4(02):453.[doi:10.3969/j.issn.1673-4785.2009.05.011]
[6]顾成杰,张顺颐,杜安源.结合粗糙集和禁忌搜索的网络流量特征选择[J].智能系统学报,2011,6(03):254.
 GU Chengjie,ZHANG Shunyi,DU Anyuan.Feature selection of network traffic using a rough set and tabu search[J].CAAI Transactions on Intelligent Systems,2011,6(02):254.
[7]杨成东,邓廷权.综合属性选择和删除的属性约简方法[J].智能系统学报,2013,8(02):183.[doi:10.3969/j.issn.1673-4785.201209056]
 YANG Chengdong,DENG Tingquan.An approach to attribute reduction combining attribute selection and deletion[J].CAAI Transactions on Intelligent Systems,2013,8(02):183.[doi:10.3969/j.issn.1673-4785.201209056]
[8]周丹晨.采用粒计算的属性权重确定方法[J].智能系统学报,2015,10(02):273.[doi:10.3969/j.issn.1673-4785.201312008]
 ZHOU Danchen.A method for ascertaining the weight of attributes based on granular computing[J].CAAI Transactions on Intelligent Systems,2015,10(02):273.[doi:10.3969/j.issn.1673-4785.201312008]
[9]陈坚,陈健,邵毅明,等.粗糙集的过饱和多交叉口协同优化模型研究[J].智能系统学报,2015,10(5):783.[doi:10.11992/tis.201406045]
 CHEN Jian,CHEN Jian,SHAO Yiming,et al.Collaborative optimization model for oversaturated multiple intersections based on the rough set theory[J].CAAI Transactions on Intelligent Systems,2015,10(02):783.[doi:10.11992/tis.201406045]
[10]王金英,韩晓冰,王艳平.二型直觉模糊粗糙集[J].智能系统学报,2015,10(6):943.[doi:10.11992/tis.201412013]
 WANG Jinying,HAN Xiaobing,WANG Yanping.Type-2 intuitionistic fuzzy rough sets[J].CAAI Transactions on Intelligent Systems,2015,10(02):943.[doi:10.11992/tis.201412013]
[11]伞 冶,叶玉玲.粗糙集理论及其在智能系统中的应用[J].智能系统学报,2007,2(02):40.
 SAN Ye,YE Yu-ling.Rough set theory and its application in the intelligent systems[J].CAAI Transactions on Intelligent Systems,2007,2(02):40.
[12]钱进,朱亚炎.面向成组对象集的增量式属性约简算法[J].智能系统学报,2016,11(4):496.[doi:10.11992/tis.201606005]
 QIAN Jin,ZHU Yayan.An incremental attribute reduction algorithm for group objects[J].CAAI Transactions on Intelligent Systems,2016,11(02):496.[doi:10.11992/tis.201606005]
[13]冯丹,黄洋,石云鹏,等.连续型数据的辨识矩阵属性约简方法[J].智能系统学报,2017,12(03):371.[doi:10.11992/tis.201704032]
 FENG Dan,HUANG Yang,SHI Yunpeng,et al.A discernibility matrix-based attribute reduction for continuous data[J].CAAI Transactions on Intelligent Systems,2017,12(02):371.[doi:10.11992/tis.201704032]
[14]高学义,张楠,童向荣,等.广义分布保持属性约简研究[J].智能系统学报,2017,12(03):377.[doi:10.11992/tis.201704025]
 GAO Xueyi,ZHANG Nan,TONG Xiangrong,et al.Research on attribute reduction using generalized distribution preservation[J].CAAI Transactions on Intelligent Systems,2017,12(02):377.[doi:10.11992/tis.201704025]
[15]陈曼如,张楠,童向荣,等.集值信息系统的快速正域约简[J].智能系统学报,2019,14(03):471.[doi:10.11992/tis.201804059]
 CHEN Manru,ZHANG Nan,TONG Xiangrong,et al.Quick positive region reduction in set-valued information systems[J].CAAI Transactions on Intelligent Systems,2019,14(02):471.[doi:10.11992/tis.201804059]
[16]黄琴,钱文彬,王映龙,等.代价敏感数据的多标记特征选择算法[J].智能系统学报,2019,14(05):929.[doi:10.11992/tis.201807027]
 HUANG Qin,QIAN Wenbin,WANG Yinglong,et al.Multi-label feature selection algorithm for cost-sensitive data[J].CAAI Transactions on Intelligent Systems,2019,14(02):929.[doi:10.11992/tis.201807027]
[17]唐玉凯,张楠,童向荣,等.不完备决策系统下的多特定类广义决策约简[J].智能系统学报,2019,14(06):1199.[doi:10.11992/tis.201905059]
 TANG Yukai,ZHANG Nan,TONG Xiangrong,et al.The multi-class-specific generalized decision preservation reduction in incomplete decision systems[J].CAAI Transactions on Intelligent Systems,2019,14(02):1199.[doi:10.11992/tis.201905059]

备注/Memo

备注/Memo:
收稿日期:2010-03-07.
基金项目: 国家自然科学基金资助项目(60805042);福建省自然科学基金资助项目(2010J01329).
通信作者:叶东毅.
E-mail:yiedy@fzu.edu.cn.
作者简介:
马胜蓝,男,1986年生,硕士研究生,主要研究方向为计算智能.
 叶东毅,男,1964年生,教授,博士生导师,主要研究方向为计算智能、数据挖掘.曾获得国家科技进步二等奖(主要成员1项)、福建省科学技术二等奖1项和福建省科学技术三等奖2项.出版著作和教材6部, 发表学术论文70余篇.
更新日期/Last Update: 2011-05-19