（运筹学与控制论专业论文）求解几类复杂优化问题的进化算法.pdf

摘要 摘要 作为一种重要的优化算法，进化算法是借鉴生物进化机制形成的一种随机搜索 算法。因不需目标函数的可微信息，又有隐并行性，故用于求解一些传统优化算 法难解决的问题。旅行商问题( t s p ) 正是经典的n p h a r d 组合优化问题之一，许多 实际问题经过简化均可建模为t s p ，因此，具有全局收敛性的遗传算法成为人们解 决t s p 的主要方法之一。本文首先提出了一个新的求解t s p 的进化算法，设计了 一种简单的整数编码方式，使得路径与某整数一一对应，优点是每个个体都可行， 运算量少，便于设计遗传算子；其次，量子遗传算法( q i o a ) 利用其高效的搜索能 力和较好维持种群多样性的能力被运用到许多难求解的优化问题，因此，深入研究 q i g a ：t 秘, 要的。本文通过引入新的可控旋转门操作及终止条件来进一步改善o i o a 的性能。改进的q i g a 不仅可以有效地跳出局部最优解，而且保持了解的质量与运 行时间的一种平衡；再次，借助前面的工作，提出了一种求解t s p 的新的q i ( 3 a ， 利用几率幅值编码，使得种群规模只有常规遗传算法的1 l o 1 s ，并适时引入了 从边寻优的两阶段局部搜索，大大加快了算法的收敛速度；最后，不仅从理论上 证明各新算法以概率1 收敛。而且数值试验也表明了它们的有效性。 关键词：遗传算法旅行商问题( t s p )全局优化量子遗传算法( o lq a ) a b s t r a c t a b s t r a c t a so n ek i n do ft h em o s t i m p o r t a n to p t i m i z a t i o na l g o r i t h m s ，e v o l u t i o n a r y a l g o r i t h m sa r er a n d o m s e a r c ha l g o r i t h m st h a ta r ei n s p i r e db yt h e p r i n c i p l e so f t h en a t u r e e v o l u t i o n w i t h o u tr e q u i r i n gt h ed i f f e r e n t i a b i l i t yo ft h ef u n c t i o n sa n dw i t h i m p l i c i t p a r a l l e l i s m ，e v o l u t i o n a r ya l g o r i t h m sa r eo r e nu s e dt os o l v es o m ed i f f i c u l tp r o b l e m s w h i c ht h ec l a s s i c a la l g o r i t h m sc a r l t t h et s pi sac l a s so fn p - h a r dc o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s m a n y p r a c t i c a lp r o b l e m s c a i lb et r a n s f o r m e di n t ot h et s p s oe v o l u t i o n a r ya l g o r i t h m sw i t ht h e g l o b a lc o n v e r g e n c eb e c o m e o n eo ft h em o s ti m p o r t a n t a l g o r i t h m st os o l v et h et s p i n t h i sp a p e r , an o v e lh y b r i dg l o b a l l yc o n v e r g e n te v o l u t i o n a r ya l g o r i t h mf o rt h et s pi s p r o p o s e d a n e wa n ds i m p l ei n t e g e r - e n c o d i n gs c h e m ei sd e s i g n e d , a n de a c hi n t e g e ri s c o r r e s p o n d i n gt oau n i q u ev a l i dt o u r , a n dv i c ev e r s a t h ea d v a n t a g e so ft h ep r o p o s e d a l g o r i t h ma r et h a ti ta l w a y sg e n e r a t e sf e a s i b l es o l u t i o n ，u s e sl e s sc o m p u t a t i o n ，a n di s e a s yt od e s i g ng e n e t i co p e r a t o r s q u a n t u m i n s p i r e dg e n e t i ca l g o r i t h m ( q i g a ) h a sb e e ns u c c e s s f u l l ya p p l i e dt o s o m ed i f f i c u l to p t i m i z a t i o np r o b l e m sd u et oi t se f f e c t i v es e a r c ha b i l i t y , a n da b i l i t yo f k e e p i n gp r o p e rp o p u l a t i o nd i v e r s i t y i ti sn e c e s s a r yt os t u d yt h eq i g a t h et r a d i t i o n a l q i g a i si m p r o v e db y i n t r o d u c i n gan e w c o n t r o l l a b l er o t a t i o ng a t ea n dan e wt e r m i n a t e c r i t e r i o nf o rg l o b a lo p t i m i z a t i o np r o b l e m s t h ei m p r o v e dq i g ac a ne f f e c t i v e l ye s c a p e f r o mt h el o c a lo p a m a ls o l u t i o n sa n dk e 印t h eb a l a n c eb e t w e e nt h es o l u t i o nq u a l i t ya n d r u n n i n gt i m e ；m o r e o v e r , b a s e do nt h i s ，an e wq i g a f o rt h et s pi sp r o p o s e d d u et o a d o p t i n gp a i r so f a m p l i t u d e s t oe n c o d e ，t h e p o p u l a t i o n s i z en e e d e di so n l y l 1 0 1 s t h a t o fs t a n d a r dg e n e t i ca l g o r i t h m a tt h es a m et i m e ，t h et w o p h a s el o c a ls e a r c hf o re d g e e v o l v i n gi si n t e g r a t e di n t oq i g a t oa c c e l e r a t ei t sc o n v e r g e n t s p e e d m o r e o v e r , t h eg l o b a lc o n v e r g e n c eo f t h et w op r o p o s e dn e w a l g o r i t h m si sa n a l y z e d , a n dn u m e r i c a le x p e r i m e n t sa r em a d e t h er e s u l t ss h o wt h ee f f e c t i v e n e s so fb o t h p r o p o s e da l g o r i t h m s k e y w o r d s ：g e n e t i ca l g o r i t h m t r a v e l i n g s a l e , m a np r o b l e m f r s r ) g l o b a l o p t i m i z a t i o nq u a n t u m - i n s p i r e d g e n e t i c a l g o r i t h m ( q i g a ) 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作过的同志对本研究 所做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担 本人签名：燃 一切相关责任。 日期：曼! ! ：! ：! ! 关于论文使用授权的声明 本人完全了解西安电子科技大学商关保留和使用学位论文的规定，即：研究 生在校攻读学位期间的学位论文工作的知识产权单位属西安电子科技大学。本人 保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技 大学。学校有权保留和送交论文的复印件，允许查阅和借阅论文；学校可以公布 论文中的全部或部分内容，可以允许采用影印、缩印和其他复制手段保存论文。( 保 密的论文在解密后遵守此规定) 本人签名 导师签名 日期：苎竖! ：! ! 日期：碰：f ! f & 第一章绪论 第一章绪论 1 1 引言 遗传算法【1 - 1 4 ( g e n e t i ca l g o r i t h m ，g a ) 是一门研究如何求解各类优化问题的学 科。最早由美国密歇根大学教授j o l n l h o l l a n d 及其学生提出的。由于它不受其搜索 空间的限制条件( 如：可行域的凸性、目标函数的可微性等) 约束，所以常用其求解 一些n p ，h a r d 问题和多目标决策等这些传统方法难求解的问题。 t r a v e l i n gs a l e s m a np r o b l e m 仃s p ) 是一个古老的问题，它在许多领域都要重要 的应用。诸如：印制电路板的钻孔路线方案、连锁店的货物配送路线等，t s p 模 型已经渗入交通运输、经济管理、系统控制、军事科学等领域。然而，由于其是 n p 困难的，长期以来，还没有十分有效的算法，尤其是对大规模的问题更是如此。 因此，对研究此问题的有效算法不仅是有重要的理论意义，而且具有重要的应用 价值。 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全 局优化概率搜索算法，主要依据依达尔文的自然选择与孟德尔的遗传变异理论。 生物进化是通过繁殖、变异、竞争和选择这四种基本形式来实现的。因此，作为 宏观意义下的仿生算法，它的本质特征是以群体的方法进行自适应搜索，并且充 分利用交叉、变异、选择等运算策略，有效地避免局部最优解，降低求解目标函 数性能的限制，减少了人机交换的依赖。正是它具有独特优势，因此，是类可 用于复杂系统优化计算的鲁棒搜索算法，广泛应用于许多领域仁8 ，9 ，1 5 1 ，但仍有一些 亟待研究和改进的地方，如：其理论不完善( 参数的设定、非概率收敛性证明等) ， 另外，其收敛速度慢、早熟收敛也是待攻克的难题。 本文将研究和设计有效的遗传算法求解两类复杂的优化问题，即t s p 和单目 标全局优化问题。 1 2 遗传算法简述 辩证唯物主义认为世界是统一的不可分割的整体，内部事物之闯是相互促进 的。因此，随着社会的进步，人们对大规模优化问题求解的需求越来越追切，各 种优化方法层出不穷，考虑生物进化与问题优化的共性，进化算法便应运而生。 进化算法主要包括四个分支，分别是：遗传算法f 切( g e n e t i ca l g o r i t h m ，g 柚、进化 求解几类复杂优化闷题的进化算法 策略【1 8 1 ( e v o l u t i o ns t r a t e g y ，e s ) 、进化规划 1 9 ( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 、遗传 规划2 0 。”( g e n e t i cp r o g r a m m i n g ，g p ) 。作为重要分支的遗传算法起源于6 0 年代对自 然和人工自适应系统的研究：7 0 年代d ej o n g 基于遗传算法的思想在计算机上进 行了大量的纯数值函数优化计算试验；在一系列研究工作的基础上，8 0 年代由 g o l d b e r g 进行归纳总结，形成了如今使用的基本遗传算法。 1 2 1 遣传算法基本概念及遗传算子介绍 通常我们假定要讨论的问题模型为 嘴， ( 1 _ 1 ) 其中f ( x ) 是目标函数，q 为问题的可行域。( 求最大问题也可以转化成求最小问题) 遗传算法首先选取一定数目解经过编码( e n c o d e ) 映射为相应数目( 称为种群规 模) 的个体( 称为个体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 ) ，种 群中每个个体又是由长度为，( 称为串长) 的基因( g e n e ) 组成，种群经过杂交 ( c r o s s o v e r ) 、变异( m u t a t e ) 、依据一定的适应度函数( f i t n e s sf u n c t i o n ) 选择( s e l e c t ) ， 再反复进化，每一次进化前的个体称为父代( p a r e n t ) ，相应父代进化后的个体称为 子代( o f f s p r i n g ) ，最终得到最优解，再把这个具有基因型( 0 髓哟，p e ) 最优解经译码 ( d e c o d e ) 映射转化为解空间的表现性( p h e n o t y p e ) 的解的形式。 另外，再有一些常用的概念： 定义1 1 通配符在一个由空间 0 , 1 ，) 7 表示所有的字符串中，字符称为通配 符。它既可以表示0 也可以表示1 ，为不确定字符；而o ，l 为确定字符。 定义1 2 模式( s c h e m a ) 一个由空间 o 1 。中的字符构成的字符串成为一个模 式，记为日。 融：芸：高掣n 。 定义1 3 模式阶( s c h e m ao r d e r ) 模式中确定字符的个数称为模式阶，记为 d ( 日) 。 定义1 4 定义距模式中第一个确定字符( 从左边数起) 的位置到最后一个确 定字符的位置阅的距离为定义距，记为烈日) 。 1 2 2 遗传算法各操作介绍 遗传算法在整个进化过程中的遗传操作是随机性的，但它所呈现出的特性并 不是完全随机搜索，它能有效地利用历史信息来推测下一代期望性能有所提高的 第一章绪论 寻优点集，这样反复进化，最后收敛到一个最优解。因此，一个完整基本的遗传 算法主要由以下几部分构成：针对问题怎样编码；初始种群的适当选取及 种群规模的设定；适应度函数的设计；遗传操作的设计；运行参数的设 定( 如：杂交概率p c 、变异概率p m 、终止算法的参数等) ；算法的终止条件8 1 。 1 、遗传编码 编码的主要作用是：把所求问题空间q 中的参数或解转化为遗传算法能操作 空间的染色体，这个过程为编码。编码是遗传算法实施的基础，只有把实际问题 的解转化为遗传空阊的基因型串结构数据，遗传算法才可以运算。其相反过程称 为译码。 通常编码规则如下p j ： 1 ) 完备性( c o m p l e t e n e s s ) 问题空间中的所有点都可对应为编码后空间的点。 2 ) 健全性( s o u n d n e s s ) g a 编码之后空间的所有染色体都能对应问题空间中的 菜一个点。 3 ) 非冗余性( n 0 n r e d u n d a n c y ) 编码后空间中的点与原问题空间的点是一一对 应的。 4 ) 符合积木块规则：应使用易产生与所求问题相关的低阶、短定义距模式的 编码方案。 5 ) 最小字符集编码规则：使问题得到自然表示所需的最小编码字符集的编码 方式。 目前常用的编码方式有：二进制编码，这种编码最基本，易于操作；g r a y 编 码，改进了二进制编码不能有效地反应h a m m i n g 距离与对应个体之间的关系：实 数编码【2 2 1 ，便于在解空闯的表现型上直接操作i 有序串编码f 3 9 ，拍埘1 ，多用于处 理组合优化问题；还有结构式编码；自适应编码1 3 , 2 8 , 2 9 1 ；等等。 当然，对具体问题必须把解空间、遗传操作、编码规则等统一考虑，才可以 得出最大发挥遗传算法作用的编码方式。 2 、初始种群的选取及种群规模的设定 根据模式定理，种群规模对遗传算法的性能影响很大。若群体规模为以，则遗 传算子可以从这一个个体中生成o c n 3 ) 个模式，并在此基础上形成更优化模块，直 到找到最优解。种群规模越大，种群的多样性越好，算法越容易跳出局部最优。 但随着种群规模的增大，计算量增大；反之，算法易产生早熟。而种群的分布情 况直接影响算法的收敛速度，如果初始种群选在最优解附近，会较快求得最优解， 反之，则会增加搜索时间。因此，合理设定一个种群规模及选取种群的方案对算 法的运行性能具有基础性的决定作用。 通常选取的规则是： 1 ) 大致估计整个解空间的分布情况，然后在此空间均匀选择初始种群中的个 求解几类复杂优化问题的进化算法 体。 2 ) 随机选择一些个体然后在可行域内找好一些的个体加入种群，不断重复， 直到达到种群规模。 种群规模的选取一般是问题越难，种群规模越大( 常考虑机器速度和人的忍 受力) ，利用已有相关问题的信息尽量减少的值，通常2 0 n 2 0 0 。 3 、适应度函数的设计 判断个体对环境的适应程度叫适应度( f i t n e s s ) ，适应度函数就是个体的生存环 境。在进化中适应值是群体中个体生存机会选择的唯一指标，适应度大的个体遗 传到下一代的概率大些，反之会在生存空间中被淘汰。 一般情况下适应度函数要依据编码设定，具体反映对求解的实际问题与最优解 接近情况，通常适应值非负。 然而，在进化初期，为避免早熟，我们希望缩小个体之间的差异；到了后期， 为了加快收敛，往往又加大个体间的差异。因此，为了解决这些问题，我们需要 将适应度函数尺度化。常用的尺度变换有如下三种： 1 ) 线性尺度化 设( r = 口f ( x ) + 6 ，其中口，b 为适当的常数，并且满足 i ，( x ) 0 i i ，( x ) 与，( x ) 平均适应度相同 i i i m a x 厂( x ) = c a v e r a g e ( f ( x ) ) ，c 【1 2 ，2 】 2 ) 幂函数法 设f ( x ) = 。 口 0 3 ) 指数法 设，( x ) = e x p ( , a t ，( 曲)多 0 例如：设f ( a 1 ) = 2 0 0 ，f ( a 2 ) ；8 ，f ( a 3 ) = 7 ，f ( a 。) = 4 ，令，( x ) = e o ”m ，则得到 ， ) = 2 7 1 8 ，f ( a 2 ) = 1 0 4 0 ，f ( a ，) = 1 0 3 6 ，f ( a ) = 1 0 2 0 ，显然，个体间的差 异变小。 4 、遗传算子的设定 遗传算法利用遗传算子产生下一代群体来实现群体进化，算子的设计是遗传策 略的主要组成部分，也是调整和控制进化过程的基本工具。主要包括：杂交、变 异、选择( 或称复制r e p r o d u c t i o n ) 。 1 ) 选择算子 不同的选择策略会导致不同的选择压力。较大的选择压力使得最优个体有较 高的复制数目从而使得算法收敛速度较快，但易于出现早熟；而较小的选择压 力能保持种群的多样性，增大了算法收敛到全局最优的概率，但是算法的收敛速 度较慢。所以，选择算子的设定要考虑具体问题和以往经验来选择合适的选择算 第一章绪论 子。 常用的选择算子有： 适应值比例选择口o j ，是最基本的选择方法( 利用轮盘赌方式实现) 、 b o l t z m a r m 选择 3 t , 3 2 ，利用退火温度的函数动态调整选择压力、保留最佳个体选择 【3 0 】( e t i t i s te l e c t i o n ) ，是群体收敛到优化问题最优解的一种基本保障、期望值选择 吲( e x p e c t e d v a l u es e l e c t i o n ) ，这种选择方法能降低一些选择误差，但操作不方便、 排序选择【3 ，2 8 ，3 4 ，3 5 ( r a n k - b a s e ds e l e c t i o n ) ，在实际计算中常采用适合动态调整选择概 率，适时改变群体选择压力、联赛选择【3 1 , 3 2 , 2 6 l ( t o u r n a m e ms e l e c t i o n ) 。能方便地将 进化效果与群体选择压力联系起来、还有排挤法( c r o w i n g ) 等。 2 ) 杂交算子 杂交算子的主要作用是增加种群的多样性，使得算法的搜索范围尽量扩散到 整个解空间。杂交操作是基因重组的过程，要把好的基因传给下一代的同时，能 生成更复杂基因结构的新个体。杂交运算是遗传算法区别于其他进化算法的重要 特征。 杂交的过程是：先随机选择要杂交的一对个体，再随机选交叉的位置( 一个或 多个) ，最后以一定的杂交概率弘实施杂交操作。所以，杂交主要考虑两方面： 一方面是如何确定交叉点的位置，另一方面是怎样进行部分基因交换。 常用的杂交算子有： 单点杂交 3 0 , 3 7 ( o n e p o i n tc r o s s o v e r ) ，只有一个交叉点，优点是比较容易保 持个体性状，但不利于长距模式的重组、多点杂交【3 0 ( m u l t i p o i n tc r o s s o v e r ) ( 两点 杂交是其一种特例) ，很难有效保持好的模式，影响算法性能，一般不建议选过多 的杂交点、均匀杂交t 3 s l ( u h i f o r mc r o s s o v e r ) ，均匀杂交优于多点杂交，任意基因位 的重要基因在均匀交叉作用下均可以重组，并遗传给下一代个体。另外，针对不 同的编码方式，也有不同的杂交算子，如：m e s s y g a 中的交叉算子【3 9 】、基于树形 结构表示的染色体位串的交叉f 2 ”、t s p 中的部分映射杂交【柏】口a r t i a l l ym a p p e d c m s s o v e r , p m x ) 、顺序杂交f 4 1 ( o r d e rc m s s o v e r , o x ) 、边重组交叉 4 2 ( e d g e r e c o m b i n a t i o nc r o s s o v e r ) ( 这些将在下一节内容介绍) 等。 3 ) 变异算子 变异的主要作用是方面改善遗传算子的局部搜索能力；另一方面维持群体 的多样性。相对于交叉算子，变异算子的作用是辅助的，局部的搜索能力。因此， 只有二者的相互配合，才能共同完成对搜索空间的全局搜索和局部搜索，从而使 得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。 变异的过程是：先以变异概率p m 为基础计算个体发生变异的概率来选择参加 变异个体，接下来计算变异个体上基因变异的概率选择发生变化的基因，这样就 使得要变异个体的某些基因位上的基因值用该基因位的其它等位基因来替换形成 6求解几类复杂优化问题的进化算法 新个体。所以，变异主要考虑两个方面：一是如何确定变异点的位置；二是如何 进行基因值替换。 常用的变异算子有： 位点变异【3 0 l ( s i m p l em u t a t i o n ) ，由于只是个别基因位上的值改变，所阱其 发挥的作用b 较慢，效果不明显、均匀变异【4 3 1 ( u n i f o r mm u t a t i o n ) ，比较适合用于 算法初期，由于可以在整个搜索空间中自由移动，因而有更多的模式、非均匀变 异【4 3 + ( n o n - u r t i f o r mm u t a t i o n ) ，可使算法在初期进行均匀随机搜索，后期进行局部 搜索，它产生的新基因值比均匀变异更接近原有基因值，故适合集中在某一区域 集中搜索、高斯变异 2 2 1 ( g a u s s i a nm u t a t i o n ) ，是改变遗传算法对重点搜索区域的局 部搜索性能的另种变异操作方法、还有对换变异、插入变异等。 5 、运行参数的设定 遗传算法中的参数设定对算法的效果影响很大，有效的参数选取不仅能使算 法快速收敛，而且使算法全局收敛。所以，如何在算法初期选取各参数一直是人 们讨论的重点。 通常的参数包括；染色体长度j 、种群规模、交叉概率w 、变异概率p m 等 等。虽然人们提出了一些改进方法，如：模糊控制参数、模拟退火方法、基于均 匀设计的参数设定等，但还要结合具体问题来设定。所以，对参数设计的研究有 待于遗传算法的发展。 6 、算法的终止条件 遗传算法的终止条件通常是用来判断群体已进化成熟不再需要进化的条件。常 用的终止条件为：最大代数，这需要一个预先估计、连续几代个体平均适应度的 差异小于某一个极小的阈值、群体中所有个体适应度的方差小于某一个极小的阈 值等。 综上所述，可以看出，g a 的运行性能与很多因素有关，要想设计一个好的算 法需要考虑求解效率和求解质量这两个主要方面。因此，要设计一个好的g a ，除 了兼顾这两方面外，还要根据问题需要来具体设计算子，充分发挥个体的进化能 力和g a 的搜索能力。 1 2 3 遗传算法的求解步骤 遗传算法以编码空间代替问题的参数空间，以适应度函数为评价依据，以编 码群体为进化基础，以对群体中个体位串的遗传操作实现选择和遗传机制，不断 进化，逐渐接近最优解，最终达到求解问题目的，从而建立起个迭代过程。 具体步骤如t 1 2 , 3 ；8 州耶l ： 第一章绪论 s t e p l 编码、初始化。随机生成初始种群p ( o ) ：设置最大进化代数，一；种群 规模；初始代数扛0 ； s t e p 2 个体评价。用所构造的适应度函数来计算种群p ( ，) 中每个个体的适应 度； s t e p 3 交叉操作。把交叉算子作用于种群； s t e p 4 变异操作。把变异算子作用于种群； s t e p 5 选择操作。把选择算子作用于种群； s t e p 6 终止判断。若t f 。，n t = t + l ，转s t e p 2 否则，把种群p ( t ) 中的最 好个体( 若问题求最大则是适应度最大的个体：反之，求适应度最小的个体) 译码， 然后作为最优解输出，结束。 上述求解步骤的具体流程图为： 罕雯k 阿- n 审套固 鏖一 l 凳i 审 悭j 匮黼粤 ，l 、 1 蠢僵酥如一 蔓卜_ j 圈1 遗传算法的运算流程图 对于通常的问题，若是执行遗传算法的基本步骤就可以按此图进行。当然， 若是再引入逆转算子、局部搜索算子等其它算予时，只要将这些新引入的算子加 在算法的流程图中要执行的位置就可以修改为要用的修改算法流程图。 1 2 4 遗传算法的基本理论 虽然g a 计算过程和形式简单，但其运行机理非常复杂。随着g a 在复杂优化 问题求解和实际过程设计中的应用，人们对g a 的理论基础给予了越来越多的关 注。主要包括以下方面： 1 ) 用什么样的模式描述g a ，怎样预测适应度的变化，特定g a 的群体促进 进化机制。 2 ) 判别g a 性能的优劣的标准怎样建立。 3 ) g a 与相对应问题的适合程度。 求解几类复杂优化问题的进化算法 4 ) g a 哪些方面优于其它启发式搜索方法。 下面主要介绍遗传算法的初期理论及其收敛性分析。 1 、遗传算法初期理论研究o 】 1 ) 模式( s c h e m a ) 理论 模式定理【 1 是遗传算法的基本原理，j ，h o u a n d 用其与隐并行性原理来解释g a 的作用【1 7 l ，从进化动力学的角度提供了能较好地解释遗传算法机理的一种数学工 具，同时也是编码策略、遗传策略等分析的基础。 定义1 5 设x = ，”= ( 曰) ”为g a 群体状态空间，h 是任一模式， p ( t ) = x 1 ( f ) ，工：( r ) ，x 。( ，) ) e z 表示g a 在第t 代时的群体，厂：i r 。为适应度函 数，则称 f ( h , t ) 2 赢，。h z n p f “) ( x ) ( 1 - 2 ) 为模式的平均适应值，这里l h n p ( f ) i 表示集合h n p ( t ) 中元素，即p ( f ) 中含有日 中元素的个体，称，( f ) = 厂0 ) 为p ( ，) 的平均适应值。 定理1 1 模式定理( s c h e m at h e o r e m ) 设g a 的杂交和变异概率分别即和 p m ，模式h 的定义距为占( 疗) ，阶为o ( h ) ，第t + l 代种群含有日元素的个数期望 值记为e 0 日n p ( r + 1 ) 口，则 e i h n p ( t + 1 ) 呤i h n p i 骂铲 i - p c 普_ 0 ( 砂p m ( 1 3 ) 该定理表明重要基因的发现过程，说明那些低阶、短定义距、超过群体平均 适应度的模式生存的数量将随迭代次数的增加以指数级增长。说明此模式表示个 体在下一代的生存能力强。是种群进化方向。 2 ) 积木块假设( b u i l d i n gb l o c k ) 积木块假设是指个体的基因块通过选择、交叉、变异等遗传算子的作用，能 够相互拼接在一起，形成适应度更高的个体编码串。 积木块假设说明了用遗传算法求解各类问题的基本思想，即通过基因块之间 的相互拼接能够产生出问题更好的解。基于模式定理和积木块假设，就使得我们 能够在很多应用问题中广泛地使用遗传算法的思想。 3 ) 关于遗传算法的欺骗问题【4 6 4 7 ( g a d e c e p t i v ep r o b l e m ) 所谓骗问题是指在给定的一些带“迷惑”性质的初始条件，使遗传算法偏离 全局最优解，这样的问题称为骗问题。 通常骗问题不满足积木块假设，属于“g a 难”，往往包含孤立最优点，很难 通过遗传算子操作达到最优解。研究结论表明，一阶模式不可能存在骗闯题，所 以，二阶模式是骗问题的最低模式。 4 ) 隐含并行性口j 7 j 8 1 0 m p l i c i tp a r a l l e l i s m ) 第一章绪论 并行性是遗传算法的最大特点之一。因为，在遗传算法的运行过程中，每代 都处理了| v 个个体，但由于一个个体编码串中隐含有多种不同的模式，所以算法 实质上却是处理了更多的模式。 一般，种群规模为的群体可能隐含2 。n 2 。种不同的模式。对不存在骗问 题的优化问题，g a 可以正确处理所有模式的竞争，并按模式定理采样，多个竞争 模式的优胜者的确定位结构一致，再按积木块假设不断发现优秀个体，最终，g a 能够正确收敛到全局最优解。所以，遗传算法的隐并行性可以使算法快速搜索出 运行较好的模式。 近年来，r a d e l i f f e 把模式分析一般化，提出了完整的傅立叶分析理论1 4 1 。采 用w a l s h 变换来证明积木块假设成立。 2 、遗传算法的收敛性分析 对于经典遗传算法己证明捌其收敛于最优解的概率小于1 ；使用精英保留策 略的经典遗传算法是以概率1 收敛到最优解。但是，到目前为止，仍没有一套准确、 完整的解释遗传算法的理论。存在的证明都是概率证明，t h o m a sb j t c k 已证明 1 1 若是一遗传算法以概率l 收敛必须满足以下两个条件： 对v x ，x 2 q ，岛是由而可达( 可达是指种群中某个个体经过遗传操作变为 种群中另一个个体的概率大于0 ) 的； ( p ( r ) 是单调的，即对v f 有 m a x f ( x ( t ) ) ：x o ) p ( f ) ) m a x ( f ( x ( t4 - 1 ) ) ：x ( t + 1 ) p ( t + 1 ) ) ( 1 - 4 ) 则该进化算法是以概率1 收敛到全局最优解x ，即 p r o b l i m 工，( ，) ) = 1 1 - 5 ) f 所以，遗传算法的概率收敛证明根据不同模型可分为以下凡类： 1 ) 常用的马氏链模型l l l 】：该模型适用于二进制编码及一些特殊的非二进制编 码的遗传算法收敛性分析。由于算法中的群体无后效性，并且各代群体之间的转 换概率与时间的起点无关，因此，主要利用马氏链状态转移矩阵的性质分析遗传 算法的极限行为。后来，又把其推广为广义有限群体模型i s l l 。 2 ) 利用泛函知识的v o s e 模型 1 1 , 1 4 ：该模型适用于简单遗传算法，不适台处理 遗传算子概率随时间变化情形。由于o a 的求解迭代过程是一种随机压缩映射， 可以把g a 求解的迭代过程可看作是由解空间到解空阊的映射，因此，利用两个 矩阵算子分别刻画比例选择与组合算子( 杂交、变异的组合) ，通过研究这两个算子 不动点的存在性与稳定性来精确刻画遗传算法的渐进行为。 3 ) 公理化模型 1 2 1 ：既可用于分析时齐又可分析非时齐遗传算法。主要通过公 理化描述遗传算法的选择算子与重组算子，并利用所引进的参量来分析遗传算法 的收敛性。 4 ) 连续( 积分算子) 模型【1 2 】：该模型适用于实数编码的连续变量遗传算法的收 0求解几类复杂优化问题的进化算法 敛性分析。但是，这个模型的框架与方法均不完善，因此，要推导出一个准确描 述连续遗传算法的动态行为的收敛结果仍需要很长的过程。 遗传算法的收敛性一直是理论研究的一个主要方面，通过收敛性研究不仅增 强算法的可信度，也为进一步构造合理高效的遗传算法提供了理论依据。 1 2 5 遗传算法的特点 虽然人们还未完全揭开遗传进化的奥秘，但遗传算法广泛高效地应用已日益引 起人们的关注，现总结其主要特点如下： i ) 遗传算法的操作对象是一组可行解，有利于算法跳出局部优，特别当采用 有效保证群体多样性的措砸时，进化算法可以有效协调局部搜索与全局搜索之间 的关系，使得到全局最优解的概率大大提高。 2 ) 遗传算法基于目标函数的取值信息，而无需梯度等高阶信息，因而适用于 大规模、高度非线性的不连续多峰函数的优化以及无解析表达式的目标函数的优 化，具有很强的通用性。 3 ) 遗传算法具有显著的隐并行性，虽然在每一代只对有限个体进行操作，但 处理的信息为群体规模的高次方。 4 ) 遗传算法操作形式简单、明了，不仅便于与其它方法结合，而且非常适合 于大规模并行机运算。 5 ) 遗传算法具有很强的鲁棒性( r o b u s t n e s s ) ，即使存在噪音的情况下，对同一 问题的进化算法在多次求解中得到的结果是相似的。 1 2 6 遗传算法的改进及应用 1 、遗传算法的改进 为了更好地发挥遗传算法的作用，众多学者从各方面对算法进行深入研究和 讨论，目前的改进策略大致可以分为以下两方面； 1 ) 改进遗传算法的各组成部分。如：设计新的编码方式、动态的、自适应的 参数操作、新奇的遗传操作等，来进一步改善算法的 生能( 如：收敛速度慢、早熟、 易陷入局部最优解等) 【5 2 5 5 1 0 2 1 0 4 l 。 2 ) 由于遗传算法的操作简单，较容易与其它方法结合，实验研究表明这种改 进相对是比较有效的，如：为克服早熟o l o v e r 【5 6 l 等提出与禁忌搜索f i 曲us e a r c h ) 结合、p o t h s i s 6 提出基于迁移和人工选择的遗传算法；为解决局部优的问题，遗传 算法分别与模糊集( f u z z ys e t ) 、与混沌( c h a o s ) 结合、与单纯形、与爬山法、神经阿 第一章绪论 络、正交设计、免疫等结合来不断优化算法。 在问题越来越复杂化的今天，优化方法也应与时俱进，只有通过不同的方式 来对算法的结构、参数、操作不断改进和提高，才能设计高效的遗传算法，满足 现代社会的需要。 2 、遗传算法的应用 尽管遗传算法理论不完善，可是却从其提出之日起，得到人们的广泛应用， 这正是因为它具有处理问题的通用框架，而且不依赖问题的具体领域，对问题的 种类有很强的鲁棒性。 遗传算法主要应用于函数优化，如一些非线性、多模型、多目标的函数优化 问题；组合优化，如解t s p 、背包问题、图形分割、装箱问题、图的着色等；生 产调度问题，如j o b - s h o p 、f l o w - s h o p 等问题：机器学习，用遗传算法处理分类器； 图象处理，如对图象的识别、提取、恢复的解决；机器人学习，如机器人路径规 划、细胞机器人的结构优化和行为协调等方面的研究和应用；人工生命，基于遗 传算法的进化模型是研究人工生命现象的重要基础理论：自动控制，在自控领域 有许多优化问题，如模糊控制器的优化设计、参数辨识、模糊控制规则学习都需 优化方法来解决，遗传算法在这些领域显示了突出的作用。 1 3t s p 的研究概况及现状 1 3 ，1t s p 的数学模型与描述 l 、t s p 的描述 旅行商这个n p - h a r d 问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 可描述为：己知各 城市之间距离的 个城市，现一旅行商从某个城市出发访问每个城市一次且仅一次 的，最后回到出发的城市，怎样安排访问路线才使其所走路径最短? 也就是说，假设有一个图g = ( 矿，e ) ，其中v 是顶点集，e 是边集，设d = ( d 。) 是由顶点i 和顶点，之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过 所有顶点且每个顶点只通过一次的具有最短路的哈密尔顿回路( - i a m i l t o n i a n c i r c u i t ) 。 定义1 6 对于某个问题不存在求解它的多项式界算法，这样的问题称为 n p - h a r d 问题。 定义1 7 求解某问题算法的复杂性是关于该问题输入规模的一个多项式的上 界，这个界称为算法复杂性的多项式界。 定义1 8 包含图g 中每个顶点只有一次的回路称为哈密尔顿圈( 回路) 。 求解几类复杂优化问题的进化算法 2 、t s p 的数学模型 若对于城市矿= v 1v 2 ，k 的一个访闯顺序为丁= ( ，t 2 ，乙) ，其中 r ，z ( i = 1 n ) ，且记f 槲= r 1 ，则t s p 的数学模型为 嘞孙- ( 1 6 ) 其中q 为这t 1 个城市不重复排列的所有可能的路径。 3 、t s p 的分类 1 ) 以距离矩阵的不同可以分为： i 对称t s p ( a s y m m e t r i ct s p , a t s p ) ，d 目= d n ，v j ，je l ，2 ，n ； i i 非对称的t s p ( s y m m e t r i et s p , s t s p ) ，z ，d “，3 i ，e o ( i ，) ，现要找一个 一条经过所有城市且每个城市只能经过一次的最短闭合路径。 由于它是n p h a r d 问题，到目前为止还没有求解它的十分简单、有效的全局收 敛算法，通常求解这类问题用启发式算法，其中进化算法是求解t s p 的一类有效 算法，目前已出现了许多这类方法 1 , 1 6 , 2 2 , 6 2 , 6 9 , 7 3 , 7 4 , 8 3 4 6 , 9 8 - 1 0 0 1 ，这些方法所采用的编码 方式一般都较为复杂，尤其与本文中算法中的编码方法相比更是如此。另外，这 些方法采用的杂交和变异算子要么比较复杂、要么往往产生不可行解，需要一些 修补技术来对产生的不可行解进行校正，更进一步来说，一般进化算法的杂交、 变异算子的搜索能力都比较有限，若不对其加入一些其它技术改进其搜索能力， 则极大地影响由其构造的进化算法的搜索能力。而本文利甩十分简单的编码方法， 即用i o ，n ! - i 】中整数表示( n + 1 ) 个城市的t s p 的一条可行路径，它比现有的同类方 法的编码方法更加简单和容易设计出有效的杂交和变异算子。另外，据此编码方 法设计了一个新的简单有效的杂交算子和变异算子，这两个算子产生的每一个后 代均为可行路径，不需进行校正。为了增强搜索能力，我们将局部搜索技术与变 异算子相结合，使产生的后代更好，因此提高了变异算子的收敛性能，基于此， 设计了一个解t s p 的新的进化算法，并证明了其以概率1 收敛到全局最