（计算机应用技术专业论文）混合遗传算法及其实现研究.pdf

摘要 摘要 遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，其 应用优势在于处理传统搜索方法难以解决的复杂和非线性问题，本论文研究内容 包括三个方面：小生境遗传算法的改进、自适应遗传算子的设计、免疫的进化算 法。本文主要工作如下： ( 1 ) 小生境技术方面，将小生境技术与双亲变异相结合，提出了一种简单的改 进小生境遗传算法，相对于基于共享的小生境遗传算法，其收敛速度与精度都有 所提高。 ( 2 ) 现有的种群“早熟”评价指标进行了分析，设计了改进的自适应遗传算子， 实验结果表明，该算法可以较好的保持种群的多样性。 ( 3 ) 在深入地研究了免疫算法机理的基础之上，将免疫机制应用于遗传算法， 较好的解决了遗传算法的“早熟”收敛，并且大大的改善了遗传算法的全局收敛 性能，提高了算法的搜索速度。 关键词：小生镜遗传算法自适应遗传算法免疫进化 a b s t r a c t a b s t r a c t g e n e t i ca l g o r i t h mi sak i n do fm n d o m s e a r c h i n gm e t h o du s i n gl i v e s n a t u r a ls e l e c t i o n a n d g e n e t i cm e c h a n i s m i t sa p p l i c a t i o np r e d o m i n a n c e l i e si nc o m p l i c a t e da n dn o n l i n e a r p r o b l e m s ，w h i c h a r ed i f f i c u l tf o rt r a d i t i o n a l s e a r c h i n g m e t h o d s t h r e e i m p r o v e d a l g o r i t h m s a r ep r o p o s e di nt h ed i s s e r t a t i o n ：i 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 ，i m p r o v e d a d a p t i v eg e n e t i ca l g o r i t h m ，g e n e t i ca l g o r i t h mb a s e do ni m m u n em e c h a n i s m ，t h e ya r e s u m m a r i z e da s f o l l o w i n g ： f i r s t l y ，t h ed i s s e r t a t i o na n a l y s e sc h a r a c t e r so fs e v e r a lt r a d i t i o n a lg e n e t i ca l g o r i t h m s f o rn i c h e f o l l o w i n gt h i s ，an e wm e t h o d ，c o m b i n e d p a r a l l e l i s me v o l u t i o nt e c h n i q u ef o r n i c h e sb a s e do nl o c a lc o m p e t i t i o nw i t hp a r e n tm u t a t i o nm e c h a n i s m ，i sp r o p o s e dw h i c h i m p r o v e dt h eg e n e t i ca l g o r i t h m sf o rn i c h e c o m p a r e dw i t hg e n e t i ca l g o r i t h mw i t h s h a r i n g ，i th a ss o m ei m p r o v e m e n t si nb o t hc o n v e r g i n gv e l o c i t ya n dp r e c i s i o n s e c o n d l y , a n a l y z i n g t h ei n a d e q u a c i e so ft h ee v a l u a t i o ni n d i c e sf o r p r e m a t u r ec o n v e r g e n c e ，an o v e l i m p r o v e da d a p t i v eg e n e t i ca l g o r i t h m ( i a g a ) i sd e s c r i b e d t h ec a l c u l a t i o nr e s u l to fa l l e x a m p l es h o w st h a t i a g ai sa b l et o g e t t h er e a l - t i m ei n f o r m a t i o no fp o p u l a t i o n d i v e r s i t yd u r i n gt h ep r o c e s so fe v o l u t i o n f i n a l l y ，a p p l y i n gt h ei m m u n em e c h a n i s mt o g e n e t i ca l g o r i t h m ，t h ei m m u n eg e n e t i ca l g o r i t h me x p a t i a t e do nt h i sp a p e rc o m e so v e r t h ep h e n o m e n o no fp r e m a t u r ei ns o m ee x t e n t t h er e s u l to f e x p e r i m e n ts h o w s t h a tt h e g l o b a lc o n v e r g e n c ea n ds e a r c h i n gv e l o c i t ya r eb o t hi m p r o v e d k e y w o r d ： n i c h e g e n e t i ca l g o r i t h m s ，a d a p t i v eg e n e t i ca l g o r i t h m ，i m m u n ee v o l u t i o n 创新性声明 本入声明所呈交的论文是我个人谯导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内黟以外，论文中不 包含其他人您经发表或撰写过的研究成果；也不包会楚获褥瑶安电子科技大学或 其它教育撬鞫的学位或诞书蕊便瘸避弱耱誊辜。与我一瓣工作静游恚对本臻究酝傲 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料瓣有不实之处，本人承担一切相关责任。 本人签名：蘧i 筮鲳 日期：兰! ! i ：堑 关于论文使粥授权的说明 本人完全了解西安电予科技大学奏关保蟹和使震学位论文豹嫂定，即：研究生 在校攻读学像期闻论文工俸的知识产狡单位属露安电子科技大学。本入保证牮逝 离校后，发袭论文或使用论文( 与学位论文相关) 工作成果时瓣名单位仍然为西 安电子科技犬学。学校商权保留送交论文的复印件，允许查阅和借阅论文：学校 霹袋公毒论文懿全部或熬分蠹容，霉激兔谗采矮影露、绩露或荚宅复裁手段缀存 论文。( 保密的论文在解密后遵守此规定) 本太签名：逖鳃 导师签名：茎i 羞 日期： 至竺主! 支垒 日期：受堕! ! ! 垃 第一章绪论 第一章绪论 1 1 引言 遗传算法( g e n e t i c a l g o r i t h m g a ) ，是一类以达尔文的自然进化论与遗传 变异理论为基础的求解复杂全局优化问题的仿生型算法。它借鉴生物界自然选择 和自然遗传机制，以概率论为基础在解空间中进行随机化搜索，最终找到问题的 最优解。 遗传算法的兴起是在8 0 年代末9 0 年代初期，但是它的历史可以追溯到6 0 年 代初期。早期的研究大多以对自然遗传系统的计算机模拟为主。早期遗传算法的 研究特点是侧重于对一些复杂的操作的研究。其中像自动博弈、生物系统模拟、 模式识别和函数优化等给人以深刻的印象。但总的说来，这是一个无明确目标的 发展时期，缺乏带有指导性的理论和计算工具的开拓。这种现象直到7 0 年代中期 由予h o l l a n d 和d e j o n g 的创造性研究成果的发表才得到改观“。”。1 9 6 7 年，b a g l e y 在他的论文中首次提出了遗传算法( g e n e t i ca l g o r i t h m ) 这一术语，并讨论了遗传 算法在自动博弈中的应用0 1 。1 9 7 0 年，c a v i c c h i o 把遗传算法应用于模式识别中“1 。 第一个把遗传算法应用于函数优化的是h o l l s t i e n 0 3 ，1 9 7 1 年他在论文计算机控制 系统中的人工遗传自适应方法中阐述了遗传算法用于数字反馈控制的方法。i 9 7 5 年在遗传算法研究的历史上是十分重要的一年，h o l l a n d 出版了他的著名专著自 然系统和人工系统的适配，该书系统的阐述了遗传算法的基本理论和方法，并 提出了对遗传算法理论研究和发展极为重要的模式理论( s c h e m a t at h e o r y ) ，该理 论首次确认了结构重组遗传操作对于获得隐并行性的重要性。j h o l l a n d 教授和他 的研究小组围绕遗传算法进行研究的宗旨有两个：一是抽取和解释自然系统的自 适应过程，二是设计具有自然系统机理的人工系统。同年，d e j o n g 完成了他的重 要论文遗传自适应系统的行为分析，他把h o l l a n d 的模式理论和他的计算实验 结合起来，这可以看作遗传算法发展过程中的一个里程碑，尽管d e j o n g 和h o l l s t i e n 一样主要侧重于函数优化的研究，但他将选择、交叉和变异操作进一步完善和系 统化，同时又提出了诸如代沟( g e n e r a t i o ng a p ) 等新的遗传操作技术，为遗传算法 及其应用打下了坚实的基础。进入8 0 年代，遗传算法迎来了兴盛发展时期，理论 研究和应用研究都成了十分热门的话题。 遗传算法有其自身的特点：智能性与本质并行性。遗传算法的智能性包括自 组织、自适应和自学习等，应用遗传算法求解问题时，在确定了编码方案、适应 2混合遗传算法及其实现研究 值函数及遗传算子后，算法将应用演化过程中获得的信息进行自组织搜索，适者 生存的选择策略赋予了遗传算法自适应的能力，同时也赋予了它根据环境的变化 自动发现环境的特征和规律的能力；遗传算法的本质并行性表现在两个方面：一 是遗传算法的内在并行性，即其本身非常适合大规模并行，二是遗传算法的内含 并行性，即它可以同时搜索解空间内的多个区域，并且相互之间进行信息交流， 这种搜索方式使得遗传算法可以以较少的计算获得较大的收益。这些特点使得遗 传算法广泛应用于控制、规划、设计、组合优化、图像处理、信号处理、机器人、 人工生命等多个领域。 1 2 1 遗传算法的基本概念 1 2 遗传算法简介 遗传算法的基本思想是基于d a r w i n 进化论和m e n d e l 的遗传学说的。 d a r w i n 进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适 应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代 的新变化。在环境变化时，只有那些能适应环境的个体特征才能保留下来。 m e n d e l 遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞 中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质； 所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生 更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存 下来。 由于遗传算法是由进化论和遗传学机理产生的直接搜索优化方法，所以在这 个算法中要用到各种进化和遗传学的概念。这些概念如下： 一、串( s t r i n g ) 它是个体( i n d i v i d u a l ) 的形式，在算法中为二进制串，并且对应于遗传学中的 染色体( c h r o m o s o m e ) 。 二、种群( p o p u l a t i o n ) 个体的集合称为群体，串是种群中的元素 三、种群大小( p o p u l a t i o n s i z e ) 在种群中个体的数量称为种群的大小。 四、基因( g e n e ) 基因是串中的元素，基因用于表示个体的特征。例如有一个串s = 1 0 1 l ，则其 中的1 0 1 l 这4 个元素分别称为基因。基因所取的的值称为等位基因( a l l e t e s ) 。 第一章绪论 3 五、基因位置( g e n ep o s i t i o n ) 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置在串中 由左向右计算，例如在串s = 1 1 0 1 中，0 的基因位置是3 。基因位置对应于遗传学 中的地点( l o c u s ) 。 六、基因特征值( g e n ef e a t u r e ) 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串s = 1 0 1 1 中， 基因位置3 中的l 。它的基因特征值为2 ；基因位置l 中的1 ，它的基因特征值为 8 。 七、串结构空间s 5 在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。 串结构空间对应于遗传学中的基因型( g e n o t y p e ) 的集合。 八、参数空间s 9 这是串空间在物理系统中的映射，它对应于遗传学中的表现型( p h e n o t y p e ) 的 集合。 九、适应度( f i t n e s s ) 表示某一个体对于环境的适应程度。 遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程 时，再进行说明。 1 2 2 遗传算法的基本原理 遗传算法g a 把问题的解表示成“染色体”，在算法中也就是二进制编码的串。 并且，在执行遗传算法之前，给出一群“染色体”，也就是假设解。然后，把这些 假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的 “染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体” 群。这样，一代一代的进化，最后就会收敛到最适应环境的一个“染色体”上， 它就是问题的最优解。很明显，遗传算法是一种最优化方法，它通过进化和遗传 机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串b 。 处，即求出最优解。 长度为l 的n 个二进制串b i ( i = 1 ，2 ，t 1 ) 组成了遗传算法的初始解群， 也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化 术语，对群体执行的操作有三种： 1 选择( s e l e c t i o n ) 这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。 故有时也称这一操作为再生( r e p r o d u c t i o n ) 。由于在选择用于繁殖下一代的个体 4 混合遗传算法及其实现研究 时，是根据个体对环境的适应度来决定其繁殖量的，故而有时也称为非均匀再生 ( d i f f e r e n t i a lr e p r o d u c t i o n ) 。 2 交叉( c r o s s o v e r ) 这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因 进行交换，从而产生新的个体。交叉算子示意如图1 1 。 父串1 父串2 父串1 父串2 l 交叉点| 交换 + 糕瓢溪蒸霉灞添黼 i 交叉点1f 交换交叉6 + l 。 疆蘸麟臻燃镳 后代串1 匕= = = = 单点交叉 两点交叉 后代串2 后代串1 后代串2 l满粼 i l 鬻霪瓤溪嚣蓬 l i纛骜，。 i 。黪蓼羚l蠹簌誊 图1 1 交叉算子示意图 3 变异( m u t a t i o n ) 这是在选中的个体中，对个体中的某些基因按变异概率p _ 执行异向转化。 在串b i 中，如果某位基因为1 ，产生变异时就是把它变成0 ；反亦反之。 1 2 3 遗传算法的步骤和意义 1 初始化 选择一个群体，即选择一个串或个体的集合b i ，i = l ，2 ，n 。这个初始的群 体也就是问题假设解的集合。一般取n = 3 0 1 6 0 。 通常以随机方法产生串或个体的集合b i , i = l ，2 ，n 。问题的最优解将通过这 些初始假设解进化而求出。 2 选择 根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适 第一章绪论5 应度准则体现了适者生存，不适应者淘汰的自然法则。 给出目标函数f ，则f ( b i ) 称为个体b i 的适应度。以公式( 1 - 1 ) p 选中b i = ；盟竹( 1 - 1 ) f ( b j ) p l 为选中b i 为下一代个体的次数。 显然从上式可知： ( 1 ) 适应度较高的个体，繁殖下一代的数目较多。 ( 2 ) 适应度较小的个体，繁殖下一代的数目较少，甚至被淘汰。 这样，就产生了对环境适应能力较强的后代。从问题求解角度来讲，就是选 择出和最优解较接近的中间解。 3 交叉 对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉 概率p 。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新 的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。 例如有个体 s 1 = l 0 0 1 0 l $ 2 = 0 1 0 1 1 l 选择它们的左边3 位进行交叉操作，则有 s l = 0 1 0 1 0 l s 2 = 1 0 0 11 1 一般而言，交叉概率p 。取值为0 ，2 5 0 7 5 。 4 变异 根据生物遗传中基因变异的原理，以变异概率p m 对某些个体的某些位执行变 异。在变异时，对执行变异的串的对应位求反，即把1 变为0 ，把0 变为l 。变异 概率p m 与生物变异极小的情况一致，所以，p m 的取值较小，一般取0 0 1 0 2 。 例如有个体s = 1 0 1 0 1 1 。 对其的第1 ，4 位置的基因进行变异，则有 s 1 = 0 0 1 1 1 1 单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进 化的单一群体。因为当所有的个体一样时，交叉是无法产生新的个体的，这时只 能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。 s潺会遗传算法及羹实瑰臻究 5 全局最优收敛( c o n v e r g e n c e t ot h eg l o b a lo p t i m u m ) 当最饶个体的逶应度_ 逸筏给定鹃润篷，或者最优令舔豹适应麓和群体遁应度 不稃上升时。则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变 嚣掰褥到静凝一代群俸取代t 一代群体，并返霞至第2 多繇选择搽孛# 楚继续锤环 执行。 强1 2 中表示了邃传舅法懿撬符过程 l 变蒡为9 阉1 2 遗话算法原爨 1 3 遗传算法研究现状 撵r t 淡l i 辱1 连, 近年来有关遗传算法的期刊论文和会议论文每颦都有数百乃至上千篇，这些文 献主要是从某个方鹾对遗传簿法进褥不同形式的改进，荠照都有锋对性的用于解 决浆类实际问题。下面从几个方面进行讨论： 1 。缡码表承 h o l l a n d 在运用模式定瑷分析编码机制时，建议使用二进制编码，但二避制编 码不能直接反映问题的固鸯结构，糟度不藤，个体长度大，占用计冀机内存多。 g r a y 编码怒将二j 制编码通过一个变换进行转换得到的编码，其目的怒克服 h a m m i n g 悬崖的缺点f 6 i ，动态编码【7 l ( d y n a m i ce n c o d i n g ) g a 是当算法收敛至某局 部最优时增加搜索的精度，从而使得在全髑最优解附近可以进行更精确的搜索， 增力琏精度的办法是在保持串长不变的前提下减小搜索区域，对于问题的变爨是实 向量的情形。可以澎接采嗣实数进行编码，这样可以直接在解的表现形上迸行遗 传操作从而便于引入与同题领域相关的启发式信息以增加算法的搜索能力1 8 用。复 数编码i 嘲韵g a 是为了描述和解决= 维嗣越，基因耀x + y i 袭示；它还可以维广到 第一章绪论7 多维问题的描述中，多维实数编码【 g a 使无效交叉的可能性大大降低，同时其合 理的编码长度也有助于算法在短时间内获得高精度的全局最优解。当问题表示的 是树和图时，我们还可以使用结构式编码。 2 适应度函数 适应度函数是用来区分群体中个体好坏的标准，是自然选择的唯一标准，选择 的好坏直接影响算法的优劣。引入适应值调节和资源共享策略可以加快收敛速度 和跳出局部最优点。对适应值进行调节就是通过变换改变原适应值间的比例关系， 常用的比例变换有线性变换、乘幂变换和指数变换等；对于一个问题采用什么变 换才能达到较优的效果。vk r e i n o b i c h 【1 2 l 等做了较详细的讨论，而swm a h f o u d 采用了共享的技术“，对子群的形成和稳定起了一定作用，文中主要用子群消失 时间的近似形式估计s h a r i n g 的界。vp e t r i d i s 采用了依据搜索进展可变的适应值 函数1 ，并用于分割问题，取得了较好的效果。杨旭东等设计了自适应选取遗传 算法的适应值函数的方法“”，该方法的计算量要比排序选择的计算量小的多，而 且有效的避免了算法的早熟收敛。 3 选择策略 优胜劣汰的选择机制使得适应值大的个体有较大的存活机会，不同的选择策略 对算法的性能有较大的影响。赌轮选择是使用最多的选择策略，但这种策略可能 会产生较大的抽样误差，于是对此提出了很多的改进方法，如繁殖池选择【1 6 】， b o l t a m a n n 选择【i7 j 等等，但是这几种策略都是基于适应值比例的选择，常常会出现 早熟收敛和停滞现象。为此又提出了非线性排名选择【8 】，这种选择不仅避免了上述 问题，而且可以直接采用原始适应值进行排名选择，而不需对适应值进行标准化； 但这种选择在群体规模很大时，其额外计算量( 如计算总体适应值和排序) 也相 当可观，甚至在进行并行实现时会带来一些同步限制。基于局部竞争机制的选择 如( 丑+ 口) 选择【l 引，它使双亲和后代有同样的生存竞争机会，在一定程度上避 免了这些问题。dtp h a m 等采用了类似梯度的方式来选择【1 9 】，不仅使较差的染色 体比较好的染色体得到更大的改进，而且还不断产生新的个体，从而不断拓展了 新的空间。dn o v e r 等引入了h a r v e s t i n gs t r a t e g i e s 来分析遗传算法的性能【2 ， h a r v e s t i n gs t r a t e g i e s 是指在每一代交叉和突变后进行两次乃至多次筛选作为下砸 的群体。tk a o 采用了d i s r u p t i v es e l e c t i o n 【2 l 】，它吸收了优等和劣等个体，实验结 果表明了两级分化有可能更容易找到最优解。为了提高种群的多样性，高峰提出 了一种基于免疫多样性的选择算子【2 2 l ，该选择算子依赖于串的稠密度和适应值， 串的稠密度越大，其保留下来的可能性就越小，具体事例证明改进算法是有效的。 4 控制参数 控制参数一般都有种群大小、交换概率、变异概率等，这些参数对遗传算法性 8 混合遗传算法及其实现研究 能影响较大。在标准遗传算法中采用经验进行估计，这将带来很大的盲目性，而 影响算法的全局最优性和收敛性。目前许多学者意识到这些参数应该随着遗传进 化而自适应的变化，d a v i s 提出自适应算子概率方法【2 ，即用自适应机制把算子概 率与算子产生的个体适应性相结合，高适应性值被分配高算子概率。w h i t l e y 提出 一种自适应突变策略与一对父串间的h a m m i n g 距离成反比【2 “，结果显示能有效的 保持种群的多样性。张良杰等通过引入i 位改进子空间概念，采用模糊推理技术来 确定选取突变概率的一般性原则1 2 ”。a r a b a s 等设计了一种群体规模可变的遗传算 法【2 6 1 ，它提出每个个体应该有年龄和生命周期的概念并淘汰年龄大于生命周期的 个体，从而使遗传算法动态的控制了群体数目，这种方法可以找出一个接近最小 代价的遗传算法，同时尽量将群体规模保持在现有水平，防止群体规模指数级增 长，以降低计算的开销。丁承明等提出利用正交试验法去优化选取g a 控制参数1 2 7 1 ， 这种方法利用正交试验的均衡分布性使得通过较少的试验就可搜索绝大部分参数 组合空间，而且还可以确定那个参数对g a 结果影响最显著，然后针对性的进行 精确搜索，从而使得g a 参数问题得到圆满的解决。为保证种群的有用多样性， 提出动态种群法1 2 引，即当迭代到一定代数，若目标函数的值相同，则现存种群中 的较差的n 个染色体被随机产生的n 个染色体所代替，使进化过程中不断有新个 体引入。刘丽利用模糊规则对选择概率和变异概率进行控制1 2 9 1 。在线改变其值。 相应的算例表明其有较好的性能。 5 遗传算子 基本遗传算法中采用单点交叉算子和简单的变异算予。它们操作比较简单，计 算量小，但是在使用过程中有很大的局限性，例如：由于单点交叉破坏模式的概 率较小，致使搜索到的模式数也较少，使算法具有较低的搜索能力。f e n g e t a l 对 多维连续空间的g a 复杂多样性进行了分析，通过建立相应的数学模型。f e n g 等 解释了在多维连续空间和大规模群体中使用均匀杂交算子【3 0 1 是如何探索新的解空 间区域，为了使得变异能够根据解的质量自适应的调整搜索区域，从而能较明显 的提高搜索能力，提出自适应变异算子【3 ”。为了保护适应值较高的模式，提出了 自适应交叉和变异1 3 2 】，如果遇到适应值较高的模式，则通过随机引入模式外的位 进行保护。为了克服早熟，引入多种群g a 3 3 j ，不同种群赋以不同的参数，实现不 同的搜索目的，通过移民算子联络各种群，通过人工选择算子保存各种群每个进 化代中的最优个体。为了防止近亲繁殖，扩大种群的多样性，抑制超长个体快速 繁殖，引进近亲繁殖算子，两个个体是否为近亲可以通过基因片段的h a m m i n g 距 离来判断，距离越大，则为近亲的可能性越小：为了加强局部搜索能力，增加漂 移算子，将染色体各基因片段的后二分之一的基因分别按一定的概率做1 的漂移， 排位越后的基因漂移的概率越大，由此产生一定数量的新个体，用基因预选机制 第一章绪论9 的小生境技术控制漂移方a t 3 4 】。因为格点法产生的点集能均匀的分布于搜索空间， 并且佳点又是最好的格点，所以可以用数论中的佳点集理论设计交叉算子【3 5 】，结 果表明它的搜索效果要比纯随机方法好，而且有效的避免早熟现象。基于生物免 疫性提出的免疫算子 3 6 1 ，能够明显抑制进化过程中的退化现象，减轻g a 的后期 波动，从而提高了搜索效率和收敛速度。 6 综合方面 孙建永等提出了可分解可拼接g a 编码【3 ”，并基于此编码分别在种群层次和 编码层次发展了动态变异和动态选择操作，这种方法很大程度上避免了早熟问题。 增强型g a 中p 引，引入了几个新算子和新的种群迁移策略，并用其对模糊逻辑控 制器进行设计，得到了便于理解的模糊集和模糊规则。用小波分析中的多尺度分 析对g a 中的染色体进行多尺度分解，这样分解后的染色体长度变短，基因交换、 变异等遗传操作更为彻底，有效的克服了基因丢失引起的早熟问题 3 9 1 。小生境技 术不仅能够保证种群中解的多样性，而且具有很强的引导进化能力，所以小生境 技术的引入，提高了g a 处理多峰函数优化问题能力【40 1 。将模拟退火过程引入遗 传算法【4 ”，在优选交叉和变异个体的过程中加入一定的“扰动”，以达到保持种群 内位串的多样性和位串之间的竞争机制，克服了算法易陷入局部极小点的问题， 使得搜索沿着全局最优方向进行。广义遗传算法【4 2 1 ，它以多点突变操作为主，以 基因交叉操作为辅，实现了从一个局部最优状态到另一个局部最优状态的转移， 使得算法获得全局最优。为了使g a 用于约束最优化，提出了一种非稳态罚函数 g a l 43 1 ，非稳态罚函数是遗传代数的函数，当代数增加时，罚函数也随着增大，同 时给g a 也带来更多的选择压力，促使g a 找到可行解。综合遗传算法的全局性和 神经网络的并行快速等特点，提出的遗传神经网络算法1 4 ”，可克服遗传算法最终 进化至最优解速度较慢和神经网络易陷入局部最优解的缺陷，具有较好的全局性 和收敛速度。采用面向对象技术设计了面向对象遗传算法【4 ”，这种方法改变了传 统的g a 中各个函数间只有参数的传递，而没有代码的继承性的状况，从概念上 提高了软件的可重用性，用户可以更方便的实现自己的编码方案和遗传算予。变 异基遗传算法【4 6 l ，采用变异算子进行局部优化搜索，并利用随机初始化技术使算 法在局部搜索能力提高的同时仍有可能找到全局最优解。贪婪遗传算法1 47 】在二次 分配问题中取得了较好的效果，在该算法中引入了新的交叉算予和移民算子，保 证了种群的多样性，并且通过比赛竞争使得各种群得到进化，很好的解决了种群 多样性及对个别好个体偏爱之间的矛盾。 混合遗传算法及其实现研究 1 4 本文主要内容 近年来，遗传算法在许多领域都得到了广泛的应用。本文在对大量的相关文 献资料进行研究的基础上，针对现有的遗传算法的不足，提出了几种改进的算法。 本文内容安排如下： 第一章简要介绍了遗传算法的基本概念、原理、步骤及意义，并概述了遗传 算法的发震现状。 第二章叙述了遗传算法的主要理论：模式定理、内含并行性，以及最优保留 遗传算法的收敛性。 第三章在对现有的小生境技术的研究基础上，基于遗传算法作用机理分析， 将小生境技术与双亲变异相结合，提出了一种改进的小生境遗传算法，相对于基 于共享的小生境遗传算法，其收敛速度与精度都有所提高。 第四章对现有的种群“早熟”评价指标进行了分拆，提出了改进的自适应遗 传算子，实验结果表明，该算法可以较好的保持种群的多样性。 第五章借鉴免疫算法机理，将免疫机制应用于遗传算法，较好的解决了遗传 算法的“早熟”收敛。并且大大的改善了遗传算法的全局收敛性能提高了算法 的搜索速度。 第二章遗传算法基本理论 第二章遗传算法基本理论 遗传算法提供了一种求解复杂系统优化问题的通用框架，隐含并行性和全局 搜索特性是它的两大显著特征，而且这是一个以适应度函数( 或目标函数) 为依 据，通过对群体个体施加遗传操作实现群体内个体结构重组的迭代处理过程。在 这一过程中，群体个体( 问题的解) 一代一代得以优化并逐次逼近最优解。本章 介绍了遗传算法所依赖的基本遗传操作：选择、交叉和变异算子，并分析了遗传 算法的基本机理，这些主要原理是以后各章研究的理论基础。 2 1 模式定理 模式( s c h e m a ) 是一个描述字符串集的模板，该字符串集中串的某些位置上 存在者相似性。不失一般性，我们考虑二值字符集 o ，l ，由此产生通常的0 ，l 字 符串。现在我们增加一个符号“一，称作“无关符”( d o n tc a r e ) 或通配符，即“刈 既可以被当作“0 ”，又可以被当作“l ”。这样，二值字符集 o ，1 ) 就扩展为三值字 符集 o ，l ，+ ，由此可以产生诸如0 1 1 0 、o 1 1 ”、0 1 o 等字符串。 定义2 1基于三值字符集 0 ，l ，+ ) 所产生的能描述具有某些机构相似性的0 、 1 字符串集的字符串称作模式。 以长度为5 的串为例，模式* 0 0 0 1 描述了在位置2 、3 、4 、5 具有形式“0 0 0 1 ” 的所有字符串，即 1 0 0 0 1 ，0 0 0 0 1 由此可以看出，模式的概念为我们提供了一种简 洁的用于描述在某些位置上具有结构相似的0 、l 字符串集合的方法。然而，模式 概念的引入并不是仅仅为了描述上的方便。在引入模式概念前，我们所看到的遗 传算法是：在某一代中，n 个互不相同的串在选择、交叉、变异等遗传算子作用 下产生下一代的n 个互不相同的串。那么，在两代之间究竟保留了什么性质，破 坏了什么性质，我们无从得知，因为我们看到的串是相互独立的，互不联系的。 而引入模式的概念后，我们看到一个串实际上隐含了多个模式( 长度为l 的串隐 含着2 0 各模式) ，一个模式可以隐含在多个串中，不同的串之间通过模式而相互联 系。遗传算法中串的运算实际是就是模式的运算，因此，通过分析模式在遗传操 作下的变化，从而把握遗传算法的实质，这正是模式定理所要揭示的内容。 定义2 2 模式h 中的确定位置的个数称作该模式的模式阶，记作0 ( h ) 。 比如模式o “i t 的阶数为4 ，而模式o t + + + 的阶数为1 。显然，一个模式的阶数 越高，其样本数就越少，因而确定性越高。 混合遗传算法及其实现研究 定义23 模式h 第一个确定位置和最后一个确定位置之间的距离称作该模 式的定义距，记作6 ( h ) 。 比如模式0 1 1 + 1 + 的定义距为4 ，而模式o ”+ 的阶数为0 。 定义2 4 设x = i n = ( b 。) n 为遗传算法群体状态空间，h v 。= o ，1 ，+ ) 是任一 模式，p ( t ) = x l ( t ) ，x 2 ( t ) ，x n ( t ) ) x 表示遗传算法在第t 代时的群体，f i r 1 为适 应度函数，则称公式( 2 - 1 ) f ( h , t 卜面南，。积 ) ( 2 - 1 ) 为模式h 的平均适应值，这里l h n p ( t ) l 表示集合h n p ( t ) e o 元素的个数，既p ( t ) 中含有h 中元素的个数。称公式( 2 2 ) ，( f ) = f ( x ) n ( 2 2 ) x e p ( t ) 为p ( t ) 的平均适应值。 定理2 ，1( 模式定理，s c h e m at h e o r e m ) 设遗传算法的交叉概率和变异概率 分别为p 。和p 。，模式h 的定义长度为6 ( h ) 、阶为0 ( h ) ，第t + 1 代群体p ( t + 1 ) 含有h 中元素个数的数学期望值记为e h n p ( t + 1 ) j 】。则 e h n p ( t + 1 ) 1 - i h n p ( t ) t 掣【l p c 磐- - 0 ( h ) p m 】 f ( ，) 卜1 证明由于遗传算法采用按适应值比例的选择策略，则易见日n p ( t ) 中元素得 以选择的期望值为 掣= 4 h n 酬掣 “h n p t o ff q ) 由于交叉操作是随机选取1 到l 一1 中的一个位置并交换两父体的一个对应子串， 于是属于模式h 的个体经过交叉后仍属于h ( 称为未被破坏) 的概率不小于 l 一见等军。而一个个体经过变异后未被破坏的概率为( 1 - p r o ) “a 另外，p ( t ) 中不属于h 中的元素也有可能经过交叉、变异后属于h ，所以第t + 1 代群体p ( t + 1 ) 中属于h 的个体数目的期望值不小于 h 例1 等【l 他篱】( 1 - ，( f ) 1 第二章遗传算法基本理论 又因为在遗传算法中p 。一般取值很小，故有 1 - p 。等】( 1 - p m p 1 - p c 等1 - 0 ( 驯小”等- 0 ( 聊。 于是足理得让。 推论2 1 在遗传算法e e ，定义长度较短、低阶且适应值超过平均适应值的模 式h ，在群体中数鼹的期望值按指数级递增。 证明设对任意，f ，都有丛! 型1 大于一个常数c l ，再记 f ( t ) 蹦 1 他篱- 0 ( 聊。1 若k i ，则由定理2 1 知 研i n p ( t + 1 ) i 】| h n p ( t ) i k 由此递推易得：口n 尸( 圳】剖h n p ( 0 ) 1 k 。于是推论成立。 虽然模式定理可以在一定意义上解释遗传算法的有效往，但它仍有以下的缺 点： ( 1 ) 模式定理只对二迸制编码才适用，对其它编码方案尚没有相应的结论 成立。 ( 2 ) 模式定理提供的只是期望值的一个下界，我们无法根据它推断算法收敛 与否。 ( 3 ) 模式定理对算法的设计如控制参数的选取没有太大的帮助。 2 2 内含并行性定理 我们已经知道，一个串实际上隐含了多个模式，遗传算法事实上是模式的运 算。对于一个长度为l 的串，其中隐含着2 0 个模式。那么，若群体规模为n ，则 其中隐含的模式个数介于2 。和n 2 。之间。显然，由于交叉操作的作用并非所有的 模式都能高概率的处理。因为一些定义距较长的模式将遭到破坏。本节将介绍遗 传算法中能以指数级增长的模式个数的下界。 在这方面，h o l l a n d 和g o l d b e r g 指出了遗传算法有效处理的模式个数为o ( n 2 ) ， 1 4 混合遗传算法及其实现研究 这意味着，尽管遗传算法实际上只对n 个串个体进行运算，但却隐含的处理了0 ( n 3 ) 个模式。h o l l a n d 将这一性质称为内含并行性( i m p l i c i t p a r a l l e l i s m ) 。其结论 如下： 定理2 2 ( 内含并行性定理) 设是一个小正数，l ： o ，令，= 去，若群体规模n = n ( 1 3 ) = 2 成， 这里b 0 是一个参数，则有 ( 1 ) 遗传算法一次处理的那些存活率大于1 一e 且定义长度2 l 。的模式数目 的期望值至少与- 础撕鬲了同阶，其中 g ( f 1 ) 乏 l + i 2当o 声 1 。 。 1 + 2 h ( 丢) 当l s ； 万2 l 。9 2 3当p 詈 这里( f ) = 一( 1 0 9 2 f - ( 1 - ( ) l o g2 ( 1 一f ) ，( 0 n 对，f c s 2 ) = f ( s “) ，则l i m p ( 厂( s ：) = f ( s ”) ) = l 因此 e g a 全局收敛。 由以上定理可直接得出如下推论： 推论2 2 在加入最优保留操作之前，具有各态遍历性的遗传算法( g a i ) 在 加入最优保豳操作后，若不改变( 或影响) g a l 的遍历性。则得到的e g a 是全局 收敛的。 2 3 2 全局收敛e g a 的实现方法及收敛性分析 2 3 2 1 最优个体保留在种群之外 设s ：为第k 代耪群s k 中的最优个体，现将保存到一个不参与选择、交叉遗 1 6 混合遗传算法及其实现研究 传操作的变量s m 中，即令s m = s ：，圊时不改变s k 的组成。然后对s k 进行交叉、 变异、复制操作。产生下一代种群s 。将s k + l 中的最优个体j ：+ ，与s m 比较，若 s ：+ l 优于s m ，则令s m = j ：+ i ，而s k + 1 保持不变：若s m 优于s ：则s m 与s 均保持不变。再对s 执行上述操作，如此反复。 在这种情况下，s ：保留在进化种群之外，不参与后续的遗传操作，仅作为独 立于算法本身的g a 迄今所发现最后个体的外部记录，对以前的算法无任何影响。 由基本遗传算法的遍历性及推论2 2 可得如下推论： 推论2 3 加入上述最优保留操作的基本遗传算法是全局收敛的。 2 3 2 2 最优个体保留在种群之内 ( 1 ) 最优个体参与后续遗传操作 设s ：为第k 代种群s k 中的最优个体，将s ：保存在中间变量s m 中，同时不改 变s k 的组成。对s k 执行遗传操作，产生下一代种群s k 十l 。将s k + l 中的最优个体s ：+ 。 与s m 比较，若s m 优于s ：则用s m 代替j ：此时s 。= 岛+ ：否则s k + l 保持 不变。然后对s 或文+ ；执行上述操作，如此反复。 下面分析此类e g a 的收敛性。设c = f i t ( s ) ：s e d ，d 是长度为l 的二进制 审集合，其维数