粗糙集多目标并行属性约简算法

粗糙集理论(RST)中,求解最小属性约简MAR (minimal attribute reduction)是一种NP-难(non-deterministic polynomialhard)组合优化问题.蚁群优化算法ACO(antcolonyoptimization)是进化算法中的一种启发式全局优化算法,粗糙集理论与ACO相结合,是求解属性约简的一种有效、可行的方式.针对蚁群优化算法易于陷入局部最优解、收敛速度慢等问题,首先以一种改进的信息增益率作为启发信息,提出了冗余检测机制,对每个被选属性和每代最优约简集合进行冗余检测,并提出了概率提前计算机制,可避免每只蚂蚁在搜索过程中相同路径上的信息反复计算;针对大数据集的属性约简问题,考虑到蚁群优化算法具有并行能力以及粗糙集中“等价类”计算的可并行性,提出一种将ACO与云计算相结合用于求解大数据集的属性约简算法,在此基础上,进一步提出一种多目标并行求解方案.该方案可以同时计算出其余属性相对于当前属性或约简集合的重要度.实验结果表明,该算法在处理大数据的情况下能够得到最小属性约简,计算属性重要度的时间复杂度由O(n2)降至O(|n|).

Multi-objective Parallel Attribute Reduction Algorithm in Rough Set

Solving the minimal attribute reduction (MAR) in rough set theory (RST) is an NP-hard combinatorial optimization problem. Ant colony optimization algorithm (ACO) is a globally heuristic optimization algorithm in evolutionary algorithms, so combining RST with ACO is an effective and feasible way to solve attribute reduction. The ACO algorithm often fall into local optimal solution, and the convergence speed is slow. This study first uses an improved information gain rate as heuristic information, and then deduction test is performed on each selected attribute and the optimal reduction set of each generation. And the mechanism of calculating probability in advance is proposed to avoid repeated calculation of information on the same path in the search process for each ant. But the algorithm can only handle small-scale data sets. The ACO algorithm has good parallelism and the equivalent classes in rough set theory can be calculated by cloud computing. This study proposes a parallel attribute reduction algorithm based on ACO and cloud computing to solve massive data sets and further investigate a multi-objective parallel solution scheme, which can simultaneously calculate the importance of the remaining attributes relative to the current attribute or reduction set. Experiments show that the proposed algorithm can obtain the MAR in the case of processing big data, and complexity of time on calculating the importance of attribute decreases from O(n²) to O(|n|).