A Cascade Algorithm of Quantum Attribute Evolution Reduction and Classification Learning Based on Dynamic Crossover Cooperation
DING Wei-Ping1,2,3, WANG Jian-Dong1, GUAN Zhi-Jin2, SHI Quan2
1.College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016 2.School of Computer Science and Technology, Nantong University, Nantong 226019 3.Provincial Key Laboratory for Computer Information Processing Technology, Soochow University, Suzhou 215006
Abstract:Attribute reduction and rule classification learning are important contents for research and application of rough set theory. Taking advantage of quantum computing to accelerate the algorithm speed and co-searching of shuffled frog leaping algorithm, a cascade algorithm of attribute reduction and classification learning based on the dynamic quantum frog-leaping crossover cooperation is proposed. Individuals in the frog swarm are represented by multi-state gene qubits, and the dynamic adjustment strategy of quantum rotation angle is applied to accelerate its convergence. By the crossover coevolution mechanism, classification rules are extracted and reduced, and decision rule chains are introduced in the classification criterion of rough entropy thresholding. The double cascade model of attribute reduction and classification learning is constructed. Experimental simulations indicate the proposed algorithm has good performance for global optimization. Compared with other algorithms, it is more efficient on attribute reduction and rule classification learning.
丁卫平,王建东,管致锦,施佺. 基于动态交叉协同的属性量子进化约简与分类学习级联算法[J]. 模式识别与人工智能, 2011, 24(6): 733-742.
DING Wei-Ping, WANG Jian-Dong, GUAN Zhi-Jin, SHI Quan. A Cascade Algorithm of Quantum Attribute Evolution Reduction and Classification Learning Based on Dynamic Crossover Cooperation. , 2011, 24(6): 733-742.
[1] Feynman R, Shor P W. Simulating Physics with Computers. International Journal of Theoretical Physics, 1982, 21(6): 467-488 [2] Deutsch D. Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer. Proc of the Royal Society of London: Series A, 1985, 400(1818): 97-117 [3] Bernstein E, Vazirani U. Quantum Complexity Theory // Proc of the 25th Annual ACM Symposium on the Theory of Computation. San Diego, USA, 1993: 11-20 [4] Shor P W. Algorithms for Quantum Computation: Discrete Log and Factoring // Proc of the 35th Annual Symposium on Foundations of Computer Science. Santa Fe, USA, 1994: 20-22 [5] Grover L K. A Fast Quantum Mechanical Algorithm for Database Search // Proc of the 28th Annual ACM Symposium on the Theory of Computing. Philadelphia, USA, 1996: 212-219 [6] Eusuff M M, Lansey K E. Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm. Journal of Water Resources Planning and Management, 2003, 129(3): 210-225 [7] Han K H, Kim J H. Quantum-Inspired Evolutionary Algorithms with a New Termination Criterion, Gate and Two-Phase Scheme. IEEE Trans on Evolutionary Computation, 2004, 8(2): 156-169 [8] Jiao Licheng, Li Yangyang, Gong Maoguo, et al. Quantum-Inspired Immune Clonal Algorithm for Global Numerical Optimization. IEEE Trans on Systems, Man and Cybernetics, 2008, 38(5): 1234-1253 [9] Xie Guangjun, Fan Haiqiu, Cao Licheng. A Quantum Neural Computational Network Model. Journal of Fudan University: Natural Science, 2004, 43(4): 700-703 (in Chinese) (解光军,范海秋,操礼程.一种量子神经计算网络模型.复旦大学学报:自然科学版, 2004, 43(4): 700-703) [10] Yang Junan, Zhuang Zhenquan, Shi Liang. Multi-Universe Parallel Quantum Genetic Algorithm. Acta Electronica Sinica, 2004, 32(6): 923-928 (in Chinese) (杨俊安,庄振泉,史 亮.多宇宙并行量子遗传算法.电子学报, 2004, 32(6): 923-928) [11] Peters J F, Skowron A. A Rough Sets Approach to Knowledge Discovery. International Journal of Intelligent Systems, 2002, 17(2): 109-112 [12] Sun Hui , Li Wen, Liu Dayou. The Minimization of Axiom Groups of Rough Set. Chinese Journal of Computers, 2002, 25(2): 201- 209 (in Chinese) (孙 辉,李 文,刘大有.粗集公理组的极小化.计算机学报, 2002, 25(2): 201-209) [13] Hu Feng, Wang Guoyin. Quick Reduction Algorithm Based on Attribute Order. Chinese Journal of Computers, 2007, 30(8): 1429-1435 (in Chinese) (胡 峰,王国胤.属性序下的快速约简算法.计算机学报, 2007, 30(8): 1429-1435) [14] Sun Lijuan, Wang Ruchuan. Application of Combination of Quantum Computation and Genetic Algorithm to Computer Network Optimization. Journal of Electronics Information Technology, 2007, 29(4): 920-923 (in Chinese) (孙力娟,王汝传.量子计算与遗传算法的融合及其在计算机通信网优化中的应用.电子与信息学报, 2007, 29(4): 920-923) [15] Liang J J, Qin A K, Suganthan P N, et al. Comprehensive Learning Particle Swarm Optimizer for Global Optimization of Multimodal Functions. IEEE Trans on Evolutionary Computation, 2006, 10(3): 281- 295 [16] Luo Xuehui, Yang Ye, Li Xia. Modified Shuffled Frog-Leaping Algorithm to Solve Traveling Salesman Problem. Journal on Communication, 2009, 30(7): 130-135 (in Chinese) (罗雪晖,杨 烨,李 霞.改进混合蛙跳算法求解旅行商问题.通信学报, 2009, 30(7): 130-135) [17] Wang Jiayang, Xie Ying. Minimal Attribute Reduction Algorithm Based on Quantum Particle Swarm Optimization. Computer Engineering, 2009, 35(12): 148-150 (in Chinese) (王加阳,谢 颖.基于量子粒子群优化的最小属性约简算法.计算机工程, 2009, 35(12): 148-150) [18] Liao Jiankun, Ye Dongyi. Minimal Attribute Reduction Algorithm Based on Particle Swarm Optimization with Immunity. Journal of Computer Applications, 2007, 27(3): 550-552, 555(in Chinese) (廖建坤, 叶东毅.基于免疫粒子群优化的最小属性约简算法.计算机应用, 2007, 27(3): 550-552, 555) [19] Friedman N, Geiger D, Goldszmidt M. Bayesian Network Classifiers. Machine Learning, 1997, 29(2): 131-163 [20] Meretakis D, Wuthrich B. Extending Nave Bayes Classification Using Long Itemsets // Proc of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego, USA, 1999: 165-174 [21] Sun Tingkai, Chen Songcan. Class Label versus Sample Label-Based CCA. Applied Mathematics and Computation, 2007,185(1): 272- 283 [22] Webb G I, Boughton J R, Wang Zhihai. Not so Nave Bayes: Aggregating One-Dependence Estimators. Machine Learning, 2005, 58(1): 5-24 [23] Do T D, Hui S C, Fong B. Associative Classification with Artificial Immune System. IEEE Trans on Evolutionary Computation, 2009, 13(2): 217-228 [24] Liu Bo, Abbass H A, McKay B. Classification Rule Discovery with Ant Colony Optimization. IEEE Computational Intelligence Bulletin, 2004, 3(1): 31-35