基于量子粒子群优化的属性约简

—65—基于量子粒子群优化的属性约简吕士颖，郑晓鸣，王晓东(福州大学数计学院，福州 350002)摘 要：量子粒子群优化(QPSO)算法改进了粒子进化策略，使粒子具有更大搜索空间，可更好地避免陷入局部最优。

该文将普通QPSO 算法转化为二进制QPSO 算法，提出基于QPSO 优化的属性约简算法。

实验结果表明，二进制QPSO 算法的约简结果优于Hu 算法和粒子群优化约简算法。

关键词：量子粒子群优化；粗糙集；属性约简Attribute Reduction Based on Quantum-behaved ParticleSwarm OptimizationLV Shi-ying, ZHENG Xiao-ming, WANG Xiao-dong(College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350002)【Abstract 】Quantum-behaved Particle Swarm Optimization(QPSO) algorithm makes change for the evolutionary strategy of particles, and the particles has much broader search space, which helps to avoid falling into local optimal. This paper transforms QPSO into binary QPSO, and combines QPSO with attribute reduction algorithm, presents attribute reduction based on QPSO. Experimental results show that this algorithm can achieve much better reduction result than Hu algorithm and particle swarm optimization reduction algorithm. 【Key words 】Quantum-behaved Particle Swarm Optimization(QPSO); rough set; attribute reduction计 算 机 工 程Computer Engineering 第34卷 第18期Vol.34 No.18 2008年9月September 2008·软件技术与数据库· 文章编号：1000—3428(2008)18—0065—02文献标识码：A中图分类号：TP301.61 概述属性约简是粗糙集理论的重要研究内容之一，用户通常希望找出信息系统或决策表尽量小的约简，但Wong S K M 等人已证明找出决策表的最小约简是NP 问题。

Hu 算法[1]是一种传统属性约简算法，它求出的属性约简不一定是最小属性约简。

研究者开始探索快速、有效的启发式搜索算法，提出将粒子群优化(Particle Swarm Optimization, PSO)算法与属性约简相结合的思想[2]。

传统PSO 算法存在易于陷入局部最优的固有缺陷，很多学者针对此问题进行改进，提出变异粒子群算法、自适应调整粒子群算法和免疫粒子群算法等。

上述算法可以在一定程度上避免PSO 陷入局部最优，但无法完全解决该问题。

受量子力学启发，文献[3-4]提出量子粒子群优化(Quantum-behaved Particle Swarm Optimization, QPSO)算法。

在量子系统中，粒子的进化策略发生了根本变化，与传统粒子群算法相比，它能更好地避免粒子陷入局部最优。

本文把QPSO 算法转化为二进制QPSO 算法，使之适用于粗糙集属性约简，采用UCI 数据，测试基于量子粒子群优化的属性约简算法，得到了最小约简结果。

2 粗糙集基本理论粗糙集理论是波兰数学家Z. Pawlak 于1982年提出的一种分析不完整、不确定数据的理论，其主要思想是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。

设信息系统,,,S U Q V F =<> ; {}12 ,,,n U x x x = 为有限的非空集合，也称为论域。

其中，12 {, ,,}n Q q q q = 是有限的属性集合；q q QV V ∈=∪，q V 为属性q 的一个取值；F 是U Q V ×→的映射；Q C D ∪＝，C 为条件属性集合，D 为决策属性集合；设P U ⊆，则{}()(, )|, (, )(, )IND P x y U U p P f x p f y p =∈×∀∈=。

定义1 设X U ⊆为论域的一个子集，P ⊆C ，则X 关于P 的下近似为{[]}p PX x U x X =∈⊆：其中，[]p x 表示U 中所有与x 在不可辨别关系IND (P )下等价的元素构成的集合。

定义2 设P ⊆C ，划分12{,,,}k Y Y Y 的P -近似精度为1()/()kP i i card PY card U γ==∑其中，card ()表示集合的基数。

定义3 设P ⊆C ，若p γ＝C γ，且不存在R ⊂P 使R γ＝P γ，则称P 为C 的一个(相对于决策属性D 的)属性约简。

所有C 的属性约简交集称为核，记为Core (C )。

3 量子粒子群算法简介根据粒子群的收敛性质，QPSO 算法对PSO 算法进化策略做了根本改变，粒子在搜索能力上优于大部分PSO 算法。

QPSO 算法能克服一般PSO 算法在收敛性能上的缺陷，具有如下特点：基金项目：福建省自然科学基金资助项目(A051008)作者简介：吕士颖(1983－)，男，硕士研究生，主研方向：算法及数据挖掘；郑晓鸣，硕士研究生；王晓东，教授收稿日期：2007-12-23 E-mail ：zhengxiaoming83@—66—(1)量子系统是复杂的非线性系统且符合状态重叠原理，它比线性系统具有更多状态。

(2)量子系统是非确定性系统，粒子运动没有确定的轨迹，而是以某一确定的概率出现在整个可行的搜索空间中的任意一个位置。

因此，粒子有更广泛的搜索空间，可避免陷入局部最优。

QPSO 模型中的量子即粒子，粒子状态由波函数(,)x t ψ表示，而不是采用传统的位置和速度表示。

量子运动行为与传统PSO 不同，由于无法同时确定量子的速度和位置，只知道量子出现在位置x 的概率为2|(,)|x t ψ，因此为了对不确定的量子位置进行测量，可采用蒙特卡洛方法进行模拟。

粒子进化过程如下[3-4]：11||ln(1/)if 0.5||ln(1/)if 0.5t t i i t ti i p Mbest x u k p Mbest x u k ββ++⎧=+− ⎪⎨=−− <⎪⎩x x i i i i ≥ (1) 其中，tix 是t 时刻第i 个粒子的位置；β是收缩扩张因子，用于控制算法的收敛速度，可在运行过程中动态调节；u , k 是概率为(0, 1)之间的随机数； Mbest 是群体中最优中心，定义为所有m 个局部最优粒子的中心位置，公式如下:1211111111(,,,)m m m mi i i in i i i i Mbest pbset pbest pbset pbset m m m m ======∑∑∑∑ (2)其中，m 是粒子的个数；i pbest 是第i 个局部最优粒子。

为了保证所有粒子向最优粒子靠拢，定义p 如下：1212()/()i p c pbest c gbest c c =++ (3) 其中，c 1, c 2为(0, 1)之间的随机数；gbest 是全局最优粒子。

量子粒子群算法步骤如下： step1 设置迭代次数1t =，初始化m 个粒子的初始位置，组成第1代种群12(){,,,}m X t x x x = ，第(1)i i m ≤≤个粒子的初始位置为1111T12(,,,)i i i id x x x =x 。

step2 比较每个粒子的适应度值与历史最优位置pbest i ，如果当前适应度值更优，则用当前适应度值更新pbest i 。

step3 比较每个粒子的适应度值与全局最优gbest ，如果当前群体中最好的适应度值更好，则更新gbest ，并记录最优粒子位置。

step4 按式(1)~式(3)更新粒子位置。

step5 1t t =+，如果t <T (T 为迭代次数)或未达到预定最优值，则转step2。

step6 输出全局最优粒子gbest 。

4 基于量子粒子群优化的属性约简4.1 信息系统的粒子模型在属性约简过程中，假设信息系统12{, ,, }n Q q q q = ，把属性的组合表示成一组0, 1组合的二进制串p ，也称为粒子，121[,,,,,,]k k n p a a a a a += ,[1,]k n ∈，0k a =表示属性k q 未被选择，1k a =表示属性k q 已被选择，粒子p 对应的P -近似精度为p r ，粒子p 的基数1()ni i card p p ==∑。

当p c r r =时，粒子p 为一个属性约简；当p c r r =且()card p 取得最小值时，此约简即最小属性约简。

4.2 适应度函数粒子的适应度主要取决于2个方面：(1)粒子的近似精度p r 越接近c r ，粒子适应度越大；(2)粒子中1的个数越少，粒子适应度越大。

因此，定义粒子适应度为 12()()()()pc r card C card p fitness p k k r card C −=+ (4)其中，12,k k 为参数；()card C 为所有条件属性总数。

4.3 粒子编码转换策略根据粒子群收敛特性[5]可知，QPSO 算法进化迭代最终必收敛于p ，那么当t →∞时，有11212()/()t i i p c pbest c gbest c c +≈=++x (5)由式(5)可知，p 介于pbest i 和gbest 之间，说明在QPSO 算法中，粒子通过追随局部最优、全局最优得到进化。

因为pbest i 和gbest 每个位的取值只能为0或1，所以当1p →时，11t id x +→；当0p →时，10t id x +→。

因此，定义函数f (x )如下：11/101/10(1)0.5()0.5x x f x x x − − ⎧=⎨< ⎩≥ (6) 1110()1()t id t idt id rand f x xrand f x +++⎧ ⎪=⎨ <⎪⎩≥ rand 为(0, 1)之间的随机 (7) 4.4 种群位置初始化在信息系统的粒子模型中，粒子采用二进制编码，粒子的每个位对应信息系统的一个属性。