基于量子蛙跳协同进化的粗糙属性快速约简

Efficient Rough Attribute Reduction Based on Quantum Frog-Leaping Co-Evolution

属性约简是粗糙集理论研究的重要内容,现已证明求决策表最小约简是一个典型NP难题.本文提出一种基于量子蛙群协同进化的粗糙属性快速约简算法.该算法构造一种动态多簇的蛙群结构,用量子态比特进行蛙群个体编码,以自适应量子旋转角调整、量子变异和量子纠缠等策略加速蛙群进化收敛,各簇蛙群以双向协同学习机制共享属性约简中相关信息.标准Benchmark优化函数测试结果表明该算法在保证收敛速度同时具有较强的平衡全局优化与局部细致搜索能力.在UCI数据集上进行属性约简比较实验,结果验证了本算法在属性约简精度和效率方面具有明显优势.

Attribute reduction is a key studying point of rough set theory.It has been proven that computing minimal reduction of decision tables is a NP-hard problem.An efficient attribute reduction algorithm based on the quantum frog-leaping co-evolution is proposed.A dynamic multi-cluster frog structure is designed,individuals are represented by multi-state qubits.The self-adaptive adjustment of quantum rotation angle,quantum mutation and quantum entanglement strategies are applied to accelerate the convergence.Cooperative searching information of different clusters during attribute reduction is shared by adopting the bidirectional co-evolutionary method.Experiments on some benchmark problems indicate the proposed algorithm has outstanding ability to balance the global exploitation and local exploration on condition of the good convergence,and results on some UCI data sets validate it is more competitive on the attribute reduction accuracy and efficiency,compared to the traditional evolutionary algorithms.