电子学报 ›› 2015, Vol. 43 ›› Issue (5): 1014-1020.DOI: 10.3969/j.issn.0372-2112.2015.05.027

• 科研通信 • 上一篇    下一篇

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

叶东毅, 陈昭炯   

  1. 福州大学数学与计算科学学院, 福建福州 350108
  • 收稿日期:2013-10-08 修回日期:2014-03-12 出版日期:2015-05-25 发布日期:2015-05-25
  • 作者简介:叶东毅 男,1964年生于福建福州.教授,博士.主要研究方向为计算智能和数据挖掘.E-mail:yiedy@fzu.edu.cn;陈昭炯 女,1964年生于福建福州.教授.研究方向为人工智能和图像处理.
  • 基金资助:

    国家自然科学基金(No.71231003)

An Efficient Combinatorial Artificial Bee Colony Algorithm for Solving Minimum Attribute Reduction Problem

YE Dong-yi, CHEN Zhao-jiong   

  1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou, Fujian 350108, China
  • Received:2013-10-08 Revised:2014-03-12 Online:2015-05-25 Published:2015-05-25

摘要:

粗糙集理论中的最小属性约简(MAR)问题是一个NP-难的非线性约束组合优化问题.本文提出一个新的求解MAR问题的组合蜂群算法,其中,引领蜂、跟随蜂和侦察蜂采用基于变异运算的搜索模式,在邻域候选蜜源的生成中引入与属性子集相关的两个度量,并且跟随蜂采用与引领蜂不同的局部搜索策略以提高搜索多样性.此外,在本文算法中,角色分工不同的蜂群以不同的方式利用迄今最好蜜源的信息进行搜索.在若干UCI数据集上的实验及其统计检验结果表明,本文算法在求解质量上优于其他的元启发式属性约简算法,因而可有效地应用于最小属性约简问题的求解.

关键词: 组合人工蜂群算法, 最小属性约简, 粗糙集, 元启发式方法, 局部搜索模式

Abstract:

Minimum attribute reduction (MAR) problem in the context of rough set theory is an NP-hard nonlinearly constrained 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 solution quality.The proposed combinatorial ABC algorithm is thus efficient and well suited for solving the MAR problem.

Key words: combinatorial artificial bee colony algorithrn, minimum attribute reduction, rough sets, meta-heuristic approach, local search schemes

中图分类号: