软件学报

作者：危前进，魏继鹏，古天龙，常亮，文益民

单位：危前进，广西可信软件重点实验室(桂林电子科技大学), 广西 桂林 54100411,魏继鹏，桂林电子科技大学 计算机与信息安全学院, 广西 桂林 541004)02,古天龙，广西可信软件重点实验室(桂林电子科技大学), 广西 桂林 54100403,常亮，广西可信软件重点实验室(桂林电子科技大学), 广西 桂林 54100404,文益民，广西可信软件重点实验室(桂林电子科技大学), 广西 桂林 54100405

关键词：蚁群优化;属性约简;粗糙集;云计算

基金：国家自然科学基金(U1811264,U1711263,61966009,61866007);广西自然科学基金(2018GXNSFDA281045);广西可信软件重点实验室研究课题(KX202024)

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

来源：2022年第7期

《软件学报》期刊编辑部

查看软件学报杂志2022年第7期