第6卷第2期 智能系统学报 Vol.6 No.2 2011年4月 CAAI Transactions on Intelligent Systems Apr.2011 doi:10.3969/j.is3n.16734785.2011.02.007 一种带禁忌搜索的粒子并行 子群最小约简算法 马胜蓝，叶东毅 (福州大学数学与计算机科学学院，福建福州350108) 摘要：为了提高基于群体智能的粗糙集最小属性约简算法的求解质量和计算效率，提出一个结合长期记忆禁忌搜 索方法的粒子群并行子群优化算法.并行的各子群不仅具有禁忌约束，而且包含多样性和增强性策略.由于并行的 子群共同陷入局部最优的概率小于一个粒子群陷入局部最优的概率，该算法可提高获得全局最优的可能性，并诚少 受初始粒子群体的影响.多个UCI数据集的实验计算表明，提出的算法相对于其他的属性约简算法具有更高的概率 搜索到最小粗糙集约简.因此所提出的算法用于求解最小属性约简问题是可行和较为有效的， 关键词：属性约简；粗糙集；禁忌搜索：粒子群优化算法；并行子群 中图分类号：TP18文献标识码：A文章编号：16734785(2011)02-013209 A minimum reduction algorithm based on parallel particle sub-swarm optimization with tabu search capability MA Shenglan,YE Dongyi (College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China) Abstract:In order to improve the solution quality and computing efficiency of rough set minimum attribute reduction algorithms based on swarm intelligence,a parallel particle sub-swarm optimization algorithm with long-memory Tabu search capability was proposed.In addition to the taboo restriction,some diversification and intensification schemes were employed.Since parallel sub-swarms have a lower probability of simultaneously getting trapped in a local opti- mum than a single particle swarm,the proposed algorithm enhances the probability of finding a global optimum and decreases the influence of initial particles.Experimental results on a number of UCI datasets show that the proposed algorithm has a higher probability of finding a minimum attribute reduction in rough sets compared with some exist- ing swarm intelligence based attribute reduction algorithms.Therefore,the proposed algorithm is feasible and rela- tively effective for the minimum attribute reduction problem. Keywords:attribute reduction;rough set;tabu search;particle swarm optimization;parallel particle sub-swarm 作为特征选择的一个有效方法「12]，粗糙集属Hdar等人提出将禁忌算法用于最小约简的搜 性约简及其算法近年来得到了广泛的研究34].其 索；而文献[8]和[9]则探讨了粒子群方法在求解 中，对于NP难的最小属性约简问题3)的研究也取 最小约简问题中的应用.相对启发式属性约简算法 得了新的进展，提出了若干基于进化计算或群体智 而言，这些最小约简算法提高了求得最小约简的可 能的最小约简算法.例如，Wroblewski和Bazan等利 能性，但是在求解质量和计算效率方面仍有待进一 用遗传算法寻找最小约简[S);R.Jensen等提出的基 步改进。 于蚁群算法的最小约简算法6；最近，Abdel-Rahman 针对上述情况，提出了一个带长期记忆的禁忌 搜索和并行子群粒子群优化方法相结合的最小属性 收稿日期：2010-0307. 约简算法.PS0算法简单、易于实现，通常比遗传算 基金项目：国家自然科学基金资助项目(60805042)：福建省自然科学 基金资助项目(2010J01329). 法收敛速度快；另一方面，应用蚁群算法求解最小属 通信作者：叶东毅.E-mai:yiey@fzu.eu.cn. 性约简问题（如AntRSAR[6])需要采取和属性个数
第2期 马胜蓝，等：一种带禁忌搜索的粒子并行子群最小约简算法 ·133· 一致的种群规模，当规模较大时，计算复杂度明显 指包含属性个数最少的一个属性约简， 增加.而应用PS0算法则没有这方面的限制.本文 所有属性约简的交集为核，记为 中并行的各子群不仅具有禁忌约束，而且包含多样 Core(C)=n Red. 性和增强性策略，采用这2种策略主要是为了降低 1.2禁忌搜索 算法陷入局部极小的可能性.实验计算结果表明，与 禁忌搜索是一种启发式算法21，其基本过程如下， 基于粒子群优化的属性约简算法、基于禁忌搜索的 算法1基本的禁忌搜索算法 属性约简算法和基于蚁群优化的最小属性约简算法 1)选择问题的一个初始解x0,设置禁忌表 相比，本文算法取得了较好的改进效果， (T)为空并且设迭代次数k:=0; 1基本概念和记号 2)根据禁忌限制生成一个当前解k的邻居解 空间M(x); 为叙述方便起见，首先简单回顾粗糙集理论的 3)计算邻居解空间M(xx)的最优解xk+1并且 一些基本概念10口以及禁忌搜索和粒子群优化的 更新禁忌表TL; 基本思想 4)如果满足停止条件则停止该算法，否则转向2). 1.1粗糙集与属性约简 1.3标准粒子群优化算法PS0 四元组S=(U,A,Vf)是一个信息系统，其中U 最早由Kennedy等人[Ia]提出的PS0算法是一 为对象的非空有限集合，即论域；A为属性的非空有 种群体搜索算法，它根据对环境的适应度将群体中 限集合，信息系统中A常分为条件属性C和决策属 的个体移动到好的区域。每个个体看作是D维搜索 性D;V=U'a,Va是属性的值域：f为U×A→V是 空间中的一个没有体积的微粒（点），在搜索空间中 一个信息函数，它为每个对象的每个属性赋予一个 以一定的速度飞行，这个速度根据它本身的飞行经 信息值，即Ha∈A,x∈U,f(x,a)∈V.设PCA且 验和同伴的飞行经验来动态调整.第个微粒表示 P≠☑，定义由属性子集P导出的二元关系如下： 为X:=（x1,x2,…,xD),它经历过的最好位置（有 IND(P)=(x,y)I Ya E Pf(x,a)=f(y,a). 最好的适应值)记为P:=（P,P2,…,PD),也称为 若(x,y)∈ND(P),则称x和y是P不可区分的，即 P·在群体所有微粒经历过的最好位置的索引号 依据P中所含各属性无法区分x和y 用符号g表示，即P,也称为g·微粒i的速度用 设集合XCU,P是一个等价关系，称PX为集合 V:=(,2,…,vn）表示.对每一代，它的第d维 X的P下近似集；PX为集合X的P上近似集；集合 (1≤d≤D)根据如下方程进行变化： BNp(X)为X的P边界域 vid =w x vu +c x rand()*(Pi-%u)+ PX={x|x∈U,[x]pCX}, c2×Rand()*(Pgd-xa), PX={xlx∈U,[x]pnX≠0}， 动=xa+V BNp(X)=PXPX. 式中：w为惯性权重；c1和c2为加速常数；rand()和 设P和Q为论域上的等价关系，Q的P正域记 Rand()为2个在[0,1]范围里变化的随机值， 作POSp(Q): POS(Q)=PX, 2基于禁忌搜索和粒子并行子群的属 I POS(Q)I 性约简算法TSPPSOAR k=Yp(Q)=- 1U| 称知识Q是k度依赖于知识P的，记作P→Q. 禁忌搜索算法通过搜索当前解的邻居来获得 当k=1时，称Q完全依赖于P;当0<k<1时，称Q 解，其中禁忌表有助于避免搜索陷入局部最优，但是 粗糙依赖于P;当k=0时，称Q完全独立于P. 该方法的搜索能力并不强；而粒子群优化算法可以 属性约简是去除一些冗余的属性而不诚少原来 通过粒子群来搜索解，具有较强的搜索能力，但是容 集合的分类质量.一个约简可以定义如下： 易陷入局部最优.本文通过结合这2种算法的思想 Red =RCI YR(D)=Yc(C), 来提高搜索能力并避免陷入局部最优，由此提出了 HBCR,YB(D)≠Ac(D)i. 一个改进的算法，记为TSPPSOAR.该算法将原始 一个数据集可能有多个属性约简，最小约简是 粒子群分解成具有较少个体数目的并行子群来提高
·134 智能系统学报 第6卷 获得最优解的概率，同时利用了带有长期记忆的禁 位置不一致的位上随机取V位置为相同.更新后该粒 忌策略和2个优化方案来提高小群体数目的子群的 子仍然保持着自身到全局最优位置的搜索能力. 搜索能力. 2)如果V>x。,先将当前粒子位置更新为与全局 一般地，基本的禁忌搜索算法仅利用了短期记忆 所经历最优位置相同，再在更新前粒子的位置和全局 即禁忌表.为了取得更好的性能，需要长期记忆来保存 所经历最优位置相同的位上随机抽取置(Vx)位置为 搜索过程中获得的重要特征.因此，在本文算法的禁忌 不同，这样粒子在到达当前全局最优位置之前还可以 搜索过程中加入了长期记忆“属性的使用频率”，并通 继续保持朝其他方向飞行搜索的能力， 过如下的2个方案来自动调节解的状态， 3)如果改变位置后粒子的位置在T,表中出现， 多样性：通过属性的使用频率来调节解，使算法 则重新执行1)、2)来生成新的位置， 在解空间搜索到新的区域。 2.5粒子的位置质量衡量标准 增强性：提高一些有较好前景（有可能达到全 算法中使用适应值来衡量粒子的位置解的质量 局最优点)的解的优先权，以搜索该类较优解周围 优劣，适应度函数如下所示4： 可能存在的更优解。 Fitness =a x(D)+Bx CI-RI I CI (1) 2.1粒子的解表示 TSPPSOAR利用二进制串来表示一个解（粒子 式中：Yr(D)是属性R相对于决策属性D的依赖 的位置).如果对于一个解x中的某个属性x(i=1, 度；R|是被选择的子集的属性个数；a和B分别控 2,…,1C1,1C1为所有条件属性的个数)的值为1， 制着依赖度的值和子集的长度，其中a取0~1的 则x具有第i个属性；同样地，如果=0，则x不具 数，B=1-a.本文中设置a为0.9，B=0.1.设置较高 有第i个属性. 的值可以尽量保证最优解本身是一个约简，而不降 2.2禁忌表 低原集合分类质量.算法的目标是最大化适应值、 禁忌表T,的作用是用来避免陷入局部最优和 2.6并行子群 避免重复生成不合适的粒子的位置解.全部为1（所 根据概率论可以得出： 有属性都被考虑)和全部为0（所有属性都不考虑） 1)如果一个粒子群A得到最优解的概率为p, 的解将长期存放在T表中.T剩余中的位置 则A陷入局部最优解的概率则为(1-p), (|TL1-2)被用于保存最近粒子到达的位置，其中 2)将A分解成n个并行子群A:,则n个A:构成 |T|表示禁忌表的长度， 一个新的群体A';在求解同一个问题时，每个子群 禁忌表的更新策略为：如果禁忌表还未存满，则 A'得到最优解的概率为卫'，总群体A'陷入局部最优 将新的粒子的位置解插人禁忌表中；否则将 解的概率为(1-p)”。 (1T,|-2)中最先插入的解替换为新的解， 3)如果p'不会远小于p,则粒子群A'陷入局部 2.3粒子速度的表示 最优的概率小于粒子群A进入局部最优的概率；因 采用文献[14]的方法，每个粒子的速度被表示 此具有并行子群的总群体A'获得最优解的概率可 为[1，'x]区间内的1个正数，表示每次粒子有多 以满足如下条件：1-(1-p')”>卫. 少个位要被改变为与全局所经历最优位置相对应的 群体个数为N的粒子群有2种分解策略：一种 位置一致.2个粒子之间的差跟2个粒子的不一致 是分解为子群个数为1，则每个子群内粒子个数为 的位的个数有关4 N/n1;另一种是选择分解的群体个数n2>n1,则每 需要注意的是，算法中必须限制粒子的速度而 个子群体内粒子个数N/n2<N/n1.2种策略分别通 避免飞过全局最优解而只能找到次优解.本文中设 过增大p'和n的值来提高获得最优解的概率，对于 置Vma=(1/3)*1C1,如果V<1,则V=1. 这2种策略章节3.2都做了实验比较， 2.4粒子位置更新策略 经过分解后的粒子群具有类似于如图1的拓扑 设更新后的速度为V,当前粒子位置和全局所 结构[5]，子群内部独立地搜索解空间，而子群之间 经历的最优位置Pt之间的不一致的位个数为xg, 通过全网络连接，互相交流着该子群经历过的最好 则更新策略如下所示。 的位置的信息 1)如果V<=x。,则在当前粒子和全局所经历最优
第2期 马胜蓝，等：一种带禁忌搜索的粒子并行子群最小约简算法 ·135· 3)通过设置w:=0来删除属性0：，计算y值； 4)如果y增加或者y不变（但是由于属性个数 减少)则更新Pt; 子群n 5)更新全局最优解Pe 最后的方案是约简激励.在TSPPSOAR迭代搜 索的过程中，得到的约简都被保存在一个叫做Red- Set的集合中.利用核的概念，在RedSet中取nR个 群 最优约简的交集构造一个新的解x.如果x的属 性个数比粒子全局经历的最优位置Pe的属性个数 图1 TSPPSOAR拓扑结构 至少少2个，则x中根据启发性信息将一个0的 Fig.1 The topology of TSPPSOAR 位置改为1.该方案一直执行到Xu中的属性个数 2.7多样性增强性方案 比Pt的属性少一个。 TSPPSOAR算法将粒子群分解为并行的子群，但 过程3[xBu]=EliteReducts(RedSet,nR) 是由于每个子群的群体个数的下降，必然会导致每个 1)如果RedSet为空则过程结束，否则到2)； 子群的搜索能力的下降.如2.6中所述，要想降低陷 2)设nr为RedSet中最优约简的属性个数，设 入局部最优的概率，必须让子群获得最优解的概率不 置xu为RedSet中ne个最优约简的交集； 会远小于原群体获得最优解的概率，所以在子群内部 3)如果x的属性个数小于(np-1),则执行 采用额外的方案来确保每个子群的搜索能力。 4),否则过程结束； 因此，TSPPSOAR应用3种方案[刃来提高搜索 4)如果P0Sm(D)等于原论域的正域个数，则 的多样性和增强性.为描述完整起见，以下介绍这3 过程结束； 个方案，第一个方案是在一定迭代时间内无法搜索 5)在x的所有0位置中选择一个，在置为1 出可以改进现有的最优解时所执行的多样性方案。 的情况下可以得到最大的r值的位置，将其置为1， TSPPSO0AR中定义了一个具有ICI维的向量v,其 转到3). 中向量中第i维代表群体中每个粒子经历过的位置 激励过程相当于在RedSet的交集“新核”基础 中选择属性i的次数.因此一个多样性的新解x“可 上，寻找比搜索到的全局最小约简p更优的解。 以通过，中每个属性的被选择的概率来获得.以下 2.8 TSPPS0AR算法 给出x的生成过程： 基于禁忌搜索和粒子并行子群的属性约简算法 过程1[x]=Diverse(v) TSPPSOAR,将原群体分解成n个并行的子群，每个子 1)随机生成数字r1,2,…,r1c∈(0,1)， 群同时进行属性约简，以提高获得最优解的概率。 2)重复执行如下步骤从i=1,2,…,1C1. 在该算法中，惯性权重W随着迭代次数的增加 3)如果>/公利则设置=1，香则设置 而不断减小，公式如下 xm=0. W=W= _Ws-W血x iter., (2) 上述的多样性方案主要选择过去较少被选择到 iterma 的属性，将粒子导向一个新的解空间，从而加大了逃 式中：Wma和Wmin为初始设定的值，iter为当前迭代 离出局部最小点的可能性， 的次数.具体算法如下， 在获得x"后，如果全局经历的最优位置Pt在 算法2 TSPPSOAR 经过一段时间后仍然没有任何改进，则TSPPSOAR 1)初始化一群粒子，包括随机的位置和速度； 应用增强性方案来改进每个粒子经历过的最优位置 初始化禁忌表T,禁忌表中包含2个位置(0，…，0) P·在过程2.2中通过对P进行约简而不减少 和(1，…，1)，设置v为空向量，RedSet为空集合， Ya(D),将原解从代数协调集调整为代数约简， 迭代次数iter为O,选择lns、impabak和lin,令Inms> 过程2 Shaking(Phet） Imp>Lha>1s.将粒子群分割成n个含有相同粒子 1)对每个粒子经历的最优位置P重复执行如 数的子群(child,child2.,…,child.),每个子群维护 下步骤； 着各自的禁忌表T、 2)将Pem中的为1的属性构造成一个新的集合 2)对于每个子群child:执行3)~8). W={01,02,…,01w1}; 3)利用式(1)求出每个粒子的适应值
·136 智能系统学报 第6卷 4)对每个粒子，将它和它经历过的最优位置 的数据信息如表1所示. P作比较，如果较优，则将其作为该粒子的最优位 表1数据集 置Pbe Table 1 Datasets 5)对每个粒子，将它和该子群全局所经历最优 数据集 实例个数 条件个数 位置g作比较，如果较优，则重新设置ge的索 Hayes 132 5 引 Bupa 345 6 6)比较ge,和总群体的最优位置ge,如果较 Corral 32 6 优，则重新设置boeatall索引. Breast 191 9 7)更新粒子的速度，利用禁忌表T更新粒子位 Led24 200 24 置 Mushroom 8124 22 Soybeanl 47 35 8)根据章节2.2中提到的更新策略更新子群 Soybean2 307 35 的禁忌表T,;根据粒子的位置更新，如果该粒子 Splice 2126 60 位置已经是一个约简，则存人RedSet,最后设置 Sponge 76 45 iteriter +1. Vote 300 16 9)如果迭代次数大于I或者总群体最优位置 3.2实验参数 ge未改进的次数超过Ip,则转向12) 首先对算法的符号做简要说明. 10)如果总群体最优位置未改进的次数超过 TSAR为基于禁忌搜索的最小属性约简算 I业，应用过程2对每个子群的每个粒子经历的最优 法7]；PSORSFS为基于粒子群优化算法的最小数型 位置Pe进行处理，转向2) 属性约简算法[4；AntRSAR6I为改进的基于蚁群 11)如果总群体最优位置未改进的次数超过 优化[6的最小属性约简算法。 I,则应用过程1来重新获得每个子群的每个粒子 TSPPS0AR(10,10)和TSPPS0AR(5,5,5)为本 的当前位置，转向2). 12)应用过程3来获得x,如果x比总群体 文所提的属性约简算法，括号内的数字(m1,2,…, 最优位置p更优，则设置pe=xu.图2为算 nw)表示的是分解方法：粒子群总群体个数为N,第i 法2的流程图. 个并行子群个数为n,且N=∑n,实验过程中对 初始化参数 每个数据集均测试100次，实验结果用数字“a”表 对于每个子群 示：代表算法在该数据集上属性约简后的属性长 度，b代表100次试验中有b次达到长度为a的属性 计算：每个粒子的适应值 约简. 每个子群每个 更新每个粒子经历 粒子所经历的 每个子群 实验中的参数设置见表2. 每个粒子 最优位置p和全局 最优位置增强 所经历最优位置pc 多样性处理 表2 TSPPSOAR、PSORSFS和TSAR参数设置 性处理 Table 2 The parameter settings of TSPPSOAR,PSORSFS and TSAR 更新总体最优位置g population V ng ITI 基于T更新粒子位性 TSPPS0AR20、15 100(1/3)×N10 7 t N PSORSFS 20 100(1/3)×N 结東 增强性 N 多样性 模式 模式 TSAR 100 10 1 AntRSAR 250 约简激励 其中pupulation为总群体个数，Vam为粒子的最 图2 TSPPSOAR算法流程 大速度.禁忌表长度1T|被设置为7，除了保存全1 Fig.2 The flowchart of TSPPSOAR 和全0的位置外，剩余5个用于保存最近访问的位 置.实验中发现，该长度的禁忌表以一定概率地让粒 3实验与讨论 子跳出局部最小点.I,和Ih.分别设置为10和20， 3.1数据集介绍 这种设置可以避免粒子花费过多的迭代时间在没有 实验测试所用的数据为11个UCI数据集，具体 任何改进的搜索中，从而让粒子进入一个新的解空
第2期 马胜蓝，等：一种带禁忌搜索的粒子并行子群最小约简算法 ·137· 间.在约简激励过程中，利用了nR(nR=10)个Red- 而从表4可以看出在大部分数据集上，3个子群的 Set中最优的约简.表格中的“一”符号表示该算法 TSPPSOAR(5,5,5)的结果比2个子群的TSPPSO0AR 没有使用该列所示的参数： (10,10)的结果更优，虽然在Vote数据集上比 3.32种TSPPS0AR分解策略比较 TSPPS0AR(10,10)的结果差，但是约简结果显示已 首先比较TSPPSOAR在2种不同分解策略下的 经具有90%的高概率达到最优约简，并且从图3中 实验结果，TSPPS0AR(10,10)代表第1种分解策 可以看出TSPPS0AR(5,5,5)比TSPPS0AR(10,10) 略，TSPPS0AR(5,5,5)代表第2种策略.实验结果 具有更小的计算消耗（计算消耗在3.4中介绍）.因 如表3、4所示；其中表4为约简的属性平均长度值. 此在子群中引入带有长期记忆的禁忌策略和多样性 表32种TSPPS0AR分解策略实验数据比较1 增强性策略保证了群体在减少粒子个数的同时不降 Table 3 The comparisons of two partition strategies in 低搜索解的能力。 TSPPSOAR(1) 下面的实验比较所提及的TSPPSOAR主要是 数据集 TSPPSOAR(5,5,5) TSPPSOAR(10,10) 指第2种策略下的算法，即指TSPPS0AR(5,5,5). Hayes 110m 110 Bupa 310 3200 2.310 Corral 410 410o0 2.1 Breast 8%g2 8%g2 1.9 Led24 112612313 1119129132 Mushroom 4%52 4057 1.7 Soybeanl 2304 2031445 15 日 Soybean2 9*105 921029119 Splice 91101w111 97103211' 月 Sponge 80g1910 8"928102 Vote 8093102 8”9102 图32种TSPPSOAR分解策略的计算开销比较 Fig.3 Computational costs on two partition strategies in TSPPSOAR 表42种TSPPS0AR分解策略实验数据比较2 Table 4 3.4 TSPPSOAR与TSAR、PSORSFS和AntRSAR的 The comparisons of two partition strategies in TSPPSOAR(2) 比较 TSPPSOAR TSPPSOAR 现将TSPPSOAR与PSORSFS、TSAR和AntR- 数据集 (10,10） (5,5,5) SAR分别进行比较，实验结果如表5所示.为了给出 Hayes 1 表5更详细的结果比较，表6中列出TSPPS0AR、 Bupa 3 3 PSORSFS、TSAR和AntRSAR的约简平均值以及这4 Corral 4 种算法约简的结果的Z检验（置信度参数为 0.05);另外，在置信度0.05差异显著情况下，用括 Breast 8.02 8.02 号标出TSPPSOAR与其他3种属性约简算法相比较 Led24 11.83 11.75 具有较优结果的算法， Mushroom 4.37 4.32 从表5~6中可以看出：在11个数据集上， Soybean1 2.66 2.12 TSPPSOAR的约简结果优于PSORSFS;在Vote数据 Soybean2 9.47 9.25 集上，TSPPSOAR约简结果不如TSAR,但在剩余的 Splice 9.34 9.20 10个数据集上，均比TSAR的约简结果好；TSPP Sponge 8.32 8.21 SOAR在数据集Hayes、Bupa、Corral、Breast、Led24和 Vote 8.05 8.12 Soybean1上与AntRSAR无显著差异，在数据集 Mushroom、Splice和Vote上约简结果略逊于AntR 从表3中可以看出在每个数据集的100次计算 SAR,在数据集Soybean2和Sponge上约简结果优于 试验中，除了Vote数据集外，TSPPS0AR(5,5,5)得 AntRSAR. 到最小约简的个数均多于TSPPS0AR(10,10)
·138 智能系统学报 第6卷 表5 TSPPSOAR、PSORSFS、TSAR和AntRSAR比较1 Table 5 The comparisons of TSPSOAR,PSORSFS,TSAR and AntRSAR(1) TSPPSOAR 数据集 TSAR PSORSFS AntRSAR (5,5,5) Hayes 10 1 1i0 10m Bupa 3100 34 310 310 Corral 40 45515 48512 410m Breast 8%92 81w 810 81m Led24 11261273131 1112213191461529 1151264133014 11261274 Mushroom 4%52 42516657168 42526778 42518 Soybeanl 23104 243741251672 2131°455136 232 Soybean2 951025 951011111220131214151 9*102411第121313 9510 Splice 9110811 910116 9108116 910 Sponge 8g110 8299391016111312 838g5107 8mg710 Vote 809102 810 890101116 810 表6 TSPPSOAR,PSORSFS,TSAR和AntRSAR比较2 Table6 The comparisons of TSPSOAR、PSORSFS、TSAR and AntRSAR(2)】 约简平均值 Z检验 数据集 TSAR- PSORSFS AntRSAR TSPPSOAR TSAR PSORSFS AntRSAR TSPPSOAR TSPPSOAR TSPPSOAR Hayes 1 Bupa 3.02 3 3 1.421 4.181 3.674 Corra 4.15 4.12 一 (TSPPSOAR) (TSPPSOAR) Breast 8.02 8 8 8 -1.421 -1.421 -1.421 20.905 7.141 Led24 11.75 13.94 12.27 11.74 -0.157 (TSPPSOAR) (TSPPSOAR) 8.689 8.646 -2.306 Mushroom 4.32 5.38 5.52 4.18 (TSPPSOAR) (TSPPSOAR) AntRSAR) 10.591 10.326 Soybeanl 2.12 3.6 3.34 2.12 0 (TSPPSOAR) (TSPPSOAR) 13.209 8.347 3.017 Soybean2 9.25 10.21 10.23 9.45 (TSPPSOAR) (TSPPSOAR) (TSPPSOAR) 14.120 14.34 -4.677 Splice 9.2 9.99 10.10 (TSPPSOAR) (TSPPSOAR) AntRSAR) 8.385 6.938 1.983 Sponge 8.21 9.22 8.79 8.35 (TSPPSOAR) (TSPPSOAR) (TSPPSOAR) -3.119 4.150 -3.119 Vote 8.12 8.54 8 (TSAR) (TSPPSOAR) AntRSAR) 本文通过比较基于依赖度值r的计算次数来评 模式下最多执行的丨C!-2次和激励过程中的 价计算开销，显然如果数据集的属性个数较多，依赖 3ICI次；PSORSFS计算开销最多为2O00次；AntR 度值r的计算将会占用大量的计算空间.TSAR的计 SAR最少需要的开销为250|Cl×Rmin,Rmin为约 算开销为最大迭代过程中所耗费的50丨C1次、增强 简的最小长度；TSPPSOAR计算开销为最大迭代过
第2期 马胜蓝，等：一种带禁忌搜索的粒子并行子群最小约简算法 ·139· 程中所耗费的l0 Opopulation次、增强模式下的 4 结束语 2n(1C1-2)次(n为并行子群的群体个数)和激励 过程中的3！C1.则各算法的计算开销为： 针对粗糙集最小属性约简问题，提出了结合基 TSARmax:54 I CI -2; 于记忆的禁忌搜索思想的粒子群并行子群算法 PSORSFSmax:2 000; (TSPPSOAR).实验的结果表明了该算法的有效性： AntRSARmin:250 I CI x Rmin; 不仅具有粒子群在问题空间上很强的搜索能力，而 TSPPS0AR(10,10)max:2000+4|(CI-2): 且通过禁忌搜索的长、短期记忆能有效地逃离局部 TSPPS0AR(5,5,5)max:1500+61(C1-2). 极小点；并行的子群提高了搜索到最小约简的概率； 如下图4~5给出各算法之间的计算开销比较， 同时计算开销小是其优于基于蚁群的属性约简算法 3.5*10 TSPPSOAR 的优势.TSPPSOAR较高概率达到最小约简的特性 3.0 -o…PSORSFS 可以有效地减少受粒子群初始粒子选择的影响，提 2.5 高了算法的适应性， 2.0 --0 1.5 D-0-0--“ 参考文献： 1.0 [1]SWINIARSKI R W,SKOWRON A.Rough set methods in feature selection and recognition[J].Pattemn Recognition Letters,2003,24:833849. [2]CHOUCHOULAS A,SHEN Q.Rough set-aided keyword 图4 TSPPSOAR、TSAR和PSORSFS的计算开销比较 reduction for text categorization[J].Applied Artificial In- Fig.4 Computational costs on TSPPSOAR,TSAR and telligence,2001,15(9):843-873. PSORSFS [3]SKOWRON A,RAUSZER C.The discemibility matrices and functions in information systems[C]//Dordrech:Kluw- er Academic Publishers,1992:311-362. ×10 140 TSPPSOAR [4]HU X.Knowledge discovery in databases:an attribute-ori- 120 AntRSAR ented rough set approach[D].Regina,Saskatchewan:Can- 100 ada,Computer Science Faculty of Graduate Studies,Uni- 60 versity of Regina,1995:1-152. [5]WROBLEWSKI,J.Finding minimal reducts using genetic 20 algorithms[C]//Proc of the Second Annual Joint Confer- 0 ence on Information Sciences.Wrightsville Beach,USA, 1995:186-189. [6]JENSEN R,SHEN Q.Finding rough set reducts with ant 图5 TSPPSOAR和AntRSAR的计算开销比较 colony optimization C]//Proceedings of the 2003 UK ig.5 Computational costs on TSPPSOAR and AntRSAR Workshop on Computational Intelligence. Bristol,UK. 2003:1522. 从图4中可以看出TSPPS0AR的计算开销介于 [7]HEDAR A R,WANG J,FUKUSHIMA M.Tabu search for TSAR和PSORSFS之间，使得计算开销保持在一个 attribute reduction in rough set theory[J].Soft Computing, 2008,12(9):909-918. 较低的状态，并且在splice数据集上拥有最低的计 [8]叶东毅，廖建坤.基于二进制粒子群优化的最小属性约 算开销.从图5中可以看出AntRSAR虽然在数据集 简算法[J].模式识别与人工智能，2007,20(3)：295- Mushroom、Splice和Vote上约简结果比TSPPSOAR 300. 优，但是蚁群算法计算开销高于TSPPSOAR,通过综 YE Dongyi,LIAO Jiankun.Minimum attribute reduction al- 合考虑计算开销和约简结果，TSPPSOAR优于AntR- gorithm based on binary particle swarm optimization[J]. SAR.综上可以看出，TSPPSOAR相对于其他3种CI Pattern Recognition and Artificial Intelligence,2007,20 属性约简算法(PSORSFS、TSAR和AntRSAR),有较 (3):295-300. 低的时间和空间开销，并且有较好的约简结果。 [9]叶东毅，恩建坤.最小约简问题的一个离散免疫粒子群 算法[J].小型微型计算机系统，2008,29(6)：550
·140. 智能系统学报 第6卷 555. [16]DENG Tingquan,YANG Chengdong.An improved ant YE Dongyi,LIAO Jiankun.Immune discrete particle swarm colony optimization applied to attributes reduction J] optimization algorithm for minimum attribute reduction prob- Fuzzy Information and Engineering,2009,54:1-6. lems[J].Journal of Chinese Computer Systems,2008,29 [17]MONTGOMERY D C,RUNGER G C.Applied statistics (6):550-555. and probability for engineers [M].3rd ed.New York, [10]王国胤.Roug映集理论与知识获取[M].西安：西安交通 USA:John Wiley Sons Ine,2003:278-326. 大学出版社，2001：23-145. 作者简介： [11]张文修，梁怡，吴伟志.信息系统与知识发现[M].北 马胜蓝，男，1986年生，硕士研究 京：科学出版社，2003：5668. 生，主要研究方向为计算智能。 [12]GLOVER F.Tabu search-part I,ORSA[J].Joural on Computing1989,1(3):190-206. [13]KENNEDY J,EBERHART R C.Particle swarm optimiza- tion[C]//Proc of the IEEE International Conference on Neural Networks.Perth,Australia,1995:1942-1948. [14]WANG Xiangyang,YANG Jie,PENG Ningsong,et al. 叶东毅，男，1964年生，教授，博士生 Finding minimal rough set reducts with particle swarm op- 导师，主要研究方向为计算智能、数据挖 timization[J].Lecture Notes in Artificial Intelligence, 掘曾获得国家科技进步二等奖（主要成 2005,3641：451-460. 员1项)、福建省科学技术二等奖1项和 [15]MENDES R,KENNEDY J,NEVES J.The fully informed 福建省科学技术三等奖2项.出版著作和 particle swarm:simpler,maybe better[].IEEE Transactions 教材6部，发表学术论文70余篇， on Evolutionary Computation,2004,7():204-210. 2011国际信息技术与应用论坛 2011 International Forum on Information Technology and Applications(IFITA 2011) 所有IFTA2011投稿论文，要反映在信息技术与应用及相关领域中未发表的有新意或创见的技术、工 程、理论、方法、应用及其它相关领域研究成果，其工作语言为“英文/中文”.TA2011的相关主题包括（但 不限于)： 1.网格计算，分布计算，并行计算，服务计算，移动计算，普适计算，对等计算，金融计算，经管计算，生物 信息计算，生物灵感计算，情感计算，科学计算，高性能计算，计算几何，数学建模，计算方法，算法研究， 2.通讯工程，软件工程，人工智能，模式识别，知识发现，数据挖掘，数据库技术，智能代理，逆向工程，信 息隐藏，数据仓库，中文处理，虚拟现实，互联网络，移动商务，电子商务，电子政务，电子医疗，工程管理，服务 管理，知识管理. 3.物联网技术，机器人技术，计算机视觉，多媒体技术，传感器网络，嵌入式系统，理论计算机，粗糙集技 术，Wb智能，自然语言处理，自然语言理解，语音处理，计算机辅助设计，计算机辅助制造，计算机辅助管 理，计算机辅助制造，产业应用、政策与发展，企业信息化. 4.管理信息系统，决策支持系统，地理信息系统，信息安全技术，数字水印，搜索引擎技术，图形图象处 理，商务智能，遥测遥控遥感，环境科学信息技术，管理科学信息技术，数学建模与模型计算，计算机应用技 术，通讯工程应用技术，自动化技术与工程。 5.基于或利用信息技术与应用的教学思想、教学理论、教学方法、教学研究、教学改革、教学创新、教学 探索、教学经验等。 会议网站：htp:/www.itaa.com/ifita/english/index.asp