（计算数学专业论文）粗糙集数据挖掘方法及其在相关决策问题中的应用.pdf

中n 民航大学硕士学位论文 摘要 数据挖掘是从数据库中抽取隐含的、以前未知的、具有潜在应用价值的信息的过程。 粗糙集理论是一种用于处理不确定性和含糊性知识的数学工具，由于其本身具有的一些 特点，比如它采用数据驱动的方法、无需任何辅助信息、易于处理离散数据并容易与关 系型数据库相融和等，因此特别适合于知识发现和数据挖掘的任务。 本文首先深入研究了粗糙集数据挖掘中的决策表约简问题，包括属性约简和属性值 约简。关于属性约简，在总结现有约简方法的基础上，改进了一种基于区分矩阵的属性 约简算法，又将粗糙集理论与智能算法相结合，提出了一种基于蚁群优化算法的属性约 简方法。其次，在值约简方面，提出了一种较快捷的基于属性值重要性排序的值约简方 法。粗糙集模型扩充方面，主要讨论了不完备信息系统及其属性约简问题，给出了一个 基于遗传算法的属性约简方法。 最后，根据前几章的讨论，设计实现了一个粗糙集数据挖掘系统模型，并将该模型 应用于基于b s 结构的飞行机组人为差错防范训练系统中。该模型系统具有良好的人机 交互界面和通用性，涵盖了数据挖掘的一般过程，具有一定的实际应用价值。 关键词：粗糙集，数据挖掘，属性约简，属性值约简，遗传算法，蚁群优化算法 中国民航大学硕士学位论x a b s t r a c t d a t am i n i n gi sap r o c e s si nw h i c hh i d d e na n dp r e v i o u s l yu n k n o w ni n f o r m a t i o nw i t h p o t e n t i a la p p l i c a t i o nv a l u ei se x t r a c t e df r o md a t a b a s e r o u g hs e tt h e o r yi sam a t h e m a t i ct o o l f o rd e a l i n gw i t hu n c e r t a i na n da m b i g u o u sk n o w l e d g e i ti sv e r ys u i t f u lf o rk n o w l e d g e d i s c o v e r ya n dd a t am i n i n g ，f o rt h er e a s o n ，i th a ss o m ec h a r a c t e r i s t i c s ，s u c ha st h em e t h o do f d a t ad r i v i n g , w h i t h o n ta n ya u x i l i a r yi n f o r m a t i o n i na d d i t i o n ，i ti se a s yt od e a lw i t hd i s c r e t e d a t aa n df u s ew i t hr e l e v a n td a t a b a s ee t c f i r s t l y , d e c i s i o nt a b l er e d u c t i o ni nt h ep r o c e s so fd a t am i n i n g , i n c l u d i n ga t t r i b u t e r e d u c t i o na n da t t r i b u t ev a l u er e d u c t i o n ，i ss t u d i e di nt h i st h e s i s a b o u ta t t r i b u t er e d u c t i o n ，a k i n do fa l g o r i t h mb a s e do nd i s c e r n i b i l i t ym a t r i xi si m p r o v e dt h r o u g hc o n c l u d i n gt h ep r e s e n t r e d u c t i o nm e t h o d s f u r t h e r m o r e ，t h er e d u c t i o na l g o r i t h mb a s e do na n tc o l o n yo p t i m i z a t i o n a l g o r i t h mi sp u tf o r w a r db yc o m b i n gr o u g hs e tt h e o r yw i t hi n t e l l i g e n ta l g o r i t h m s e c o n d l y , a b o u ta t t r i b u t ev a l u er e d u c t i o n ，ak i n do fr a p i dm e t h o di sa l s op u tf o r w a r di nt h i st h e s i s ，w h i c h i sb a s e do no r d e r i n go nt h ei m p o r t a n c eo fa t t r i b u t ev a l u e t h e ni tm a i n l yd i s c u s s e sa t t r i b u t e r e d u c t i o no ft h ei n c o m p l e t ei n f o r m a t i o ns y s t e ma n d # v e sa t t r i b u t er e d u c t i o nm e t h o db a s e do n g e n e t i ca l g o r i t h mi nt h ef i e l do fr o u g h s e tm o d e le x t e n s i o n f i n a l l y , ad a t a m i n i n gm o d e lb a s e do nr o u g hs e ti sd e s i g n e di nt e r m so ft h ed i s c u s s i o ni n t h ef o r m e rc h a p t e r s a l s o ，t h em o d e li sa p p l i e di nm i s t a k e - p r e v e n t i n gt r a i ns y s t e mb a s e do n b ss t r u c t u r ef o rf l i g h tc r e w n em o d e ls y s t e mh a se x c e l l e n th u m a n - m a c h i n ei n t e r f a c ea n d g e n e r a lf e a t u r e ，i nw h i c ht h en o r m a lp r o c e s sa b o u td a t am i n i n gi si n c l u d e d i ti sv e r i f i e dt o h a v ea p p l i c a t i o nv a l u ei np r a c t i c e r o u g hs e tt h e o r y , d a t am i n i n g , a t t r i b u t er e d u c t i o n , a t t r i b u t ev a l u er e d u c t i o n , g e n e t i ca l g o r i t h m ，a n tc o l o n yo p t i m i z a t i o na l g o r i t h m n 中国民航大学硕士学位论文 中国民航大学学位论文独创性声明 人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知， 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中国民航大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 中国民航大学学位论文使用授权声明 中国民航大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件 和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内 容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全 部或部分内容。论文的公布( 包括刊登) 授权中国民航大学研究生部办理。 研究生签名：刻座堑导师签名：理氢墨日期：塞煎! 呈：蛋 中国民航大学硕l ：学位论文 1 1 论文选题背景与意义 第一章绪论 随着信息技术的高速发展，数据库应用的规模、范围和深度在不断扩大，使得无论 是商业企业、科研机构或是政府部门，都在很短的时间内积累了海量的、以不同形式存 储的数据资料。由于这些数据资料十分繁杂，仅仅依靠传统数据库的检索查询机制己远 远不能满足现实需要，它迫切要求自动地和智能地将待处理的数据转化为有用的信息和 知识，从而达到为决策服务的目的。数据挖掘正是为迎合这种需要而产生并迅速发展起 来的用于开发信息资源的一种新的数据处理技术。 数据挖掘( d a t am i n i n g ，d l v l ) 是数据库中的知识发现( k n o w l e d g ed i s c o v e r y i n d a t a b a s e ，k d d ) 过程中的关键步骤，它是从大型数据库或数据仓库中提取人们感兴趣的知 识的高级处理过程，这些提取的知识是隐含的、事先未知的、潜在有用的信息，可以表 示为概念、规则、模式等形式。数据挖掘融合了数据库技术、人工智能、机器学习、统 计学、知识工程、面向对象方法、信息检索、高性能计算以及数据可视化等最新技术的 研究成果n 一。在数据挖掘中，所存储的数据往往含有大量冗余或不完整的属性，严重降 低了数据挖掘的时间效率和质量，因此如何删除冗余属性，简化知识的表达，是一个极 具挑战性的工作。 近年来，粗糙集理论在数据挖掘与知识发现方面得到了广泛的发展和应用。粗糙集 理论与其它处理不确定性问题理论的最显著区别是它无需提供问题所需处理的数据集 合之外的任何先验信息，而是直接从给定问题的描述集合出发，通过不可区分关系和不 可区分类确定给定问题的近似域，从而找出该问题的内在规律嘲。其主要思想就是在保 持信息系统分类能力不变的前提下，通过知识的约简，导出问题的决策或分类规则。这 种思想和方法给数据挖掘注入了新的生命力，大大促进了数据挖掘的发展，并在实际应 用中取得了较好的效果，为人们做出正确的决策提供了很大帮助，具有较为广泛的应用 前景。 1 2 粗糙集理论的发展及研究现状 经典逻辑中只有真、假二值，但实际上有大量含糊现象存在于真、假二值之间。早 在1 9 0 4 年，谓词逻辑的创始人g f r e g e 就提出了含糊( v a g u e ) - - 谊- ，并把它归结到边界区 域，也就是说在全体论域上存在一些个体既不能在某个子集上被分类，也不能在该子集 的补集上被分类。 中国民航大学硕士学位论文 1 9 6 5 年，l a z a d e h 创立了模糊集合( f u z z ys e t ) 论，不少理论计算机科学家和逻辑 学家，试图通过这一理论解释g f r e g e 的含糊概念，但该理论并没有给出明确的数学公式 描述这一模糊概念，所以无法计算出边界上具体的含糊元素的数目。 1 9 8 2 年，z p a w l a k 针对g f r e g e 的边界思想提出了粗糙集( r o u g hs e t ) ，他把那些无法 确认的个体都归属于边界域，而这种边界域被定义为上近似集与下近似集之间的差集， 由于上近似集和下近似集都可以通过等价关系给出确定的数学公式描述，所以含糊元素 数目可以被准确的计算出来，即在真、假二值之间的含糊程度可以计算，从而实现了 g f r e g e 的边界思想。 粗糙集自提出以来就一直得至l j z a d e h 的重视，并给予很高评价，他将粗糙集与模糊 逻辑、概率推理、神经网络、混沌理论、遗传算法及其他进化优化算法等一起列为他所 新提倡的各种软计算的基础理论。 1 9 9 1 年，p a w l a k 的专著( r o u g hs c t s - 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 ) 4 1 的问世，标志着粗糙集理论及其应用研究进入了活跃期。1 9 9 2 年，第一届关于粗糙集理 论的国际学术会议在波兰召开；1 9 9 3 年在加拿大召开了第二届粗糙集与知识发现国际研 讨会；1 9 9 4 年在美国召开了第三届粗糙集与软计算国际研讨会；1 9 9 6 年在日本召开了第 四届粗糙集、模糊集与机器发现国际研讨会；1 9 9 7 年在美国召开了第五届粗糙集与软计 算国际研讨会；1 9 9 8 年在美国召开了第六届粗糙集、数据挖掘与粒度计算国际研讨会； 1 9 9 9 年在日本召开了第七届粗糙集、模糊集、数据挖掘与软计算国际研讨会；2 0 0 1 年在 日本召开了第八届粗糙集理论与软计算国际研讨会。除上述国际研讨会外，每两年一届 的粗糙集与当前的计算发展国际会议至今已举办了五届。 国内各高校和科研机构从上世纪9 0 年代后期开始了对粗糙集理论的研究。1 9 9 6 年， 我国出版了第一部旨在介绍粗糙集理论的专著。2 0 0 1 年5 月在重庆召开了中国第一届粗 糙集与软计算学术研讨会；2 0 0 2 年9 月在苏州召开了第三届粗糙集会议；2 0 0 3 年5 月，在 重庆召开了第九界粗糙集、模糊集、数据挖掘与软计算国际研讨会。近年来，粗糙集理 论己逐渐引起国内计算机科学界和数学界的关注，相信会有越来越多的学者投入到该领 域的研究中来。 目前对粗糙集理论的研究主要集中在以下几个方面： l 、粗糙集的数学性质研究方面包括粗糙集的代数结构和拓扑结构等。与数学理论 的结合使得一些新的概念己经出现，如“粗糙理想 和“粗糙半群嘲等。 2 、粗糙集理论拓展的研究，包括： ( 1 ) 关系的推广。如基于相似关系的粗糙集模型、基于一般二元关系的粗糙集 模型，另外将对象所在的等价类看作该对象的一个邻域，从而推广导出基于邻域算子的 粗糙集模型；结合模糊集理论将粗糙集理论进行拓展，如将普通关系推广成模糊关系或 模糊划分而获得模糊粗糙集模型等。 ( 2 ) 近似空间的拓展。如变精度粗糙集和概率粗糙集模型等； ( 3 ) 基于布尔代数的粗糙集模型。在综述文献 5 中提出了基于布尔代数粗糙集 2 中国民航大学硕t 学位论文 模型的概念。文献 6 则以布尔代数为基本系统，对几种基于此系统方法的拓展进行了 简单研究。 3 、粗糙集的公理化研究。文献 7 从拓扑的角度给出了含有6 条公理的公理组来刻 画粗糙集，文献 8 从公理组中公理独立性的角度研究，对文献 7 中的公理进行了简化， 去除了部分公理。 4 、粗糙集与其它软计算方法的联系与融合，包括与模糊集、证据理论等的关系p 1 ， 与遗传算法以及其它智能算法的融合等n 。 5 、基于粗糙集的逻辑研究吸引了众多的学者。粗糙集理论的创始人p a w l a k 定义了 “粗糙逻辑一和“决策逻辑 的概念，通过粗糙逻辑中的“真 、“假 、“粗糙真、 “粗糙假和“粗糙不一致 来研究决策逻辑，关于这方面的内容可参见文献 1 1 。 6 、连续属性离散化研究。由于粗糙集理论只能处理离散数据，因此对于连续属性 要进行离散化。n g u y e nsh 等作了很多这方面的工作n 2 1 ，他强调离散化在粗糙集中有自 身的特点，即要求一致化离散，他还将布尔逻辑引入到离散化中，以获得所有可能的离 散化结果。 7 、约简算法的研究。属性( 值) 约简是粗糙集理论的核心内容之一。文献 1 3 从定 义属性重要性出发对约简进行了研究，文献i t 4 则提出了属性约简的简单遗传算法方 法，文献 1 5 基于差别矩阵提出了一种混合遗传算法方法，文献 1 6 讨论了动态约简。 粗糙集理论的生命力在于它的实用性，从诞生到现在不过2 0 多年，就已经被广泛应 用到许多领域，主要包括： l 、将粗糙集应用于股票数据分析。文献 1 7 用粗糙集方法分析了十年间的股票历 史数据，研究了股票价格与经济指数之间的关系，获得的预测规则得到了华尔街证券交 易专家的认可。 2 、将粗糙集应用于医疗临床诊断阳。粗糙集方法可以根据以往的病例归纳出诊断 规则，特别是发现一些医生没有预料到的规则，用来辅助诊断新的病例。 3 、粗糙集在国际关系上的应用。文献 1 9 用粗糙集方法建立了以色列、巴勒斯坦、 约旦、埃及、叙利亚和沙特阿拉伯六个国家关于中东合并问题的基于各自立场的谈判模 型。 4 、粗糙集在人工神经网络中的应用。人工神经网络具有并行、高度容错和泛化能 力强的特点，但当样本较多时，训练时间过长，文献 2 0 应用粗糙集简化训练样本数据 集，大大提高了训练速度。 5 、粗糙集在智能控制中的应用乜。实际系统中有很多复杂对象难于建立严格的数 学模型，因而传统的数学模型控制方法难以奏效。模糊控制模拟人的模糊推理和决策过 程，将操作人员的控制经验总结为语言控制规则，取得了较好的控制效果。 6 、在知识发现和数据挖掘中的应用1 。h uxh 等将面向属性的归纳与粗糙集结合 起来用于知识发现，首先用面向属性的概念树爬升技术对属性进行泛化，然后用粗糙集 方法进行属性约简并生成规则。 3 中国民航大学硕士学位论文 7 、在模式识别3 、图像处理嘲1 、决策分析嘲、工程数据分析哺1 和故障诊断旧1 等许 多方面的应用。 目前国际上研究粗糙集的一些高校和研究机构开发了些粗糙集的模型系统甚至 实用系统。波兰华沙大学和挪威科技大学联合开发了一个基于粗糙集理论框架的数据分 析工具包r o s e t t a ，包括数据的预处理、属性约简和规则产生以及对所得规则的验证和分 析，实现了对数据挖掘和知识获取的支持。美国肯萨斯大学开发的一套基于粗糙集的经 验学习系统l e r s ( l e a m i n gf r o me x a m p l e sb a s e do nr o u g hs e t s ) 己被美国国家航空航天 管理局( n a s a ) 的j o h n s o n 空间中心采用。除上述经典系统外，研究人员还开发了很多其他 粗糙集系统，如波兰工业大学的r o s e ，挪威t r o l ld a t ai n c 的r o u g he n o u g h 和加拿大 r e g i n a 大学的k d d r 等。 1 3 粗糙集理论基础3 町 在粗糙集理论中，研究的领域称为论域，对论域的全部知识均来自对通过观察、测 量等手段获得的数据的划分。为了数据分析的方便，通常将这些数据表示为二维数据表 的形式。表由行和列组成，每一行代表一个数据对象，每- - n 代表对象的一个属性，这 样的表称为知识表达系统，有时也称为信息系统。 定义1 3 1 称四元组s = ( u ，a ，v ，厂) 是一个知识表达系统，其中u 表示对象的 非空有限集合，称为论域；a 为属性的非空有限集合：v f f iu k ，圪表示属性口的值 d 域；厂：u a _ y 是一个信息函数，它为每个对象的每个属性赋予一个信息值，即 v x e u ，a a ，有厂 ，口) 屹。 定义1 3 2 知识表达系统s1 ( u ，a ，v ，厂) ，r 是属性集a 的一个子集，满足 g r a ，定义尺上的不可区分关系i v d ( r ) 为： i n d ( r ) 1 o ，y ) 【，ui c a 尺，o ，口) 一f ( y ，口) 显然，v x ，y ，z u ，i n d ( r ) 满足： 自反性：o ，x ) s i n d 僻) ； 对称性：o ，y ) e i n d 俾) 辛( y ，x ) i n d 僻) ； 传递性：o ，y ) e i n d 俾) 且( y ，z ) e i n d 俾) 净 ，z ) i n d 僻) 。 因此，i n d 俾) 是一个等价关系。在不致引起混淆的情况下，i n d 似) 可简记为r 。 不可区分关系是粗糙集理论的基础，它体现了这样的事实：由于可获得的信息和数 据的不完备，使得我们缺乏足够的知识去区分论域中的某些数据对象。在粗糙集理论中， 将这种具有相同的信息而无法区分的数据对象的集合称为不可区分类。 定义1 3 3 知识表达系统s 一( u ，a ，v ，厂) ，t o o ( r ) 是其上的一个不可区分关 系，v x e u ，称i x 且一 ) ，ul ，y ) i n d 僻) ) 为尺的不可区分类( 或等价类) 。 4 中国民航大学硕士学位论文 i n d ( r ) 在u 上形成的所有不可区分类的集合 墨，x ：，x 。 满足： 五一g ，f = 1 2 ，玎； 置nx = 1 2 i ，f 乒j ，1s f ，_ sn ； n u 五一u 。 i - 1 从而该集合构成了个对论域u 的划分，记为v i n d ( r ) ( 或简记为u r ) 。 性质1 1 论域u 上的不可区分关系与u 上的划分一一对应。 证明：设尺是u 上的不可区分关系，慨u ，记 k ki 忸，e ui ，工，) e n d ( r ) 因为“，x ；) e i n d ( r ) ，所以毛k 】足，从而k 】矗一彩。当x j k k 时，对辟，k ， 有“，x ，) e i n d ( r ) 和o ，x k ) e i n d ( r ) 成立，从而 ，& ) 肋俾) ，故x k k k ，于是 k k k ，同理可证【鼍k b j 且，从而【鼍k p j 】置。当x ，斜葺k 时，“，z ，) q 苣i n d ( r ) ， 故薯盛b f k ，于是k 】r n x 小- 0 。又显然u k k - - u 。综上，j 5 c 产生u 上的一个划分。 而t 副 反之，设x 一，x ：，以) 是u 的一个划分，令r = “，z ，) i 毛互，z f 以】，易证r 是u 上的不可区分关系，且当鼍互时，【薯k 一五。 性质1 2 【乩。= n x l 。 口匕k 性质1 3 若4 4 么，则对v x e u ，p l p k 扛k 。 对于u 上的两个不可区分关系i n b ) ，i n d ( c ) 及其对u 的划分u b ，u c ，若对 坛u ，有b l b 】c ，则u 曰与u c 之间存在偏序关系，称u b 为较u c 更精 细的划分，记为【厂曰_ ) ，nc n 一0 ，由引理2 3 知p o s c 。p ) 一p o s c ( d ) ，再由约简的定义 ，j 知必存在b c ，使b 是c 的d 约简，显然口岱b ，这与a e c o 髓o ( c ) 相矛盾。 充分性若存在c o = 忙 ，由定义2 4 2 知瓴，x j ) 岱i n d ( d ) ，且薯，x j 中至少有一个 属于p o s c ( d ) 。设薯e p o s c p ) ，则【薯l 一 x j l ，i x , 】c 唯 ii x ，】c 一 4 ，故而岳p 傩c 一 。，( d ) ， 从而p o s c 4 。 p ) 一p o s c ( d ) ，因此a e c o 船o ( c ) 。 表2 3 决策表s 的区分矩阵( 按定义2 4 2 )表2 4 决策表s 的区分矩阵( 按定义2 4 1 ) 刃 口，埘1 2 j 对称 1 2 jo力 c 1 2 j p ，c ) g gf 2 j乃 口，b ，c ) 彩 p 彩彩gf 2 if 2 j 乃 和，6 ) 彩对称 p ) 彩彩 c 口，b ，c p ，c 彩 和，6 乃9 口，b ，c 彩 p ) i 2 j彩 p ，c 彩f 2 j 重新考察例2 1 ，由定义2 4 2 得其区分矩阵如表2 3 所示，仍按s k o w o r n 方法便 可得到正确的约简p ，c ，核也为p ，c ) 。作为对比，按定义2 4 1 的区分矩阵如表2 4 所 示，显然表2 3 中矩阵的非空元素比表2 4 和表2 2 中矩阵的非空元素都要少。由以上 的分析显然可见，如果一个不相容决策表的不相容程度很大时，这种方法构造的区分矩 阵的非空元素将会大大减少，从而减少算法运行的时间和空间复杂度。 2 4 3 基于改进区分矩阵的属性约简算法 经典的s k o w o r n 方法在区分矩阵的基础上，将矩阵非空元素的合取范式转化为极小 析取范式的过程是相当复杂的，近年来主要是依靠人工转化，而不便于在计算机上编程 实现。为便于实际应用，本文提出一种基于改进区分矩阵的启发式属性约简算法。 算法2 5 基于改进区分矩阵的启发式属性约简算法 输入：决策表s - ，c u d ，y ，) 。 输出：属性核c 锨e ，一个约简尬d 步骤l ：初始化僦= 囝，r 四= 彩； 步骤2 ：由定义2 4 2 求决策表的区分矩阵m - 如) 。； 步骤3 ：检查v 勺一0 的项，若ic i = 1 ，则僦一c o r e u 如 ； 步骤4 ：v 勺一f 2 i ，如果c 0 1 胚n 勺一f 2 j ，则令勺lf 2 j ；否则计算勺中各属性出现的 频数； 中国民航入学硕士学位论文 步骤5 记频数最大的属性为g ，若v c f a ，停止并输出r e d = c o r e ；否则 c o r e = c o r e u c k ，转步骤4 。 2 4 4 实例分析 我们以发表在 p o p u l a rs c i e n c e ) ) 上的c n 己( c 缸t e s tr e s u l t s ) 数据库为例进行试验。 该数据库含有九个条件属性c = c 1 ，c 2 9e 9 c 9 ，一个决策属性d ，共有2 l 条记录。设 u i “，而，x 2 。 ，按照算法2 5 ，当执行完步骤3 后得到c o r e = c 4 ，c 9 ) ，执行步骤4 划去区分矩阵中包含c 4 或c 9 的项后，仍存在白一g ，此时加入频数最大的属性为c 1 ，再 执行步骤4 ，加入频数最大的属性c 5 后，便得到一个约简r e d 一 c 1 ，c 4 ，c 5 ，c 9 ) ，它与用定 义得到的约简相一致。 2 5 基于蚁群算法的属性约简方法 2 5 1 蚁群优化算法( a c o ) 简介汹例 由意大利学者md o r i g o 等人提出的蚁群优化算法是受真实蚂蚁集体觅食行为的启 发而发展起来的一种群体智能算法。研究发现，单只蚂蚁的能力虽然有限，但大量蚂蚁 在觅食时，每只蚂蚁都能在其经过的路径上释放一种特殊的分泌物一信息素。当它们碰 到一个还没有走过的路口时，就随机的挑选一条路径前行，同时释放出与路径长度有关 的信息素，使得其余蚂蚁倾向于朝着该物质强度高的方向移动，某条路径上经过的蚂蚁 数越多，其上留下的信息素的量就越多，后来蚂蚁选择该路径的概率也越高。这样就形 成了一种正反馈机制，使得蚁群能在较短时间内找到蚁巢与食物源之间的最短路径。同 时整个蚁群还能够适应环境的变化，当蚁群的运动路径上突然出现障碍物时，蚁群也能 够很快地重新找到最优路径。模拟蚂蚁群体觅食行为的a c o 算法具有分布式控制、多 主体和潜在并行性的优点，因此特别适合大型复杂问题的求解。 蚁群算法最经典的应用是寻求旅行商问题f r s p ) 的最优解。b p 的简单描述是：给 定厅个城市，一个旅行商从某个城市出发，访问各城市一次且仅一次后再回到原出发城 市，要求找出一条最短的巡回路径。已经证明t s p 是一个典型的n p 问题，用全局搜索 算法精确的求出其最优解几乎是不可能的，而必须采用启发式搜索算法，在可以接受的 时间内寻找最优解。t s p 具有广泛的代表意义和应用前景，许多现实问题均可以抽象为 t s p 的求解问题。 我们以求解t s p 的流程来说明蚁群优化算法的基本框架，如图2 1 所示。对该模 型稍做修正，便可应用于其它问题。 1 6 中国民航大学硕士学位论文 初始化：n - - o ，各路径信息素仁常数，将m 只蚂蚁随机放在u 个城市上，对所有蚂蚁置其初始禁忌表t a b u = f 2 j 上 一对每只蚂蚁计算其转移概率，利用“轮盘赌”选择下一个城市j ，并将城市j 加入各自的t a b i l 表1 一 上 更新每只蚂蚁经过的各条路径上的信息素 上 in o t a b u 是否已满? 上s 输出本次搜索的最优路径 上 ii 是否到达最大设定循环次数n ? 卜、 n o 清空t a b u 表，n + i 输出最短路径，结束 i 一。 图2 1 蚁群优化算法( a c o ) 求解t s p 流程图 2 5 2 基于蚁群优化算法的属性约简 根据a c o 算法流程的基本框架，结合属性约简的特点，对含n 个条件属性的决策 表s 一，c u ，v ，厂) ，我们将属性集c 映射成一个强连通图g = ，e ) ，其中y 是由n 个节点组成的集合，分别对应n 个条件属性，e 是任意两节点间的边集，即 e p 1 0 f ，川f ，j - 1 ，2 ，万 。采用路径编码描述解的状态。根据上节讨论，在蚁群优化算 法的内循环中，对每只蚂蚁k ，采用与基于信息熵的启发式约简算法类似的方法进行路 径搜索。根据属性约简的特点，采用全局信息更新路径上的信息素。其算法的基本框架 如图2 - - 2 所示。 为便于算法的具体描述，首先介绍几个有关蚁群算法的记号。 a n t s 一仉2 ，七，小表示有m 只蚂蚁的蚁群，k e a n t s 表示第k 只蚂蚁，o ) 表示 t 时刻残留在边e g ，j ) 上的信息素量，o ) 表示t 时刻蚂蚁k 经过边p o ，j ) 后该边的信息 素增量，o ) 表示一次循环结束后，边e o ，j ) 上的信息素总增量。每只蚂蚁只能走合 法的路径，除非一次循环已结束，否则不允许它转到已访问过的节点，该过程由蚂蚁的 禁忌表来控制。设t a b u 。为蚂蚁k 的禁忌表，则蚂蚁在经过节点f 后，就将该节点加入禁 忌表t a b u 。中，表示下次不能再选择节点i 。 1 7 中国民航大学硕士学位论文 开始，初始化蚁群广1 1 达到预定的熵? 广1 1 选择下一个属性 全局信息素更新 记录本次循环最优解 比较并判断是否 满足结束条件? 输出最小约简，结束 图2 - - 2 基于蚁群优化算法的属性约简基本框架 基于a c o 算法求最优约简的具体算法步骤如下： 输入：决策表s = ，c o o ，y ，) 输出：s 的一个约简r e d 步骤l ：初始化循环次数n _ 0 ；设置最大循环次数眦； 信息素量霉c ( c 为常数) ；初始信息素增量：薯0 ； 步骤2 ：将m 只蚂蚁随机不重复的放在n 个节点上伽 ) ， 环次数n = n + 1 ，初始禁忌表t a b u f = f 2 i ，i e 仉2 ，小 ； 每条边e ( i ，j ) 上的初始 内循环次数k 一1 ，外循 步骤3 ：将蚂蚁k 到达的节点加入其禁忌表t a b u 。，若h ( d i t a b u 。) - n ( d l c ) ，结束 蚂蚁k 的本次搜索，转步骤6 ；否则转下一步； 步骤4 ：对蚂蚁k 按下式计算其转移概率： 露一 甚，如果j 以o ) ， 三。以 k 严叱w 0 ， 否则 这里以o ) = c - t a b u k 表示蚂蚁k - f - - 步可以选择的节点集合。嘞净百石丽1 为启 发信息函数； 步骤5 - 以轮盘赌方式按概率露选择每只蚂蚁下一个要到达的节点j 后，转步骤3 。 步骤6 ：若k ) 一) ，攸，c ) 定义3 4 3 决策表s ；，cu d ，矿，厂) ，b c ，若下列两个条件成立： ) ，( 吃，曰) 一y ( 以，c ) 且o ) 一o ) ； v c