Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (1): 145-149.

• 数据库、信号与信息处理 • Previous Articles     Next Articles

Swarm intelligence based attribute reduction algorithm using game strategies

MA Shenglan, YE Dongyi   

  1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2012-01-01 Published:2012-01-01

一种基于博弈策略的群智能属性约简算法

马胜蓝,叶东毅   

  1. 福州大学 数学与计算机科学学院,福州 350108

Abstract: This paper establishes relationship between particle swarm optimization algorithms and game theory, on the basis of which a swarm intelligence based search mechanism is proposed and applied to solving the attribute reduction problem in the context of rough sets. The proposed attribute reduction algorithm can set up different participatory groups and game strategies, construct corresponding pay utility matrix, and produce optimal combinations through gaming procedure. Numerical experiments on a number of UCI datasets show the proposed game strategies based reduction algorithm is superior to particle swarm optimization, tabu search, gene algorithm and PSO with mutation operator in terms of solution quality, and has lower computational cost.

Key words: particle swarm optimization, rough set, attribute reduction, pay utility matrix, game strageties

摘要: 建立了粒子群算法与博弈论之间的联系,在此基础上,引入一种基于博弈策略的群智能搜索机制,并应用于粗糙集最小属性约简问题的求解。由此构建的属性约简算法,可以设置不同的参与团体及其博弈策略,构建相应的支付效用矩阵,并能通过博弈过程构建策略的最优组合。多个UCI数据集的实验计算表明提出的基于博弈策略的新算法求解质量优于粒子群优化算法、禁忌搜索、遗传变异和变异粒子群优化算法,并具有较小的计算开销。

关键词: 粒子群, 粗糙集, 属性约简, 支付效用矩阵, 博弈策略