（计算机应用技术专业论文）基于模糊集的蚁群聚类算法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随着信息科学的飞速发展，获取和存储海量数据已不是什么难 事，但面临如此海量数据，若不加分析和处理，它们可能没有任何 意义。因此，“数据爆炸与知识贫乏”的局面促使了数据挖掘领域 的飞速发展。聚类分析是数据挖掘中的一个重要分支，也是国内外 学者研究的热点。群体智能作为一个新兴领域，自从2 0 世纪8 0 年 代出现以来，也引起了多个学科领域研究人员的关注。其中的典型 算法蚁群聚类算法，也为聚类分析提供了一个良好的算法。 本文首先回顾了聚类分析的概念、分类和方法；然后介绍了模 糊集的相关概念以及模糊聚类算法；其次研究了群体智能研究现状 及典型算法，包括蚁群算法、蚁群聚类算法和微粒群优化算法的主 要思想、描述和分析；最后重点对蚁群聚类算法进行了研究，并发 现基本模型和l f 算法存在一些缺陷，会导致不相似的数据对象本 该被拾起而可能未被拾起，相似的数据对象本该被放下而可能未被 放下的情况，从雨影响聚类的效果。针对这一缺陷，并注意到“相 似”本身是一个模糊概念，本文提出用模糊集理论相关知识来解决： 首先定义了平均距离，其次基于平均距离定义了“相似”这一模糊 子集的隶属度函数，最终数据对象的拾起或放下由隶属度与置信水 平a 相比较来决定。最后，改进算法通过编程实现，通过测试证明 了改进算法的优越性。 总的来说，改进算法具有如下优点：首先减少了心算法中的 参数数量，而且新参数a 的含义更加直观。其次，由于每次循环中 不用计算拾起概率与放下概率，因此减少了计算量，也更接近于智 能生物的思维过程。最后，改进算法对选取相似性参数口的敏感程 度有所降低。 关键词：数据挖掘；聚类分析；模糊集；群体智能；蚁群算法 西南交通大学硕士研究生学位论文第| i 页 a b s t r a c t w i t l lt h er a p i dd e v e l 叩m e n t0 fj l i f b i l a t i 0 t e c h n o l o g y ，t h e r ei sn o d i f ! 丘c l l l t y i n o b t a i l i i n g a n ds t 晌g m a 锚d a b 姐y 咖b u t i f 鲫c h m 掷 d a t ac o u l dn o tb e 孤a l y z e da n dp r o c e s s e d ，t h e yw o u l db eo fn 0 s i g n i f i c a n c e s ot h ep r e s e n t n d i t i o n0 f “d a t ad r o w l l i n gb u ts t a r v i n g f o rk n o w l e d g e ”u r g e st h er 印i dd e v e l o p m e n lo fd a t am i n i n g c l u s t e r a n a l y s i si sa ni m p o n a n c eb r a n c ho fd a t am i n i l l g ，a n da l s 0t h eh o ts p o t s t l l d i e db ym es c h o l a 娼a th o m ea l l da b r o a d s i n c cs w a mi m e l l 培e n c e o c c u r r c di nt h e1 9 8 0 s 船a e w 舡l dd e v e l o p i n gf i e l d ，i th 昭a t t m c t e dt h e a t t e n t i o no fr c s e 盯c h e r si ns e v e r a lf i e l d s t 1 l e r c i n ，t h et y p i c a la 1 9 0 r i t h m ， i e ，a n t l o n yc l u s t e r i n ga 1 9 0 r i t l l r l l ，w i l lp r o v i d eag o o da l g o r i t h r nf o r c l u s t e ra n a l y s i sa sw c l l i nt h i st h e s i s ，t h ec o n c e p t i o n ，d a s s 强c a t i o n 卸dm e m o do fc l u s t e r a n a l y s i sa 坤f e v i e w e d 丘r s t l y ，她dt h e nt l i er e l a t e dc o n c 印曲no ff i i z z y s e t 如df u z z yd u s t e f i i 培姐a l y s i sa r ci i l 吣d n e x t t h cr 髓ea r c ：h s t a m sa dt y p i c a la 1 9 0 r i t l l l no fs w 锄血c 1 1 i g c n c ca r es t i i d i e d ，i n d u d i l l g t h ep r i m a r yi d e a ，d e s 甜p t i o n 趾da i l a l y s i so fa n tc o l o n yo p t i i l l i z a t i o n ， a n t c o l o n yc l u s t e r i n ga l g o 血l l i n 趾dp a 埘d es w a n no p t i m i z a t i o n f i n a l ly ，t h er e s e a r c h e s1 a ys t r e s so n 卸tc o l o n yc l u s t e r i n ga 1 9 0 r i t h m ，卸d t h ea u t h o rf i n d st h a tt h e r ea r cs o m cd e f e c t si nb a s i cm o d e la n dl f a l g o m h m ，w h i c hw o u l dc a u s et h a td j s s i m i l a rd a t ao b j e c tm a yn o tb c p i c k e du pa n ds i m i l a rd a t ao b j e c tm a yn o tb ed r o p p e d ，i h e r e b yt h e e 仃e c io fd u s t e r i n gi si n n u e n c e d 1 f lt h i st h e s i s ，a i m i n ga tt h ed e f e c ta n dr e g a r d i n gt h a t “s i m i l a r i t y ” i t s e l fi saf u z z yc o n c c p t ，“i sp u ff o n v a r dt ou s et h er c l a t i v ek n o w l e d g e o ff l l z z ys e tm e o r yt os o l v et h i sd e f c c t 胁to fa l l ，a v e r a g ed i s t 髓c ei s 西南交通大学硕士研究生学位论文第l ll 页 d e f i n e d ；s e n d l yt h ef u l l c t i o no fd e g r c eo fm 锄b e r s h i po f i s j m i l a r i t y ” i sd e f i n e db a s e do na v e m g ed i s t 卸c e ；m i r d l yt h ep i c k u po rd r o po ft h e d a t ao b j e c ti sd e f e m i n e db yt h e m p a r i s o nb e t 、】i r e e n d e 掣e eo f m e m b e r s l l i pa n dc o n f i d e n c e1 e v e l ：a tl 鹏t ，t h ei m p r o v e da l g o r i t 椭i s r e a l i z e db yp m g 姗m i n ga i l di t ss u p c r i o r i t yi sp r 0 v e d g e n e 础y ，t i i ei m p r 0 v e da l g o r i t i i i nh 舔t h ef b l l 喇n ga d v 距t a g e s ： ( 1 ) t l l cn u m b e ro fp a 姗e t e 璐i ni ja l g o f i t h mh 勰d r o p p e da n dt h e m e a i l i n g o fn e wp a r 枷e t e r i se a s i c rt o u n d e r s t a n d ；( 2 ) i ti s u n n e c e s s a r yt 0c a l c u l a t et h ep r o b a b j l i t y0 fp i c k u p 柚dd r o pi nc v e r y i t e r a t i o n ，s ot h e 柚0 u n t0 fc a l c u l a t i o ni sr e d u c e da n di ti sm u c hc l o s e r i ot h i n l 【i n gp r o c e s so fi n t e i l i g e n tc r e a t u r c s ；( 3 ) t h e r ei ss o m er e d u c t i o n i nt h es e n s i t i v i t yo fi m p m v e da 1 9 0 r i t h r nt os i m i l a rp a r 栅e t e r 口 k e y w o r d s ：d a t am i n i g ；c l u s t e n g ；f u z z ys e b ； s w a 珊i n t e l g e n 傀；a n tc o i o n ya i 印n t h m s 西南交通大学硕士研究生学位论文第1 页 第一章绪论 1 1 论文的研究背景及选题意义 随着信息科学的发展，人们能以更快速、更容易、更廉价的方 式获取和存储数据，由此积累的数据以指数方式增长，数据量轻而 易举达到g b 甚至1 1 b 级，而且高维数据也日益成为主流。然而，现 有的数据库系统只能进行数据录入、修改、查询、统计等事务性的 处理过程。却不能发现这些数据背后隐含的知识。因此，人们往往 难以从这些海量数据中获取有用的知识，并且这些海量数据及其高 维特征使得传统的数据分析手段相形见绌，从而造成“数据爆炸与 知识贫乏”的尴尬局面。如何从这些海量数据中发现对决策有用的 信息和知识，使急剧增长的数据真币变成有价值的资源，于r 益成 为一个需要迫切解决的问题。在这样的背景下，数据挖掘( d a t a m i n i n g ，d m ) 和知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，k d d ) 技术应运而生，并得到了蓬勃的发展，充分显示了其强大的生命力。 数据挖掘出现于2 0 世纪8 0 年代后期。1 9 8 9 年8 月，第n 届国际 人工智能会议在美国底特律召开。会上，数据库中知识发现的概念 首先被提出来，其含义是在数据库中发现人们所不知道的、潜在的 知识和有用的信息n 1 9 9 5 年，首届k d d d a t am 幽g 国际学术会议在加拿大蒙特利 尔召开。会上，数据挖掘这一术语被学术界正式提出来，为在海量 数据中提取信息带来了新的希望。从此以后，k d d d a t am i i l i n g 国 际学术会议每年召开一次。 数据挖掘就是指从大量的、不完全的、有噪声的、模糊的、随 机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在 的有用信息和知识的过程。就数据本身来说，它并不能指导我们的 西南交通大学硕士研究生学位论文第2 页 实践，只有当数据被分析处理而上升为知识时，才能够指导我们认 识世界和改造世界。因此，数据好比矿石，而知识好比所淘的金。 而原始数据可以是结构化的，如关系数据库、数据仓库中的数据， 也可以是半结构化的，如文本、图形、图像、多媒体数据，甚至是 分布在网络上的异构数据。发现知识的方法可以是数学的，也可以 是非数学的：可以是演绎的，也可以是归纳的。因此，数据挖掘是 一个多学科领域，包括数据库技术、统计学、人工智能、神经网络、 模式识别、信息检索、高性能计算、数据可视化等学科。 数据挖掘能够使人们摆脱“数据爆炸与知识贫乏”的尴尬局面， 从众多的数据中挖掘出有用的知识，以指导人们更好地认识世界和 改造世界，因此，对数据挖掘的研究具有重要的意义，况且数据挖 掘领域还是一个比较年轻的领域，还需要投入大量人力物力进行更 深入的研究。 1 2 国内外现状综述 经过十多年的飞速发展后，国外在数据挖掘领域内取得了长足 的进步和丰富的经验。 在研究领域，不仅充分吸收和借鉴各学科取得的丰硕成果，而 且各学科领域的国际学术刊物也纷纷开辟了知识发现和数据挖掘 专题或专刊。如i e e e 的k n o w l e d g ca n dd a t ae n g i n e e r i n g 会刊首先在 1 9 9 3 年出版了k d d 技术专刊。随后，各类k d d 会议、研讨会纷纷 涌现，许多领域的国际会议也将k d d 列为专题讨论。1 9 9 9 年，i e e e 和a c m 再次推出k d d 专刊，介绍数据挖掘在各个领域的应用成果。 在i n t e m e 止也有不少相关网站，介绍最新动态及下载数据挖掘软件 和研究资料，如h 仕p ：嘲 ，k d 朋路c t s m 等。 在软件开发领域，自2 0 世纪9 0 年代初开始出现数据挖掘商用软 件以来，众多软件开发商纷纷加入近来。其中能够提供广泛的数据 西南交通大学硕士研究生学位论文第3 页 挖掘能力的产品有m m 公司的h l t e l l i g e n tm i n e r ，s a s 公司的 e n t e r 口r i s e m i n e r 旨在为某个部门求解问题的产品，有u n i c a 公司的 r e s p o n s em o d e l e fs e 星皿e n t o r ，m m 公司的b u s i n e s sa p p l i c a t i o n 等。 在应用领域，美国的读者文摘( r e a d e r sd i g e s t ) 出版公司运 行着一个积累了4 0 多年的业务数据库，其中容纳了遍布全球的1 亿 多个订户的资料，数据库每天2 4 小时运行，正是基于对客户资料数 据库进行数据挖掘的优势，使读者文摘出版公司能够从通俗杂志扩 展到专业杂志、书刊和声像制品的出版和发行业务：还有美国n b a 的著名篮球教练，利用i b m 公司提供的数据挖掘技术，临场决定替 换队员，一度在业界被传为佳话。 在国内，数据挖掘的研究起步稍晚，大多数研究项目是由政府 资助进行的，如国家自然科学基金、8 6 3 计划等，从事数据挖掘研 究的人员主要集中在大学和科研院所，所研究的多为理论性方面的 内容，国产数据挖掘的软件则刚刚起步，但发展速度较快。可以预 见，随着理论研究取得的成果和市场的成熟，将会出现优秀的国产 数据挖掘软件产品。 1 3 论文的研究内容 根据挖掘任务，数据挖掘可分为分类和预测、关联规则、聚类 分析、序列模式、孤立点分析等。其中聚类分析是数据挖掘中的一 个重要分支，也是国内外学者研究的热点。本文正是以聚类分析作 为研究对象，并结合了模糊集和群体智能的相关理论，进行了如下 研究： ( 1 ) 聚类分析的概念、分类和方法； ( 2 ) 模糊集的相关概念以及模糊聚类算法，其中重点介绍了 目前应用广泛的f c m ( f u 踞yc m 啪s ) 算法，并分析了其优点和 不足： 西南交通大学硕士研究生学位论文第4 页 ( 3 ) 群体智能的起源、研究现状及典型算法，包括蚁群算法、 蚁群聚类算法和微粒群优化算法； ( 4 ) 对蚁群聚类算法进行了改进，这也是本文的重点。针对 l f 算法存在的一些不足，结合模糊集理论，定义了平均距离、基 于平均距离的隶属度函数，由隶属度与置信水平a 相比较来决定数 据对象的“拾起”或“放下”，最后改进算法通过编程实现，证明 了改进算法的合理性。 1 4 论文结构安排 论文分为4 章。安排如下： 第一章为绪论，介绍了论文的研究背景、国内外现状及本文的 研究内容； 第二章简要介绍了相关的理论基础，包括聚类分析的概念及各 种方法、模糊集的相关概念以及模糊聚类算法、群体智能的起源及 典型算法； 第三章首先分析了模糊聚类算法中应用广泛的f c i m 算法及优 缺点，其次对l f 算法的思想及算法进行了分析，最后，针对l f 算法存在的一些不足，结合模糊集理论，对其进行了改进。 第四章为实验分析，对改进算法进行了测试实验，通过与原算 法的对比，验证了改进算法的合理性。 西南交通大学硕士研究生学位论文第5 页 第二章相关知识基础 2 1 模糊集理论概述 到目前为止，处理现实对象的数学模型可以分为三大类：确定 性数学模型、随机性数学模型和模糊性数学模型。 在现实生活中，有些现象在一定条件下是必然发生的，如扔出 一块石头必然落在地上，而如果我们知道石头扔出时的高度、初速 度和夹角，就能在石头落地前计算出石头能扔出多远。这类现象称 为确定性现象，经典数学正是研究此类现象。力学、热力学、电磁 学等基本规律都是建立在经典数学的基础上，可以用相应的微分方 程来表示。行星围绕太阳运行的轨道便是有万有引力推导出来的， 也正是这样的推导发现了海王星。曾经有些科学家认为一切自然现 象都可以用微分方程来描述，以致想建立一个描述一切自然现象的 统一的微分方程，结局必然是失败的。 在现实生活中，还存在另一种现象，如抛一枚硬币，其结果只 能是正面或反面，而在抛之前不能确定结果是正面还是反面，但经 过大量的重复试验正面朝上的次数接近一半。这类现象称为随机 现象。概率论、数理统计、随机过程等就是研究随机现象的数学学 科。其应用几乎遍及所有自然学科及国民经济各部门。如工业中产 品质量的抽样检验、元器件的寿命评估，农业生产中各种因素对农 作物的显著影响，气象部门进行天气预报，电力部门进行负荷预测， 统计局进行各项经济指标的统计等等。 在人的思维和语言中，许多概念都是模糊的。如年轻、漂亮、 可口、聪明等绝大多数形容词都是模糊的概念。正是这些模糊的概 念极大地压缩了信息的输入量、处理量和存储量，保证能实时而满 意地处理所面临的各种问题，否则面对纷繁复杂的客观事物及其变 意地处理所面临的各种问题，否则面对纷繁复杂的客观事物及其变 西南交通大学硕士研究生学位论文第6 页 化多端的状态，光是它们的组合数目就是天文数字，更别说存储和 实时处理了。人类智能与机器功能之间有着本质的区别，人脑善于 判别和处理不精确的、非定量的模糊信息，这也是为什么运算速度 达千亿次每秒的现代计算机的智能水平只相当于两三岁的小孩。而 如何描述和处理模糊信息呢? 这就是模糊数学。1 9 6 5 年，美国加州 大学控制论专家l a z a d c h 教授1 1 1 】的奠基性论文“f 旺z ys e t s ”的发 表，标志着模糊数学的诞生。尽管模糊数学诞生很晚，但其发展十 分迅速，已包含模糊数学理论、模糊语言和模糊逻辑、模糊数学的 应用等领域，而且它仍处于不断完善和发展中。 模糊数学的应用遍及众多领域，如在模糊控制、模式识别、聚 类分析、人工智能及信息处理、系统决策、系统评价、数据库等方 面取得了显著的成就。目前，模糊理论方面的专业学术杂志有：模 糊系统与数学( 中国模糊系统协会会刊) 、f u z z ys e t sa n ds y s t e m s 、 f u z z ym a t h 、b u s e f a l 、i e e et r a n s a c t i o n so n f u z z ys y s t e m 等。 2 1 1 理论的产生 十九世纪末，康托创立了集合论。集合论已成为现代数学的基 础。 如果我们对一切周围事物仔细考虑的话，集合的概念还不能概 括所有事物。因为在康托的集合论中，一事物要么属于某集合，要 么就不属于，这里没有模棱两可的情况。但在自然界中，在日常生 活中，模糊现象或模糊概念比比皆是，如年轻、漂亮、好吃等。对 于这些模糊的概念，由于它没有明确的内涵和外延，所以无法用普 通集合论来加以描述，即是说，在这样的集合里，一个元素是否属 于某个集合，不能简单地用“是”或“否”来回答，这里有一个渐 变的过程。早在2 0 世纪2 0 年代，著名的哲学家和数学家b r l l s s e l l 就写出了有关“含糊性”的论文。他认为所有的自然语言均是模糊 西南交通大学硕士研究生学位论文第7 页 的。 1 9 6 5 年，美国加州大学控制论专家l 丸z a d e h 教授的奠基性论 文“f u 盈ys c l s ”的发表，标志着模糊数学的诞生。z a d c h 教授通过 长期对控制论的研究，深刻地感到精确数学的局限性，即有时不能 准确地描述客观现实，并且以往的数学很难在心理学即社会科学领 域发挥更大作用，不是因为这些科学太简单，不必应用数学，恰恰 相反，是因为这些科学的规律太复杂，以往的数学无法准确地反映 它们的真实面貌。z a d c h 教授重新研究数学的基础集合论，发 现了问题症结所在。集合论是以形式逻辑的同一律、矛盾律和排中 律为基础的，它要求客观事物绝对的“非此即彼”。为达到精确严 格的目的，人们在研究过程中，舍弃了事物本身特有的或多或少存 在着的模糊性，把客观事物简化，把思维过程绝对化。这样一来， 以严谨精确著称的数学这门科学，却不能完全反映客观事物的本来 面目。为了对客观事物进行更准确的描述，z a d e h 教授沿着集合论 中特征函数的思路，提出了隶属函数，即把( o ，1 ) 扩充为【o ，1 】 区间，用区间【0 ，l 】来描述事物的模糊性。 人类认识世界从模糊到精确，又从精确到模糊，这不是倒退， 而是人类的认识水平上升到一个新的高度。 2 1 2 概念与特点 定义2 1 设给定论域u ，u 到 0 ，1 闭区间的任一映射蝴：u _ o ，1 ，其中廿卜心( 曲，都确定u 的一个模糊子集墨，怕叫垂的 隶属函数，以( 曲叫测一的隶属度。 特别地，当隶属函数的值域由区间 0 ，1 蜕化为 o ，1 ) 时， 隶属函数便蜕化为特征函数，模糊子集就蜕化为普通集合了。 西南交通大学硕士研究生学位论文第8 页 正如普通集合由其特征函数所完全确定那样，模糊子集完全由 其隶属函数所确定。 模糊子集能较客观地反映现实中存在着的模糊概念，但在处理 实际问题过程中，要最后作出判断或决策时，往往又需要将模糊子 集变成各种普通集合。这就是 一截集的概念。 定义2 2 给定爿f ( u ) ，对任意 0 ，1 ，称经典集合 a = u lp ( 曲 为一的 一截集， 称为阈值或置信水平。 定理2 1 、r 0 ，1 ，且asy ，则爿，爿 这个定理说明截集置信水平越低， 越大；反之，置信水平 越高，4 就越小。 2 2 群体智能概述 在动物世界中，经常能看到如下的场景：成千上万只小鱼成群 结队在大海中游动。它们时而散开，时而聚拢。看似跟随节拍翩翩 起舞，其实它们是在运用群体的力量躲避猎食者的捕杀。当猎食者 冲进鱼群时，鱼儿纷纷散开，以至于猎食者不能确定捕杀哪只鱼； 当猎食者冲出鱼群时，鱼儿又纷纷聚拢，再次利用群体的优势保护 个体不受攻击。鱼群能够群体游动，并没有依靠一只或几只领头的 鱼来带领，而是仅仅遵循以下的简单规则： ( 1 ) 避免碰撞( c 0 u i s i o n a v o i d 缸c e ) ：避免与邻近的鱼相撞； ( 2 ) 速度一致( v e l o c i t ym a l c h i n g ) ：与邻近的鱼保持同样 的速度； ( 3 ) 向中心靠拢( f l o c kc t c r i i i g ) ：与邻近的鱼保持较近 的距离。 西南交通大学硕士研究生学位论文第9 页 群体智能( 孙r 锄h t e l l i g e l l ) 【2 】作为一个新兴领域，自从2 0 世纪8 0 年代出现以来，引起了多个学科领域研究人员的关注，已 经成为人工智能以及经济、社会、生物等交叉学科的热点和前沿领 域。所谓群体智能，是指无智能的主体通过合作，表现出智能行为 的特性。对群体智能的研究起源于对以蚂蚁、蜜蜂等为代表的社会 性昆虫的群体行为的研究。作为实现群体智能的每一个个体，它们 的功能相对于整个问题的求解是有限的，而且每个智能个体在整个 智能系统中只能实现总体功能的一小部分，其智能寻优方式实现是 通过智能群体的总体优化特征来实现的。群体智能具有如下特点： ( 1 ) 个体与个体和个体与环境的交互作用的实现是完全分布式 控制，具有良好的自组织性； ( 2 ) 没有中心的控制与数据，系统更具有鲁棒性，不会由于某 一个或者某几个个体的故障而影响整个问题的求解； ( 3 ) 可以通过个体之间的非直接通信进行合作，这样的系统具 有更好的可扩展性； ( 4 ) 每个自治个体的能力十分简单，只需要最小智能，具有简 单性。 群体智能已应用于工厂生产计划的制定和运输部门的后勤管 理。美国大平洋西南航空公司采用了一种直接源于蚂蚁行为研究成 果的运输管理软件，结果每年至少节约1 0 0 0 万美元费用开支。英 国联合利华公司己率先利用群体智能技术改善其一家牙膏厂的运 转状况。美国通用汽车公司、法国液气公司、荷兰公路交通部和美 国一些移民事务机构也都采用这种技术以改善其运转的机能。 但群体智能的研究还处于初级阶段，还存在很多未解决问题。 首先，它们都是基于概率的算法，从数学上的证明还比较困难，所 做的工作也比较少，因此缺乏坚实的数学基础。其次，这些算法都 是为解决某一类问题的专用算法，各种算法之间的共性较少。因此， 应该更多地把目光投向群体智能系统的底层机制研究上来，如自组 西南交通大学硕士研究生学位论文 第10 页 织( s e l f - o r | 舯i z a t i o n ) 、间接通信( s 岖m e 瑁y ) 、涌现( e l m r g c n c c ) 等机制。 目前，国内外研究得比较多而且也比较成熟的算法有蚂蚁优化 算法、蚂蚁聚类算法、粒子群优化算法，还有对蚂蚁分工的研究。 ( 1 ) 蚁群算法原型 蚁群算法【1 2 】( a n ts y s t e ma l g o r i t h m ) 是由意大利学者m d o r i 印 等人于1 9 9 1 年首先提出的。经过大量的观察研究发现，蚂蚁具有 找到蚁巢与食物之间的最短路径的能力。这种能力是靠其在所经过 的路径上释放出一种挥发性分泌物称为信息素( i ，h e m o n e ) 的物质 来实现的。蚂蚁在行动的过程中，会在经过的路径上留下信息素。 对于一条路径，选择它的蚂蚁越多，则在该路径上蚂蚁所留下的信 息素的强度就越大，而信息素强度大的路径会吸引后面更多的蚂 蚁，从而形成一种正反馈效应。信息素随时间挥发，在较短的路径 上浓度较大，因而蚂蚁总是可以找到更短的路径取食。用人工蚂蚁 来模仿自然蚂蚁，在走过的路径上留下信息素，为解决各种寻优问 题提供了一种新的方法。该算法已经被成功地应用在很多复杂的组 合优化问题上。m d 0 r i 9 0 首先将该方法用于求解旅行商问题( t s p ) 问题。 旅行商问题就是指给定n 个城市和城市间的距离，求一条通过 各城市的最短路径，使得每个城市只能被访问一次。砖p 问题用图 论可描述为：给定图g 一缈，e ) ，其中y 一 u ，屹，以 为顶点集， e k ，e ：，巳) 为边集，d 表示边距离或费用，求一个长度最短的 h a m i l t 图。 首先引入如下记号： 如( f ，一1 2 ，h ) ：城市f 和城市，之间的距离； 唾o ) ：f 时刻位于城市f 的蚂蚁的个数 西南交通大学硕士研究生学位论文第1 1 页 m ：蚂蚁的数量，珊2 善岛( f ) ； o ) ：f 时刻在边( f ，) 上的信息素强度： o ) ：启发函数，表示城市j 转移到城市j 的启发程度。 西o ) ：在f 时刻蚂蚁七由城市f 转移到城市j 的转移概率， j n t l o w e d t 。 每只蚂蚁的行为应符合如下特征： 1 ) 当从城市f 到城市j 的过程中或完成了一次循环后，蚂蚁在 边( ，j ) 上释放相应强度的信息素。 2 ) 根据两城市间的距离和连接两城市的路径上的信息素强度 来选择下一个将要访问的城市； 3 ) 完成一次循环前，不允许蚂蚁选择已经访问过的城市，用 一个数据列表船妇f f 盯来控制这一点： 初始时刻，各条路径上分布的信息素强度相等，即( 0 ) - c ( c 为常数) 。蚂蚁七( 七一1 ，2 ，腮) 在运动过程中。根据各条路径上的信 息素函数决定转移方向。f 时刻位于城市f 的蚂蚁七选择城市j 为目 标城市的概率为 p ：o ) l ( f 切f ( f ) 茹 o j 口l t o w e d l 枷e 括e ( 2 1 ) 其中，口f f d w 耐。= ( 0 ，1 ，n 1 ) ，表示蚂蚁七下一步允许 选择的城市；参数4 反映蚂蚁在运动过程中所积累的信息，其值越 西南交通大学硕士研究生学位论文第12 页 大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径：参数p 为启发信 息在蚂蚁选择路径中的相对重要性。 经过n 个时刻，蚂蚁完成一个循环，各路径上的信息素要根据 如下公式进行调整： b o + n ) 一( 1 一p 弦口o ) + 了。( f ) ( 2 - 2 ) ( f ) 一善f ；( f ) ( 2 - 3 ) 式( 2 2 ) 中，p 表示信息素挥发系数，l p 则表示信息素残留 因子； 厶巧( f ) 表示在本次循环中路径玎上的信息素的增量。初始 时刻，( o ) - c ，巧一o 。式( 2 3 ) 中，瞄) 表示第七只蚂蚁 在本次循环中在边( f ，j ) 上释放的信息素强度。 由于表达式o ) 的不同，d o r i 9 0 m 给出了三种不同的基本蚁 群算法模型：蚁周系统( a m - c y c l es y s t 锄) 、蚁量系统( a n t q u 柚t i t y s y s t e m ) 和蚁密系统( a m - d e 璐i t ys y s t c m ) 。 在a n t - c y c l c 系统中 o ) 。j 罢，若第七只蚂蚁在本次循环中经过( f ，) i o ， 否则 ( 2 4 ) 式中，q 表示蚂蚁循环一周后释放在所经过路径上的信息素总 量；“表示第七只蚂蚁在本次循环中所走路径的长度。 在髓t - q u 锄t i t y 系统中 西南交通大学硕士研究生学位论文第1 3 页 噶。 罢，! 三七只蚂蚁在f 和f + 1 之间经过( f 。 仕；， l o ，否则 苗一倦薯翥七只蚂蚁在和1 之间经过 。 c 2 算法描述如下( 以趾t q d e 系统为例) ： ( 1 ) 初始化过程 f = o ：t 为时间计数器 c = o ；札为循环次数计数器 ( 0 ) 一c ； ，设每条路径( f ，j ) 信息素初始值 - 0 ； 信息素强度的增量的初值设为0 嘞0 ) - 弛； 胁6 一g ； 在初始阶段，禁忌表为空 将m 只蚂蚁随机地置于万个节点上； s = 1 ：伽为禁忌表索引，将各蚂蚁的初始城市置于当前禁忌表中 f o r f = 1 t o d o 女d f 七= 1 l o6 f p ) d o 纽6 0 ) - f ； ( 2 ) 重复直到禁忌表满，这一步要重复如- 1 ) 次 s is + 1 ： 西南交通大学硕士研究生学位论文第14 页 f o r j = 1 t 0 冗d o f b r 七= l t 0 趣( f ) d 0 以概率或o ) 选择城市五 将蚂蚁t 移动到矗 将刚刚选择的城市，加到细b 心中； ) ( 3 ) f b r 七= l t o md o 根据禁忌表的纪录计算k ； f o r j = 1 t 0 加1d 0 搜索蚂蚁t 的禁忌表： ，f ) - 6 o ) ，缸6 0 + 1 ) ) ；，伪，f ) 是在蚂蚁t 的禁忌表中连接城 市o ，s + 1 ) 的路径 峨( f 棚) i a 啪) + 詈 ( 4 ) 对于每一路径o ，) ，根据公式( 2 - 2 ) 、( 2 - 3 ) 和( 2 q 计算p + 栉) f - f + ，l ： 对每条路径g ，j ) ，设a o ，f + n ) 一o ( 5 ) 记录到目前为止的最短路径 i f c 札一 清空所有的禁忌表： s = 1 ： 西南交通大学硕士研究生学位论文 第15 页 t _ 0 r f = 1 t o nd o f o r 七= 1 t o 岛o ) d 0 细妇i o ) - f ； f _ f + 1 ： 对于每一条路径o ，) ，设置o ，f + 1 ) 一0 ； 返回步骤( 2 ) ； ) e l s e 输出虽短路径： 随后诸多学者陆续使用了该算法解二次分配问题、皇后问题 等。所解决的问题以各种t s p 问题为主，另外有函数优化问题、背 包问题等，而且从离散空间扩展到了连续空间。在解决这些问题的 性能方面，比之于传统的优化算法，蚂蚁优化算法表现出了良好的 性能。 ( 2 ) 蚂蚁聚类算法的基本模型 详见3 2 节。 ( 3 ) 微粒群优化算法( p a n i d es w 删o p l i m i z a l i o n ，p s 0 ) p s 0 “。咖是k e n n e d y 和e b e r h a r t 在1 9 9 5 年提出的一种新型计算智 能算法，该算法受到飞鸟集群活动的规律性的启发。该算法一经提 出，立刻引起进化计算领域学者们的广泛关注，短短几年便获得快 速发展，在诸多领域得到应用而且应用范围越来越广泛。己形成学 术界一个新的研究热点。 假设在一个d 维目标搜索空间有m 个微粒，每个微粒的位置表示 一个潜在的解。第f 个微粒的位置向量z 。- 0 n ，t ：，) ，第f 个微 西南交通大学硕士研究生学位论文 第16 页 粒的速度向量k - ( v n ，v 。，v 。) ，它经历过的最佳位置( 有最好适 应度) 记为只- 0 。p 。，p 。) ，也称为个体极值p 。整个微粒 群迄今为止搜索到的最优位置记为只- ( p 1 1 ，p 1 2 ，p 庐) ，也称为 全局极值g 。更新后的微粒速度k h l 为： k “1 - k + c 。，1 娌一z ：) + c ：乇( 只一x ；) ( 2 7 ) 其中，为惯性权重，表示当前速度对下一代速度的影响权重： c 和c 2 为加速常数；n 和r 2 是两个在 o ，1 范围内的随机数。更新后 的微粒位置孑为： x ? “- z j + k ( 2 8 ) 算法流程如下： 1 ) 初始化一微粒群，其中所有微粒的位置和速度都是随机的； 2 ) 对每个微粒，将它的当前位置和它经历过的最佳位置p 。作 比较，如果当前位置更好，则将其作为当前的最佳位置p k ，； 3 ) 对每个微粒，将它的当前位置和群体中所有微粒所经历的最 优位置占。作比较，如果这个微粒的位置更好，则将其设置为当前 的最优位置g ： 4 ) 根据式( 2 7 ) 和( 2 - 8 ) 更新微粒的速度和位置； 5 ) 如未达到结束条件( 通常为预设的运算精度或迭代次数) 则返回步骤2 ) ，否则取当前g 。作为最优解。 西南交通大学硕士研究生学位论文第1 7 页 公式( 2 7 ) 中，第一部分为微粒当前速度乘以惯性权重，表 示微粒依据自身的速度进行惯性运动。第二部分为“认知”部分， 表示微粒本身的思考，即微粒自身信息对自己下一步行为的影响， 致使下一代微粒围绕此点震荡搜索。第三部分为“社会”部分，表 示微粒间的信息共享和相互合作，即群体信息对微粒下一步行为 的影响。 此后，文献 5 结合了进化计算与p s 0 的思想，提出了杂交p s o 的概念。文献 6 引入一个可变的邻域算子来改进标准p s 0 的性能， 它能保持微粒群的多样性，避免过早收敛，能有效地获得全局最优 解。文献 2 9 在基本p s 0 的基础上发展了离散二进制p s o ，给组合 优化问题的求解带来更好的应用前景。文献 8 将微粒分成多群， 每群微粒具有不同的运动方向，增加了搜索的多样性和搜索的广泛 性，避免微粒陷入局部最优。 p s 0 算法已应用于函数优化、神经网络训练及其它进化算法常 应用的领域等。p s o 最直接的应用是解决大多数优化问题，包括多 目标优化和带约束优化问题。p s o 还广泛应用于人工神经网络，不 仅用于训练网络的权重，而且进化网络的结构。由于p s o 算法只有 很少的参数需要调整，因此还成功应用于其他领域，如电力、通讯、 机械、生物工程等领域。 2 3 聚类分析概述 “物以类聚，人以群分”。分类问题可以分为有监督的分类 ( s u p e r v i s c dc l 鹞s i 矗c a t i o n ) 和无监督的分类( u 璐up c ：i s c d a 醛s 墒c a t i o n ) 两种。 有监督的分类可分为两步：第一步，用具有类别标识的样本对 系统进行训练，以建立一个分类模型；第二步，用此分类模型对未 知样本进行分类。因此有监督的分类需要对问题有足够的先验知 西南交通大学硕士研究生学位论文第18 页 识。 无监督的分类则是以事物间的相似性作为类勇划分的依据，在 这一过程中没有关于分类的先验知识，也没有人们的指导，因而属 于无监督的范畴。无监督的分类又称为聚类分析。聚类分析是数据 挖掘中的一个重要研究内容。聚类分析是将一组对象分成若干类， 使得类内的对象尽可能相似，不同类之间的对象尽可能相异。主要 的聚类方法大致分为如下几类： ( 1 ) 划分方法( p a n m o n i n g m c t h o d ) 给定雄个数据对象或一个抖元组的数据库，一个划分方法构建数 据的七个划分，每个划分表示一个聚类，并且船；万。也就是说，它 将数据对象划分为t 类，同时满足如下的要求：每个类至少包括 一个对象；每个对象必须属于且仅属于个类( 但是在某些模糊 划分技术中第二个要求可以放宽) 。 典型算法有k - 平均、k 中心点、c i a r a n s 等算法以及它们的 变形算法。常用的k 平均算法如下： 1 ) 输入划分的数薰七和 个数据对象 2 ) 随机选择七个对象作为初始的类中心 3 ) r e p 】i a t 4 ) 将每个对象重新分配到与类中心距离最小的类 5 ) 重新计算类中心 6 ) u n n l 类中心不再发生变化 这类算法存在一些不足，例如，需要事先给出分类数七，并且 不适合发现非凸面形状的类，对噪声数据和孤立点敏感。 ( 2 ) 层次方法( h i 盯砌i c a lm e t h o d ) 层次方法可分为凝聚的和分裂的两种。凝聚的方法开始时将每 个对象各自视为一类，然后根据类间相似度将对象或类进行合并， 直至所有对象或类合并为一类，或达到一个终止条件，如达到给定 的聚类数目。分裂的方法在开始时将所有对象视为一类，然后每一 西南交通大学硕士研究生学位论文 第19 页 类被分解为若干子类，直至每个对象自成一类，或达到一个终止条 件。 层次方法的优点是计算量比较小，但是它具有聚类过程不可逆 的缺陷。因为某对象或类在被合并或分解后，下一步的计算将在新 的类上进行，假如在以后的计算中发现有更好的聚类结果，先前所 做的合并或分解操作已不能被撤销，这样可能会影响最终的聚类质 量。 基于上述缺陷，结合了其它聚类方法的改进层次方法应运而 生。如b 瓜c h 算法首先用树结构对对象进行层次划分，然后采用其 它的聚类算法对聚类结果进行求精。又如c r 算法不用单个质心 或对象来代表一个类，而采用固定数目的具有代表性的点来表示每 个类，从而可调整聚类的形状以达到非球形的聚类；然后根据一个 特定的收缩因子向类中心收缩或移动它们，收缩因子的使用减小了 噪音对聚类结果的影响。在算法的每一步，有最小距离的代表点对 ( 每个点来自一个不同的类) 的两个类被合并。该算法也存在一些 不足，如要求用户给出聚类数目、收缩因子等参数，而这些参数又 对聚类结果有较大的影响。 ( 3 ) 基于密度的方法( d 锄s i t y b 豳c dm c 廿1 0 d ) 大多数划分方法只能发现球状的类，不能发现任意形状的类， 因为它是基于对象间的距离进行聚类的。而基于密度的聚类方法能 发现任意形状的聚类结果，因为它不是基于距离的，而是基于密度 函数进行聚类。其主要思想是：只要临近区域的密度( 对象或数据 点的数目) 超过某个阀值，就继续聚类。也就是说，对给定类中的 每个数据点，在一个给定范围的区域中必须至少包含给定数目的 点。它也对用户定义的参数敏感，参数的选择可能显著地影响聚类 结果。 主要算法有d b s c a n 、o p l r i c s 、d e n c l u e 等算法。 ( 4 ) 基于网格的方法( 班d - b 鹪e dm