（计算机应用技术专业论文）基于聚类方法的小生境遗传算法研究.pdf

硕十学位论文 摘要 遗传算法作为一种基于自然选择和遗传理论的通用优化算法，已成功应用于 组合优化、机器学习、工程优化、图象处理、人工生命、自动程序设计等诸多领 域。随着研究的不断深入，遗传算法在处理多模态优化问题时的不足逐渐暴露。 简单遗传算法不能很好的保持种群多样性，容易陷入多峰函数的局部极值点，导 致早熟收敛；同时，由于遗传漂移简单遗传算法一般只收敛到多峰函数的一个峰， 因此不能满足某些实际问题要找到多个峰的要求。小生境作为处理多峰优化问题 的一种有效手段，得到了广泛关注，并已经成为遗传算法领域的一个研究热点。 目前，小生境的设计和理论研究还不成熟，缺乏统一的小生境进化模型，小 生境形成方法与种群多样性保持、进化搜索性能之间的关系在理论分析与实验研 究方面尚不成熟。针对以上问题，本文对基于聚类的小生境遗传算法进行了研究， 主要工作与研究成果如下： ( 1 ) 提出了一种多源扩散的蚁群小生境遗传算法，该算法通过选取多个信息素 扩散源和保留源中心点来保持种群多样性，并通过信息素扩散提高遗传算法的搜 索效率，该算法能有效的避免遗传算法的早熟收敛，使算法最终收敛到全局最优 解。 ( 2 ) 提出了一类改进的基于聚类的小生境遗传算法，把聚类思想用于小生境的 实现，通过聚类和代表个体保留来提高种群的多样性和多峰搜索性能，从而达到 多峰收敛的目标，并通过m a r k o v 链模型证明了该类算法能够收敛到多峰函数的多 个最优峰。 ( 3 ) 设计了一种基于山峰聚类的小生境遗传算法，算法采用改进的山峰聚类提 高种群多样性，并用多峰函数进行仿真实验，实验数据表明它比确定性排挤小生 境和共享小生境的多样性更好，能够搜索到更多的峰。 关键词：遗传算法；小生境；聚类；多样性；早熟收敛 a b s t r a c t g e n e t i ca l g o r i t h m ， w h i c hi sb a s e d0 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 f y ，h a s b e e ns u c c e s s f u l l ya p p l i e di nc o m b i n a t i o no p t i m i z a t i o n ，m a c h i n el e a r i l i n g ，e n g l n e e n n g 0 p t i m i z a t i o n i m a g ep r o c e s s i n g ，a f t i f i c i a l l i f e ，a u t 0p r o g r a m m m ga n d o t h e rd o m a ：n a 赢c a t i o n s a st h ef e s e a r c hg o i n gd e e p l y ，t h e s h o r t c o m i n g s o f g e n 豇沁a 1 9 0 r n h m ：n 五二l i n g w i t hm u l t i m o d a lo p t i m i z a t i o n a r e g r a d u a l l ye x p o s e m 轼m p l e g e n 吼：c a l g o f i t h mc a n ，tk e e pag o o d d i v e r s i t y i nt h e w h o l es e a r c h i n 岛s 0i tw o u l d b e p o s s l l y i m m e r s e di ns o m el o c a lo p t i m a ls i t u a t i o n ，w h i c hl e a d s t op r e m a t u r ec o n v e r g e n c 六丫n t h eo t h e rw a y ，g e n e t i ca l g o r i t h m st e n dt oc o n v e r g e t oo n l yo n ep e a ko fm u l t l 。p e a k s f u n c t i o n ，w h i c hc a n ，t s a t i s f yt h en e e do fs e a r c h i n g m o r e h a no n ep e a k a s a n e f f e c t i v ew a yo fd e a l i n gm u l t i p e a ko p t i m i z a t i o np r o b l e m s ， t h en i c h em e t h o dh a s b e e n w i d e l yc o n c e r n e d a sah o t s p o ti nt h eg e n e t i ca l g o r i t h mr e s e a r c h a r e a n o w a d a v s ，w i t h o u tp e r f e c tt h e o r ya n du n i f i e dm o d e l ，i t i sd i f f i c u l tt oa n a l y z e t h ec o n n e c t i o na m o n gn i c h ef o r m i n gm e t h o d ，p o p u l a t i o nd i v e r s i t y m a i n t a l n l n ga ? d e v o l u t i o n a r ys e a r c h i n ge f f i c i e n c yi nt h c o r y a n d e x p e f i m e n t t h i st h e s i ss t u d l e d t ，e n i c h eg e n e t i ca l g o r i t h m b a s e do nc l u s t e r i n g ，a n dt h em a i nw o r k a n df e s e a r c hr e s u l t s a r ea sf b l l o w s ： t l v ， am u l t i s o u r c e d i f f u s i o na n tc o l o n y n i c h eg e i l e t i ca l g o n t h m w a s p r o p o s e d ，w h i c hi sb a s e do na n tc o l o n yp h e r o m o n e d i f f u s i o n t h l sa l g o 1 。h ms e l e c ： 二n jr e s e f v e ss e v e r a lp h e r o m o n es o u r c e si n 。r d e rt om a i n t a i n d 1 v e r s l ya n dd l f l u s ( 三d t h ep h e r o m o n et oi m p r o v et h es e a f c h i n ge f f i c i e n c y t h ea l g o r i t h mc a ne f f e c t l v e l y p r e v e n tp r e m a t u r ec o n v e r g e n c e o fg e n e t i ca l g o r i t h m 1 s e c o n d l y ， a ni m p r o v e dn i c h eg e n e t i ca l g o r i t h m b a s e do nc l u s t e n n g w a s p r 。p o s e d ，w h i c ha p p l i e sc i u s t e r i n gm e t h o d i n t 0r e a l i z a t i o no fn i c h e i ti sp r o v e dt h a t t h ea l g o r i t h mc a nc o n v e r g et os e v e r a lo p t i m u m sb yt h e m a r k o vc h a mm o d e l t h i r d l v ，an i c h eg e n e t i ca l g o m m b a s e do nm o u n t a i nc l u s t e r i n gw a sp r o p o s e d ， w h i c hi m p r o v e s t h ed i v e r s i t yb y t h ei m p f o v e d m o u n t a i nc l u s t e r i n g m e t h o d e x p e r i m e n to fm u l t i p e a kf u n c t i o ns h o w s t h ed i v e r s i t yo ft h i sa l g o r l h m1 sb e 。e r 。h a 芑 t h 0o fd e t e r m i n i s t i cc r o w d i n gn i c h ea n df i t n e s s s h a r i n gn i c h 色a n 叭hp r 叩0 8 酣 a l g o r i t h mc a ne x p l o r eo u tm o r ep e a k s k e yw 。r d s ：g e n e t i ca l g 。r i t h m ；n i c h e ；c l u s t e r i n g ；d i v e r s i t y ；p r e m a t u r e c 。n v e f g e n c e 基于聚类方法的小生境遗传算法研究 图1 1 图2 1 图3 1 图3 2 插图索引 v 3 3 5 5 1 2 2 图义 程意图图流何试试法几测测 算的1 5 传式数数遗模函函 硕一l 二学位论文 附表索引 表3 1 信息素对算法性能影响表2 1 表3 2 多源机制对算法性能影响表2 2 表3 3 测试函数性能指标表2 3 表3 4 各算法性能比较表2 3 表5 1 测试函数性能指标表一3 9 表5 2 函数1 多峰优化性能表3 9 表5 3 函数2 多峰优化性能表4 0 表5 4 函数3 多峰优化性能表一4 0 表5 5 函数4 多峰优化性能表4 0 表5 6 函数5 多峰优化性能表4 0 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：i 习昂 日期： 。8 年岁月塔日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在一年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打” ) 作者签名： 导师签名： 1 司伟 日期：硒牌t 月玎日 日期：2 口0 8 年 月2 夕日 硕士学位论文 第1 章绪论 1 1 课题研究背景及其意义 1 1 1 生物进化论和遗传学理论 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是模拟遗传选择和自然淘汰的生物进 化过程的计算模型，由美国m i c h i g a n 大学教授j o h nh o l l a n d 于1 9 7 5 年首先提出， 遗传算法的主要思想是基于d a r w i n 的生物进化论和m e n d e l 的遗传学【。 生命的基本特征包括生长、繁殖、新陈代谢和遗传与变异，生命是进化的产 物，现代的生物是在长期进化过程中发展起来的。达尔文( 1 8 5 8 年) 用自然选择 ( n a t u r a ls e l e c t i o n ) 来解释物种的起源和生物的进化，其自然选择学说包括以下三个 方面： 1 ) 遗传( h e r e d i t y ) ，这是生物的普遍特征，“种瓜得瓜，种豆得豆，亲代把 生物信息交给子代，子代按照所得信息而发育、分化，因而子代总是和亲代具有 相同或相似的性状，生物的这个特征使得物种能够稳定存在。 2 ) 变异( v a r i a t i o n ) ，亲代和子代之间以及子代的不同个体之间总有些差异， 这种现象称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。 3 ) 生存斗争和适者生存，自然选择来自繁殖过剩和生存斗争。由于弱肉强食 的生存斗争不断地进行，其结果是适者生存，具有适应性变异的个体被保留下来， 不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，物种变异 被定向朝一个方向积累，于是性状逐渐和原来的祖先物种不同，演变成新的物种。 这种自然选择过程是一个长期的、缓慢的、连续的过程。 达尔文的进化理论是生物学史上的一个重要里程碑，它解释了自然选择作用 下生物的渐变式进化。1 8 6 6 年孟德尔发表了“植物杂交实验 的论文，他提出的 遗传学的两个基本规律一一分离律和自由组合律，奠定了现代遗传学的基础。2 0 世纪2 0 年代以来，随着遗传学的发展，一些科学家用统计生物学和种群遗传学的 成就重新解释达尔文的自然选择理论，他们通过精确地研究种群基因频率由一代 到下一代的变化，来阐述自然选择是如何起作用的，形成现代综合进化论 ( s y n t h e t i ct h e o r yo fe v o l u t i o n ) 。综合进化论对达尔文的进化给予了新的更加精确的 解释【2 6 1 。 基于聚类方法的小生境遗传算法研究 1 1 2 遗传算法的基本思想及其历史 2 0 世纪六十年代初，一些生物学家开始利用计算机对遗传系统进行模拟。在 此期间，美国m i c h i g a n 大学教授j o h nh o l l a n d 正在从事自适应系统的研究，受生 物学家们模拟结果及生物进化论与遗传学说的启发，h o l l a n d 在a s f r a s e r 和h j b r e m e r m a n n 等工作的基础上提出了位串编码技术及相应的算法。随后，h o l l a n d 将该算法( 当时称为g e n e t i cp l a n ) 用于自然和人工系统的自适应行为的研究之中， 并于1 9 7 5 年出版了其开创性著作a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s 。 书中将g e n e t i cp l a n 作为生物进化的一种抽象，并给出了在g e n e t i cp l a n 下适应性 的一个理论框架。后来，h o l l a n d 的学生们对该算法加以改进并应用于优化及机器 学习等问题，该算法也被正式命名为遗传算法( g e n e t i ca l g o r i t h m ) 7 8 j 。 遗传算法是从代表问题可能潜在解集的一个种群( p o p u l a t i o n ) 开始的，而一个 种群则由经过基因( g e n e ) 编码( c o d i n g ) 的一定数目的个体组成，每个个体实际上是 染色体( c h r o m o s o m e ) 带有特征的实体。染色体作为遗传物质的主要载体，即多个 基因的集合，其内部表现( 即基因型) 是某种基因组合，它决定了个体的外部表现， 如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一 开始遗传算法需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码 的工作很复杂，遗传算法往往进行简化，如采用二进制编码，实数编码等。初代 种群产生之后，按照适者生存和优胜劣汰的原理，逐代( g e n e r a t i o n ) 演化产生出越 来越好的近似解。在每一代，根据问题域中个体的适应度( f i t n e s s ) 大小挑选 ( s e l e c t i o n ) 个体，并借助于自然遗传学的遗传算子( g e n e t i co p e r a t o r s ) 进行组合交叉 ( c r o s s o v e r ) 和变异( m u t a t i o n ) ，产生出代表新的解集的种群。这个过程导致种群像 自然进化一样后代种群比前代更加适应于环境，末代种群中的最优个体经过解码 ( d e c o d i n g ) ，可以作为问题近似最优解i 弘1 3 j 。 遗传算法在提出之初并未立即受到普遍关注，其研究仅限于h o l l a n d 及其学 生和同事。除了计算机性能方面的原因外，也由于当时基于符号处理的人工智能 方法正处于巅峰时期，使人们尚无暇顾及其他方法的有效性和适应性。“这显然不 属于人工智能研究的范畴。及“为什么要关注一个模仿数万年历史的研究? ”代 表了当时计算机科学界一部分人对遗传算法的典型观点。到了八十年代，人们越 来越清楚地认识到传统人工智能方法的局限性，加之计算机速度的提高和并行计 算机的普及，遗传算法开始日益引起人们的重视和兴趣。1 9 8 5 年，首届遗传算法 国际学术会议召开；1 9 8 9 年g o l d b e r g 的g e n e t i ca l g o r i t h m si ns e a r c h ，o p t i m i z a t i o n a n dm a c h i n el e a r n i n g 一书的出版对遗传算法的研究起了一定的承前启后的推动 作用：进入九十年代，遗传算法的研究及各种改进的遗传算法如雨后春笋般地不 断在各种学术期刊及国际学术会议上发表，形成了国际性的遗传算法研究热潮。 2 硕f ：学位论文 1 9 9 2 年，h o l l a n d 的著作由m i t 再版；1 9 9 3 年，以遗传算法为主要研究对象的国 际性学术期刊e v o l u t i o n a r yc o m p u t a t i o n 创刊( m i t 版) ，1 9 9 7 年i e e e t r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n 创刊。 遗传算法自创立以来，己被先后成功地应用于机器学习、工程优化、图象处 理、经济预测、系统合成、人工生命、自动程序设计等诸多领域，引起了包括数 学、物理学、化学、生物学、计算机科学、社会科学及工程应用领域科学家们的 极大兴趣。日前，遗传算法已成为无可争议的跨学科的热门研究课题1 1 4 ，”】。 1 1 3 遗传算法流程 遗传算法流程如下： 图1 1 遗传算法流程图 遗传算法计算过程为： 选择编码方式：基因型串结构数据的产生。 产生初始群体：随机生成个串结构数据为初始种群集合。 计算初始群体的适应度值：构造适应度函数。 3 基于聚类方法的小生境遗传算法研究 如果不满足终止条件，则执行循环 1 ) 选择：选出优良个体，实现适者生存原则。 2 ) 交叉：遗传操作。得到新一代个体，体现信息交换思想。 3 ) 变异：随机选择一个个体并改变其值。概率通常在0 0 0 1 o 1 。 4 ) 计算新一代群体的适应度值。 ) 循环结束：解码，输出最优解。 1 1 4 遗传算法基本术语 遗传算法的基本术语1 2 】： 进化代( g e n e r a t i o n ) ：算法的迭代步称为进化代，或简称代。 群体( p o p u l a t i o n ) ：所求解问题的多个解的集合称为群体。常记为p ( f ) ，f 表示 所处的代数。最初的群体p ( 0 ) 一般是从问题可能潜在的解的集合中随机生成的。 个体( i n d i v i d u a l ) ：组成群体的每一个解称为一个个体，常记为q ( f ) ，口：( f ) ， 6 盘 奇。 群体规模( p o p u l a t i o ns i z e ) ：群体内个体的数目称为群体规模，常记为。 一般来说，群体规模在整个进化过程中是不变的。 编码( e n c o d i n g ) ：在使用遗传算法解决问题之前，需要将问题的解进行编码， 即将问题的解通过变换映射到基因空间，也即遗传算法的搜索空间。基因空间中 的点通常是字符串的形式，最简单的是用 o ，1 _ 定义的二进制串。 解码( d e c o d i n g ) ：编码的逆过程。 染色体( c h r o m o s o m e ) ：经过编码后得到的代表问题解的位串称为染色体。 基因座( l o c u s ) ：基因所在染色体中的位置称为基因座。 等位基因( a 1 1 e l e ) ：同一基因座可能有的全部基因称为等位基因。 基因型( g e n o t y p e ) ：染色体内部表现即基因组合的模型称为基因型，或称遗 传子型。 表现型( p h e n o t y p e ) ：个体的外部表现即表现型。染色体作为遗传物质的主 要载体，其基因型决定了个体的表现型。编码即为从表现型到基因型的映射。 适应值( f i t n e s s ) ：个体适应环境的程度( 与最优解接近的程度) 称为适应值。 适应值较高的个体获得更多的繁殖机会。 选择( s e l e c t i o n ) ：指以一定的概率从群体中选择若干个体的操作。一般而言， 选择的过程是一种基于适应值的优胜劣汰的过程。 父代( p a r e n t ) 及子代( o f f s p r i n g ) ：根据某种规则来产生其下一代个体的个 体称为其下一代个体的父代，产生的下一代称为它的子代。 4 硕上学位论文 复制( r e p r o d u c t i o n ) ：指从群体中选择若干个体直接插入到新一代群体中去 的操作。 交叉( c r o s s o v e r ) ：在两个染色体的某一个或某几个相同位置进行切断，将 各子串分别交叉组合形成两个新的染色体的过程，又称为杂交或基因重组 ( r e c o m b i n a t i o n ) 。 变异( m u t a t i o n ) ：指染色体的基因发生某种改变，从而产生出新的染色体的 过程。 遗传算子( g e n e t i co p e r a t o r s ) ：即遗传操作，包括复制、交叉、变异等。 1 1 5 多模态优化问题 在函数优化的实际问题中，有时会遇到极复杂的多峰函数，其局部优解众多， 全局最优解的分布完全未知，这一类问题就是多模态优化问题。在求解计算这类 问题中，有时候不仅要在可行域内寻找全局最优解，而且需要找到多个全局最优 解和局部最优解，从而为决策者提供多种选择或者多方面的信息。由于各种因素， 遗传算法的结果一般只收敛到一个解，因此无法满足多峰搜索的要求。如何使遗 传算法能够搜索到多个最优解，已成为一个重要的研究方向。 1 2 遗传算法研究的主要内容 遗传算法的主要本质特征在于群体搜索策略和简单的遗传算子。群体搜索使 遗传算法得以突破领域搜索的限制，可以实现整个解空间上的分布式信息采集和 搜索；遗传算子仅仅利用适应值度量作为运算指标进行随机操作，降低了一般启 发式算法在搜索过程中对人机交互的依赖。 遗传算法所追求的也是当前群体产生比现有个体更好个体的能力，即遗传算 法的可进化性或称群体可进化性。因此，遗传算法的理论和方法也就是围绕着这 个目标展开。遗传算法的主要研究方向： 1 ) 遗传算法的基础理论研究。其主要是以收敛分析为主，即群体收敛到优化 问题的全局最优解的概率。从整体上讲，可以分为基于随机过程的收敛性研究和 基于模式定理的收敛性分析。前者称为遗传算法的随机模型理论，随机模型理论 说明对于搜索过程可表示为离散时间的马尔科夫链模型( m a r k o vc h a i nm o d e l ) ，从 而可采用已有的随机过程理论进行严密的分析。由后者称为遗传算法的进化动力 学理论，由h o l l a n d 提出的模式定理可以称为遗传算法进化动力学的基本定理， 模式定理和建筑模块假说构成了求解优化问题时遗传算法具备发现全局最优解的 充分条件。尽管还存在着不完善之处，但是它为深入研究遗传算法的运行机理奠 定了基础。 2 ) 遗传策略研究与设计。为了维持群体可进化性并最终搜索到问题的全局最 5 基十聚类方法的小生境遗传算法研究 优解，遗传算法必须采用适宜的运算形式，这就是遗传策略。其划分为微观遗传 策略和宏观遗传策略。微观策略主要讨论群体规模、遗传算子的形式和参数设计， 以及对g a 求解能力的影响。宏观策略主要对g a 流程的再设计从而改变g a 的 宏观特征，或者以g a 流程为基础，引入其他算法构成混合g a ，以提高g a 求解 问题全局最优解的能力。另外，针对多模态函数的优化问题，如何构造一种优化 算法，使之能够搜索到尽量多的或者全部全局最优解和有意义的局部最优解，已 成为一个重要的研究邻域。 3 1 遗传算法编码方式。在遗传算法编码方式问题上，h o l l a n d 建议采用二进 制编码，并得到许多学者的支持。浮点数编码具有精度高、便于大空间搜索的优 点，越来越受到重视。从整体上讲，二进制编码的进化层次是基因，而浮点编码 的进化层次是个体。同时，对于非二进制编码，可以结合具体问题领域的知识， 设计合适的遗传算子。 4 l 遗传算法的其他问题。包括：实际应用中涉及的问题大多数是带有约束条 件的，能否处理好约束问题，是能否成功应用遗传算法的关键问题。遗传算法的 并行化研究( p a r a l l e lg a ，p g a ) 。设计各种并行执行策略、建立相应的并行算法的 数学基础，对提高进化算法的效率有重要的意义。p g a 主要有细粒度和粗粒度两 种计算模型，具体实现的方法有同步主从式，异步并发式和网络分布式三种。对 p g a 的研究表明：只要通过保持多个群体和恰当地控制群体问的信息交换来模拟 并行过程，即使不使用并行计算机，也能提高算法的执行效率。 1 3 本文的研究内容及结构安排 本文主要研究了遗传算法的基本理论和实现技术，重点研究了用于解决多峰 优化问题的小生境遗传算法。从小生境实现技术的现状出发，通过借鉴蚁群算法 和聚类算法，设计了几种新的混合遗传算法，并运用m a r k o v 链模型对算法的收敛 性做了分析。具体的工作包括： 1 l 研究了小生境遗传算法的发展现状，对不同的小生境实现技术做了概述， 并对其优缺点做出了评价，总结了遗传算法的多样性和多峰搜索性能的评价标准， 并指出了小生境遗传算法存在的一些问题和今后主要的研究方向。 2 1 设计了一种多源扩散蚁群遗传算法。算法以蚁群信息素扩散为基础，选取 多个信息素扩散源，通过信息素扩散和保留源中心点保持种群多样性，并提高遗 传算法的搜索性能，通过仿真实验证实了该算法能有效的避免遗传算法的早熟收 敛，从而收敛到全局最优解。 3 、l 提出了一类改进的基于聚类的小生境遗传算法。该类算法以聚类算法为基 础，通过聚类和代表个体保留保持种群多样性，提高种群的多峰搜索性能，达到 多峰收敛的效果。在一个假设的前提下，通过m a r k o v 链模型证明了该类算法能够 6 硕上学位论文 收敛到多峰函数的多个最优峰，从而根本上解决多峰问题的优化。 4 ) 设计了一种基于山峰聚类的小生境遗传算法。该算法以改进的山峰聚类为 基础，根据上面提出的一类算法设计得到，通过多个多峰函数的仿真实验，比较 了它与简单遗传算法及其他两个小生境技术的遗传算法的性能，实验结果表明该 算法具有最好的多峰搜索性能。 本文的具体章节安排如下： 第一章介绍了本文的选题背景和意义，并通过查阅大量文献，概括了遗传算 法的历史以及研究现状，指明了本文的主要工作。 第二章介绍了小生境遗传算法的研究现状，具体阐述了几种主要的小生境实 现技术和手段，并分析了他们的优缺点，总结了多样性和多峰搜索性能的评价准 则。 第三章介绍了一种多源扩散蚁群遗传算法的设计过程，以及与其他遗传算法 的性能比较。 第四章介绍了一类改进的基于聚类的小生境遗传算法，通过m a r k o v 链模型分 析了其收敛性。 第五章介绍了一种基于山峰聚类的小生境遗传算法的设计过程，以及它与其 他小生境技术的多峰搜索性能比较。 最后是全文的结论和展望。 7 基十聚类方法的小生境遗传算法研究 第2 章小生境遗传算法 2 1 小生境思想介绍 在生态学中，小生境( n i c h e ) 指特定环境下的一组资源，物种( s p e c i e s ) 指在某 一小生境下生存的一类相似个体。同一物种内的个体竞争地消耗同种资源，不同 物种倾向于占据不同的小生境。生物通过竞争与合作形成一个具有物种多样性的 平衡生态系统。受生态系统进化的启发，形成了小生境进化算法的思想。在小生 境进化算法中，一个种群类似于一个生态系统，具有某种相似性的一组个体类似 于物种。将一个物种看成一个子种群，因此，物种、子种群、小生境是一对一的 关系。小生境进化算法的基本目标就是形成和维持稳定的多样化子种群，在搜索 空间的不同区域中并行地进化搜索，从而克服遗传漂移的均匀收敛趋势，实现多 峰、多目标问题的优化和复杂系统的仿真。首先提出模拟小生境进化的思想是 h o l l a n d f ，研究者们相继提出了不同的小生境技术方法，如排挤、共享、标签等， 并在应用中取得了一定的成功。 2 2 小生境遗传算法现状 遗传算法在用于多模态函数优化时，一般只收敛到一个解，并且往往收敛到 局部极值点，出现早熟收敛。遗传算法的遗传漂移现象使种群均匀地收敛于单一 的优良解，导致早熟收敛和可选优良解的丢失。增加变异概率可以抑制遗传漂移， 但是大概率变异会频繁破坏己形成的优良积木块，从而使遗传算法退化为随机搜 索算法。降低选择压力可降低遗传漂移速度，但不能消除种群的均匀收敛趋势， 不能从根本上抑制遗传漂移。 受小生境思想的启发，国际上研究遗传算法的专家们相继提出在遗传算法中 引入了各种小生境技术方法，如排挤、共享、标签等，并在应用中取得了一定的 成功，从而使遗传算法求解多模态优化问题成为可能。 2 2 1 排挤模型 由d ej o n g 提出的排挤模型【1 6 】是一种维持群体多样性的选择方法。在自然界 中，当某种群体中个体大量繁殖时，为争夺有限的生存资源，个体之间的竞争压 力加大，个体消亡的概率提高，生存概率下降。排挤模型在遗传选择操作时，新 的子串仅仅代替与之相似的父代个体。 排挤模型主要有标准排挤、确定性排挤( d e t e 姗i n i s t i cc r o w d i n g ) 和概率排挤 8 硕士学位论文 ( p r o b a b i l i t yc r o w d i n g ) 等几种。 d ej o n g 的标准排挤算法【1 6 】在每一代仅选择一定比例g c ( 代间隙) 的个体参 与繁殖，对每一个子代个体，从父代种群中随机地选择c f ( 排挤系数) 个个体，替 换其中最相似的一个个体，相似性使用h a m m i n g 距离测度。由于随机选择c f 个 个体的采样误差会导致较多的替换错误，标准排挤虽然改善了种群多样度，但在 多峰问题应用中仅表现了有限的小生境维持能力。 m a h f o u d i l 7 l 提出的确定性排挤将规模为n 的种群随机配成n 2 对，每一对父 代个体通过交叉和变异生成两个子代个体，每一个子代个体和一个父代个体通过 联赛竞争成为下一代种群的成员。联赛采用能产生最大相似性替换的分组，相似 性采用父子之间的欧几里德距离测度。确定性排挤已成功地应用于某些多峰问题 的优化，表现了较强的小生境维持能力【1 8 _ 2 1 1 。 确定性排挤策略有可能导致低适应值小生境的丢失，概率排挤1 2 2 】即为克服此 缺陷的小生境技术。概率排挤的子代个体与相似的父代个体进行概率联赛竞争， 按适应值比例替换父代个体，因此引入了低适应值子种群的恢复压，种群的多样 性比确定性排挤更好。 基于相似性替换的排挤算法简单，实现效率高，无需目标问题的先验知识和 控制参数，是一类隐含的自适应小生境技术。但相似性判断均未考虑搜索空间的 实际结构，当替换者和被替换者不属于搜索空间同一局部最优解的邻域时会产生 替换错误，此时，新生小生境可能替换已形成的小生境，从而降低小生境形成与 维持能力。 2 2 2 适应值共享模型 g o l d b e r g 和r i c h a r d s o n 提出了一种基于适应值共享机制【2 3 】的小生境技术，通 过降低群体中相似个体的适应值，来限制相似个体在群体中的过度增长，从而保 持种群的多样性，建立并维持稳定的小生境。 适应值共享首先要定义共享函数，共享函数表示两个个体之间的相似性水平， 如果两个个体之间关系比较密切时，共享函数值较大，反之较小。个体的共享度 等于该个体与所有其他个体的共享函数值的总和。然后根据共享度变换个体的适 应度，使得共享度高的个体适应度减低，从而避免某一模式的个体在群体中过度 繁殖。 共享已成功地应用于多峰函数优化和多目标问题优化中。虽然共享是流行的 小生境技术，但共享技术有3 个不足之处：( 1 ) 计算共享适应值需要d ( ，z 2 ) 的距离 测度开销；( 2 ) 设置参数需要适应值曲面的先验知识，显然，这一要求大大地限制 了共享技术的有效应用范围；( 3 ) 基于搜索空间的峰值分布为均匀等距离分布的假 设，即对全体个体，取相同的值。距离测度的计算开销相对于简单适应值函数的 9 基于聚类方法的小生境遗传算法研究 评估成本是较大的，但相对于复杂适应值函数的评估成本，距离测度计算开销几 乎可忽略不计。但是后两种缺陷( 即所谓小生境半径问题) 严重地妨碍了共享的 应用。 2 2 3 聚类 聚类将初始种群的每一个个体视为一个小生境，进化过程应用模糊聚类分析 动态地合并、分解和生成小生境，在每个小生境内部计算共享适应值。这种方法 可以使共享技术实现不再需要适应值函数曲面先验知识，但算法比较复杂，小生 境形成与维持需要大量的附加计算开销，实现成本高，且引入了其它控制参数。 2 2 4 标签 标签( t a g g i n g ) 技术【2 4 1 在每个二进制编码串基础上增加七个附加位，用于表 示每个个体所属的子种群，七个位可表示2 个子种群。每个个体的附加位随机地 初始化，因此，初始子种群是随机地划分的。交叉操作限制在子种群内部进行， 个体的共享适应值等于其原始适应值除以相应子种群大小。由于编码方案的改进， 完全消除了计算共享度的距离测度开销，使共享的实现不再需要小生境半径参数。 但由于初始子种群划分是随机的，单个子种群可能覆盖多个不同峰，子种群之间 不能避免相互重叠，标签技术不能消除个体从低峰区域向高峰区域的遗传漂移， 因此，标签技术能够并行地找到若干高适应值的全局最优或局部最优解，但会丢 失低适应值峰值。 2 2 5 序列小生境 序列小生境技术【2 5 】对同一目标问题反复地运行遗传算法，每一次运行结束时 脱机保持已找到的最优解，在下一次运行时，用类似计算共享适应值的方法降低 已找到最优解小生境半径范围内所有解的适应值，以减少重复访问已找到最优解 的概率。虽然从概念上讲，序列小生境技术是共享技术的串行化，但大量比较实 验表明，序列小生境技术不能真正避免对相同最优解的重复访问，且需要花费比 并行小生境技术多得多的函数评估次数才能找到所需要的多个最优解。与共享技 术一样，该方法也存在小生境半径问题。 2 3 性能评价标准 2 3 1 在线性能和离线性能 d ej o n g 提出了两种评价遗传算法性能好坏的标准：在线性能分析和离线性 能分析。f 时刻的在线性能是指从0 到f 时刻群体中所有出现过的个体的平均值； f 时刻的离线性能是指从o 到f 时刻，所有最优个体适应值的平均值。 1 0 硕上学位论文 但是，这两种性能标准主要是反映算法的收敛速度，而缺乏对每一代种群的 分布情况以及算法终止时解的质量的分析，因此是不适用于多峰问题的性能评价。 用遗传算法研究多峰问题时，性能分析应该更关注于种群中解的分布，也就是峰 值的发现和维持，收敛速度不是首要目标。 2 3 2 有效峰的数量 有效峰的数量( n u m b e ro fe f f e c t i v ep e a k sm a i n t a i n e d ，n e p ) ，当搜索空间中某 个峰在种群中存在至少一个元素，且该元素的适应值至少达到该峰所对应的局部 极值的8 0 时，这样的峰称为一个有效峰，种群维持的有效峰的数量表示算法搜 索到的有效局部最优解的个数，是对算法的并行搜索能力的测度。 2 3 3 平均峰值比 平均峰值比( a v e r a g ep e a kr a t i o ，a p r ) ，种群中每个有效峰都存在一个适应值 最大的元素，该元素称为有效局部最优解，种群中全体有效局部最优解的适应值 之和除以搜索空间中全体真实局部最优解的适应值之和称为平均峰值比，该指标 是对种群中的多个有效局部最优解的平均质量的测度，理想值被规范化为1 。 2 3 4 全局最优解比 全局最优解比( g l o b a lo p t i m u mr a t i o ，g o r ) ，种群中适应值最大的有效局部 最优解称为有效全局最优解，有效全局最优解的适应值与真实全局最优解的适应 值之比称为全局最优解比，该指标是对种群中的有效全局最优解的质量的测度， 理想值被规范化为1 。 2 3 5 多样性 按照生物学的进化理论，多样性是生物种群进化的基础。同样，群体的多样 性也是遗传算法能够搜索全局最优解的基本条件。对于遗传算法的搜索过程来讲， 群体的多样性保证了遗传算子正常发挥进化和重组效应，其中，选择算子将减少 群体的多样性；交叉算子保持群体多样性不变，变异算子则提高群体的多样性1 2 6 1 。 群体的多样性对于多峰问题的求解尤为重要。只有当群体中存在足够多的相 异个体，有一定的多样性，才能保证遗传算法有能力搜索更多的峰而不至于早熟。 否则，如果群体多样性低，显然不能指望算法能搜索到多个不同的峰值。 下面给出群体多样性的计算方法【2 7 】： 任意优化问题的二进制编码空间为佃，舻，群体规模设为厅，群体所包含个体 集合p t 他，吃，吃 ，其中6 f 一 岛忽，吃j ，j = 1 ，2 ，疗，多样性测度： 肌c 咖1 一忐( ：| ；m a x 弘喜叫一扣弘薹1 一) ) 仁1 ， 1 1 基于聚类方法的小生境遗传算法研究 显然，朋( p ) f 0 ，1 1 ，当肌( p ) = o 时，群体多样性消失，个体之间无差别；当朋( p ) = 1 时，群体的多样性最大。对于f 代群体，其多样性测度为胁( p ( f ) ) 。 2 4 种群“早熟”的定量评价指标 遗传算法的每一代种群始终保持多样性是遗传算法有效运行的前提条件。在 种群规模一定的情况下，种群多样性越大，就越有可能产生出更优子代，而一旦 种群丧失了多样性，种群个体间相互趋同，则“早熟现象就越容易发生。理论 研究表明，传统的遗传算法( s g a ) 不能保证收敛到全局最优解，而如果将父代最 优解直接复制到子代中去，虽然有可能全局收敛，但又易于发生“早熟”。改进遗 传算法的困难在于：一方面为了保证遗传算法能全局收敛，必须使群体中有足够 多不同的个体，即保护群体的多样性；而另一方面，为了加快算法的收敛速度， 又必须使群体中的个体尽快向最优解方向靠拢，这样将不可避免的降低种群的多 样性，增加种群“早熟 的可能。因而，正确评估种群个体的“早熟 程度( 或称 多样性程度) ，对遗传算法性能的改进起着非常重要的作用。 2 4 1 两种定量评价标准的定义 目前，可对种群的多样性程度做定量评价的指标有如下两种【2 8 】： 1 1 种群个体空间分布方差 定义1 若第f 代种群中的个体x j 由l 个基因构成，即x x j l ，x ；2 ，x 严 ， f 仙2 ，m ，m 为种群中个体的数目，定义第f 代种群的平均个体为： 一 一( 1 ) 一( 2 ) 一工 x 一 一，)( 2 2 ) 一仃、m j n 、 其中立。= y 乏，m ，由此定义第f 代种群的方差为： 舒 d ，= 【叫n ，d j ，d 严】( 2 3 ) 肼 - ，2 其中研d = 罗z d i 1 m ，z 1 ，2 ，上 口 可以看出，方差d ，是维的行向量，每一个分量表示出了种群在该维坐标上 的空间分布。显然，d ! 。) 越大，则种群在第，维坐标上的空间分布就越大。 2 ) 种群的熵 定义2 若第f 代种群有q 个子集：s n ，s ：，s l q ，各个子集所包含的个体数目 口 记为is ni ，is ，：l ，is l ql ，且对任意f ，n 2 ，研，氏n 一彩，! = ! 瓯；4 ，a 为 第f 代种群的集合，则第f 代种群的熵为： d 巨= 一础慨 ( 2 4 )