（运筹学与控制论专业论文）基于并行蚁群优化的分类技术应用研究.pdf

、 l 0 e ， 丫 c l a s s i f i c a t i o nr u l ee x t r a c t i o nb a s e do ni n t e r a c t e dm u l t i p l e a n tc o l o n i e so p t i m i z a t i o na l g o r i t h m at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fs c i e n c e b y l i n gj u n ( o p e r a t i o n a lr e s e a r c ha n dc y b e r n e t i c s ) t h e s i ss u p e r v i s o r ：p r o f e s s o r s a n g l i n j u n e2 0 1 1 胄， ri 丫 易 了 每 辟? q l ? 一大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文= = 基王羞堑丛登垡丝的佥耋这苤廛届婴窥：。除论文中已 经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以 明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发 表或未公开发表的成果。本声明的法律责任由本人承担。 序7 学位论文作者签名：2 忽! 盈 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论 文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式 出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保 密口在年解密后适用本授权书。 不保密囱( 请在以上方框内打“”) 论文作者签名：凌咩 导师签名： 论文作者签名：彼车 导师签名： 素淋 n 、 1 日期：h f f 年6 月讧日 ，r 、 碡 中文摘要 摘要 数据库内容非常丰富，其中蕴藏着大量的信息，而分类是一种数据分析的形 式，分类分析已经成为数据挖掘技术中重要而且热门的研究领域之一，其目标就 是根据已有的数据分类归纳出每类的一般性的描述。2 0 0 2 年r a f a e ls p a r p i n e l l i 在 他的文章【1 】中首次提出了基于蚁群优化( a n tc o l o n y0 p t i m i z a t i o n ) 的分类算法 蚂蚁矿工算法( a n t m i n e r ) 。他的这篇论文开辟了蚁群算法应用的一个新领域， 同时也开创了分类算法的一个新的里程碑。然而a n t m i n e r 算法存在着早熟与陷入 局部最优的缺陷，针对这些缺陷本文在a n t m i n e r 算法的基础上提出了基于并行蚁 群优化的分类算法i m a c o ( i n t e r a c t e dm u l t i p l ea n tc o l o n i e so p t i m i z a t i o n ) ，新算 法在原算法的基础上做了以下三点改进： 1 ) 采用多重信息素，每一种信息素都只允许构建一个类别，蚂蚁先选择分类 类别，然后释放相应的信息素。 2 ) 对状态转移规则的改进：引入伪随机概率转移规则，替换a n t m i n e r 算法 中的随机概率转移规则。 3 ) 引入相关度的概念来衡量规则的分布均匀程度，从而达到动态调整路径选 择策略的目的。实验结果表明，改进后的新算法不仅在分类预测精度上要高于原 算法而且得到的分类规则也比原算法简单。 文章最后使用u c i 标准数据库中的四个数据对该算法进行了检验，实验结果 表明该算法与原算法相比在分类的准确度上有一定提高，所得到的分类规则也更 简洁。 、关键词：分类规则；蚁群优化；a n t m i n e r 算法；并行计算；聚合度 眩 了亨 英文摘要 a b s t r a c t t h ec o n t e n to fd a t a b a s ei s v e r yr i c h ，w h i c h b e a r sal o to fl n f o r m a t i o n c l a s s i f i c a t i o ni saf o r mo fd a t aa n a l y s i s c l a s s i f i c a t i o na n a l y s i sa sak i n do fd a t am i n i n g t e c h n o l o g yh a sb e c o m ea ni m p o r t a n ta n dh o tr e s e a r c ha r e a s ，a n dt h eg o a lo fw h i c hi s s u m m a r i z i n gt h eg e n e r a ld e s c r i p t i o n o fe a c ht y p eo nt h eb a s eo fe x i s t i n gd a t a c l a s s i f i c a t i o n i n2 0 0 2 ，r a v e ls p a r p i n e l l ip r o p o s e dc l a s s i f i c a t i o na l g o r i t h mo nt h e b a s eo fa n tc o l o n yo p t i m i z a t i o n h i sp a p e ro p e n e du pan e wa p p l i e df i e l df o ra n t c o l o n ya l g o r i t h m h o w e v e r ，p r e c o c i o u sa n dl o c a lo p t i m i z a t i o n a r et h ed e f e c t so f a n t - m i n e ra l g o r i t h m f o rt h e s ed e f e c t s ，w ep r o p o s e di n t e r a c t e dm u l t i p l ea n tc o l o n i e s o p t i m i z a t i o ni nt h i sp a p e r t h en e wa l g o r i t h mm a k e st h ef o l l o w i n gt h r e ei m p r o v e m e n t s o nt h eb a s eo ft h eo r i g i n a la l g o r i t h m ： 1 ) m a k eu s eo fm u l t i p l ep h e r o m o n e s ，a n dj u s ta l l o w se a c hp h e r o m o n eb u i l do n e c a t e g o r y a n ts e l e c t sc a t e g o r yf i r s t ，a n dt h e nr e l e a s et h ec o r r e s p o n d i n gp h e r o m o n e 2 ) i m p r o v e m e n to nt h es t a t et r a n s i t i o nr u l e s ：i n s t e a do ft h em n d o mp r o b a b i l i t yo f t r a n s i t i o nr u l e sw eu s et h ep s e d o - r a n d o mp r o b a b i l i t yo ft r a n s f e rr u l e si nt h e a n t m i n e ra l g o r i t h m 3 ) u s et h ec o n c e p to fd e g r e eo fp o l y m e r i z a t i o nt om e a s u r et h ed i s t r i b u t i o nu n i f o r m i t y o fr u l e ss oa st oa c h i e v et h ep u r p o s eo fd y n a m i ca d j u s t m e n tp a t hs e l e c t i o ns t r a t e g y e x p e r i m e n t a lr e s u l t ss h o wt h a tt h en e wa l g o r i t h mn o to n l yi m p r o v e sp r e d i c t i o n a c c u r a c yi nc l a s s i f i c a t i o n ，b u ta l s oh a ss i m p l e rc l a s s i f i c a t i o nr u l e st h a nt h eo r i g i n a l a l g o r i t h m a tt h ee n do ft h ep a p e r ，f o u rd a t ao ft h eu c is t a n d a r dd a t a b a s ea r eu s e dt ot e s tt h e n e wa l g o r i t h m t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tc o m p a r e dw i t ht h eo r i g i n a l a l g o r i t h m ，t h en e wa l g o r i t h mn o to n l yi m p r o v e sp r e d i c t i o na c c u r a c yi nc l a s s i f i c a t i o n ， b u ta l s oh a ss i m p l e rc l a s s i f i c a t i o nr u l e st h a nt h eo r i g i n a la l g o r i t h m k e yw o r d s ：c l a s s i f i c a t i o na l g o r i t h m ；a n t - m i n e ra l g o r i t h m ；a n tc o l o n ya l g o r i t h m ； a g g r e g a t ed e g r e e 、，吁 i 心 气 口 目录 目录 第1 章绪论1 1 1 研究背景1 1 2 研究意义、目的2 1 3 本文主要内容和结构3 第2 章基本蚁群优化算法模型及其改进算法。4 2 1 弓j 言4 2 2 蚁群优化( a c o ) 算法基本原理及其实现5 2 3 基于a s 算法的几种改进算法1 0 第3 章数据分类算法1 3 3 1 数据挖掘技术概述1 3 3 2 数据挖掘的功能一1 3 3 3 分类规则挖掘常用算法1 5 3 4a n t m i n e r 算法1 7 3 5 本章总结2 3 第4 章基于多目标并行蚁群优化( i m a c o ) 的分类算法2 5 4 1i m a c o 的提出背景2 5 4 2i m a c o 算法模型的建立2 6 4 3i m a c o 算法参数的选取规则3 0 4 4 实验结果与分析。3 0 第5 章结束语3 3 5 1 本文所做的主要工作一3 3 5 2 展望3 3 参考文献3 5 附录1 ：t i c - t a c t o e 实验结果4 0 附录2 ：c a re v a l u a t i o n 实验结果4 3 目录 附录3 - n u r s e r y 实验结果4 8 致 射5 1 个人履历5 2 v 1 j 和 p 、 弋菱 基于并行蚁群优化的分类技术应用研究 第1 章绪论 1 1 研究背景 当今，数据挖掘技术( d a t am i n i n g ) 2 - 4 】随着信息量的急剧膨胀越来越体现出 了其应用价值，数据挖掘也已经成为了计算机科学中的一个重要研究方向。数据 挖掘的目标就是从海量数据中提取有用的知识，因为在这个信息爆炸的时代，信 息过量是人们无法逃避的问题，数据挖掘技术就是为了应对“信息爆炸，但知识 匮乏”而形成的一门学科。经过十几年的发展，并伴随着理论研究的深入以及实 际需求的不断增长，国外学者已经开发出了一些具有使用价值的数据挖掘系统1 5 6 j ， 其中有较强影响力的有：s p s s 公司的c l e m e n t i n e 、i b m 公司的i n t e l l i g e n tm i n e r 、 s a s 公司的e n t e r p r i s em i n e r 等。与国外相比，我国在数据挖掘技术这一领域的研 究起步比较晚，且在早期没有形成统一的整体力量。但是从1 9 9 3 年起，国家自然 科学基金首次支持了这一领域的研究项目，到目前为止，国内很多科研单位和高 等院校都开展了数据挖掘的基础理论及其应用研究【 9 1 ，其中比较有名的有北京系 统工程研究所对模糊方法在数据挖掘中的应用有较深入的研究，北京大学还开展 了数据立方体代数的研究工作，上海交通大学、南京大学等在研究非结构化数据 的知识发现以及w e b 数据挖掘等领域取得了较好的成绩。 海量的数据与知识的贫乏导致了数据挖掘领域的出现，而数据挖掘就是一个 从大规模的数据库中提取以前未知的、隐含的、有潜在使用价值、有效的的有用 信息的一个过程，数据挖掘的主要目标是采用智能化、自动化的新技术来分析海 量数据，以此获得其非线性的内在关系和充分利用宝贵的数据资源，并消除不确 定性，它是当今众多学科领域特别是数据库领域最前沿的研究课题之一。因为对 于大规模的组合优化问题来说，很多确定性算法根本就无法解决，因此寻找好的 近似算法就成了研究组合优化问题的一个热点：而自热生态系统和生物体之间可 通过自身的演化能使很多问题得到完美，这些问题很多在人类眼里是高度复杂的。 近些年来受此启发，相继出现了一些试图通过模拟自然生态系统机制来解决复杂 优化问题的仿生优化算法( 如：蚁群算法、遗传算法、微粒群算法、人工鱼群算 第1 章绪论 法、人工免疫算法、混合蛙跳算法等) ，这些算法与经典的数学规划原理截然不 同。这些算法的出现为那些传统的最优化技术难以解决的组合优化问题提供了可 行的解决方案，这大大丰富了现代优化技术。9 0 年代初意大利学者m d o r i g o 等人 受到蚂蚁觅食行为的启发，通过模拟真实蚂蚁搜索路径的行为提出了蚁群算法 ( a n tc o l o n ya l g o r i t h m ) 1 0 , l l 】。蚁群算法是一种新型的模拟进化算法，该算法提 出之初并没有引起研究者们的关注，直到1 9 9 6 年d o r i g o 等在i e e e 上发表了文章 【1 0 】，在这篇文章中d o r i g o 不仅更加系统的将蚁群算法的基本原理进行了阐述，而 且进一步完善其数学模型，还将其与禁忌搜索算法、模拟退火算法、遗传算法等 算法进行了仿真实验比较，这篇文章中把单纯解决对称t s p 问题扩展到了解决指 派问题、车问作业调度问题以及非对称t s p 问题上，在蚁群算法发展史上这是一 篇奠基性的文章。该文章发表之后引起了国内外学者的广泛关注，随着对蚁群算 法研究的不断深入，其应用领域也得到了迅速的拓宽，蚁群算法在模型改进及与 其他仿生优化算法的结合等方面展现出了该算法的魅力所在。直到2 0 0 2 年，英国 学者p a r e p i n e l l i 和他的同事首次将蚁群算法应用到了数据分类领域，提出了第一个 基于蚁群算法的数据分类方法a n tm i n e r 算法【。 1 2 研究意义、目的 尽管到目前为止蚁群算法的严格理论尚未完善，算法的收敛性证明也只是停 留在具体改进算法上，对其参数设置的研究也都还处于试验分析阶段，但是它的 应用范围已经扩展的很多方面，由最初的t s p 问题慢慢渗透到了数据挖掘、图像 处理、网络路由等多个应用领域；由最开始的只能解决离散域问题逐渐扩展到能 够解决连续域问题；所解决问题的维数也由最开始的一维静态优化问题发展到解 决多维动态组合问题。同时国内外很多学者在对基本蚁群算法模型进行改进以及 与其他仿生类优化算法的融合方面都取得了非常丰富的研究成果，因此使得蚁群 优化算法这种新兴的仿生算法展现出了其广阔的发展前景。 英国学者p a r e p i n e l l i 首次将蚁群算法成功应用到数据挖掘领域，创建了 a n t m i n e r 算法。目前蚁群算法在数据挖掘领域的应用主要集中在数据分类和聚类 譬 冬 q ， 恼 基于并行蚁群优化的分类技术应用研究 这两个方面，与其他仿生优化算法相比，蚁群算法在数据挖掘上的应用结果虽然 比较突出，但也存在着不少需要改进的地方：主要体现在算法的实现机制显得比 较单一，其信息素更新策略、状态转移规则的选取、各参数初始值的设置等方面 都还有进一步研究的余地，而对这些方面的研究将有助于完善蚁群算法在数据挖 掘领域中的应用。 本论文主要目的是为了进一步提高蚁群算法在数据分类中应用的性能，采取 对其信息素更新策略、状态转移规则等设置做出更合理的调整手段，并引入新的 实现机制以改善a n t m i n e r 存在的过早陷入停滞、预测准确率偏低的现象。 1 3 本文主要内容和结构 本论文系统的介绍了蚁群算法的思想及实现、常见的分类算法，详细分析了 a n t m i n e r 算法，并在此基础上做出了三方面的改进提出了基于并行蚁群优化的分 类算法。为了检验改进后的算法效率，文中将新算法在四个公丌数据集( t i c t a c t o e 、 c a re v a l u a t i o n 、m u s h r o o m s 和n u r s e r y ) 上进行了实验分析。得到实验结果表明新 算法在预测精度上有明显的优势，而且所得到的规则列表在简单性方面要好于原 算法。 本文的主要结构如下：全文共分五章，第1 章简要介绍了课题的研究意义、 国内外有关蚁群算法和分类规则挖掘算法的研究现状；第2 章介绍了蚁群算法的 起源和实现以及基于a c o 算法框架的一些变种算法；第3 章介绍了分类规则挖掘 的常见算法并详细介绍了第一个基于a c o 框架的分类算法a n t m i n e r 算法；第 4 章是本文的核心内容，针对a n t m i n e r 算法的不足，从信息素的释放、状态转移 规则和衡量规则质量这三个方面对原算法进行改进，改进后新算法最大的特点就 是根据不同的类标号释放不同的信息素，使得蚂蚁可以并行工作，能够得到较为 简单的分类规则。并在最后通过实验做了进一步的证明；文章最后一章结束语对 本文的主要工作进行了总结。 第2 章基本蚁群优化算法模型及其改进算法 第2 章基本蚁群优化算法模型及其改进算法 2 1 引言 为了更好的说明蚁群优化算法，先简单介绍一些基本的组合优化问题的基本 概念以及常见的启发式算法。 组合优化问题的实质就是使得所给定的目标函数的解达到最优，这就涉及找 到一组离散变量的值，从形式化的角度上来看，组合优化问题是一个三元组 o ，厂，q ) ，其中s 是候选集( c a n d i d a t es o l u t i o n ) 的集合；厂是目标函数；q 为约束 条件。优化的目标就是找出一个全局最优的可行解( 满足约束条件的解) 使得目 标函数的值达到最大( 或最小) 。 一般而言存在两种类型的方法来进行组合优化问题的求解：即近似算法和确 定性算法。确定性算法( e x a c ta l g o r i t h m ) 是一种可以保证找到问题的最优解，而 且事实已经证明：对于任何规模有限( 即复杂度不为指数型) 的组合优化问题来 说，算法都可以在一个可以接受的运行时间内得到最优解，这个运行时间的长短 取决于问题的复杂程度。但往往实际中有很多问题的指数级复杂度的求解时间是 人们所不能接受的，所以唯一可行的方法就是降低最优值的精度以换取计算效率 的提高。近似算法( a p p r o x i m a t ea l g o r i t h m ) 就是在相对较低的计算成本下寻求好 的或接近最优解的解，但这并不意味着算法能够保证一定能找到最优解，而近似 算法在非严格定义下被称作启发式算法( h e u r i s t i cm e t h o d s ) 。在组合优化领域一 些应用最广泛的启发式算法包括：模拟退火算法( s i m u l a t e da n n e a l i n gs ac e m y 1 9 8 5 ，k i r k p a t r i c k ，g e l a t t1 9 8 3 ) 、禁忌搜索算法( t a b us e a r c ht sg l o v e r1 9 8 9 ，1 9 9 0 ； g l o v e r & l a g u n a1 9 9 7 ) 、进化计算算法( e v o l u t i o n a r yc o m p u t a t i o ne cf o g e l ，o w e n s & w a l s h ，1 9 6 6 ；h o l l a n d ，1 9 7 5 ) 、贪婪随机自适应搜索过程( g r e e d yr a n d o m i z e da d a p t i v e s e a r c hp r o c e d u r e s ，g r a s pf e o & r e s e n d e ，1 9 8 5 ，1 9 9 5 ) 、蚁群优化算法( a n tc o l o n y o p t i m i z a t i o na c od o r i g o & s t u t z l e ，1 9 9 2 ，1 9 9 9 ，2 0 0 2 ) ，全面介绍元启发式算法的文 献请参考g l o v e r 和k o c h e n b e r g e r ( 2 0 0 2 ) 的文章。 v h - “ p q 馑 基于并行蚁群优化的分类技术应用研究 2 2 蚁群优化( a c o ) 算法基本原理及其实现呻川 2 2 1 蚂蚁的觅食行为及双桥实验 在自然界中有很多种类蚂蚁的视觉感知系统都是发育不全的，甚至还有一些 种类的蚂蚁是完全没有视觉的，生物学家关于蚂蚁行为的研究表明，蚂蚁群体中 的个体之间以及个体与生存环境之问的信息传递大部分都是基于蚂蚁产生的一种 化学物质，而人们通常把这种化学物质称之为信息素( p h e r o m o n e ) 。在觅食过程中， 蚂蚁用信息素来标记已经走过的路径，这条路径往往是从食物源到蚁穴的最短路 径，后继的蚂蚁j 下是通过感知群体中其他个体释放的路径信息素选择最佳路径到 达食物的所在地，而蚂蚁觅食的这一自然生物行为方式j f 是蚁群优化算法( a n t c o l o n yo p t i m i z a t i o na c o ) 算法的灵感来源。当蚂蚁从蚁穴走到食物源，或者从食 物源走到蚁穴时，都会在其经过的地面上释放信息素，从而只要有蚂蚁经过的路 径都会附上蚂蚁释放出来的信息素，其他蚂蚁则可以探测出路径上的信息素的浓 度大小，并根据信息素浓度的不同来选择自己将要行走的路径，简单来说就是信 息素浓度最高的路径被其他蚂蚁选择重复行走的概率也是最高的。下图是著名的 双桥实验： 图2 1 双桥实验 f i g 2 1d o u b l eb r i d g ee x p e r i m e n t 第2 章基本蚁群优化算法模型及其改进算法 实 验 次 数 的 百 分 比 实 验 次 数 的 百 分 比 在某一分支卜的数量百分比( a ) 在较短分支上的数量再分比( b ) 图2 2 双桥实验得到的结果 f i g 2 1t h er e s u l to fd o u b l eb r i d g ee x p e r i m e n t 可以用以下方法进行解释这个实验结果，在( 图a ) 中在刚开始的时候两条分 支上都不存在信息素，所以蚂蚁第一次在这两条分支间进行选择的概率是相同的， 也就是说初始的选择不存在任何的偏向性。虽然初始选择的概率是相同的，但是 由于在选择的过程中会出现随机波动，使得两个分支上的蚂蚁数肯定会出现不同， 这样蚂蚁多的分支上所释放的信息素浓度肯定高于另一分支，高浓度的信息素又 吸引了更多的其他蚂蚁选择这条分支，这个系统的正反馈作用过程使得最后几乎 所有的蚂蚁都集中到了一条分支上；对于( 图b ) 的实验情况则不太一样，初始选 择时也跟上个实验一样，蚂蚁是以相同的概率进行选择分支路径，但是对于相同 基于并行蚁群优化的分类技术应用研究 蚂蚁数目的两条路径来说，短分支路径上的蚂蚁在蚁穴与食物源之间的一个来回 间隔要小，因此在短分支上更新的信息素的浓度就要高于长分支路径上的信息素 浓度，同样的，由于系统正反馈的作用机制，使得越来越多的蚂蚁选择短分支路 径，这也是上面这个双桥实验结果所展示的。 双桥实验的结果显示出了自然界中的蚂蚁群体具有一种内在的自优化能力， 它们可以凭借自身的生理机制找出所在环境中任意两点之间的最短路径，这就启 发我们能够通过一个概率函数来设计一种人工蚂蚁，让它们在模拟双桥的图上移 动，找出蚁穴和食物源两点间的最短路径。 2 2 2a s 模型的建立【1 2 _ 1 5 】 蚁群优化算法模型中的人工蚂蚁实际上代表的是一个构建图的过程，但这个 构建图是根据转移概率规则进行随机构建的，构建图的过程一般分为两个步骤， 第一步先随机选择一个节点，第二步则是按概率选择规则从符合条件的解成分( 节 点) 中挑选出最佳的节点依次添加从而构建出一个完整的路径解。我们考虑一个 最小化问题( s ，厂，q ) ，对每一个候选解s s 有，( s ，t ) 为目标函数值，其中时间参 数f 表明目标函数厂( s ，f ) 和问题的约束q ( f ) 都与时间f 有关，q ( f ) 是约束条件的集 合，找到一个全局的最优可行解s 就是整个组合优化问题的求解目标。给定了上 述的问题描述，a s 系统中的人工蚂蚁就可以通过在完全连接图g c = ( c ，l ) 上随机 游走并释放信息素来进行构建解，c 是完全图上的成分点，集合l 是连接边。图g c 称为构建图( c o n s t r u c t i o ng r a p h ) ，l 中的元素称为连接( c o n n e c t i o n s ) ，问题的 约束q ( f ) 包含在人工蚂蚁遵循的策略中。a s 算法的一般包含以下几个方面的内 容：构建图、约束、信息素和启发式信息、解的构建、信息素更新。下面以t s p 问题为例来实现a s 的建立。 构建图：在旅行商问题( t s p ) 中，问题的描述图与上述描述是一致的，成分 的集合c 对应着点的集合，也即c = 。边的集合对应着连接即= 彳，且在每一 第2 章基本蚁群优化算法模型及其改进算法 条边上都带有一个权值，代表点z 和j 之间的距离，整个问题的解状态就是旅行商 在游历过程中出现的所有可能的状态的集合。 约束：在旅行商游历的过程中每一个城市最多只能被访问一次且所有城市都 要被访问过这是旅行商( t s p ) 问题中唯一的约束。a s 算法的实现为：蚂蚁在每 一构建步中只能在还没有被访问过的城市集合中选择下一个城市节点，也就是说 蚂蚁k 在城市f 的可行解邻域彬是由所有还没有被访问过的城市所组成的。t s p 问题中的信息素t ，表示在访问城市i 后直接访问城市，的期望度；启发式信，亩, r l u 代 表蚂蚁随机选择城市j 的概率，一般直接取氇f 一1 d 矿 构建解：在解的构建方面，每一只蚂蚁最初都从一个起点城市出发，这个起 点城市是随机选取的，每经过一次迭代，蚂蚁就向当前解中添加一个尚未被访问 过的城市，当候选集中所有的城市都被蚂蚁访问过一遍之后，解的构建过程就终 止了。在这个过程中，蚂蚁之间都是利用启发式信息和信息素按照一定的概率规 则从所有候选城市中选择的，其选择概率公式如下： 露= 也也 磊 t 彳吖 j n ； 0 j 圣n ( 2 1 ) 其中嘞= l d 是启发式信息，这个启发式信息是预先给定的；参数口决定了信 息素的相对影响力，参数决定了启发式信息的相对影响力，而孵则是一个可行 域集合，它代表了蚂蚁k 在城市i 能够直接到达的所有相邻的城市。 参数口和声具有如下作用：如果口；0 ，那么最靠近f 的城市被选出来的概率 是最大的，这相当于一种经典的随机贪心算法；若一0 ，则只有信息素的放大系 数在起作用，也就相当于算法只使用了信息素的效果，而没有利用任何启发式信 息因素所带来解的偏向性，特别是在口 1 的情况下，算法很快就会陷入停滞的状 态，这个时候往往得到是是一个局部最优解，跟全局最优解相差甚大。 基丁并行蚁群优化的分类技术虑用研究 信息素的更新：当一条完整的路径被蚂蚁构建出来之后，蚂蚁将会更新每条 边上的信息素，首先，所有边上的信息素都会减少一个常量因子的大小，然后在 蚂蚁经过的边上增加信息素。信息素的蒸发根据下面的式子进行执行： 一( 1 一p ) v ( i ，j ) e l ( 2 2 ) 其中p 是信息素蒸发率，有0 p 1 。参数p 的作用是避免信息素的无限累积， 而且还可以使算法“忘记 前较差的路径。在信息素的蒸发步骤之后，所有的蚂 蚁都在它们经过的边上释放信息素： 一+ 晷噶v ( ，_ ) ( 2 3 ) 和。 其中口是第足只蚂蚁向它经过的边释放的信息素量。口噶定义为： 峥g 韫 4 ， 其中c 代表了第k 只蚂蚁建立的路径t 的长度，即在t 中所有边的长度之 从上面的结果我们可以看出，若蚂蚁构建出来的路径越短，那么这条路径上 的各条边就会获得相对多的信息素量。一般来说，如果选择同一条边上的蚂蚁数 目比较多，则该边所在的路径总长度就相对较短，那么这条边就会获得相对多的 信息素，在之后的迭代中它就更有可能被其他蚂蚁选择。 a s 算法的高层伪代码如下： p r o c e d u r ea c 0f o rt s p i n i t i a l i z e d a t e w h i l e ( n o tt e r m i n a t e ) d o c o n s t r u c t s o l u t i o n s u p d a t e p h e r o m o n e u p d a t e s t a t i s t i c s e n d w h i l e e n d - p r o c e d u r e 第2 章基本蚁群优化算法模型及其改进算法 2 3 基于a s 算法的几种改进算法 a s 算法是一个非常简单的基本算法，随着测试实验规模的不断扩大，a s 算 法的整体性能下降的非常严重，因而国内外很多学者关于a c o 算法的研究工作主 要集中在如何改进基本a s 算法上来提高算法的性能【1 铋】。其中最著名的两个性能 最佳的a c o 算法是最大最小蚂蚁系统m 删s 劬甜r a i n a n ts y s t e m ) 【1 6 】和蚁群系统 a c s ( a n tc o l o n ys y s t e m ) 1 1 7 , 1 s 1 。 2 3 1 最大最小蚂蚁系统m m a s ( m a x r a i na n ts y s t e m ) m m a s 算法针对a s 算法的不足，在其基础之上对彳s 算法做了4 项主要的改 进工作： 首先，它强调了对最优路径的开发，只有迭代最优的蚂蚁才被允许释放信息 素。( 在迭代中构建出最优路径的蚂蚁，分为当前最优和至今最优) 。其次，把 所有路径上的信息素大小的取值范围限制在一个区间 z 。i m 。 内。第三，将信息 素取值范围的上界设定为其初始值，并设置一个比较小的信息素蒸发率，这样做 的可以使得算法能在初始的搜索过程中能够尽可能多的进行路径搜索。最后，在 m m a s 算法中，每当系统进入了停滞状态，或者经过一定代数的迭代得到的路径 长度并没有得到改进，那么所有路径上的信息素都会被重新初始化，这样能够避 免系统陷入局部最优后算法停止。 信息素更新策略在m m a s 算法中也作出了改进：只有所有的蚂蚁都完成路径 构建之后，m m a s 算法力开始对路径上的信息素进行更新，其更新公式如下： _ ( 1 一p ) 锢露删 ( 2 5 ) 其中四z 乒7 1 c 6 8 。 2 3 2 蚁群系统a c s ( a n tc o l o n ys y s t e m ) a c s 算法也是a s 算法的基础上引入了以下3 个方面的改进： 第一，a c s 算法使用了一种的行为选择规则相较于彳s 算法更具积极意义，从 而能够得到比a s 更好的搜索效果。 基于并行蚁群优化的分类技术应用研究 第二，信息素释放动作和信息素蒸发都只在至今最优路径上进行，其他路径 不进行信息的释放蒸发。 第三，蚂蚁在构建路径的时候每经过一条边就会立即减少这条边上一定量的 信息素，这样就能加大蚂蚁探索其余路径的可能性。 在a c s 算法中，提出了伪随机比例规则，位于城市i 的蚂蚁k 根据这个规则选 择城市7 作为下一个访问的城市，这个规则由下式给出： f ；j a r g m a x 慨【n v a qs 吼 ( 2 6 ) ，皇j二o ， 。 i ， 否则 一 其中q 是一个随机变量，它服从区间 0 ，1 上的均匀分布，q o ( osq os1 ) 是一个 参数，它代表着当前蚂蚁选择最优移动方式的概率，而，由式( 2 1 ) 给出的一个 概率分布所产生出的随机变量( 其中口- - 1 ) ，也即蚂蚁每次都有1 一q o 的概率执行 式( 2 1 ) 所给出的规则即有偏向性的探索各条未知边。上面所谓的最优移动方式 就是根据启发式信息值和以往信息素的累积量求出来的( 即蚂蚁继续开发已知的 路径) 。通过调整参数q 。，可以控制蚂蚁对未知路径的探索程度，从而决定算法 是应该去探索未知区域还是集中搜索至今最优路径附近的区域。 信息素更新：在a c s 算法中，信息素的更新分为全局信息素更新和局部信息 素更新。在a c s 算法中，全局信息素更新规则如下，只有找到至今最优路径的蚂 蚁才能被允许在迭代之后释放信息素。a c s 算法的信息素更新规则由下面的式子 给出： * - - ( 1 - p ) r o + 加哼v ( i ，j ) e t 缸 ( 2 7 ) 其中墨毋；1 c 缸，值得注意的是，在a c s 算法中，只有丁缸这条最优路径的边 上的信息素才能释放或蒸发。除了全局信息素的更新规则之外，a c s 算法还使用 了一个局部的信息素更新规则，蚂蚁在路径的构建过程中每经过一条边o ，j ) 就会 立刻调用这条更新规则更新该边上的信息素： _ ( 1 - 亭) r o + 鼠 ( 2 8 ) 第2 章基本蚁群优化算法模型及其改进算法 其中，亭和是两个参数，亭满足0 宇 1 ，z o 是信息素量的初始值。 基于并行蚁群优化的分类技术应用研究 第3 章数据分类算法 3 1 数据挖掘技术概述 数据挖掘( d a t am i n g ) 技术就是将有用的知识从海量数据中“挖掘”或“提 取”出来。现代的数据挖掘技术都是从机器学习、统计学和数据库这三个主要方 面来定义的。从不同的角度来理解数据挖掘的定义都不同：数据挖掘技术从机器 学习的观点来看是从海量数据中抽取有用信息，这些有用的信息往往隐藏在海量 的未知数据当中；数据挖掘技术从数据库的角度来看指的是发现知识的一个过程。 数据库提供了基本的数据模型并存贮数据，数据库中的知识发现( 1 d ) 是识别 可理解的数据模式的一个过程【2 5 】，这是有效、新颖、具有潜在用处，而k d d 的过 程说明了知识发现经常意味着经验、重复、用户的交互设计、决策和习惯等。一 般的说，k d d 通过数据库中的知识发现表明了一个从低层次数据抽象到高层知识 的过程，在数据库中的数据及相关集合中人们可以抽象出对自己有用的知识、有 规律的数据或者高层次的信息。从根本上来说，数据库中的知识发现( k d d ) 与 数据挖掘( d m ) 是不同的，但是也有人把他们等同看待，其实数据挖掘( d m ) 只是k d d 的一个步骤。现在数据挖掘汇聚了不同领域的研究者，形成了一门交叉 学科。 一般的数据挖掘的过程如下： ( 1 ) 问题的定义：首先需要确定数据挖掘的任务和目的，这是数据挖掘过程 中最重要的一步。 ( 2 ) 数据准备：确定了任务和目的之后就是预处理数据。 3 2 数据挖掘的功能【冽 数据挖掘系统可以根据所挖掘的知识类型的不同可以分为特征和区分 ( c h a r a c t e r i z a t i o na n dd i s c r i m i n a t i o n ) 、关联分析( a s s o c i a t i o na n a l y s i s ) 、分类分 析( c l a s s i f i c a t i o na n a l y s i s ) 、偏差分析( d e v i a t i o na n a l y s i s ) 、聚类分析( c l u s t e r i n g 第3 章数据分类算法 a n a l y s i s ) 、相似性分析( s i m i l a r i t ya n a l y s i s ) 、演变分析( e v o l u t i o na n a l y s i s ) 、孤 立点分析( 异常数据) ( o u t l i n e ) 等分类。 ( 1 ) 特征和区分 目标类数据特性的汇总或者一个一般特征就是数据的特征，通常数据特征是 由用户通过指定到类数据库查询收集的；区分描述的输出是区分规则，用户可以 对特征和区分的描述进行操作。所谓数据区分就是将其他对比类对象与目标类对 象的一些一般特征进行比较，目标类和对比类都是由用户来指定的，而对应的数 据则是通过数据库来查询提取的。 ( 2 ) 关联分析 关联规则的一般形式是形如：x 号y ，即“4a a 以垮且a a 吃的规 则。其中4 f o 1 ，肌) ) ，b ，( 歹 1 ，咒) ) 是属性和对应属性的值。关联分析用于建 立各个数据对象之间已经存在的隐含的联系，关联分析实质上就是发现关联规则。 ( 3 ) 分类和预测 分类就是描述或识别数据类或概念的模型的一个过程，它通过训练集建立模 型，并使用所得到的模型来预测类标号未知的对象。因为分类所得到的模型是基 于对训练数据集的分析，所以分类可以用来预测数据集中对象的类编号，但是在 某些应用中，人们可能希望预测未知的数据值或某些遗漏的而不仅仅只是类标号， 从这样的角度上来讲，若所需要的预测值为数值数据，通常都称之为预测。预测 不仅涉及数据值预测而且还涉及到类标号预测，但是通常意义上预测都是只限于 值预测，因此和分类还是有着本质上的不同。相关分析与分类和预测的实现时间 点是不同的，它是在分类和预测前进行的一项活动，其主要功能是将对于分类和 预测无用的属性排除出去。 ( 4 ) 聚类分析 聚类分析分析的是数据对象而不考虑已知的类标号，它的作用与分类和预测 不同，一般的在聚类分析的过程中，所提供的训练数据是不提供类标号的，聚类 的作用就是根据数据属性产生我们所需要的标号，所有的数据对象的划分依据都 基丁并行蚁群优化的分类技术虑