Abstract Based on binary particle swarm optimization, a minimum attribute reduction algorithm for a decision table is presented. A proper fitness function is defined. Thus, the minimum attribute reduction problem is equivalently transformed into a binary combinatorial optimization problem without additional nonlinear constraints. The concept of a seed particle is introduced with its protection strategy. Finally, an improved binary particle swarm optimization algorithm is proposed to solve the transformed problem. Experimental results show the effectiveness of the presented algorithm.
[1] Pawlak Z, Slowinski R. Rough Set Approach to MultiAttribute Decision Analysis. European Journal of Operational Research, 1994, 72(3): 443459 [2] Wang Guoyin. Rough Set Theory and Knowledge Acquisition. Xi’an, China: Xi’an Jiaotong University Press, 2001 (in Chinese) (王国胤.Rough集理论与知识获取.西安:西安交通大学出版社, 2001) [3] Zhang Wenxiu, Liang Yi, Wu Weizhi. Information System and Knowledge Discovery. Beijing, China: Science Press, 2003 (in Chinese) (张文修,梁 怡,吴伟志.信息系统与知识发现.北京:科学出版社, 2003) [4] Wong S K M, Ziarko W. On Optimal Decision Rules in Decision Tables. Bulletin of Polish Academy of Science, 1985, 33(11/12): 693696 [5] Hu X H, Cercone N. Learning in Relational Databases: A Rough Set Approach. Computational Intelligence, 1995,11(2):323338 [6] Wang Jue, Wang Ren, Miao Duoqian, et al. Data Enriching Based on Rough Set Theory. Chinese Journal of Computers, 1998,21(5):393400 (in Chinese) (王 珏,王 任,苗夺谦,等.基于Rough Set 理论的“数据浓缩”.计算机学报, 1998, 21(5): 393400) [7] Miao Duoqian, Hu Guirong. A Heuristic Algorithm for Reduction of Knowledge. Journal of Computer Research and Development, 1999, 36(6): 681684 (in Chinese) (苗夺谦,胡桂荣.知识约简的一种启发式算法.计算机研究与发展, 1999, 36(6): 681684) [8] Ye Dongyi. An Improvement to Jelonek’s Attribute Reduction Algorithm. Acta Electronica Sinica, 2000, 28(12): 8182 (in Chinese) (叶东毅.Jelonek属性约简算法的一个改进. 电子学报, 2000, 28(12): 81 82) [9] Dai Jianhua, Li Yuanxiang. Heuristic Genetic Algorithm for Minimal Reduction Decision System Based on Rough Set Theory // Proc of the 1st International Conference on Machine Learning and Cybernetics. Beijing, China, 2002, Ⅱ: 833836
[10] Li Dingfang, Zhang Wen , Li Guibin, et al. Genetic Reduction Algorithm Based on Feasible Region. MiniMicro Systems, 2006, 27(2): 312315 (in Chinese) (李订芳,章 文,李贵斌,等.基于可行域的遗传约简算法.小型微型计算机系统, 2006, 27(2): 312315) [11] Kennedy J, Eberhart R C. Particle Swarm Optimization // Proc of the IEEE International Conference on Neural Networks. Perth, Australia, 1995: 19421948 [12] Parsopoulous K E, Vrahatis M N. Recent Approaches to Global Optimization Problems through Particle Swarm Optimization. Natural Computing, 2002, 1(2/3): 235306 [13] Kennedy J, Eberhart R C. A Discrete Binary Version of the Particle Swarm Algorithm // Proc of the IEEE International Conference on Systems, Man and Cybernetics. Piscataway, USA, 1997: 41044109 [14] Wu Qidi, Wang Lei. Intelligent Particle Swarm Optimization Algorithm Research and Application. Nanjing, China: Jiangsu Education Press, 2005 (in Chinese) (吴启迪,汪 镭.智能微粒群算法研究及应用.南京:江苏教育出版社, 2005) [15] Wang Kangping, Huang Lan, Zhou Chunguang, et al. Particle Swarm Optimization for Traveling Salesman Problem //Proc of the 2nd International Conference on Machine Learning and Cybernetics. Xi’an, China, 2003: 15831585 [16] Huang Yanxin, Zhou Chunguang, Zhou Shuxue, et al. A Hybrid Algorithm on Class Cover Problems. Journal of Software, 2005, 16(4): 513522 (in Chinese) (黄艳新,周春光,邹淑雪,等.一种求解类覆盖问题的混合算法.软件学报, 2005, 16(4): 513522) [17] Tasgetiren M F, Sevkli M, Liang Y C, et al. Particle Swarm Optimization Algorithm for Single Machine Total Weighted Tardiness Problem // Proc of the Congress on Evolutionary Computation. San Diego, USA, 2004, Ⅱ: 14121419 [18] Salman A, Ahmad I, Madani S A. Particle Swarm Optimization for Task Assignment Problem. Microprocessors and Microsystems, 2002, 26(8): 363371 [19] Rameshkumar K. Discrete Particle Swarm Optimization Algorithm for Permutation Flowshop Scheduling to Minimize Makespan // Wang L, Chen K, Ong Y S, eds. Lecture Notes in Computer Science. Berlin, Germany: SpringerVerlag, 2005, 3612: 572581 [20] Clerc M. Discrete Particle Swarm Optimization. Heidelberg, Germany: SpringerVerlag, 2004 [21] Zeng Jianchao, Jie Jing, Cui Zhihua. Particle Swarm Algorithms. Beijing, China: Science Press, 2004 (in Chinese) (曾建潮,介 婧,崔志华.微粒群算法.北京:科学出版社, 2004)
2007, Vol. 20 
