（环境工程专业论文）基于量子粒子群的粗糙集属性约简算法及流域站网分析.pdf

独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特n j i i 以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：趸。叁丝1 日期：兰旦2 三：! 三：17 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：趸支红1 导师( 签名) 期2 。1 2 - t 7 摘要 实现江河水资源的科学利用和发展，需要对流域各类水文监测站点采集的 数据进行深入的分析，以了解流域的内在规律和各种特征之间的内在联系。一 方面由于监测站点的观测设备和观测条件的不同，很多河流没有系统完整的数 据，又有很多河流采集的数据资料冗长复杂，为研究和应用带来了困难；另一 方面监测站点的布设大多由经验选定位置，可能出现监测站点的分布不能反映 流域特征的情况，或是分布过于密集，出现重复建设的情况。因此采集的流域 信息存在复杂性、主观性和不确定性的特征，需要不确定性分析和数据约简的 方法对流域信息进行处理。 传统的粗糙集属性约简算法存在各种的限制和不足，在流域数据约简中的 应用存在问题，本文在应用粗糙集属性约简算法对流域数据进行约简的同时， 引入量子粒子群算法对粗糙集属性约简算法进行改进，得到新的属性约简模型， 并结合实例将模型应用于流域数据的约简中，验证模型的效果，为流域数据约 简提供了一种可行方法。本文的研究内容主要包括以下几个方面： 1 ) 系统介绍粗糙集理论相关概念和各类属性约简算法，分析各类属性约简 算法在流域数据约筒应用中的不足，结合粗糙集理论的特征，引入量子粒子群 算法对属性约简算法进行优化。 2 ) 从粒子编码、适应度函数设计、粒子更新和粒子编码转化几个方面对基 于量子粒子群算法的属性约简模型的建立进行了详细的阐述，并通过实例和标 准u c i 数据集对模型的正确性和运算效率进行了分析和验证。 3 ) 将基于量子粒子群算法的属性约简模型应用于流域数据约简中，对于某 流域，用7 个水文监测站点代表原来1 4 个水文监测站点的特征，并通过b p 神 经网络预测验证了结果的有效性。约简结果提高了流域水文数据的利用率，同 时对水文监测站点的合理布设提供了一个方面的参考。 论文的创新点主要包括以下几方面： 1 ) 将量子粒子群算法引入对粗糙集属性约简进行优化，根据粒子群本身的 特性结合粗糙集的知识得到了基于量子粒子群算法的属性约简模型。 2 ) 将基于量子粒子群算法的属性约简模型应用于流域数据约简，为流域数 据约简提供了一种新的可行的方法，也为水文站点的合理布设提供了参考。 关键词：流域站网，数据约简，粗糙集，粒子群算法 a b s t r a c t f o rr e a l i z i n gs c i e n t i f i cu t i l i z a t i o na n dd e v e l o p m e n t ，w es h o u l da n a l y z ed a t a c o l l e c t e db ya l lk i n d so fh y d r o l o g i c a lm o n i t o r i n gs i t e si nb a s i n ，i no r d e rt ou n d e r s t a n d t h ei n h e r e n tl a wo fb a s i na n dt h er e l a t i o n s h i po fv a r i o u sc h a r a c t e r i s t i c s o nt h eo n e h a n d ，b e c a u s eo ft h ed i f f e r e n c eo fe q u i p m e n ta n do b s e r v a t i o nc o n d i t i o no f h y d r o l o g i c a lm o n i t o r i n gs i t e s ，t h e r ea r em a n yr i v e r sw i t h o u tc o m p l e t ed a t a , a n dt h e r e a r eo t h e rr i v e r sw h i c hh a v el o n ga n dc o m p l e xd a t a , s ot h ed a t ai sh a r df o rr e s e a r c h a n da p p l i c a t i o nu s e o nt h eo t h e rh a n d ，t h el o c a t i o no fah y d r o l o g i c a lm o n i t o r i n gs i t e i sa l w a y ss e l e c t e db ye x p e r i e n c e ，a n di t sp o s s i b l et h a tt h ed i s t r i b u t i o no fm o n i t o r i n g s i t e sc a n n o tr e f l e c tt h eb a s i n ，o rm o n i t o r i n gs i t e sa r el o c a t e dt o oc l o s e ，w h i c hw i l l b r i n gd u p l i c a t ec o n s t r u c t i o n f o rt h i sr e a s o n ，t h ed a t ao fb a s i nh a st h ec h a r a c t e r i s t i c s o fc o m p l e x i t y , s u b j e c t i v i t ya n du n c e r t a i n t y w en e e du n c e r t a i n t ya n a l y s i sm e t h o dt o p r o c e s st h ed a t ao fb a s i n t h et r a d i t i o n a la t t r i b u t er e d u c t i o na l g o r i t h m so fr o u g hs e th a v ek i n d so f r e s t r i c t i o n sa n di n s u f f i c i e n c y , s ot h ea l g o r i t h m sc a n n o tb eu s e di nr e d u c t i o no fb a s i n d a t as u c c e s s f u l l y b a s e do nt h ea t t r i b u t er e d u c t i o na l g o r i t h m so fr o u g hs e t ，t h i sp a p e r u s e st h ep s ot oi m p r o v ea t t r i b u t er e d u c t i o na l g o r i t h m s ，g e r i n gan e wa t t r i b u t e r e d u c t i o nm o d e l ，w h i c hw i l lb eu s e di nr e d u c t i o no fb a s i nd a t ac o m b i n i n gt h ei n s t a n c e i tw i l lp r o v i d eaw o r k a b l em e t h o df o rr e d u c t i o no fb a s i nd a t a t h er e s e a r c hm a i n l yc o n t a i n st h ef o l l o w i n ga s p e c t s t h i sp a p e ri n t r o d u c e st h er e l a t e dc o n c e p t so fr o u g hs e ta n da l lk i n d so fa t t r i b u t e r e d u c t i o na l g o r i t h m ss y s t e m a t i c a l l y , a n da n a l y z e st h ei n s u f f i c i e n c yi nr e d u c t i o no f b a s i nd a t ao fa l lk i n d so fa t t r i b u t er e d u c t i o na l g o r i t h m s t h e nu s et h ep s ot oi m p r o v e t h er e d u c t i o na l g o r i t h mc o m b i n e d 诵t l lt h ec h a r a c t e r i s t i c so fr o u g hs e tt h e o r y d e t a i lt h ec o n s t r u c t i o no fa t t r i b u t er e d u c t i o nm o d e lf r o mp a r t i c l ec o d i n g ，f i t n e s s f u n c t i o nd e s i g n ，p a r t i c l eu p d a t ea n dp a r t i c l ec o d ec o n v e r s i o nb a s e do nq u a n t u mp s o t h r o u g he x a m p l e sa n ds t a n d a r du c id a t as e t s ，w ea n a l y z ea n dc h e c kt h ec o r r e c t n e s s a n da p p l i c a b i l i t yo ft h em o d e l c o m b i n e dw i t l lp r a c t i c a ld a t a , a t t r i b u t er e d u c t i o nm o d e li sa p p l i e dt ob a s i nd a t a r e d u c t i o n w i t ht h em o d e l ，s e v e nh y d r o l o g i c a l m o n i t o r i n g s i t e sa r ec h o s e nt o i i r e p r e s e n tt h eo r i g i n a lf o u r t e e nh y d r o l o g i c a lm o n i t o r i n gs i t e s t h e nt h r o u g ht h eb p n e u r a ln e t w o r kp r e d i c t i o n , t h ee f f e c t i v e n e s so ft h ep r o p o s e dr e s u l t si st e s t e d t h e r e d u c t i o nr e s u l ti m p r o v e st h eu t i l i z a t i o nr a t eo fb a s i nd a t aa n dp r o v i d e sr e f e r e n c eo n r e a s o n a b l el a y o u to fh y d r o l o g i c a lm o n i t o r i n gs i t e s k e yw o r d s ：h y d r o l o g i c a lm o n i t o r i n gs i t e s ，d a t ar e d u c t i o n ，r o u g hs e t ，p s o i i i 武汉理工大学硕士学位论文 日三量 目冰 摘要i a b s t r a c t i i 第一章绪论。1 1 1 研究背景和研究内容1 1 1 1 研究背景和意义1 1 1 2 课题来源2 1 1 3 研究内容2 1 2 国内外研究现状。3 1 2 1 流域数据挖掘研究现状3 1 2 2 粗糙集理论研究现状4 1 2 3 粒子群算法研究现状6 1 2 4 复合粗糙集理论和粒子群算法在流域信息分析中的应用现状7 1 3 论文组织结构8 第二章粗糙集基本理论和属性约简算法9 2 1 粗糙集基本理论。9 2 1 1 信息系统与不可分辨关系9 2 1 2 不精确范畴、近似与粗糙集1 0 2 1 3 知识约简和核。13 2 1 4 值约简。15 2 1 5 求核算法15 2 2 属性约简算法1 6 2 2 1 基于区分矩阵的约简1 6 2 2 2 基于启发信息的约简。1 8 2 2 3 基于遗传算法的约简18 2 3 属性约简算法在流域数据中的应用分析2 0 2 4 本章小结2 1 第三章粒子群算法概述2 3 3 1 粒子群算法的基本原理2 3 武汉理工大学硕士学位论文 3 2 基本粒子群算法2 4 3 3 粒子群算法的改进2 5 3 4 离散二进制粒子群算法2 6 3 5 量子粒子群算法2 8 3 6 本章小结2 9 第四章基于量子粒子群的粗糙集属性约简。3 1 4 1 基于量子粒子群的属性约简算法设计3l 4 1 1 编码设计3 1 4 1 2 适应度函数设计3 2 4 1 3 粒子更新。3 3 4 1 4 粒子编码转换3 4 4 2 量子粒子群约简算法框架3 4 4 3 算法分析3 6 4 4 实验分析3 6 4 4 1 实例数据3 6 4 4 2 仿真实验3 8 4 5 本章小结4 1 第五章基于量子粒子群算法的属性约简算法在流域站网数据中的应用4 3 5 1 数据来源及预处理4 3 5 2 数据离散化4 5 5 3 流量数据约简4 6 5 4 约简效果验证4 7 5 5 结果分析5 0 5 6 本章小结5 1 第六章总结与展望5 3 6 1 全文总结5 3 6 2 研究工作展望5 4 致谢5 5 参考文献5 7 攻读学位期间发表论文和科研情况6 1 武汉理工大学硕士学位论文 第一章绪论 1 1 研究背景和研究内容 1 1 1 研究背景和意义 水科学研究中，存在大量的不确定性信息，这些不确定信息有的是客观存在 的，有的是由于数据资料不完整，也有的是因为人们对某些问题的内在原理或 变化规律不清晰，如果忽视信息的不确定性，会对研究过程和结果产生较大的 影响。 我国很多的水系往往没有系统、完整的水文、水质和水利数据，影响科学研 究的开展；虽然随着流域现代化建设的不断加深，各种检测技术得以广泛应用， 但是随之而来的是冗长庞大的数据资料，我们难以挖掘其中的隐含信息。另一 方面，流域上的水文观测站点的设置时间比较早，大多是根据经验选定位置， 但是一条河流的水文情况是复杂多变的，在有些水流平缓、河道形态稳定的河 段可能布设了几个观测站，出现重复建设的问题，造成了资源的浪费。因此流 域信息存在复杂性、主观性和不确定性，为我们研究和掌握流域的内在变化规 律带来了很大困难。由于流域信息的不确定性，快速有效地处理数据、准确地 在海量数据中获取有效的信息成为难点问题，急需不确定性分析和数据约简的 方法。 数据挖掘( d a t am i n i n g ，d m ) 是一项数据库应用技术，是从大量数据中获 取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程【1 】。简单来说， 就是从日常积累的大量数据中发现潜在的、有价值的信息。发现的知识可以被 用于信息管理、决策支持、分析预测等，同时可以进行数据自身的维护。粗糙 集理论( r o u g hs e t ，r s ) 是数据挖掘方法中一种处理不确定、不精确与不完全数 据的新数学理论和方法，它无需提供问题所需处理的数据集合之外的任何先验 信息，对问题的不确定性描述或处理也是比较客观的，因而成为数据挖掘中的 重要框架【1 】。粗糙集理论已经在机器学习、决策支持、模式识别等领域成功应用。 属性约简是粗糙集理论的一个重要组成部分，它的研究在实际应用中有着重 要的意义。属性约简就是要删减掉冗余的属性，用简洁的属性集来表示原有知 识，但是信息系统或决策表的最小属性约简已经证明是一个n p 问题，对于大型 武汉理工大学硕士学位论文 的数据库通常得到的是近似约简。因此，研究有效的数据约简算法，降低算法 的时间复杂度，寻求快速的约简仍然是粗糙集理论研究的热点之一。 粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 是一种高效的群集智能协同 优化算法，它的实现程序简洁，参数调整比较少，在处理众多优化问题上己显 示出独特的优越性和实效性。在粗糙集的研究中，已经有专家学者提出粒子群 算法与属性约简相结合的算法，与传统的启发式算法相比，其具有更为广泛的 搜索空间，可以提高获得最优解的可能性，在属性数目较多时具有更好地效果。 应用粒子群算法对粗糙集理论进行算法优化，以此对流域数据进行数据约简， 可以有效处理流域数据的不确定性，快速处理海量数据，从中进行知识发现， 为流域科学研究提供有力的保障。同时，通过分析约简结果，我们可以从侧面 分析水文观测站布设的科学性，优选出重要的水文观测站点进行重点建设和升 级，以降低水文观测站点建设的成本，达到节约资源的目的。 1 1 2 课题来源 本文依托湖北省杰出青年基金资助项目“清江流域水文站点空间拓扑结构优 化研究”( 2 0 0 9 c d a 0 1 5 ) ，技术方法上得到中央高校基本科研业务费专项资金资 助课题、交叉学科创新研究项目“致矿异常挖掘与预测组合的群集智能方法” ( 2 0 1 0 i i 0 1 4 ) 支持。 1 1 3 研究内容 一条河流、一个流域中存在很多水文监测站点，每个监测站点之间是存在着 内在联系的，如果可以用其中一部分监测站点的信息就可以完成流域的某些研 究，这样就可以减少监测站点的数量，在保持信息的完整性的基础上，为国家 节省人力和资金。问题的关键就是找到监测站点信息之间的联系，从而对其进 行约简，选出可以代表整个流域信息的检测站点。 针对流域数据存在的复杂性和不确定性，选用粗糙集方法对流域数据进行约 简，本文首先介绍经典粗糙集理论、粗糙集约简理论的相关背景和概念，并对 几种主要属性约简算法进行介绍，然后应用粗糙集进行属性约简；由于粗糙集 方法存在收敛速度慢、难得到最小约简等问题，本文随后介绍粒子群算法的算 法步骤和改进方向，引入量子粒子群算法对粗糙集属性约简进行优化，得到基 于量子粒子群算法的粗糙集属性约简算法，并验证其有效性；最后应用此算法 武汉理工大学硕士学位论文 应用于流域站网数据中，为流域数据的约简提供一种新的可行方法。 论文研究内容结构如图1 1 所示。 研究背景和意义 i i 文献回顾 l l l 粗糙集理论相关概念和属 粒子群算法及其改进l i 性约简方法 ii 粗糙集属性约简的粒子群算法优化 l li 适应 编码 度函粒了 粒了 设计 数设 更新 编码 计 转化 iill i 基于量子粒子群算法的粗糙集 属性约简模型 工 模型验证 i 改进的模型在水文监测站优选 中应用 工 结论与展望 1 2 国内外研究现状 图1 1 论文结构图 1 2 1 流域数据挖掘研究现状 对于流域数据挖掘的研究现在主要集中在径流预测、洪水预报和水库调度中。 上世界九十年代，k a r u n a n i 廿l in 将人工神经网络模型尝试性地应用于河道洪水 演算3 4 1 ；龚政，张东生等针对长江南京段的水文观测资料，采用b p 神经网络对 河流水位进行预测，结果表明b p 神经网络混合训练了多种影响因素，预测效果 武汉理工大学硕士学位论文 比常用的线性相关方法要好【3 5 】；王玲，黄国如采用聚类方法将径流序列分成几 部分，分别用神经网络建立子模型，然后将这些子模型合成一个总的预报模型， 模型表现出更加优良的性能，较大地提高了径流模拟的精度【3 6 j ；覃光华、丁晶 等在构造时序样本的时候引入遗忘因子和期望因子，分别反映了对时间较远的 资料的遗忘和对近期预测的期望，以此构造了新的神经网络预报模型，模型具 有敏感功能，模型的应用可以对资料信息有更充分的利用眵7 】；刘招、黄强等针 对水电站水库最优出力问题，应用可变精度粗糙集进行知识发掘，得了到出力 决策规则。这种基于粗糙集的规则隐含了决策时段以外的入库水量信息，不仅 考虑当前时段水库来水和水位，还综合以前的数据进行决策的常规优化调度， 具有更大的灵活性和合理性【3 8 1 。杨道辉、马光文等将粒子群优化算法用于b p 网 络模型的训练，对模型参数进行优化，优化后的模型有更好的收敛速度和精度眇j 。 徐松，陈守伦，梁伟将模拟退火粒子群算法应用在在水电站中长期优化调度中， 以洪家渡水电站为例进行了实验，结果表明改方法可以应用于非线性水库优化 调度问题，结果精度高、收敛速度快，为解决水电站中长期优化调度问题提供 了一种有效的方法 4 0 1 。 1 2 2 粗糙集理论研究现状 粗糙集理论由波兰数学家p a w l a k z 在1 9 8 2 年提出，他在粗糙集的数学性质 与逻辑系统上进行了深入的分析，但是最初很多的研究成果发表在了波兰的学 术期刊上，粗糙集在在国际上并没有得到广泛的关注。1 9 9 1 年p a w l a k 出版了专 著( ( r o u g hs e t ：t h e o r e t i c a la s p e c t so fr e a s o n i n ga b o u td a t a ) ) 1 4 5 j p a w l a k 在书中 将粗糙集理论的相关概念和只是进行了系统详细的阐述，这本专著起到奠定粗 糙集理论数学基础的作用，从此开始了粗糙集研究的热潮。1 9 9 2 年波兰召开了 第一届国际粗糙集理论研讨会，从此世界上每年都会召开以粗糙集理论为主题 的国际会议，这极大促进了粗糙集理论的发展。1 9 9 6 亚洲地区的第一次粗糙集 理论研讨会在日本东京召开，这次国际粗糙集研讨会促进了亚洲地区粗糙集理 论的研究与应用。 从粗糙集理论提出到现在的3 0 年年，学者们在它的理论和应用方面都取得 了大量的成果，粗糙集理论有了快速的发展。国内对粗糙集理论的研究相对较 晚，但是发展是比较迅速的。目前，我国已连续举办了1 1 届“中国r o u g h 集与 软计算学术会议”。2 0 0 1 年我国召开了第一个粗糙集理论方面的全国性的学术研 武汉理工大学硕士学位论文 讨会；2 0 0 3 年，我国第一次国际性粗糙集学术研讨会第九届国际粗集、模 糊集、数据挖掘与粒度计算学术研讨会。二十一世纪以来，许多高等院校和科 研机构都相继对粗糙集理论进行了相关的研究和应用，并取得了一定的研究成 果【4 1 ，4 2 1 。 属性约简是粗糙集理论的核心问题之一，属性约简的目的就是在保持原数据 集合分类能力不变的前提下，在原属性集合中选出一个或多个属性子集来代表 原数据集。属性约简一直是粗糙集理论研究的热点，常用的属性约简算法可以 分为以下三类： 1 ) p a w l a k 数据约简算法。 这是由属性约简的定义得到的算法，它对属性集的所有属性进行考察，从中 选出所有满足条件的属性子集，这种算法是理论指导，但是其具有指数型的时 间复杂性，算法计算时间长，尤其在对属性数目很多的数据集进行约简时计算 量会很大，在实际应用中会有很多限制。 2 ) 基于区分矩阵的约简算法。 由波兰数学家s k o w r o n 提出的区分矩阵是求解属性约简的有力工具，也是 现在研究比较充分的属性约简算法。该算法通过引入代数知识，把对信息系统 的决策表的知识约简转化为对区分矩阵化简问题。h u 等提出了一种求决策表核 属性和属性约简的方法，通过方法得到的差别矩阵，差别矩阵中的单属性元素 就是决策表的核【2 】；杨明提出了一种基于改进差别矩阵的属性约简增量式更新算 法，这种算法对差别矩阵进行快速更新，每次更新求取属性核，同时利用更新 前的约简结果为依据进行计算，提高了属性约简的更新效率【3 】。基于区分矩阵的 约简算法最大的特点是简单、易于实现，但是该算法只能处理数据量较小的信 息系统，对于有海量数据的信息系统计算能力很有限。 3 ) 启发式属性约简算法。 启发式属性约简算法是现阶段学者研究比较多的算法，这类算法以属性重要 度等概念为启发信息，按照各种算法的启发规则对启发信息进行更新，最终得 到属性约简。w a n g 以条件信息嫡为启发信息提出了一种属性约简算法【4 】；h u 将 启发式的思想应用于区分矩阵中，以属性重要性为启发信息，提出了一种属性 约简算法【5 】；王国胤等将信息论引入粗糙集，从不同的角度分析了粗糙集理论的 相关知识，以信息熵为启发信息提出了属性约简算法【6 】；杨明引入了基于条件信 息熵的近似约简这一概念，以此提出基于条件信息熵的近似约简算法，以弥补 基于条件信息熵的属性算法的不足，结果表明此方法可以增强高噪声的能力【7 1 。 武汉理工大学硕士学位论文 有些研究者尝试用随机性的算法来求解最小约简，w r o b l e w s k i 将遗传算法 与贪心算法相结合，提出了一种融合的算法来寻找最小约简【8 】；b j o r v a n d 在 w r o b l e w s k i 的工作基础上将核属性加入到了候选属性集当中，提高了算法的运 行速度和效果唧；z h a i 通过求解上、下近似集将数据集分为确定和非确定数据集， 再应用遗传算法从中提取规则，形成了比较完整基于遗传算法的属性约简算法。 随着粒子群算法的广泛应用，开始有学者将其应用于粗糙集优化中，叶东毅等 将决策表最小属性约简问题转化为0 1 组合优化问题，从而用二进制粒子群算法 进行求解，取得了良好的效果【lo 】；王加阳等提出了一种基于量子粒子群算法的 属性约简算法，并验证算法的效果【l 。 1 2 3 粒子群算法研究现状 受鸟群群体行为的启发，j a m e sk e n n e d y 博士和r u s s e l le h e r h a r t 博士于1 9 9 5 年提出了粒子群算法【1 2 】，该算法概念简单，控制参数少易于实现，自提出以来 就得到广泛关注和应用。i e e e 第一届国际群智能研讨会于2 0 0 3 年召开，此后每 年召开一次，极大促进了粒子群算法的发展。由于粒子群算法在解决复杂组合 优化问题中表现出优越的性能，现已在工程设计与优化、机器人控制、电力系 统和工业生产优化等领域进行了较为成功的应用【1 3 ，1 4 】。 国内外学者对粒子群算法优化改进进行了大量的研究，极大丰富了粒子群算 法，提高了算法的效率。 目前粒子群算法改进主要在一下几方面进行。 1 ) 通过控制参数进行算法优化。 通过控制粒子群算法的参数可以影响粒子移动的轨迹，从而影响粒子搜索区 域，所以可以对算法进行优化。s h i 等对j k e n n e d y 和r e h e r h a r t 提出的经典粒 子群算法进行了修改得到现在广为使用的标准粒子群算法【l5 】；随后c l e r c 和 k e n n e d y 提出了自适应粒子群模型，通过引入收缩因子来达到减小粒子振荡幅度 的效果，从而加速粒子收敛速度【1 6 】；s h i 等提出了一种用模糊规则动态调整惯性 权重方法，实验得出算法比惯性权重线性减小的方法有更好的效果【r 7 】李宁等 采用余弦减小的方法，使惯性权重随着迭代代数变化，也得到了不错的效果【l 引。 2 ) 多样性改进 标准的粒子群算法主要的问题在于早熟，容易陷入局部最优，不能进行全局 的搜索，随着迭代次数的增加粒子种群的多样性降低快。为了避免早熟，一些 武汉理工大学硕士学位论文 学者提出通过控制种群多样性来进行算法的优化。b l a c k w e l l 对多样性进行了度 量，以此为根据对多样性进行控制【1 9 】；t k r i n k 等通过控制粒子的冲突和聚集来 控制多样性，此方法显著提高粒子群算法解多峰函数的性能；x h u 与r e b e t h a r t 提出了多种不同的策略来增强种群多样性，包括种群随机多代初始化思想等， 希望以此来达到防止陷入局部最优的效果【2 0 】。谢晓峰等希望对粒子的速度和位 置的更新进行控制，采用的小概率随机变异的方法，结果表明方法可以增强种 群的多样性，算法因此有了更强的全局搜索能力【2 l 】；s u n 等人在量子力学的启发 下提出了量子粒子群优化算法 2 2 , 2 3 ，随后又将变异操作引入，提出了有变异的量 子粒子群优化算法【2 4 j 。 3 ) 与其它优化算法结合 粒子群算法与其它优化算法如遗传算法、模拟退火算法等的本质目标是一致 的，各种算法的思想原理不同，技术方法也不同，他们各有自己的优势和不足， 不同的优化算法结合在一起往往能有不错的效果。肖琳等借鉴遗传算法中的“杂 交”思想提出了杂交粒子群算法，引入了一个杂交算子，粒子的更新被赋予杂 交概率，保持了粒子的多样性【2 5 1 ；吕振肃等通过引入变异操作提出变异粒子群 算法降低了算法出现早熟现象的危险【2 6 】；高鹰等将混沌优化思想引入到粒子群 算法中，改善了算法的稳定性与适应性【2 7 1 ，随后，又将模拟退火算法引入，同 时加入杂交运算和高斯变异操作，提出了一种混合粒子群算法【2 引。另外， a l a v a n d a r 2 9 1 、o l e s e n 3 0 等提出将细菌趋药性算法与粒子群算法混合；s h u 3 1 1 、 x i n 3 2 】等提出将差分进化算法与p s o 进行混合策略；k a v e h l 3 3 1 等提出将p s o 与 蚁群算法进行混合等。 1 2 4 复合粗糙集理论和粒子群算法在流域信息分析中的应用现状 粗糙集理论和粒子群算法经过这么多年的研究和应用，但是粗糙集理论和粒 子群算法的结合方面的研究还不多，其在流域信息分析中的应用就更少了，但 是已经有学者将两者分别应用于流域信息的分析中。 吴佳文，王丽学，汪可欣将粗糙集理论应用于年径流预测中，建立基于粗糙 集理论的预测模型，从预测建模、数据筛选和决策规则生成的全过程表明了应 用粗糙集理论进行年径流预测的可行性【4 9 】。史旭明将粗糙集属性约简应用于气 象预测因子的约简中，用约简后的预测因子通过模糊神经网络预测对降水量进 行了预测【5 。粒子群算法在流域信息分析中的应用主要集中在与其它方法结合 武汉理工大学硕士学位论文 解决问题的方面。杨道辉，马光文，杨梅应用粒子群算法对小波人工神经网络 的训练进行优化，用于水电站径流预测中，算法具有原理简单、实用性强的特 点，提高了预测精度【5 1 1 。刘晋，黄强等将粒子群算法应用在水位流量关系拟合 中，对于拟合结果同传统优化方法和遗传算法进行了对比分析，结果表明粒子 群算法更简便、更实用【5 2 1 。王丽学，王丽娜等基于粒子群算法寻优选择，构建 了基于粒子群算法的支持向量机模型，应用于大伙房水库月径流预测中，与没 有粒子群优化的支持向量机模型进行了结果对比，该模型收敛速度快、预测精 度高【5 3 1 。 1 3 论文组织结构 本文对应用粗糙集方法对流域数据进行约简这一问题进行研究，引入粒子群 算法对粗糙集属性约简进行优化，得到新的属性约简模型，并将模型应用于流 域数据约简中。 第一章：主要介绍本文的研究背景和意义、研究内容和粗糙集理论和粒子群 算法的国内外研究现状。 第二章：介绍了粗糙集理论和粗糙集属性约简算法，粗糙集理论详细介绍了 信息系统与不可分辨关系、不精确范畴、上下近似集、属性约简与属性核等； 属性约简算法着重介绍了三类算法，分别是基于区分矩阵的约简、基于启发信 息的约简和基于遗传算法的约简，分析了各种算法的优缺点；最后介绍了一种 求属性核的算法。 第三章：介绍了粒子群算法的基本原理和基本粒子群算法的算法流程，给出 了粒子群算法的两种主要改进方法，参数改进和邻域结构改进，最后介绍了适 于粗糙集方法的二进制粒子群算法和量子量子群算法。 第四章：利用量子粒子群算法对粗糙集属性约简方法进行优化，主要解决了 粒子编码设计、适应度函数设计、粒子更新设计和粒子编码转化设计，得到基 于量子粒子群算法的粗糙集属性约简模型。随后通过实例信息系统和u c i 标准 数据集对模型的正确性进行了验证。 第五章：应用基于量子粒子群算法的粗糙集属性约简模型对流域流量数据进 行了约简，并对约简结果进行了模拟验证。 第六章：对论文的成果和创新点进行总结，并提出研究的不足和改进方向。 武汉理工大学硕士学位论文 第二章粗糙集基本理论和属性约简算法 粗糙集是一种处理模糊和不确定性知识的数学工具，它的主要思想是在保 持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则【4 1 1 。目 前，粗糙集理论已经在一些领域得到成功的应用，如模式识别、机器学习、决 策支持、预测建模等。流域数据拥有数据量大、存在不确定性的特点，粗糙集 理论的特性可以使其应用于流域数据挖掘和约简中，得到约简后的流域数据集。 本章首先介绍粗糙集理论的基本概念和属性约简的方法。 2 1 粗糙集基本理论 2 1 1 信息系统与不可分辨关系 定义2 1 设四元组胆( 以a ，kd 为一个信息系统。其中泸缸l ，x 2 ，x 3 ，) 且u ：o 为我们感兴趣的对象组成的有限集合，成为论域，u 中元素称为对象； 彳= 口，a 2 ，a 3 ，) 且彳仍为属性的有限集合，么中的元素称为属性；f 是u 和 彳的关系集合，也称为信息集，即庐 7 ：汕吲脚) ，其中k 为口，( 脚) 的值域。 信息系统是数据库的抽象描述。在信息系统中的关系集合f 是非常重要的，它 是对象集与属性集之间的纽带，也是知识发现的基础。在信息系统s 中，属性 集合彳如果由条件属性集合c 和决策属性集合d 组成，即a = c u d ，且c o d = o ， 则信息系统s 称为决策信息系统或决策表，记为胆( 以c u d ) ，其中决策属性通 常只有一个，即胆( 以c u d ) ，其中d 为决策属性。 表2 1 信息系统实例 武汉理工大学硕士学位论文 表2 1 给出了一个信息系统s ，其中论域泸扛l ，沈，x 3 ，弘，z 5 ，粕) ，属性集合 a = a l ，a 2 ，a 3 ，田，如果条件属性集合c = a l ，a 2 ，a 3 ) ，决策属性集合胪 田，那么 信息系统肛( uc u d ，以刃就是一个决策表，可以得到属性值域圪1 = l ，2 ，3 ， = 1 ，2 ) ，v a s = 1 ，2 ) ，信息函数舷l ，a 1 ) = 3 ，瓜5 ，a o = 2 。 定义2 2 不可分辨关系是粗糙集理论中一个重要的概念。在信息系统p ( 配a ， 圯用中，属性集彳的任意子集占定义论域u 上的一个二元关系r s ，工f ，而r s 。 给定属性集b ，如果对于任意a e b ，口0 f ) = 口( 动，则而与x s 不可分辨，其中 表示元素x 对于属性a 的属性值，记为胎= o b 劫胁d 嘲( 劫( a ，动。显然舶表 示等价关系，舶所有等价类的集合记为u r 曰。 不可分辨集被称为基本集，对于表2 1 中的实例，属性子集 口j 定义的三个 基本集为 r e , x 6 ) ， x e , x z , x s 和 拗) ；属性子集 ，) 定义的基本集为 x j ) ， x 2 , x s , x ， x s 和 粕) 。 如果g f 瑚属于关系如，那么而，而记为b 不可分辨，关系如的等价关系定 义为b 基本集。 2 1 2 不精确范畴、近似与粗糙集 令雁u ，当x 能用属性子集k 确切描述，即x 是属性子集k 所确定的u 上的不分明集的并时，称x 是k 可定义的，否则称z 是k 不可定义的。k 可定 义集也称k 精确集，k 不可定义集称作k 非精确集或k 粗糙集。 提出两个精确集，它们是上近似( u p p e ra p p r o x i m a t i o n ) 和下近似( 1 0 w e r a p p r o x i m a t i o n ) ，我们可以用上近似和下近似来对粗糙集进行定义。 定义2 3 给定信息系统辟( 以a ，圪用，给定任意子集x g u 和一个不可分表 关系足，x 的上近似集和下近似集可用r 的基本集定义如下： r x = u ( yev ri y 研 一r x = 1 9 ( y v rl ynx = 西) 集合b n r 0 0 = 再弘舣称为x 的尺边界域；p o s r ( x j l - - r x 称为肖的尺正域； n e g r ( x ) = u - - r x 称为x 的尺负域。显然： r x = p o s u ub r 必或p o s r ( x ) 是u 中根据不可分辨关系尺得到的肯定属于z 的元素组成的 集合；砝是u 中的元素根据不可分辨关系r 判断出可能属于x 的元素集合； b n r ( x ) 是u 中的元素经过不可分辨关系r 判定，不能肯定属于x 同时不能肯定 武汉理工大学硕士学位论文 属于描( 即u - x ) 的元素集合；n e g r ( x ) 是u 中的元素根据不可分辨关系判定肯 定不属于x 的元素集合。粗糙集的概念图如图2 1 所示。 e o s j ( x ) 图2 1 粗糙集概念示意图 以表2 1 所示的信息系统为例，令r = a 2 ，a 3 ，片缸j 殉加) ，由不可分辨关 系尺导出的等价类为 x j ， x 2 , x 3 , x 4 ， x s 和 ) ，x 的尺下近似集幽，_ x j 扔) ， x 的上近似集r x = x i , x 2 , x 3 , x 4 , x 5 ) ，b n x ) = x 2 , x 3 , x 4 ，n e g