最小属性约简问题的一个有效的组合人工蜂群算法

摘要

粗糙集理论中的最小属性约简（MAR ）问题是一个NP-难的非线性约束组合优化问题。本文提出一个新的求解MAR问题的组合蜂群算法，其中，引领蜂、跟随蜂和侦察蜂采用基于变异运算的搜索模式，在邻域候选蜜源的生成中引入与属性子集相关的两个度量，并且跟随蜂采用与引领蜂不同的局部搜索策略以提高搜索多样性。此外，在本文算法中，角色分工不同的蜂群以不同的方式利用迄今最好蜜源的信息进行搜索。在若干UCI数据集上的实验及其统计检验结果表明，本文算法在求解质量上优于其他的元启发式属性约简算法，因而可有效地应用于最小属性约简问题的求解。%Minimum attribute reduction (MAR) problem in the context of rough set theory is an NP-hard nonlinearly con-strained combinatorial (binary ) optimization problem .In this paper ,a new combinatorial artificial bee colony (ABC ) algorithm is presented for solving the MAR problem .Mutation operation based search schemes are introduced for employed bees ,onlooker bees and scout bees .Two different metrics related to attribute subsets are used to generate candidate neighboring food sources .Different local search strategies between an employed bee and its recruited onlooker bees allow for a more diversified neighboring search around a current food source .Moreover ,the information of the so-far best solution is exploited in various ways by employed bees , onlookers and scouts ,respectively .Performance comparisons with existing best performing meta-heuristic approaches for the MAR problem were carried out on a number of UCI data sets .In addition ,a standard statistical t-test is used for evaluation purpose .The experimental results show that our combinatorial ABC approach compares favorably with all the other approaches in terms of solu-tion quality .The proposed combinatorial ABC algorithm is thus efficient and well suited for solving the MAR problem .