（计算数学专业论文）关于混合遗传算法改进的研究.pdf

西北大学硕士学位论文 摘要 为了克服标准遗传算法( s g a ) 收敛速度较慢，且局部搜索能力不强的缺点， 本文将经典优化算法与遗传算法进行结合，构造新的混合遗传算法。通过引入经 典优化中局部搜索能力较强的充分下降条件、w b l f e 条件、g o l d s t e i n 条件确定步 长，而搜索方向采用共轭梯度方向进行局部搜索，由此得到一类高效的非精确的 混合遗传算法。并对算法进行收敛性分析，得到算法的收敛性。 为了克服黄金分割搜索方法在解决多峰优化问题中的局限性，根据其在单峰 优化问题中的优异表现，受到一维的黄金分割的思想的启发，结合文献 【2 7 】 2 8 】【2 9 】中将二维黄金分割算法的形式推广到三维，再将三维的形式推广到高 维，从而得到一种数值结果很好的变形的黄金分割混合遗传算法。通过对基准函 数的测试，将几种算法的数值结果进行比较，得出新的混合遗传算法的数值效果 优于其它的算法。 针对带有约束条件的优化问题，结合筛选法的混合遗传算法，采用筛选法来 处理约束条件，得到既不同于罚函数处理，又不同于多目标规划的新的混合遗传 算法。 【关键字】遗传算法筛选法罚函数黄金分割非精确搜索 两北大学硕上论文 s u b j e c to nm o d i 6 e dh y b dg e n e t i ca l l g o r i t h m a b s t r a c t i i lo r d e ft oo v e r c o m et h es 1 0 w e rc o n v e r g e n c eo ft h es t a n d a f dg e n e t i ca 1 9 0 r i t l l l i l ( s g a ) ，锄di nw h i c ht h el o c a ls e a r c hi sw e a k ，t h ep a p e rw i l lc o m b i n et h et r a d i t i o n a l 0 p t i m i z a t i o n a n dg e n e t i ca l g o r i t h m f i r s tb yi n t r o d u c i n gt h es u f f i c i e n td e c r e a s e c o n d i t i o n ，t h ew o l f ec o n d i t i o na i l dt h eg o l d s t e i nc o n d i t i o nw i t ht h e i rs t r o n gl o c a l s e a r c h c a p a b i l i t i e s ，d ot h es t 印l e n 垂hs e l e c t i o n 7 1 1 l e s e a r c hd i r e c t i o ni s u s i n g c o n j u g a t eg r a d i e n td i r e c t i o n a ne 仃i c i e n t 孤dc o n v e r g e n th y b r i dg e n e t i ca l g o r i t h mi s o b t a i n e d i no r d e rt oo v e r c o m et h el i m i t a t i o n so ft h eg o l d e ns e l e c t i o nm e t h o di ns o l v i n gt h e m u l t i 一叩t i m i z a t i o np r o b l e m s ，i na c c o r d a n c ew i t hi t so u t s t a i l d i n gp e d o m a n c ei n a s i n 酉eo p t i m i z a t i o np r o b l e m ，i n s p i r e db yt h eo n e d i m e n s i o n a lg o l d e ns e l e c t i o n ，i nt h e l i t e r a t u r e s 【2 7 】【2 8 】【2 9 】，2 dg o l d e ns e l e c t i o na l g o r i t h mi se x t e n d e dt o3 d ，a n dt h e n e x t e n d e dt oh i g h - d i m e n s i o n a l ，t h u sg a i n e dah y b r i dg e n e t i ca l g o r i t h md e f b n n a t i o n w i t hg o o dn u m e r i c a lr e s u l t s t l l l r o u g l lt h eb a s e l i n ef u n c t i o nt e s t ，w ec o m p a r e dt h e n u m e r i c a l r e s u l t so ft h e s ea l g o r i t h m s 觚dk i l e wt h es t r e n g t h s 柚dw e a l ( 1 l e s s e so f 趾g o r i t h m t os o l v et h ec o n s t r a i n to p t i m i z a t i o np r o b l e m s ，t h eh y b r i dg e n e t i ca l g o r i t h mw i t h t h ef i l t e rm e t h o di sak i n do fu s i n gt h ef i l t e fm e t h o d ，a n di sd i l l e r e n tf r o md e a l i n g w i t hp e n a l t yf u n c t i o n ，a n dd i f f e r e n t 矗o mt h em u l t i - o b j e c t i v ep l a n n i n gn e wh y b r i d g e n e t i ca l g o r i t l l i l l k e yw o r dg e n e t i c 灿g o r i t h m t h ef i l t e rm e t h o d p e n a l t yf u n c t i o ng o l d e n s e l e c t i o nt h es u f f i c i e n td e c r e a s ec o n d i t i o n i i 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适 学位论文作者签名：指导教师签名： 艚年莎月( 严日沙缉6 月俨日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 一躲孝撕 v 僻占月爿日 两北大学硕上论文 第一章引言 1 1 遗传算法的起源及历史发展过程 遗传算法起源于对生物系统所进行的计算机模拟研究。早在2 0 世纪4 0 年代， 就有学者开始研究如何利用计算机进行生物模拟技术，他们从生物学角度进行了 生物的进化过程模拟、遗传过程模拟等研究工作。进入6 0 年代后，美国密执安 大学的h o l l a n d 教授及其学生们受到这种生物模拟技术的启发，创造出了一种基 于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术 遗传算法。下面是在遗传算法的发展进程中一些关键人物所做出的一些主要贡 献。【2 1 ( 1 )j h h o l l a n d 2 0 世纪6 0 年代，h o l l 锄d 运用生物遗传和进化的思想来研究自然和人工自 适应系统的生成以及它们与环境的关系，借鉴生物遗传的机制，提出以群体的方 法进行自适应的搜索和遗传算法的基本定理模式定理( s c h e m at 1 l e o r e m ) ， 并实现了第一个基于遗传算法的机器学习系统一一分类器系统( c l a s s i f ! i e r s y s t e m s ，简称c s ) 。 ( 2 ) j d b a 舀e y 1 9 6 7 年，b a 酉e y 首次提出了“遗传算法 一词，认为在算法执行的不同阶 段使用不同的选择概率有利于防止遗传算法早熟现象，从而创立了自适应遗传算 法的概念。 ( 3 )k a d ej o n g 1 9 7 5 年，d ej o n g 结合模式定理进行大量的纯数值函数优化计算实验，树立 了遗传算法的工作框架，并建立了著名的d ej 0 n g 五函数测试平台。 ( 4 ) d j g o l d b e r g 1 9 8 5 年，g o l d b e r g 出版的专著搜索、优化和机器学习中的遗传算法( g e n e t i c 舢9 0 r i t h m si ns e a r c h ，o p t i m i z a t i o na n dm a c h i n ek a m i n g ) ，系统总结了遗传算法 的主要研究成果，全面而完整的论述了遗传算法的基本原理及其应用。 ( 5 )l d a v i s 1 9 9 1 年，d a v i s 编辑出版了遗传算法手册( h a n d b o o ko fg e n e t i c 两北大学硕上论文 趾g o r i t h m s ) ，本书为推广和普及遗传算法的应用起到了重要的指导作用。 ( 6 )j r k o z a 1 9 9 2 年至1 9 9 4 年，k b z a 将遗传算法应用与计算机程序的优化设计自动生 成，提出了遗传编程( g e n e t i cp r o 伊a m m i n g ，简称g p ) 的概念。 我国开展遗传算法的研究主要在9 0 年代，是继专家系统、神经网络后的第 三大热点研究问题。 1 2 遗传算法的应用 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的 具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗 传算法的一些主要应用领域【2 】【3 】【4 】【5 】： ( 1 ) 函数优化 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用 算例。很多人构造出了各种各样的复杂形式的测试函数，有连续函数也有离散函 数，有凸函数也有凹函数，有低维函数也有高维函数，有确定函数也有随机函数， 有单峰值函数也有多峰值函数等。用这些几何特性各据特色的函数来评价遗传算 法的性能，更能反映算法的本质效果。而对于一些非线性、多模型、多目标的函 数优化问题，用其他优化方法较难求解，而遗传算法却可以方便的得到较好的结 果。 ( 2 ) 组合优化 遗传算法对于组合优化中n p 完全问题非常有效，在求解旅行商问题、背包 问题、装箱问题、图形划分问题等方面得到成功的应用。 另外，遗传算法在生产调度问题、自动控制、机器人学、图象处理、人工 生命和机器学习等方面也有应用。 1 3 遗传算法的特点 作为一种随机的优化与搜索方法，遗传算法有着其鲜明的特点： ( 1 ) 遗传算法的操作对象是一组可行解，而非单个可行解；搜索轨道 有多条，而非单条，因而具有良好的并行性。 ( 2 ) 遗传算法只需利用目标的取值信息，而无需梯度等高价值信息， 因而 适用于任何大规模、高度非线性的不连续多峰值函数的优化以及无解析表达式 2 西北人学硕士论文 的目标函数的优化，具有很强的通用性。 ( 3 ) 遗传算法择优机制是一种“软”选择，加上其良好的并行性，使它具 有良好的全局优化性和稳健性。 ( 4 )遗传算法操作的可行解集是经过编码化的( 通常采用二进制编码) ，目 标函数解释为编码化个体( 可行解) 的适应度，因而具有良好的可操作性和简单 性。 1 4 遗传算法目前面临的问题 遗传算法对于形式复杂，不易精确求解解析表达式的优化问题较一般的经典 优化算法而言具有一定的优势。遗传算法的最大的缺陷就是收敛速度慢、局部搜 索能力较差、很容易陷入局部最优、出现早熟问题。早熟问题是遗传算法在发展 过程中不断被改进的地方。 目前只有两种解决办法：一种是采用二进制编码，根据二进制编码的特点采 用相关的高效的搜索方法，结合概率搜索方法，构成混合遗传算法；另一种是采 用十进制编码或者实数编码，结合经典优化里的搜索方法，构成的一类高效的混 合遗传算法，并得到这类算法的收敛性。因而，我们在算法的构造上仍需创新， 得到更好的方法和其数值结果及收敛性。 3 两北大学硕上论文 第二章遗传算法的基本理论与方法及混合遗传算法的改进研究 2 1 简单遗传算法的基本结构描述 基于对自然界中生物遗传与进化机理的模仿，针对不同的问题，很多学者设 计了许多不同的编码方法来表示问题的可行解，开发出了许多种不同的遗传算子 来模仿不同环境下的生物遗传特性。因而，由不同的编码方法和不同的遗传算子 就构成了各种不同的遗传算法。但这些遗传算法都具有共同的特点，g o l d b e r g 【2 3 】 总结出了一种统一的最基本的遗传算法基本遗传算法( s i m p l eg e n e t i c 趟g o r i t h m s ) ，简称( s g a ) 。基本遗传算法只使用选择算子、交叉算子和变异算 子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传 算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一 定的应用价值。 一般认为，遗传算法有5 个基本组成部分( 这是由m i c h a l e w i c z 归纳的) 【6 l ： 1 ) 问题的解的遗传表示 2 ) 创建解的初始种群的方法 3 ) 根据个体适应值对其进行优劣判定的评价函数 4 ) 用来改变复制过程中产生的子个体遗传组成的遗传算子 5 ) 遗传算法的参数值 遗传算法维持由一群个体组成的种群p o ) ( f 代表遗传代数) 。每一个个体均 代表问题的一个潜在解。每一个体都被评价优劣并得到其适应值。某些个体要经 过称作遗传操作的随机变换，由此产生新的个体。而遗传操作即上面谈到的基本 遗传算子选择算子、交叉算子和变异算子。从父代种群和子代种群中选择比 较优秀的个体就形成了新的种群。在若干代以后，算法收敛到一个最优个体，该 个体很有可能代表着问题的最优或次优解。遗传算法的一般结构可以描述如下见 图1 ： 4 两北大学硕上论文 图l 2 2 编码 在遗传算法的运行过程中，它不对所求解问题的实际决策变量直接进行操 作，而是对表示可行解的个体编码施加选择、交叉、变异等遗传运算，通过这种 遗传操作来达到优化的目的，这是遗传算法的特点之一。遗传算法通过这种对个 体编码的操作，不断搜索出适应度较高的个体，并在群体中逐渐增加其数量，最 终寻求出问题的最优解或近似最优解。在遗传算法中如何描述问题的可行解，即 把一个问题的可行解从其解空间转化到遗传算法所能处理的搜索空间的转换方 法就称为编码。 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键 步骤。编码方法除了决定个体的染色体排列形式之外，它还决定了个体从搜索空 间的基因型变换到解空间的表现型时的解码方法，编码方法在很大程度上决定了 如何进行群体的遗传进化运算以及遗传进化运算的效率。 5 西北大学硕十论文 一个好的编码方法，有可能会使得交叉运算、变异运算等遗传操作可以简单 的实现和执行，而一个差的编码方法，却有可能会使得交叉运算、变异运算等遗 传操作难以实现，也有可能会产生很多可行解集合内无对应可行解的个体，这些 个体经解码处理后表示的解称为无效解。虽然有时产生一些无效解并不完全都是 有害的，但大部分情况下它却是影响遗传算法运行效率的主要因素之一。 针对一个具体应用问题，如何设计一个一种完美的编码方案一直是遗传算法 的应用难点之一，也是遗传算法的一个重要研究方向。可以说目前还没有一套既 严密又完整的指导理论及评价准则能够帮助我们设计编码方案。 2 3 适应度函数 在研究自然界中生物的遗传进化现象时，生物学家使用适应度这个术语来衡 量某个物种对于其生存环境的适应程度。对生存环境适应程度较高的物种将有更 多的繁殖机会；而对生存环境适应度较低的物种，其繁殖机会就相对较少，甚至 会逐渐灭绝。与此相类似，遗传算法中也使用适应度这个概念来度量群体中各个 个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。适应度 较高的个体遗传到下一代的概率就较大；而适应度较低的个体遗传到下一代的概 率就相对较小一些。度量个体适应度的函数称为适应度函数( f i t n e s sf l l n c t i o n ) 。 遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一步 的有关搜索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。评 价个体适应度的一般过程是： ( 1 ) 对个体编码串进行解码处理后，可得到个体的表现型。 ( 2 ) 由个体的表现型可计算出对应个体的目标函数值。 ( 3 ) 根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的 适应度。 2 4 选择算子 在生物的遗传和进化过程中，对生存环境适应度较高的物种将有更多的机会 遗传到下一代的机会；而对生存环境适应程度较低的物种遗传到下一代的机会较 少。模拟这个过程，遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作： 适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗传 到下一代群体中的概率较小。遗传算法中的选择操作就是用来确定如何从父代群 6 西北人学硕士论文 体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。 选择操作建立在对个体的适应度进行评价的基础之上。选择操作的主要目的 为了避免基因缺失、提高全局收敛性和计算效率。 最常用的选择算子是基本遗传算法中的比例选择算子。但对于各种不同的问 题，比例算子并不是最合适的一种选择算子，所以人们提出了其他一些选择算子。 下面介绍几种常用选择算子。 ( 1 ) 比例选择【7 】 比例选择方法是是一种回放式随机采样的方法。其基本思想是：各个个体被 选中的概率与其适应度大小成正比。由于是随机操作的原因，这种选择方法的选 择误差比较大，有时甚至连适应度较高的个体也选择不上。 设群体大小为m ，个体i 被选中的概率以为： 儿= 1 亭上一g = 1 ，2 ，m ) ( 2 1 ) e 由上式可见，适应度越高的个体被选中的概率也越大。 ( 2 ) 确定式采样选择【1 】 确定式采样选择方法的基本思想是按照一种确定的方式来进行选择操作。 其基本操作过程是【8 】： 1 ) 计算群体中各个个体在下一代群体中的期望生存数目f ： m = m 木丘善互( f = 1 ，2 ，m ) 2 2 2 ) 用m 的整数部分 m 确定各个对应个体在下一代群体中的生存数目。其 中 f 表示取不大于f 的最大的整数。由该步共可确定出下一代群体中的 荟【n j 】个个体。 3 按照i 的小数部分对个体进行降序排序，顺序取前m 一善【n ；】个个体 7 西北人学硕上论文 加入到下一代群体中。至此可以完全确定出下一代群体中的m 个个体。 这种选择操作方法可以保证适应度较大的一些个体一定能够被保留在下一 代群体中，并且操作也比较简单。 ( 3 ) 排序选择9 】 排序选择方法的主要思想是：对群体中的所有个体按适应度大小进行降序， 基于这个排序来分配各个个体被选中的概率。其具体操作过程是： 1 ) 对群体中的所有个体按其适应度的大小进行降序排序。 2 ) 根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次 序分配给各个个体。 3 ) 以各个个体所分配的概率值作为其能够被遗传到下一代的概率，基于这 些概率值用比例选择的方法来产生下一代群体。 2 5 交叉算子 在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色 体，从而产生出新的个体或物种。交配重组是遗传和进化过程中的一个主要环节。 模拟这个环节，在遗传算法中也使用交叉算子来产生新的个体。 遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互 交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化 算法的重要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法。 遗传算法中，在交叉运算之前还必须先对群体中的个体进行配对。目前常用 的配对政策随机配对，即将群体中的m 个个体以随机的方式组成等配对个体 z 组，交叉操作是在这些配对个体组中的两个个体之间进行的。 交叉算子的设计和实现与研究的问题密切相关，一般要求它既不要太多地破 坏个体编码串中表示优良性状的优良模式，又要能够有效地产生出一些较好的新 个体模式。另外，交叉算子的设计要和个体编码设计统一考虑。 常见的交叉算子有如下几种： ( 1 ) 单点交叉 单点交叉( o n e - p o i n tc r o s s o v e r ) 又称为简单交叉，它是指在个体编码串中 随机设置一个交叉点，然后在相互交换两个配对个体的部分染色体。单点交叉的 重要特点是：若邻接基因座之间的关系能提供较好的个体性状和较高的个体适应 8 两北人学硕上论文 度，则这种单点交叉操作破坏这种个体性状和降低个体适应度的可能性最小。 ( 2 ) 双点交叉与多点交叉 双点交叉( t 、) i r o p o i n tc r o s s o v e r ) 是指在个体编码串中随机设置两个交叉点， 然后再进行部分基因交换。双点交叉的具体操作过程是： 1 ) 在相互配对的两个个体编码串中随机设置两个交叉点。 2 ) 交换两个个体在所设定的两个交叉点之间的部分染色体。 ( 3 ) 均匀交叉【1 0 】 均匀交叉( u n i f o mc r o s s o v e r ) 是指两个配对个体的每一个基因座上的基因 都以相同的交叉概率进行交换，从而形成两个新的个体。均匀交叉实际上可归属 于多点交叉的范围，其具体运算可通过设置一个屏蔽字来确定新的个体的各个基 因如何由哪一个父代个体来提供。均匀交叉的主要操作过程如下： 1 ) 随机产生一个与个体编码串长度等长的屏蔽字形= w l w 2 咝m ，其中z 为个体编码串长度。 2 ) 按下述规则从彳、b 两个父代个体中生成两个新的子代个体彳、b ： 若m = 0 ，则彳在第f 个体基因座上的基因值继承4 的对应基因值，b 在第f 个体基因座上的基因值； 若眦= 1 ，则彳在第f 个体基因座上的基因值继承b 的对应基因值，b 在第f 个体基因座上的基因值。 均匀交叉操作的示例如下： 彳：z 口a x 口d x 塑塑銮墨 ，彳五眵哆玖y 习昀秒 b ：乃罗 少明哕 。们0 1 0 1 0 1 0 1 b 。) c 砀f 巧z 砀z 砀 2 6 变异算子 在遗传算法中使用变异算子主要有以下两个目的【1 】： 1 ) 改善遗传算法的局部搜索能力。遗传算法使用交叉算子已经从全局的角 度出发找到了一些较好的个体编码结构，它们以接近或有助于接近问题的最优 解。但仅使用交叉算子无法对搜索空间的细节进行局部搜索。这时若再使用变异 算子来调整个体编码串中的部分基因，就可以从局部的角度出发使个体更加逼近 9 西北人学硕上论文 最优解，从而提高了遗传算法的局部搜索能力。 2 ) 维持群体的多样性，防止出现早熟现象。变异算子用新的基因值替换原 有基因值，从而可以改变个体编码串的结构，维持群体的多样性，这样就有利于 防止出现早熟现象。 ( 1 ) 均匀变异【1 1 1 均匀变异操作是指分别用符合某一范围内均匀分布的随机数，以某一较小的 概率来替换个体编码串中各个基因座上的原有基因值。 均匀变异的具体操作过程是： 1 ) 依次指定个体编码串中的每个基因座为变异点。 2 ) 对每一个变异点，以变异概率从对应基因的取值范围内取一随机数来 替代原有基因值。 假设某一个体为x ；氆五而，若吒为变异点，取其值范围为 【u ：舻【厂急】，在对个体x 进行均匀变异操作后，可得到一个新的个体 x = 吼x ：西，其中变异点的新的基因值是：t = u 急+ ，：。一u ：；。) 式中， ，为【0 ，1 】范围内符合均匀概率分布的一个随机数。 均匀变异操作特别适合与遗传算法的初期运行阶段，它使得搜索点可以在整 个搜索空间内自由的移动，从而可以增加群体的多样性，使算法处理更多的模式。 ( 2 ) 非均匀变异【1 1 1 这种方法由j a n i l o w 和m i c h a l e w i c h 提出。它的设计目的是为了得到较高的 精确度而具有微调能力。对于给定的父代x ，如果它的元素被吒选中进行变异， 结果的后代是x 。= 瓴，五，) ，其中吱从下面两种可能的方案中随机选择： 函数o ，y ) 返回范围【0 ，) ，】中的一个值，当遗传代数f 增加时，该值越来越趋向于 0 。该特性导致算子在早期( f 很小) 均匀地搜索解空间，而到了晚期则在很小的 区域进行搜索。函数o ，y ) 的形式如下： 1 0 22 ) )吨 以 p o + 一 故& 暑 = 黾t 两北大学硕十论文 o ，y ) = y ，( 1 一) 6 ( 2 3 ) 其中r 是区间上的随机数，丁是最大遗传代数，6 是确定非均匀程度的参数。该 算法有可能产生不可行的后代。如果这种情况发生，可以减小随机数，的数值。 以上为遗传算法的基本操作算子及具体的实施过程。 2 7 前人所做的混合遗传算法 在2 0 世纪的最后1 0 年里，人们已经详细研究了遗传算法和局部搜索启发式 方法相结合从而解决优化问题中将局部优化作为其辅助成分。在混合算法中，每 一个新产生的后代在进入种群之前需要进行局部搜索使其移动到局部最优点上。 遗传搜索是进行种群的全局广度搜索；而局部搜索则是进行染色体中的局部深度 搜索。由于遗传算法和局部搜索方法的互补特性，混合方法通常比任何一种方法 的效果都好。 目前存在两种常见的遗传局部搜索形式。一种以b m a r c k i 觚【1 2 】进化为特 色，另一种以b a l d w i n 效应为特色【1 2 】。两种方法都采用了个体在整个生命过程 ( 一代) 中进行学习( 爬山) 这样的比喻说法。在l a m a r c k i 锄进化中，个体爬 山后被重新放回到种群中。而在b a l d w i n 效应中，个体的基因型保持不变，改变 的仅为其适应值。根据w h i t l e y ，g o r d o n 和m a t h i a s 通过一些测试问题获得经验， 在采用相同的局部搜索方法的前提下，存在k i l i l a r c k i a n 策略收敛到局部最优解 而b a l d w i n 搜索策略收敛到全局最优解的情况。然而在所有的测试问题中， b a l d w i n 策略均比h m a r c k i a n 要慢许多。 下面是爬山法的具体操作的步骤： 跏p 1 初始化种群，并进行编码，并计算个体适应度值的大小，进行排序； s t e p 2 进行轮赌盘选择操作，并保存几个最优解； s t e p 3 进行交叉算子操作，并更新种群中的个体； s t e p 4 进行变异操作，并更新种群中的个体； 鼬p 5 进行爬山法的局部搜索； s t e p 6 判断种群中的个体是否满足算法所要求的精度，若满足则停止，若不满 足则转s t e p 3 。 西北大学硕十论文 第三章三种新的混合遗传算法 3 1 结合非精确搜索条件的混合遗传算法( n h g a ) 3 1 1 算法的基本思想和原理 本算法的基本思想是将经典优化问题中的非精确搜索确定步长的方法与遗 传算法结合用于多峰值的复杂优化问题。由于简单遗传算法的局部搜索能力较 差，我们将非精确搜索应用于局部搜索，搜索方向采用牛顿方向或者共轭梯度方 向，对简单遗传算法进行改进，得到一种高效的、数值效果佳的混合遗传算法。 3 1 2 算法的主要操作算子 这里我们采用有别于传统的交叉变异算子，即在实数编码过程中常采用的算 术交叉以及高斯变异算子，同时在选择策略中使用的排序选择操作，并在种群进 化的过程中使用了杰出者保存策略。 1 ) 杰出者保留策略 在遗传算法的运算过程中，通过对个体进行交叉、变异等遗传操作而不断 地产生出新的个体。虽然随着群体的进化过程会产生出越来越多的优良个体，但 由于选择、交叉、变异等遗传操作的随机性，它们也有可能破坏掉当前群体中适 应度最好的个体。而这是不是我们所希望发生的，因为它降低群体的平均适应度， 并且对遗传算法的运行效率、收敛性都有不利的影响。所以，我们希望适应度最 好的个体要尽可能的保留到下一代群体中。为了达到这个目的，可以使用最优解 保存策略进化模型来进行优胜劣汰操作，即当前群体中适应度最高的个体不参与 交叉运算和变异运算，而是用它来替换掉本代群体中经过交叉、变异等遗传操作 后所产生的适应度最低的个体【1 】。 杰出者保留策略进化模型的具体操作过程是： 找出当前群体中适应度最高的几个个体，构成杰出者集合。 若当前群体中个体的适应度比杰出者集合中的个体的适应度函数值 高，则将其替换掉杰出者集合中适应度低的个体； 若当前群体中适应度函数值比杰出者集合中个体的适应度函数值低， 则将种群中适应度最差的个体替换掉。 西北大学硕一卜论文 而杰出者集合中的个体不参与种群个体的交叉、变异操作。 杰出者保存策略的实施可以保证所得到的最优个体不会被交叉变异操作所 破坏，它是遗传算法的收敛性的一个重要的保证条件。但同时这种策略也容易使 得某个局部最优个体不易被淘汰掉，反而很快的扩散，从而导致算法的全局搜索 能力不强。通常该方法一般要与其他一些选择操作方法配合使用才会有很好的效 果。 2 ) 算术交叉【1 4 1 1 1 5 】 算术交叉( a r i t h m e t i cc r o s s o v e r ) 是指由两个个体的线性组合运算而产生出 两个新的个体。为了能够进行表示个体线性组合运算，算术交叉的操作对象一般 是由浮点数编码所表示的个体。 假设在两个个体x ：、e 之间进行算术交叉，则交叉运算后所产生的两个新 的个体是： x ，1 = a x ：+ ( 1 一口) x j ( 3 1 ) l x ? 1 ；口e + ( 1 一口) 砟 式中，a 为一参数，它可以是一个常数，此时所进行的交叉运算称为均匀算 术交叉；它也可以是一个由进化代数所决定的变量，此时所进行的交叉运算称为 非均匀交叉。 算术交叉的主要操作过程是： 确定两个个体进行线性组合时的系数口。 依据( 3 1 ) 式生成两个新的个体。 3 ) 高斯变异【1 4 】【1 5 】 高斯变异这种方法起源于进化策略。【1 6 】【1 7 】一般在进化策略中的一个个体包 含两个元素o ，仃) ，其中第一个向量x 表示搜索空间中的一个点，而第二个向量盯 表示标准差。后代o ，仃) 由下式产生： 其中( 0 ，口) 是均值为0 ，标准差为仃的独立高斯随机数向量。 1 3 生 盯 ， m 斛 昌 暑 盯 两北大学硕：t 论文 4 ) 非精确搜索的判断条件 在经典优化里，非精确搜索与精确搜索是两类不同的步长选取方式，精确搜 索的步长在进行下一代迭代的过程中是确定的、唯一的，而非精确搜索的步长则 是不确定的、不唯一的，它的步长是一个取值范围，有一个区间范围。这个区间 范围的选取则是根据g o l d s t e i n 条件、w b l f e 条件、充分下降条件来判断得到的。 这三类条件是根据目标函数的函数值以及一阶导数条件来构造的形式如下：设 & 一吒畋，其中为步长因子，以为搜索方向。 这里搜索方向的以是牛顿方向 + 1 = & + 吼d i ( 3 3 ) 小测 4 ， 或者共轭梯度方向。 5 ) 共轭梯度方向的构造【1 8 】【1 9 】【驯 在经典优化里，共轭梯度法是一类典型的优化算法，它的局部搜索能力较强， 收敛性也很好，一般为二阶收敛的( 在适当的条件下) ，下面我们简单说明共轭 梯度方向是如何构造的，假设n 维函数，共轭梯度方向是一组搜索方向 既p ：，以，它们是共轭的，其中p 。为初始搜索方向最速下降方向，矩阵彳为 目标函数的h e s s i a n 矩阵，然而n p ：，见以及p 。它们是关于彳共轭的。其构造 方法如下：设r o 为初始点的梯度值 2 矗为第k 步迭代的步长因子 + ，；讫+ 仇第k + 1 步迭代 珞+ 。= 以+ 。- 6 为第k + 1 步迭代点的梯度值。由于经典优化里共轭梯度法是 针对目标函数为二次函数的优化问题的，这里彳为二次函数的h e s s i a n 矩阵或其 近似，6 为一次项的系数。但在本文提出的混合算法里，目标函数可能不是二次 函数，所以+ ，为第k + 1 步迭代点的梯度值。 1 4 西北人学硕上论文 轧= 籍= 霖构造第k + 1 个搜索方向的系数迭代公式 见+ 。= 一吃+ 反+ 。既第k + 1 个搜索方向迭代公式 按照上述迭代公式构造共轭的搜索方向得到： 小k 麓丸。2 吼= w 瓴) 展为一个参数 参数展的选择有三种情况2 1 j 【2 2 l ： 欣：反；粤 g t 一1 9 i 一1 脚；展；亟掣 n e w ：反。一亟掣 一1 反- 1 6 ) 叠岫j j o g 0 1 d s t e i n 准贝j 【1 8 j 【1 9 】【刎： f q t 、+ q 一们g ：s ksf b t + s k 、) sf q 0 + p g ：s k ， 其中o p 昙，瓯为目标函数的梯度 w r o l f e - p o w e l l 准则：若设伊 。) 一厂瓴+ a 畋) ，则( 1 ) 式转化成 妒( 口t ) s 伊( o ) + p a t 驴( o ) 9 0 。以仃g ；以 ( 3 1 0 ) 和( 3 1 1 ) 共同构成了w r o l f e p o w e u 准则。 充分下降条件准则： f b k + s o sf q 0 + p 盛s k 本算法采用以上三种判断准则来进行局部搜索。 3 1 3 算法描述 非精确搜索的混合遗传算法描述 ( 3 5 ) ( 3 6 ) ( 3 7 ) ( 3 8 ) ( 3 9 ) ( 3 1 0 ) ( 3 1 1 ) ( 3 1 2 ) 西北人学硕上论文 在描述开始前，先介绍一f 后面用到的参数及符号： 设种群规模为p 咿诬，种群中个体 五，z ：，x 胛觑) ，g ) 表示第k 代种群， 记种群进化代数的上限为g 。 跏p l 初始化种群，初始化参数口，c ( 0 力； s t e p 2 给出问题的十进制编码，计算适应度函数值，适应度函数取 砌哪= ，o ) ，并对种群的个体排序，将最好的6 个个体进行存储，记为杰出 者集合j ) ，存储最优个体的适应度函数值，记为k ，计算种群的平均适应值， 记为k ； s t e p 3 对种群进行轮盘赌选择，选择概率为见，见= 只f s “m 只f ； s t e p 4 算术交叉( a r i t h m e t i cc r o s s o v e r ) 设pc 为交叉概率，由选择算子选出pc _ ，l 对双亲，对每组双亲实施 算术交叉，设其中一组的染色体分别为彳= 口。口2 露m 和曰= 既，则由该 组双亲生成的个体记作c = q c 2 厶，q 一q + ( 1 一娩，其中为【0 ，1 】间均匀随 机数。更新种群中的个体，生成新的种群； s t e p 5 高斯变异( g a u s s i a nm u t a t i o n ) 高斯变异的变异概率以= o 1 ，生成随机数m r ，符合正态分布，当变异概 率小于随机数时，则个体进行更新x ；= x ；+ 胁，将所有个体变异生成新的种群。 采用高斯变异，在进化初期有利于预防早熟，后期则可获得较强的局部探优能力； s t e p 6 进行非精确的局部搜索，对个体采用充分下降条件进行判断，即 1 ，瓴+ p 仇) ，瓴) + c ( 1 一p ) w 也) 见，p = 去p ，或者利用g o l d s t e i n 条件 j 二 ，瓴) + ( 1 一p ) 吒w 瓴) 丁仇 o ，集合m 。= x ql 厂( x ) s ，+ 满足优( m 。) q 0 ， 即m ，的p 6 哪“p 测度大于0 ，其中q 为一常数且0 o ，有j 姆p ( d f ) = o 成立。其中 z = ，( z ) ，f 珊v x 叉丽辛，( ) ，( z ) ，厂f 定义3 称求解问题( 3 1 3 ) 的g 钳依概率收敛到0 。 下面引入几个引理： 引理1 种群丽重的每一个个体x ，经过赌盘被选择的概率p 苫卢 o 。 ( p 是一常数) 证明由 1 9 西北大学硕十论文 只：魁丛盟， 口却f ( 厂( 置) ) x t 兀陋，6 】，伍) 连续可知： 在区域q 2 口口f ，岛止， 口如( 厂( 五) ) 有最大值口d 印f 。，有最小值口d 印f 耐。 所以 一。：呈塑丛地滏一苫! 堕虹 o 爹口却f ( ，( 五”胁却x 。 口却f ( ，( 五”朋嬲倒m x 令窖粤；证毕。 ? m 口d 口p t 。? 引理2 集合 【l 谢乙互互( 夏丽) 】m 。) 一 乙耐【乙c i ( i 丽) m 。】) ，其中t 是选 择算子，瓦是交叉算子，乙是变异算子，瓦蜊是生成下一代的算子。 证明对于t ( i 两) ，不妨设墨，x ：，小x 是其中的个体，经 过乙i i ( 丽) 后，个体为x 。，x ：，x 。，x 口+ 1 ，x - ，进入m ，的个体不妨设为 x 。：x ：x 。：且有，( z ) s ，( 彰+ 。) ，o ；1 ，2 ，q 一1 ) 由m 。的定义可知： ，( x ；) 一，s ，f 一1 ，2 ，口，而且厂仁j + 。) s ，( z ) ，其啊2 鼋，f 一1 ，留 又由乙叫定义可知： 蹦张c 丽删，= f 拦麓爱： 而乙i ( i 两) 中的个，c 松。，x ：，瓦经过乙鲥作用后即 t 乙鲥陬i i c 丽，m 娜中个体为 未譬一乏茹：三 其中l 【x ：小，x 0 ) ，j = q + 1 ，m 两北大学硕上论文 所以t 五谢陬i i c 丽，m m = 主( 乏0 乏鬈：三， 从而命题得证。 然后我们给出算法收敛性的证明： 定理l 假设1 成立的前提下，该混合遗传算法依概率收敛。 证明在进化的第f 代，对种群x o ) 中的任意个体置依概率p 被选择和交叉 操作后变异操作，若进行的是共轭梯度的点变异，则变异的概率是p p 掣，若 进行的是随机点变异操作，则被变异的概率是p 笪书：型【1 一( 1 一己) 1 说明：初始化参数m ( 每一代种群的个数就是种群规模p 掣妇) ，( 中间种群 的个数) ，陟i 是集合的阶即中元素的个数，形是。到之间随机整数集) 用随机点变异对任意一个个体置进行操作后，将产生一个随机向量 亭= ( 缶，岛，色) r ，皇o = 1 ，2 ，1 ) 是独立的随机变量，且服从均匀u ；，包) ，对 e q 2 珥h ，包】，设变异后产生的新的个体为掣，则成立 尸( x ；m ) = r ( y 坳昌上m 似) _ - l o 矗r i = i 1 )i = i q ) 令i 鱼一= 仃，显然o ( 口( 1 设为经过局部搜索变异后进入m 。的概率。所以 i = i 1 ) 经过变异后新的个体进入膨，的概率大于 p 訾乓+ 只p 挚旷蹦b 而经过变异后新的个体进入第f 代的概率是 缸p 粤+ p 学【1 _ 蹦” 由引理2 知，对第f 代中任意个体置经过选择，交叉，变异形成下一代操作后进 2 1 西北人学硕上论文 入m 。的概率砭等于x ；经过选择，交叉，变异操作后进入m ，然后形成下一代的 概率。所以有 弘缸p 粤+ p 华【1 - ( 1 毗 苫等p 华岬一删 由引理1 知 耻等p 挚【1 - 蹦h 令叩。等卢盟岩盟【1 一( 1 一己) 1 显然。墨，7 1 ，因而对第f 代任意个体置经过 一代后没有进入m 。的概率s 1 一，7 仃因此， p t = f ：一f 、) s p ( 前f 代中经过变异后没有产生一个个体进入m 。】- ) s ( 1 一，7 仃y 所以 o s l i m p ( 皿 ) s l i m ( 1 一野仃) = 0 故l i m p ( 口 ) 一o 由定义3 知该g 钳是依概率收敛的。 从定理1 的证明过程中可以看到，在本文提出的混合遗传算法是【2 6 】中的算法框 架中的一种，得出结论本文中的混合遗传算法是依概率收敛的1 3 1 5 小结 本算法是将经典优化中的非精确局部搜索的搜索方法