（管理科学与工程专业论文）遗传算法及其在聚类分析中的应用.pdf

硕士学位论丈 m a s t e r st h e s i s 中文摘要 遗传算法是以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与 群体内部染色体的随机信息交换机制相结合的高效全局寻优算法。它提供了一种求 解非线性、多模型、多目标等复杂系统优化问题的通用框架，它不依赖于问题具体 的领域，已经广泛应用于许多科技领域并取得了成功。但是传统遗传算法有一些不 足，如收敛速度慢，有时会出现早熟收敛等。遗传算法还需要进一步研究。 聚类分析是数据挖掘中的核心技术之一，也是多元统计分析的主要分支之一。 经过多年的发展，聚类分析具有坚实的理论基础并形成了系统的方法学体系，然而 传统聚类分析方法大多局限于理论上的分析并依赖于对数据分布特征的概率假设， 较少考虑具体应用中的实际数据特征与差异。因此，如何克服传统聚类分析方法对 这种概率假设的依赖，成为近年来学术界的研究热点。 本文针对上述问题开展遗传算法改进以及基于遗传算法的聚类分析方法研究。 在深入分析普通遗传算法和传统聚类分析方法机理的基础上，分别提出了一种模糊 自适应遗传算法和伪并行遗传聚类分析方法。模糊自适应遗传算法的思想是通过模 糊推理系统，利用种群的方差和熵来自适应调整交叉概率和变异概率，从而保证种 群的多样性，仿真实验结果表明这种遗传算法明显地提高了寻优性能，较好解决了 普通遗传算法的早熟收敛问题；伪并行遗传聚类分析方法的思想是采用实数编码方 式对每个样本所属的类别进行编码，通过空类的识别和修复来修正不合法的染色 体。在引入离散随机变异算子和优化方向变异算子的基础上，结合迁移策略和插入 策略，达到兼顾局部收敛速度和全局收敛性能的目的，从而克服了传统的基于聚类 准则的聚类算法对初始化敏感以及容易陷入局部极值的问题。与k 一均值算法对比仿 真实验，表明了这种基于伪并行遗传算法的聚类新方法的可行性和有效性。 关键词：遗传算法；聚类分析；模糊控制器：伪并行遗传算法 a b s t r a c t g e n e t i ca l g o r i t h mb a s e do nn a t u r a ls e l e c t i o na n dg e n e t i ct h e o r y , i sag l o b a l o p t i m i z a _ t i o na l g o r i t h mw h i c hc o m b i n et h er u l e s o ft h ef i t t e s ts u r v i v a la n dt h e c _ h r o m o s o m e sr a n d o mp e r m u t a t i o nm e c h a n i s mw i t h i ng r o u p si nt h ep r o c e s so fb i o l o g i c a l e v o l u t i o n i tp r o v i d e st h ec o m m o nf r a m e w o r kf o ras o l u t i o no fn o n l i n e a r , m u l t i m o d e l ， m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e mi nt h ec o m p l e xs y s t e m s i tn e e d s n o td e p e n do nt h e s p e c i f i ca r e a so ft h ep r o b l e m ，a n dh a sb e e nw i d e l ys u c c e s s f u l l yu s e di nm a n yf i e l d so f s c i e n c ea n dt e c h n o l o g y h o w e v e r , t r a d i t i o n a lg e n e t i ca l g o r i t h mh a ss o m es h o r t c o m i n g s ， s u c ha ss l o wc o n v e r g e n c e ，a n dp r e m a t u r ec o n v e r g e n c es o m e t i m e sa n ds oo i l g e n e t i c a l g o r i t h ma l s on e e d sf u r t h e rs t u d y c l u s t e ra n a l y s i si so n eo ft h ec o r et e c h n o l o g i e so fd a t am i n i n ga sw e l la so n eo ft h e m a i l lb r a n c ho fm u l t i v a r i a t es t a t i s t i c a la n a l y s i s a f t e ry e a r so fd e v e l o p m e n t ，c l u s t e r a n a l y s i sh a sas o l i dt h e o r e t i c a lf o u n d a t i o na n df o r m e das y s t e m a t i ca p p r o a c hs y s t e m h o w e v e rt h et r a d i t i o n a lc l u s t e ra n a l y s i sm e t h o dh a sl a r g e l yb e e nc o n f i n e dt ot h e o r e t i c a l a n a l y s i sa n dp r o b a b i l i t ya s s u m p t i o n si n t h ed a t ad i s t r i b u t i o n , f e w e rt oc o n s i d e rt h e s p e c i f i cc b a 形嵋t e r i s t i c sa n dd i f f e r e n c e sa m o n gt h ea c t u a ld a t a t h e r e f o r e ，t h ep r o b l e m h o wt oo v e r c o m et h ed e p e n d e n c eo fp r o b a b i l i t yh y p o t h e s i s i nt h et r a d i t i o n a lm e t h o d o fc l u s t e ra n a l y s i sh a sb e c o m ea na c a d e m i cr e s e a r c hh o ts p o tp r o b l e mi nr e c e n ty e a r s a c c o r d i n gt h ea b o v e m e n t i o n e di s s u e s ，t h i st h e s i sw i l lr e s e a r c ht h ei m p r o v e m e n to f g e n e t i ca l g o r i t h ma n dc l u s t e ra n a l y s i sw h i c hb a s e do nt h eg e n e t i ca l g o r i t h m w i t ht h e r e s e a r c ho fm e c h a n i s mb e t w e e ng e n e r a lg e n e t i ca l g o r i t h ma n dt r a d i t i o n a lm e t h o do f c l u s t e ra n a l y s i s ，ip r e s e n ts o m em e t h o d sf o re a c ho t h e r ：f u z z ya d a p t i v eg e n e t i ca l g o r i t h m ， p s e u d o p a r a l l e lg e n e t i cc l u s t e ra n a l y s i s m e t h o d t h ei d e ao ff u z z ya d a p t i v eg e n e t i c a l g o r i t h mw h i c hu s e dp o p u l a t i o nv a r i a n c ea n de n t r o p yi sd e d i c a t e dt oa d j u s tt h ec r o s s p r o b a b i l i t ya n dm u t a t i o np r o b a b i l i t yi nt h ef u z z yi n f e r e n c es y s t e m ，s oi t w i l le n s u r et h e d i v e r s i t yo ft h ep o p u l a t i o n t h er e s u l t so f s i m u l a t i o ne x p e r i m e n t ss h o wt h a tt h e p e r f o r m a n c eo fg e n e t i ca l g o r i t h mh a sb e e nl a r g e l yi m p r o v e d ，i ti s b e t t e rt os o l v et h e g e n e r a lg e n e t i ca l g o r i t h mp r o b l e m o f p r e m a t u r ec o n v e r g e n c e ；t h e i d e ao f p s e u d o p a r a l l e lg e n e t i cc l u s t e r i n ga n a l y s i si st h a tw ec o u l de n c o d es a m p l e so f e a c ht y p e w i t hr e a l c o d e d ，t h r o u g ht h ea i rk i n do fi d e n t i f i c a t i o na n dt h e nr e p a i rt h e i n c o r r e c t i i 硕士学位论炙 m a s t e r st h e s i s c l l r o m o s o m e b a s e do nt h ei n t r o d u c t i o no fd i s c r e t er a n d o mm u t a t i o na n do p t i m i z a t i o n d i r e c t i o nm u t a t i o no p e r a t o r , w ec a nc o m b i n em i g r a t i o ns t r a t e g i e sa n di n s e r tt a c t i c s ， a c h i e v et h ep u r p o s eo fb o t hl o c a lc o n v e r g e n c es p e e da n dg l o b a lc o n v e r g e n c ep r o p e r t i e s c o n s e q u e n t l y , t h i sm e t h o dw i l lo v e r c o m et h ei n i t i a l i z a t i o ns e n s i t i v ei s s u e ，a sw e l la st h e i s s u eo fe a s yt of a l li n t ol o c a le x t r e m ew h i c ho w n e db yt h et r a d i t i o n a l c l u s t e r i n g a l g o r i t h mb a s e do nt h ec l u s t e r i n gc r i t e r i a t h es i m u l a t i o ne x p e r i m e n tc o m p a r e d 谢m k - m e a n sa l g o r i t h ms h o w st h a tt h en e wc l u s t e r i n gm e t h o db a s e do nt h ep s e u d o - p a r a l l e l g e n e t i ca l g o r i t h mi sf e a s i b l ea n de f f e c t i v e k e y w o r d s ：g e n e t i ca l g o r i t h m ；c l u s t e ra n a l y s i s ；f u z z yc o n t r o l l e r ；p s e u d o - p a r a l l e l g e n e t i ca l g o r i t h m i 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 土蠛喊川年6 其如 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中 师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 作者签名：王塌 喊砷年月 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布，并可按“章程”中的 规定享受相关权益。回童诠塞堡窒卮溢卮! 旦圭生；旦二生；旦三生筮盔! 作者签名：王娟 作者签名：土嗄惫 日期：砷年月r 日 导师签名： 弓磋犬八 呐：叩年二月，日 八m，卜月似傻刁年 名 沙 签 师期 字日 硕士学位论丈 m a s t e r st i - 1 e s l s 1 1 引言 1 绪论 1 1 1 选题的依据及意义 1 9 7 5 年，美国密歇根大学的心理学教授、电子工程学与计算机科学教授 j o h n h h o l l a n d 和他的同事与学生共同研究了具有开创意义的遗传算法理论和方 法。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、 自适应搜索算法。简单而言，它使用了群体搜索技术，将种群代表一组问题解，通 过对当前种群施加选择、交叉和变异等一系列遗传操作，从而产生新一代的种群， 并逐步使种群进化到包含近似最优解的状态。“遗传算法以单一字符串的形式描述 所研究的问题，只需利用适应度函数值来进行优化计算，而不需要函数导数等其它 辅助信息，特别适合解决其它搜索算法无法解决或难以解决的复杂的和非线性的问 题。而且其思想简单、易于实现以及表现出来的健壮性，因而遗传算法赢得了许多 应用领域，特别是近年来在问题求解、优化和搜索、智能控制、机器学习、人工生 命和模式识别等领域取得了许多令人鼓舞的成就1 。 “以遗传算法为核心的进化 算法，已与模糊系统理论、人工神经网络等一起成为计算智能研究中的热点，受到 广泛的关注。但是，遗传算法作为一种随机优化算法，存在一些自身的局限性，其 中最主要的问题是收敛速度慢和早熟两大问题口1 。”圆目前，国内外专家就收敛速度 慢和早熟问题已经开发出了多种各不相同的改进遗传算法，使得遗传算法的性能不 断得到提高，但仍存在缺陷，遗传算法还需进一步研究。 聚类分析是数据挖掘中的核心技术之一，是研究数据问逻辑或物理的相互关系 的技术。它通过一定的规则将数据集划分为在性质上相似的数据点构成的若干个 类。聚类分析的结果不仅可以揭示数据间的内在联系与区别，同时也为进一步的数 据分析与知识发现提供了重要的依据，如数据问的关联规则，分类模式以及数据的 变化趋势等。作为统计学的重要研究内容之一，聚类分析具有坚实的理论基础并形 成了系统的方法学体系1 ，然而，基于统计学的聚类分析方法大多局限于理论上的 分析并依赖于对数据分布特征的概率假设，较少考虑具体应用中的实际数据特征与 韩万林，张幼蒂：遗传算法的改进，中国矿业大学学报2 0 0 0 ，1 ( 2 9 ) ：1 0 2 1 0 5 w o n gs c ，w o n gc k ，a n dt o n gc o ap a r a l l e l i z e dg e n e t i ca l g o r i t h mf o r t h ec a l i b r a t i o no fl o w r ym o d e l y 1 p a r a l l e lc o m p u t i n g 2 0 0 1 ，2 7 ( 1 2 ) ：1 5 2 3 1 5 3 6 ： 硕士学位论炙 m a s t e r st h e s i s 差异。面对传统聚类方法的局限性，近年来，一些学者提出基于遗传算法的聚类方 法h 儿5 1 ，并取得了较好的效果。但是遗传算法仍然存在一些缺陷，如局部搜索能力 差，容易陷入早熟，效率不高。因此进一步开展遗传算法在聚类分析中的应用研究 是很有意义的研究的方向。 1 1 2 本文所做的工作 遗传算法是以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与 群体内部染色体的随机信息交换机制相结合的高效全局寻优搜索算法。本文全面研 究遗传算法的理论研究和应用研究现状。其中遗传算法的理论研究着重研究算法理 论基础、数学模型，早熟机理的探索与预防，参数设置对算法的影响，编码方法和 并行计算等方面。在应用方面，主要研究目前遗传算法在聚类分析中应用状况。 尽管遗传算法有很多优点，也有许多专家学者对遗传算法进行不断研究，但目 前存在的问题依然很多。其中早熟问题是遗传算法改进的一个关键方面，本文针对 早熟问题，结合模糊控制器来自适应调整遗传算子，实现自适应模糊遗传算法。聚 类分析是数据挖掘的重要内容，本文将遗传算法应用于聚类分析中，设计了一种基 于伪并行遗传算法的聚类分析方法，实验证明了该方法聚类的有效性。 1 2 国内外研究现状 1 2 1 国内外遗传算法理论研究现状 早在2 0 世纪4 0 年代，就有学者开始研究如何利用计算机进行生物模拟的技术， 他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。进入 6 0 年代后，美国密执安大学的h o l l a n d 教授及其学生们受到这种模拟技术的启发， 创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率 优化技术遗传算法。“1 9 6 7 年，h o l l a n d 的学生b a g l e y 在其博士论文中首次提 出了“遗传算法 一词，他发展了复制、交叉、变异、倒位、显性等遗传算子，在 个体编码上使用双倍体的编码方法。h o ll a n d 教授用遗传算法的思想对自然和人工 自适应系统教学研究，提出了遗传算法的基本定理模式定理( s c h e m at h e o r e m ) ， 并于1 9 7 5 年出版了第一本系统论述遗传算法和人工自适应系统的专著a d a p t a t i o n i nn a t u r a la n da r t i f i c i a ls y s t e m e l 。 “进入9 0 年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研 雷英杰，张善文，李继武，周创明：( m a t l a b 遗传算法工具箱及应用，西安电子科技人学f j j 版社2 0 0 5 ：1 8 2 硕士学位论丈 m a s t e r st h e s i s 究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应 用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业 应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中办得到了迅 速的发展，这些无疑都给遗传算法增添了新活力口1 。”下面分别从遗传算法的理论 研究和应用研究来介绍遗传算法的研究现状。 遗传算法的理论研究主要集中在算法理论基础、数学模型、早熟机理的探索与 预防、参数设置对算法的影响、编码方法和并行计算等方面。下面分别论述： ( 1 ) 遗传算法的理论基础、数学模型 “遗传算法的理论基础、数学模型主要集中于对算法的收敛性、复杂性、收敛 速度的研究。h o l l a n d 首先用模式定理“解释”了遗传算法的搜索行为，该研究成 果奠定了遗传算法的数学理论基础阳9 l 。最近，一些学者对模式定理的正确性提出 了质疑。马丰宁n 伽通过测试黎曼函数和相应的理论分析，指出模式定理推导中的错 误，并提出了新模式定理；g r e f e n s t e t t e n 指出模式定理不能保证适应度变换的唯 一性。”圆近几年，遗传算法全局收敛性分析取得了突破性进展。利用m a r k o v 链分 析基本遗传算法的性能被使用；也有学者利用m a r k o v 链状态转移矩阵的特征根来 分析遗传算法的收敛行为。w a l s h 函数分析和傅里叶分析是遗传算法过程分析的重 要工具。w a l s h 函数是基函数完备的正交集，可提供类似傅罩叶变换的表示方式。 “b e t h k e 口6 1 运用w a l s h 函数和模式转换发展了一种有效的分析方法；h o l l a n d 进一 步扩展了这种计算。k o s t e r s 等 使用傅里叶函数来分析遗传算法，建立了一套完 整的分析框架。1 9 9 5 年，s t a n f o r d 大学w o l p e r t 和m a c r e a d y 教授提出了n of r e el u n c h 定理( 简称n f l ) n 町，它是一个重要理论研究成果。总体而言，遗传算法的基础理论 研究至今还没有取得突破性进展，理论与应用之间还存在着很大差距。” ( 2 ) 编码方法 “遗传算法自2 0 世纪7 0 年代初提出以来，在许多领域的理论与工程实践中都有 成功的应用。其编码方法也在不断地改进。最基本的是二进制编码。其它的编码方 法有格雷码、实数编码、符号编码、多参数编码和编码等，并在相关领域的优化应 用中取得了很好的效果。”在具体问题中采用何种编码对算法的性能有很大影响， 也是遗传算法首要要解决的问题。模式定理、积木块假设都适合采用二进制编码， 在其基础上定义的。但是二进制编码存在汉明距离的问题。灰色编码可用于克服二 。王宏杰，魏先峰，薛周，建彭丹：遗传算法综述科技经济市场2 0 0 8 6 ：1 4 o 马：l 三宁遗传算法与遗传规划运行机理的研究天津人学博一l ：学位论文1 9 9 8 李敏强，寇纪淞，林丹等：遗传算法的皋奉理论及心用北京：科学j f ；版社，2 0 0 2 哚，f r 明，刘玉树，阎光伟：遗传算法的编码理论j 应用计算机工程与应用2 0 0 6 0 3 第8 6 页 3 硕士学位论文 m a s t e r st h e s i s 迸制编码映射的不连续问题。“为了克服早熟现象，s c h r a u d o l p h 等n 町提出了动态变 量编码，通过对d e - j o n g 的5 个函数进行测试，发现动态变量编码的优化效果优于普 通二进制编码。双倍体是高等生物染色体的重要特性，有长期记忆等作用，早期的 研究者提出了双倍体表示咖1 。g o l d b e r g 和s m i t h 2 1 1 用动态背包问题进行比较研究， 实验表明双倍体比单倍体的跟踪能力强。浮点数编码具有精度高、便于大空问搜索 的优点，因此浮点数编码越来越受到重视。 “此外，多值编码、实值编码、区间 值编码、d o l t a 编码、对称编码以及将以往的合成编码分解成多个相对独立编码的 独立编码策略等多种编码方法也都被证明各有优缺点。” 这些编码方法的提出是启 发式的，目前还缺乏理论基础来判断各种编码方法的好坏并指导它们的设计。因此 建立完善的理论指导是非常必要的。 ( 3 ) g a 参数选取 控制参数选择的是否合理直接影响算法的收敛速度和搜索效率，当前没有完善 的理论指导它的选择，还主要是根据经验。遗传算法需要选择的运行参数主要有群 体规模地交叉概率凡、变异概率p m 、终止代数l 这些参数对遗传算法的性能 有较大的影响，需恰当的选取。传统的杂交概率和变异概率的设置是静态人工设置。 现在有人提出动态参数的设置方法，以减少人工选择参数的困难和盲目性。 ( 4 ) 早熟问题 遗传算法的早熟问题也就是未成熟收敛问题，还没有找到最优解，种群已经失 去了进化能力。如果不解决这个问题，那么就难以发挥遗传算法的性能，解决复杂 问题。那么怎样判断是否是早熟，或者未成熟收敛。通常的表现是群体中所有的个 体进化一定的代数后就陷于同一极值而停止进化了，或者接近最优解的个体总是被 淘汰，算法一直不收敛，找不到最优解。考虑导致未成熟收敛的原因，在遗传算法 进化的各个步骤都可能引起这个问题。其中最主要的原因是在进化过程中，未得到 最优解以前，群体就失去了多样性。所以防止早熟问题要控制种群多样性。“目前 判断早熟收敛的方法主要是根据群体适应度均方差嘲2 副在连续几代的变化情况来 确定，若其变化微弱或保持不变，则说明种群早熟收敛。但仅靠这一变化量来断定 种群是否早熟收敛是不全面的。邓莉1 提出了将种群的进化代数和群体适应度均方差 作为模糊逻辑控制器判断早熟收敛的标准。” “李世伦等1 为避免近亲繁殖导致早 熟，提出了基于模糊聚类的种群分类改进的遗传算法。但是这些算法未将遗传操作与 。余有明，刘玉树，阎光伟：遗传算法的编码理论孑应用计算机工程与应用2 0 0 6 0 3 第8 6 页 。郑程s ，郝忠孝：遗传算法理论综述，计算机丁程j 设计2 0 0 3 2 1 第5 0 页 邓莉，鲁瑞华：一种改进的抑制早熟收敛的模糊遗传算法，计算机科学2 0 0 7 1 1 1 5 0 - 1 5 3 4 硕士学位论丈 m a s t e r s1 h e s i s 种群的进化状态联系起来，忽视了遗传操作与内部进化状态的相关性。 ( 5 ) 并行计算 “遗传算法在解决一些实际问题时，由于它一般具有较大的群体规模，需要对 较多的个体进行大量的遗传和进化操作，特别是要对大量的个体进行适应度计算和 评价，从而使得算法的进化运算过程进展缓慢，难以达到计算速度的要求，因而人 们越来越重视遗传算法的并行计算问题。 并行计算的基本思想是先将复杂的任 务分解成若干个子任务，再将多个子任务对应多个处理器，最后它们各自在各自的 处理器上单独运行。并行遗传算法就是基于以上的思想。将遗传算法在多个并行计 算机上执行，以提高效率，解决一些非常复杂的问题。当前，全局并行遗传算法、 粗粒度并行遗传算法、细粒度并行遗传算法和混合并行遗传算法是并行遗传算法的 四大类。目前，最为流行的是粗粒度并行g a 。“文献 2 9 1 讨论了并行g a 的迁移现象 及群体规模估算模型，分析了迁移的过程，揭示了迁移的实质，并提出了在理想条 件下的迁移计算模型。基于迁移计算模型导出了粗粒度并行g a 进化质量评估模型。 虽然并行遗传算法能有效地求解许多难题，也能在不同类型的并行计算机上有效地 实现。但仍有一些基本的问题需要解决d 引，如：确定通信拓扑，如何降低通信开销， 能否找到最优的区域数等。 固 “并行遗传算法的硬件支持环境一般要求在并行机( t r a n s p u t e r 网络，s i m d ， m i m d 等) 或局域网上实现，而对于很多实时性要求不高的优化问题，这样的运行环 境是不需要的。因此，在并行遗传算法思想上产生的伪并行遗传算法被需要也被广 泛的应用。”近十几年来，遗传算法得到了迅速发展。“遗传算法提供了一种求解 复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强 的鲁棒性，所以很多学科都有广泛应用。目前，遗传算法在生物技术和生物学、化 学和化学工程、计算机辅助设计、物理学和数据分析、医学与医学工程、动态处理、 建模与模拟、微电子学、模式识别、生产调度、人工智能、电信学、机器人学、开 矿工程、售货服务系统等领域都得到应用，成为求解全局优化问题的有力工具之一 【6 】” 李世伦，罗懋康，何小勇：基于种群分类解决遗传算法的“早熟”与“漂移”问题p q j i i 大学学报( 工程科学 版) 2 0 0 6 i i ：1 2 7 1 3 0 圆郑市平，郝忠孝遗传算法理论综述计算机工程与设计2 0 0 3 2 1 第5 0 页 o 朱长武，戴e 平，刘智并行遗传算法在并行多机调度中的心用微计算机信息2 0 0 7 2 3 ( 2 - 3 ) ：2 0 0 2 0 1 陈晓方、桂1 j 华、吴敏、王雅琳一种基于混沌迁移的伪并行遗传算法及j 应用控制理论与应用2 0 0 4 1 2 第 9 9 7 页 雷英杰，张善文，李继武等m a t l a b 遗传算法工具箱及应用西安：两安电子科技大学；i 版社2 0 0 5 ：1 5 ： 硕士学位论炙 m a s t e r st h e s i s 1 2 2 国内外遗传算法在聚类分析中的应用研究现状 聚类分析是数据挖掘中的核心技术之一，也是模式识别中的一个重要问题。近 年来，出现一些利用遗传算法进行聚类分析的研究，且取得了较好的效果口妇口2 儿圳。 “这种方法采用了k 一均值的基本思想，与k 一均值不同的是它使用遗传算法而不是 一般的迭代来进行聚类划分的优化。基于遗传算法的聚类方法的优点是不需要关于 待分类数据的先验分布知识，也不会受初始解选择的影响而得到次优解m ，。 “1 9 9 3 年f a l k 提出了所谓的分组遗传算法( g r o u p i n gg e n e t i ca l g o r i t h m ，g g a ) 】，他设计适当的染色体表达来获取问题的编码，并应用于各种分组、分割以及聚 类问题。1 9 9 4 年a l - s u l t a n 提出用t a b u 搜索算法求解k - m e a n s 聚类问题，它通 过对划分矩阵u 的随机搜索以获得全局最优解。1 9 9 9 年k r i s h m a 以k 均值算子代 替交叉算子，设计了一种混合遗传算法口 ，并根据g u n t e r 引入的有限状态齐次马 尔可夫链证明了该算法以概率1 收敛到全局最优点。”圆“2 0 0 0 年m a u l i k 采取聚类 中心的浮点数编码方式啪1 ，设计了浮点数交叉、变异操作，从而使遗传算法的搜索 效率得以提高。2 0 0 2 年，c r i s t o f o r d 将遗传算法与k - m e a n s 结合起来，并且使用 变长基因编码，它不仅能提高k - m e a n s 算法的效率，还能运行多个k - m e a n s 算法以 确定合适的k 值例。s a r a f i s 则将遗传算法应用于k - m e a n s 的目标函数构建中，并 提出了一个新的聚类算法h 们。固2 0 0 6 年，朱玲利等h 1 3 将遗传算法和聚类分析结合提 出遗传聚类分割并应用于c 工图像分割中。2 0 0 8 年，刘宇在文献h 2 3 中提出了基于自 适应遗传算法的模糊聚类算法，并将其应用于员工绩效考核成绩。 然而，实验证明当样本数目、维数和类别数较大时，这些算法常常会出现早熟 现象，即过早的收敛于局部极优点的现象。聚类问题的规模越大，早熟越容易发生。 虽然某些算法在理论上是以概率l 收敛至全局最优的，但是这种收敛性是由变异过 程中概率转移矩阵的互通性保证的，而通常变异操作仍然很难从局部极优点跳出， 遗传算法从初始状态到全局最优状态的转移时间的平均期望可能大大超过我们的 预期。因此，好的遗传聚类算法应该兼顾局部收敛速度和全局收敛性。 不论从理论还是应用的角度看，最紧迫的应是关于算法收敛性问题的研究，特 别是过早收敛的防止。“这对g a 的实际应用关系重大。就g a 本身的研究而言，应 该说，我国起步较晚，近十几年才陆续看到一些介绍性的文章、专著以及初步的研 究报告。和国外工作比较，国内工作多只停留在论文这一层次，很少看到具体实际 应用，与研究成果商品化的差距就更远。理论研究与实际应用不够紧密，阻碍我国 傅景广，许刚，王裕国基于遗传算法的聚类分析计算机工程2 0 0 4 ，3 0 ( 4 ) ：1 2 2 1 2 4 圆m i 二 固f d j 上 6 ： 硕士学位论丈 m a s t e r st h e s l s 高新技术的迅速发展。 1 3 主要研究思路和研究方法 1 3 1 主要研究思路 首先，从理论研究和应用研究两个方面来全面分析遗传算法的研究现状。理论 研究是基础，着重研究算法理论基础、数学模型，早熟机理的探索与预防，参数设 置对算法的影响，编码方法和并行计算等方面。而应用研究是目的，着重分析遗传 算法在聚类分析中的应用现状。然后，针对遗传算法的不足，提出改进算法。接着， 在分析遗传算法在聚类分析中的应用现状的基础上，提出新的基于遗传算法的聚类 方法。再对该算法结合行业景气分析与预测的景气指标筛选开展实证研究，来验证 算法的有效性。最后，对整篇论文进行总结。 1 3 2 主要研究方法 ( 1 ) 一次文献和二次文献的查阅 对遗传算法、聚类分析等理论知识，虽然通过研究生阶段的学习已经有一定程 度的积累，但要想出色地完成本论文的创作，这些知识还需要进一步的巩固和扩展、 需要进行全面而系统化的掌握，所有这些都需要通过一次文献和二次文献的查阅来 完成。 ( 2 ) 实验模拟和仿真分析 本论文中涉及到一些算法的设计和分析，如遗传算法的改进、基于遗传算法的 聚类算法，要想对这些算法的性能( 主要表现为算法的复杂性和效率) 进行分析， 需要用相应的工具( 如m a t l a b 等) 进行实验模拟和仿真分析。 1 4 主要研究内容及创新点 1 4 1 主要研究内容 ( 1 ) 遗传算法的研究现状研究 全面研究遗传算法的理论研究和应用研究现状，是整个论文研究的基础。其中 遗传算法的理论研究着重研究算法理论基础、数学模型，早熟机理的探索与预防， 西傅景广，许刚，= f 裕国基于遗传算法的聚类分析计算机工程2 0 0 4 ，3 0 ( 4 ) ：1 2 2 1 2 4 7 ： 硕士学位论文 m a s t e r st h e s l s 参数设置对算法的影响，编码方法和并行计算等方面。在应用方面，主要研究目前 遗传算法在聚类分析中应用状况。 ( 2 ) 遗传算法的改进问题研究 尽管遗传算法有很多优点，也有许多专家学者对遗传算法进行不断研究，但目 前存在的问题依然很多，如：适应度值标定方式多种多样，没有一个简洁、通用的 方法；早熟问题：收敛较慢。因此需要进一步研究遗传算法的改进问题。 ( 3 ) 遗传算法在聚类分析中的应用研究 一些学者已经开展遗传算法在聚类分析中的应用研究，并取得了一定的效果， 但是遗传算法仍有一些缺陷，而且还面临着计算复杂度的问题。因此进一步开展遗 传算法在聚类分析中的应用研究是很有必要。 1 4 2 本文创新之处 ( 1 ) 本文围绕遗传算法和遗传算法在聚类分析中的应用展开研究，对遗传算 法及其在聚类分析中的应用现状进行了深入剖析。 ( 2 ) 针对标准遗传算法在实际应用中存在的早熟问题，设计了标准遗传算法 的一种改进形式模糊自适应遗传算法。 ( 3 ) 针对传统的基于聚类准则的聚类算法初始化敏感和容易陷入局部极值的 问题，设计了一种新的基于伪并行遗传算法的聚类方法。 ： 硕士学位论丈 m a s t e r st h e s i s 2 遗传算法介绍 2 1 遗传算法实现技术 遗传算法的主要操作包括选择、交叉和变异；编码和适应度函数的设计也是其 中的关键。对于参数的选择目前主要是根据经验进行选取。有些很复杂带有约束参 数的问题也要解决约束处理问题。 2 1 1 遗传算法伪代码和流程图 遗传算法是1 9 7 5 年美国教授h o l l a n d 与他的学生和同事共同研究提出来的， 它是模拟自然界生物进化机制发展起来的随机全局搜索和优化方法。就其发展过程 而言，2 0 世纪7 0 年代是兴起阶段，8 0 年代是发展阶段，9 0 年代至今是高潮阶段。 它不依赖问题的具体领域，具有广泛的适用性。 标准遗传算法也口l 基本遗传算法，它给出了遗传算法的最原始的基本的结构原 理，通常只包括选择、交叉和变异三个遗传算子。它是一种借鉴生物界自然选择和 自然遗产机制的随机搜索算法。它易于理解，已经有一些现成的程序可以利用，很 多改进的遗传算法都是在起基础上发展起来的。对它的研究很有理论和现实意义。 标准遗传算法的基本流程如图2 1 所示，其主要运算过程有： ( 1 ) 编码 编码是遗传算法的首要内容，编码方式有很多，在优化之前必须先将解空问的 解数据解码成基因型串结构数据，它们的不同组合表示不同的数据。 ( 2 ) 初始种群的生成 一般都是根据编码机制，随机生成初始种群，一个种群包含多个染色体，这些 代表了数据样本。 ( 3 ) 适应度检测评价 适应度函数用来评判染色体的好坏。要根据具体的问题来设计，适应度函数的 形式，适应度函数的设计也是多种多样的，要具体问题具体分析。 ( 4 ) 选择 选择又叫复制，是在群体中选择生命力强的个体产生新的群体的过程。选择算 子是遗传算法的一个基本操作，它有一定的选择概率从父代中选出较优良的个体， 使它有机会遗传到下一代中。最常用的选择算子是轮盘赌选择。 9 硕士学位论文 m a s t e r st h e s i s ( 5 ) 交叉 交叉也较重组，是按照一定的概率从群体中选择两个个体，交换这两个个体的 某个或某些位。交叉是遗传算法中最主要的操作，在交叉之前需要对个体配对，交 叉算子在具体的实现过程中要考虑具体的问题。目前常用的交叉算子有单点交叉、 两点交叉、多点交叉、均匀交叉和算术交叉。 ( 6 ) 变异 变异操作可以起到两个作用改善遗传算法的局部搜索能力和维持种群多样性。 变异操作是先随机选择要变异的一个个体，以一定概率随机改变该基因位的值。一 般来说变异概率设置为o 1 ，这是个比较低的值，这符合自然进化的规律。常用的 变异算子有基因位突变，均匀变异和非均匀变异。 ( 7 ) 终止条件判断 若条件不成立，则转到步骤( 3 ) ，否则终止运算并输出最优解。 图2 - 1 标准遗传算法流程图 1 0 硕士学位论文 m a s t e r st h e s i s “一个简单的遗传算法被g o l d b e r g 用来进行轮廓描述并用来举例说明遗传算 法的基本组成。t 代种群用变量p ( t ) 表示，初始种群p ( 0 ) 是随机设计的，简单遗传 算法的伪代码描述如下：” p r o c e d u r eg a b e g i n t = o ：，囝 i n i t i a l i z ep ( t ) ； e v a l u a t ep ( t ) ； w h i l en o tf i n i s h e dd o b e g i n t = t + l ； s e l e c tp ( t ) f r o mp ( t 一1 ) ； r e p r o d u c ep a i r si np ( t ) ； e v a l u a t ep ( t ) ； e n d e n d ， 2 1 2 编码方法和评估策略 编码是遗传算法设计中的关键步骤，它的好坏直接影响选择、交叉、变异等遗 传操作运算。 “在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其空间转化 到遗传算法所能处理的搜索空间的转换方法称为编码。 目前的编码方式有很多： 二进制编码、格雷码编码、实数编码、多参数级联等等。 二进制编码是由二进制符号0 和l 所组成的二值符号集。它是最常见的一种编 码方式。它有以下一些优点： ( 1 ) 编码、解码操作简单易行 ( 2 ) 交叉、变异等遗传操作便于实现 ( 3 ) 符合最小字符集编码原则 ( 4 ) 利用模式定理对算法进行理论分析。 。雷英杰，张善文，李继武，周创明m a t l a b 遗传算法工具箱及应用西安：西安电子科技火学出版社2 0 0 5 ：1 3 o 问匕 同上 l l ： 硕士学位论丈 m a s t e r st h e s i s 二进制编码的缺点是：对于一些连续函数的优化问题，由于其随机性使得其局 部搜索能力较差，如对于一些高精度的问题，当解迫近于最优解后，由于其变异后 表现型变化很大，不连续，所以会远离最优解，达不到稳定。而格雷码能有效地防 止这类现象。 格雷码编码是这样的一种编码方法，其连续两个整数所对应的编