（计算数学专业论文）遗传算法收敛特性的离散鞅分析.pdf

遗传算法收敛特性的离散鞅分析 摘要 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a s ) 是模拟自然界生物进 化过程与机制求解问题的自适应自组织人工智能技术，最早由美国 m i c h i g a n 大学的j o h nh o l l a n d 所提出。遗传算法通过模拟达尔文“优 胜劣汰，适者生存”的原理鼓励产生好的结构，通过模仿孟德尔遗传 变异理论在迭代过程中保持已有的结构，同时寻找更好的结构。由于 具有鲜明的生物背景和适用于任意函数类等特点，遗传算法被广泛应 用于机器学习、人工神经网络训练、程序自动生成、专家系统的知识 维护等一系列超大规模、高度非线性、不连续、多峰函数的优化。 作为一种全局搜索算法，遗传算法的基本框架已经形成，也有了 广泛的用途和不断的发展和改进。但已有的研究都是就g a s 的某一 特定实现，或在某一相对弱的意义下讨论算法的收敛性( 或在某一特 定的度量下研究收敛速度) ，均具有相当局限性，可以说，到目前为 止，还没有一套完整的理论可以准确全面地阐明一般g a s 的收敛性， 从而对其在大量应用中所表现的全局优化能力作出理论解释；也还没 有找到一个适当的度量与论证方法精确刻画g a s 在不同实现下的收 敛速度，从而对g a s 的各种改进作出统一、公正的评判。这种一般 数学理论基础的缺乏正致命地限制着g a s 的进一步推广、改进与应 i 用。针对这些情况，溶文主要作了以下三方面的工作： 上海交通大学硕士学位论文 ( 1 ) 从鞅论方面来分析遗传算法的收敛性：在已有的用下鞅分析g a s 的几乎处处强收敛的理论基础上进一步作出改进，给出g a s 几乎 r 处处弱收敛的条件。汨遗传算法求解一个问题，总希望尽可能快 、1 地找到该问题的全局最优解，而我们在执行遗传算法时，通常只 要求在一个种群空间中有一个全局最优解就可以停止，不需要使 得种群的每一个解都为全局最优，因为这将大大增加执行的时间， 在实践中是不可行的。而几乎处处强收敛性就是要求种群中的每 一个个体都收敛到全局最优解。所以为了对实际操作有更大的帮 助，本文给出算法几乎处处弱收敛的条件。 ( 2 ) 讨论遗传算法的收敛率：本文对于经典遗传算法c g a 和杰出遗传 算法e g a ，以第n + l 代最佳解的期望值与全局最优解的差值对第 ”代最佳解与全局最优解的差值的比作为衡量收敛率的标尺，给 出了遗传算法的一般收敛率的阶；对于整体退火遗传算法g a g a ， 定义第n + l 代解的平均值的期望与全局最优解的差值对第一代解 ， 的平均值与全局最优解的差值的比为收敛率。1 这两种收敛率的定 义只以概率形式来表示算法的收敛速度，因而更直接明了，使在 实际操作遗传算法中能直接对具体的概率参数进行调整来改进算 法性能，而不需要再计算或推导其它参数。在这两种收敛率的定 义下，本文证明：随着种群规模的扩大，选择强度的增大，以及 杂交率和变异率的减小，算法能更快地收敛。此外，整体退火遗 传算法的收敛率还与问题的目标函数之间的最大差值有关。因为 不同的问题，其目标函数和选择压力是不同的，所以收敛率是因 上海变通大学硕士学位论文 问题而异的。j ( 3 ) 用实验验证：对一个求函数最大值问题用m a t l a b 语言编程， 分别对经典遗传算法、杰出遗传算法和整体退火遗传算法进行壬： ! 析，验证所确定的收敛率。l 实验证明了对于同一个问题，同一种 遗传算法的参数性能好坏决定了这种遗传算法收敛到全局最优解 的快慢程度，较好地验证了本文第三章所确定的收敛率的结果。r 关键词：遗传算法，下鞅，收敛性，收敛率，整体退火遗传算法 、 、 t h em a r t 矾g a l e a n a l y s i so f t h ec o n v e r g e n c ep e r f o r m a n c e o f g e n e t l ca l g o r i t h m s g e n e d ca l g o r i t h m si sas e l f - a d a p t i v e a n d s e l f - o r g a n i z e d a r t i f i c i a l i n t e l l i g e n c et e c h n o l o g y , w h i c hs i m u l a t e st h ep r o c e s so f n a t u r a le v o l u t i o n t os o l v et h e p r a c t i c a lp r o b l e m s t h i s s t o c h a s t i cs e a r c ha l g o r i t h mw a s p r o m o t e db yj o h nh o l l a n d ，ap r o f e s s o rf r o mm i c h i g a nu n i v e r s i t y i n 19 7 5 ，h o l l a n dp u b l i s h e da 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 ， w h i c hi n t r o d u c e d g e n e t i ca l g o r i t h m s i nd e t a i l t h e a l g o r i t h m s u s ea c o d i n gm e t h o d o nb i n a r ys u i n gc a l l e dc h r o m o s o m e ，a n d t h em a i ni d e ai s t os i m u l a t et h ee v o l u t i o n a r yp r o c e s so ft h eg r o u pm a d eu po f t h e s es t r i n g s b yn o w , t h ea l g o r i t h m s h a v eb e e nw i d e l yu s e di nm a c h i n el e a r n i n g ， a r t i f i c i a ln e u r a l n e t w o r k ，s p e c i a l i s ts y s t e m a n d m a n y o t h e rf i e l d s a sa g l o b a ls e a r c ha l g o r i t h m ，w e h a v et h ef u n d a m e n t a lf r a m e w o r ko f g a sa n di t sw i d ea p p l i c a t i o n b u ti t st h e o r yi sf a rf r o mc o m p l e t e ，w h i c h t oag r e a te x t e n tl i m i t si t sf i l r t h e rd e v e l o p m e n t b yf a r , g a sh a v en o t h e o r e t i c a lf r a m e w o r ki ng e n e r a l s oi no r d e rt om a k eu pf o rt h i sm a r g i n ， t h em a i nc o n t r i b u t i o n so f t h i sw o r ka r et h ef o l l o w i n g s ： 上海交通大学硕士学位论文 ( 1 ) m a r t i n g a l ea n a l y s i so f t h ec o n v e r g e n c eo f g e n e t i ca l g o r i t h m s ：b a s e d o nt h es u b m a r t i n g a l ea n a l y s i so ft h es t r o n gc o n v e r g e n c eo f g a s ( a s ) ，t h i s w o r kh a sm a d ea ni m p r o v e m e n tb ya n a l y z i n gt h ew e a k c o n v e r g e n c eo f g a s ( a s ) w h e n w eu s eg a st os o l v ea p r o b l e m ，w e n e e d n tr e q u i r et h a t a l lt h ei n d i v i d u a l sa r et h e g l o b a lo p t i m a , w h i c h w i l lb e q u i t e t i m e - c o n s u m i n g t h i s i sw h yw ed i s c u s st h ew e a k c o n v e r g e n c e o fg a s ( 2 ) c o n v e r g e n c e r a t eo f g a s ：a f t e rd i s c u s st h ec o n v e r g e n c e ，w e n a t u r a l l y w a n tt od i s c u s st h ec o n v e r g e n c er a t es oa st of u r t h e ri t sa p p l i c a t i o n i fa n a l g o r i t h mc o n v e r g e si nav e r ys l o ws p e e d ，i th a sn o u s ei np r a c t i c e s ow e w a n tt od e t e r m i n et h e p a r a m e t e r st h a ti n f l u e n c e t h ec o n v e r g e n c es p e e do f t h ea l g o r i t h mt oa c c e l e r a t et h ec o n v e r g e n c e ，a n d g i v e t h es a r i s f l y i n gr e s u l t i nt h e g i v e np r e c i s i o n t h i sa r t i c l eg i v e s t h ed e g r e eo f c o n v e r g e n c e r a t eo f t h r e ew i d e l yu s e dg a s u n d e rt h ed e f i n i t i o n so f c o n v e r g e n c e r a t eo fg a s i nt h i sa r t i c l e ，w ec a np r o v et h a ta st h es i z eo ft h ep o p u l a t i o ni n c r e a s e s ， s e l e c t i o np r e s s u r eg o e st oz e r o ，a n dt h ep r o b a b i l i t i e so fc r o s s o v e ra n d m u t a t i o n g o t oz e r o s ，g a s c o n v e r g e m o r e q u i c k l y ( 3 ) e x p e r i m e n t a lv e r i f i c a t i o n ：b yp r o g r a m m i n gt h ef u n c t i o np r o b l e mi n m a t l a b ，t h ea r t i c l ep r o v e st h a tt h ec o n v e r g e n c er a t e so ft h r e eg e n e t i c a l g o r i t h m s ：c g a ，e g aa n dg a g a d e t e r m i n e da b o v ea r ec o r r e c t t h i s a r t i c l ep r o v e st h a tt h ei m p o r t a n tp a r a m e t e r so fg a si n f l u e n c eg r e a t l yt h e c o n v e r g e n c ep e r f o r m a n c eo f g a s 上海交通大学硕士学位论文 k e y w o r d s ： g e n e t i ca l g o r i t h m s ，s u b m a r t i n g a l e ，c o n v e r g e n c e ， c o n v e r g e n c er a t e ，g l o b a la n n e a l i n gg e n e t i ca l g o r i t h m 上海交通大学硕士学位论文 第一章综述 1 1 优化问题的寻优算法 在信息技术、经济管理、工业工程、交通运输、通信网络等诸多领域中有许 多优化问题，这类问题可以统一表示为下面的数学模型川： ( 1 1 ) ( 1 2 ) ( 1 3 ) 其中，x = 工。，x ：，x n 】7 为决策变量，( x ) 为目标函数，式( 1 - 2 ) 、( 1 3 ) 为 约束条件，【，是基本空间，r 是u 的一个子集。满足约束条件的解x 称为可行 解，集合尺表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。 它们之间的关系如图 图i 一1最优化问题的可行解及可行解集合 对于上述最优化问题，目标函数和约束条件种类繁多，有的是线性的，有的 是非线性的：有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。 随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其优化 问题的最优解既不可能，也不现实，因而求出其近似最优解或满意解是人们的主 要着眼点之一。总的说来，求最优解或近似解的方法主要有三种：枚举法、启发 式算法和搜索算法。 ( 1 ) 枚举法：枚举出可行解集合内的所有可行解，以求出精确最优解。 对于连续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差 而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低， 有时甚至在目前最先迸的计算工具上都无法求解。 ( 2 ) 启发式算法：寻求一种能产生可行解的启发式规则，以找到一个最 优解或近似最优解。该方法的求解效率虽然比较高，但对每一个需要求解的问题 都必须找出其特有的启发式规则，这个启发式规则无通用性，不适合于其他问题。 ( 3 ) 搜索算法：寻求一种搜索算法，该算法在可行解集合的一个子集内 进行搜索操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能 够得到问题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和求 趵尺u 九艇k x m 虬 ，l 上海交通大学硕士学位论文 解效率上达到一种较好的平衡。 随着问题种类的不同，以及问题规模的扩大，要寻求到一种能以有限的代价 来解决上述最优化问题的通用方法仍然是一个难题。而遗传算法却为我们解决这 类问题提供了一个有效的途径和通用框架，开创了一种新的全局优化搜索算法。 1 2遗传算法 遗传算法( g e n e t i ca l g o r i t h m s 以下简称g a s ) 是一类模拟自然界生物进 化过程与机制求解问题的自适应自组织人工智能技术。它的核心思想源于这样的 基本认识：从简单到复杂、从低级到高级的生物进化过程本身是一个自然、并行 发生的、稳健的优化过程，这一优化过程的目标是对环境的适应性，而生物种群 通过达尔文的“自然选择，优胜劣汰”规律和孟德尔的“遗传变异”来达到进化 的目的。生物的进化是通过繁殖、变异、竞争和选择这四种基本形式来实现的。 如果把待解决的问题描述为对某个目标函数的全局优化，则g a s 求解问题的基 本作法是：把待优化的目标函数解释作生物种群对环境的适应性，把优化变量对 应作生物种群的个体，由当前种群出发，利用合适的复制、杂交、变异与选择操 作生成新的一代种群。重复这一过程，直至获得合乎要求的种群或达到规定的进 化代数。 由于具有鲜明的生物背景和对任意函数类( 特别可以无表达式) 可用等突出 特点，g a s 自8 0 年代中期以来引起人工智能领域的普遍关注，并被广泛应用于 机器学习、人工神经网络训练、程序自动生成、专家系统的知识库维护等一系列 超大规模、高度非线性、不连续、多峰函数的优化。9 0 年代以来，对该类算法 的研究日趋成为计算机科学、信息科学与最优化领域研究的热点。 因为遗传算法被认为是对人类自然演化过程的模拟，所以我们首先描述一下 人类的自然演化过程： ( 1 ) 这种演化过程发生在染色体( c h r o m o s o m e ) 上，因为生物的所有遗传 信息都包含在其染色体中，所以染色体决定了生物的性状。染色体是由基因( g e n e ) 及其有规律的排列所构成的。 ( 2 ) 生物的繁殖过程是由其基因的复制( r e p r o d u c t i o n ) 过程来完成的。 ( 3 ) 变异( m u t a t io n ) 可以使子代染色体不同于父代染色体：通过两个父 代染色体的交配( c r o s s o v e r ) 可以产生全新的染色体。 ( 4 ) 自然选择使适应值好的染色体比那些适应值差的染色体有更多的繁 殖机会。染色体的选择、变异和重组进程是无记忆的。将这些概念反应在数学上 就形成了遗传算法的基本概念。 遗传算法的运算基础是字符串或字符段，它就相当于生物学中的染色体。字 符串( 段) 由一系列字符组成，每个字符都有特定的含义，它就相当于基因，即 染色体d n a 片段。 遗传算法的迭代过程，相当于生物学的逐代进化。遗传算法中的复制( 又称 选择) ，体现了生物界中的“自然选择，优胜劣汰”。遗传算法的杂交，相当于 生物界的交配：遗传算法的变异类似于生物界的变异，所以遗传算法的杂交和变 异体现了盂德尔的“遗传变异”理论。 遗传算法仿效生物的进化和遗传，将生物学的基本原则用于优化计算中，所 以不仅遗传算法的指导性原则与生物学吻合而且基本术语也相似。表卜1 列举 上海交通大学硕士学位论文 了生物学术语在遗传算法中的对应意义，从中可以进一步了解遗传算法的生物学 含义。 序号遗传算法生物学 l字符串、字符段 染色体 2字符基因 3迭代进化 4复制( 选择)优胜劣汰 5交叉( 杂交) 交配 6 变异变异 7 字符位置基因位置 8字符串结构 基因型 表1 - 1 遗传算法的术语枉生物学的台义 定义1 2 1 1 2 ( 个体和个体空间) g a s 通常作用于原问题变量的某个有限长 度离散编码( 常为定长二进制字符串) 。所谓卜个体x ，即是长度为，的0 和l 字 符串，通常称之为个体( i n d i v i d u a l ) ，按遗传学的术语，个体也称为染色体 个体的分量称作基因：f 称作个体的链长，卜个体的全体记作s = f 0 ，1 。，称为个 体空间。 定义1 2 2 忙( 母体和母体空间) 所谓母体是一对个体( ，x ：) ，其中 工s ( j - l ，2 ) 。所有母体的全体称为母体空间，即 s 2 = ( x i ，x 2 ) ；工t ，x 2 s 定义1 2 3 1 2 ( 种群和种群空间) 所谓j v 一种群是个个体组成的集合( 个 体允许重复) ，简称种群( p o p u l a t c o n ) 。n 称作种群规模，种群规模在迭代过 程中一般是固定的。称 s “= x = ( x l ，x 2 ，一，x ) ，z ，s ( f ) ) 为v 一种群空间。 定义1 2 4 1 2 1 ( 适应值函数) 在g a s 中，待优化的问题通常被转化为某个合 适适应值函数( f i t n e s sf u n c t i o n ) 的极大化，而替代作用于原优化变量本身。适 应值函数是个体空间s 到正实数空间的映射，即适应值函数厂为 ，：s 斗r + 在遗传算法中用到的唯一信息是实际出现在群体中个体的适应值。通过模拟 生物界自和然选择和自然遗传过程，遗传算法通过选择、杂交和变异三个遗传算 子把一个群体变到一个新的群体。 ， 鲎竖差王把当前群体中的个体按与适应值成比例的概率复制到新的群体中。 上海交通大学硕士学位论文 选择算子的作用效果是提高了群体的平均适应值。因为低适应值个体趋向于被淘 汰，而高适应值个体趋向于被复制，所以在选择运算中群体的这些改进具有代表 性，但这是以损失群体的多样性为代价的。选择算子并没有产生新的个体，当然 群体中最好个体的适应值不会改进。最常用的选择算子是以个体适应值成比例的 所谓比例选择及基于排序的选择等。我们用只“表示第一代的选择概率。 盘銮簋王( 有性重组) 可以产生新的个体，从而检测搜索空间中新的点。选 择算子每次仅作用在一个个体上，而杂交算子每次作用在从母体空间中随机选取 的两个个体上。杂交算子产生一个或两个子代，它们一般与其母体不同，每个子 代都包含两个母体的遗传物质。需要提出的是，本文中均设杂交后产生一个子代。 我们用”表示第一代的杂交概率。 杂交算子有多种，有单点杂交算子，单点随机杂交算子，均匀随机杂交算子 等。其中最简单的单点杂交算子的作用过程如下：首先产生一个在1 到，一1 ( ， 为染色体的长度) 之间的一随机数f ：然后配对的两个母体串相互对应地交换从 f + 1 到，的位段。单点杂交算子的一个重要特征是它可产生于原配对串完全不同 的子代串；另一个重要特征是它不会改变原配对串中相同的位，一个极端情况适 当两个配对串相同时，杂交算子不起作用。杂交算子可以产生具有更高平均值和 更好个体的群体。 銮昱差王也是遗传算法中经常用到的遗传算子，它以一个很小的概率随机地 改变染色体串上的某些位，对于二进制串，就是相应的位从1 变为0 或0 变为l 。 变异算子具有增加群体多样性的效果。比起复制和杂交算子，变异算子是遗传算 法中次要的算子，它在恢复群体中失去的多样性方面具有潜在的作用。在没有另 外说明的情况下，本文中的变异算子是以一个很小的概率改变染色体串上的每一 个位。我们用己4 表示第h 代的变异概率。 图卜2遗传算法的运算过程示意 4 上海交通大学硕士学位论文 遗传算法的主要步骤如下： ( 1 ) 初始化：设置进化代数计数器疗- 0 ：设置最大进化代数s z e p ；随机生 成个个体作为初始群体牙( o ) ； ( 2 ) 个体评价：计算群体2 ( n ) 中各个个体的适应值 ( 3 ) 杂交运算； ( 4 ) 变异运算； ( 5 ) 选择运算，得到下一代群体x ( n + 1 ) ； ( 6 ) 终止条件判断。若，7 s t e p ，则，：打+ 1 ，转( 2 ) ；若h s t e p ，则以 进化过程中得到的具有最大适应值的个体作为最优解输出，终止计算。 与其它一些优化算法相比，遗传算法主要有以下几个特点： ( 1 ) 遗传算法以问题变量的编码作为运算对象而不是用问题的实际值本 身。这种编码处理方式使得我们在优化计算过程中可以借鉴生物学中染色体和基 因等概念，模仿自然界中生物的遗传和进化等机理，也使得我们可以方便地应用 遗传操作算子。特别是对一些无数值概念或很难有数值概念，而只有代码概念的 优化问题，编码处理方式更显示出了其独特的优越性。 ( 2 ) 遗传算法直接以目标函数值作为搜索信息，而传统的优化算法还需 要目标函数的导数值等其它一些辅助信息才能确定搜索方向。这个特性对很多目 标函数是无法或很难求导数的函数，或导数不存在的函数的优化问题，以及组合 优化问题等，应用遗传算法就显得比较方便。 ( 3 ) 遗传算法同时使用多个搜索点的搜索信息，从由很多个体所组成的 一个初始种群开始最优解的搜索过程，而不是从一个单一的个体开始搜索。因为 单个搜索点所提供的搜索信息毕竟不多，所以搜索效率不高，有时甚至使搜索过 程限于局部最优解而停滞不前。遗传算法从种群到种群的搜索方法可咀提高搜索 的信息率，这是其特有韵一种隐含并行性。 ( 4 ) 遗传算法使用概率搜索技术而不同于传统的确定性的搜索方法，从 而增加了其搜索过程的灵活性。虽然这种概率特性也会使得种群中产生一些适应 度不高的个体，但随着进化过程的进行，新的种群总会更多地产生一些适应度不 高的个体实践和理论都已证明了在一定条件下遗传算法总是以概率l 收敛到问 题的最优解。当然，杂交概率和变异概率等参数也会影响算法的搜索效果和搜索 效率，所以如何选择遗传算法的参数在其应用中是一个比较重要的问题 由于遗传算法的上述特点，它提供了一种求解复杂系统优化问题的通用框 架：而且它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性( 即对初值 的独立性) ，所以广泛应用于很多学科。遗传算法主要应用领域有： 1 函数优化。它是遗传算法的经典应用领域，也是对遗传算法进行性能评 价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其它优化 方法较难求解，而遗传算法却可以方便地得到较好的结果。 2 组合优化。组合最优化问题的特点是可行解集合为有限点集。因为现实 生活中的大量优化问题是从有限个状态中选取最好的，所以大量的实际优化问题 是组合最优化问题。对于复杂问题，应该把主要精力放在求其近似最优解，也就 是满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算 法对于组合优化问题非常有效。 上海交通大学顽士学位论文 3 机器人学。机器人是一类复杂的难以精确建模的人工系统，而遗传算法 的起源就来自于对人工自适应系统的研究，所以机器人学理所当然地成为遗传算 法的一个重要应用领域。 4 图像处理。图象处理是计算机视觉中的一个重要研究领域。遗传算法在 这些图象处理中的优化计算方面，尤其是模式识别、图象恢复、图象边缘特征提 取等方面得到了应用。 5 还有生产调度问题、自动控制、人工生命、遗传编程、机器学习等领域。 1 2 1 三种主要遗传算法的简介 下面介绍一下本文将要讨论的三种遗传算法。 经典遗传算法c a n o n i c a lg e n e t i ca l g o r i t h m ( 简称c g a ) ： ( 1 ) 置女= o ，随机产生初始种群j ( o ) ；( 一( o ) ，工2 ( o ) ，h ( o ) ) s ”；种群规 模为，即每一代产生个个体，x ，为第i 个个体。 ( 2 ) 独立地从当前种群中选取对母体进行杂交，产生个中间个体作为 中间种群： ( 3 ) 对杂交后的中间种群进行变异； ( 4 ) 对变异后的中间种群进行选择。得到下一代种群； x ( k + 1 ) ；( 工l ( 七+ 1 ) ，x 2 ( 七+ 1 ) ，一，x ( 七+ 1 ) ) s “； 州 按概率规则只1 ( 牙( 月) ，_ ) = ，( 置) 厂( 孔) 选择个体的方式称为比例选择，通常 i - i c g a 是按比例选择来产生下一代的。 ( 5 ) 检验停止准则，若满足则停止，否则k = k + i ，转( 2 ) 。 杰出遗传算法e l i t i s tg e n e t i ca l g o r i t h m ( 简称e g a ) t 与经典遗传算法不同的是杰出遗传算法将种群规模扩展到v + 1 ，且将每代种 群中的最好个体置于种群的第一位，并保留这个个体到下一代不参加竞争。如 种群2 ( k + 1 ) = ( 一( 七) ，x ：( 豇) ，h ( 七) ，x 。( 女) ) s ”中，x l ( 女) 为第t 代种群的最好 个体，它不参加下一代的竞争。 e g a 选择下一代种群中第一个个体的概率是 掣口 卜尚，”烈氟枷， 即保留种群的最佳个体至下一代。这里h 表示种群j 中个体工的数目， 集合 b ( x ) = k ；，( t ) f ( x a j c s 称为j 的最优解集。 6 上海交通大学硕士学位论文 i 口( j 1 表示集合占( 贾) 的基数。 而选择其它个个体仍然按照比例选择方式。 整体退火遗传算法g l o b a la n n e a l i n gg e n e t i ca l g o r i t h m ( 简称g a g a ) ： 整体退火遗传算法是在经典遗传算法的选择过程中融合了模拟退火算法，选 择概率 掣辟。乞，矿) - 卉一，。f 兰e f ( x ) r + z ，。 ” j = ll r ；l i = 1 其中l 满足些l = 0 - 记号j 。2 表示从种群牙和三中选择个体作为下一代种 群，即父代种群牙参加下一代的选择，2 为杂交、变异后的中间种群。 1 3遗传算法收敛特性的现有结论 研究遗传算法的收敛性并估计其收敛率是解释和预测该算法特征的重要理 论因素。但目前关于遗传算法的收敛性的理论很不完整，而且也少有关于遗传算 法收敛率的文章。下面是对收敛性和收敛率现有结论的一些分析。 先给出收敛的几个定义： 定义1 3 1 称 0 使得g 。= g 。p 。而c g a 的转 c + - 卜c i m + = 卜m ，s + = 卜s ， p + = p p 、r u l l o i u ：，u ： ； l ； ! p 儿u u “= 匿 0 p u 2 2 ； p u l 【k 其中u 是在选择后保留当前最佳个体后形成的转移矩阵。 上海变通大学硕士学位论文 在文献 6 中指出，记录历代种群的最好个体仅为一种独立于算法自身的外 部记录，它对遗传算法本身无任何改进，该文提出了遗传算法的一类非时齐选择 退火选择，即选择算子采用如下方式： r、 掣( 工) ：e 几) ，| f e 九叫佤i ， 4。 l ，鬲一，j t o ) 单调下降趋于零而变异算子和杂交算子不作变化。 该文献得出：允许父代参加竞争是退火选择遗传算法收敛的充要条件，并且 这种算法称为整体退火遗传算法g a g a ，它能保证种群中的任何一个个体以概率1 收敛到总体最优解集，还有自然的停机准则。 文献 7 中的g a w i 和g a w o 模型分析均可得出转移概率矩阵为本原的，所 以存在q ” 0 不依赖于初始分布，这说明时齐g a s 不收敛于全局最优，虽然它们 收敛于平稳分布并且收敛级数为几何的。 文献 8 用鞅论来分析g a s 的几乎处处强收敛性，给出了较为系统的结果。 与通常优化技术中的搜索方式不同，g a s 作为自适应的随机搜索方法，其搜索方 式是从种群到种群，而不是从一个解到另一个解( 如牛顿法，模拟退火法等) 。 该文章取代了传统的遍历性分析，首次尝试运用鞅理论，通过把遗传算法演化过 程处理作平均适应值函数过程，把平均适应值函数过程转化为下鞅，证明了大 类常用遗传算法能以概率l 确保在有限步内收敛到问题的全局最优解。 可以看出，目前现有的关于g a s 的收敛性的文献大都用m a r k o vc h a i n 理论 来分析和描述。虽然用m a r k o vc h a i n 理论描述g a s 有直接，精确的特点，但这 类方法只能根据转移矩阵本原的特性而得到算法趋于某一平稳分布，这与优化中 所指的收敛性不同，同时并不保证g a s 以概率1 收敛到全局最优。而且，由于一 般问题的解空间都很大，从而转移矩阵的阶也很大，这使得具体确定，分析转移 阵的性态十分困难，更不用说具体描述其平稳分布了。因而对于较大规模的g a s ， m a r k o vc h a i n 分析只能籍于遍历性考察而得出相应g a s 收敛性的某些“粗糙” 结论。而且，该模型在很大程度上依赖于染色体的编码形式，如常用的二进制等。 虽然文献 8 用鞅论来分析g a s 的几乎处处强收敛性，但是几乎处处强收敛 性要求种群中的每一个个体都收敛到全局最优解，所以会耗费大量的机器执行时 间，在实际执行过程中是不可行的。 1 3 2 遗传算法收敛率的部分现有结论 研究了收敛性，我们自然希望讨论收敛率，以希望能对实际应用有所帮助。 文献 4 对e g a 估计出以( 1 一o ( kj ”) 为下界的收敛率，其中土是模小于1 的 关于转移矩阵p 的最大特征值。转移概率矩阵有j 个子矩阵p ( f ) ，3 i p ( o 的阶为 ( i ) ( f ) r ( o = ( - i ：一 f = “卅) 。这里设种群规模为奇数，种群 1 0 上海交通大学硕士学位论文 的第一位保存当前最好解在解空间中的位置，其中解空间按f ( i ) 的递减顺序排 列。种群按i ( m ) 升序排列，f ( m ) 是当前最好解在解空间中的序号，即i ( m ) 越 大，该种群的最优适应值越小。而在一个种群中，f ( m ) 小于其它个体的序号。 可得= i 1 ) = 跏， 存在常数c ，满足9 1 l c 阻l ”，这里r 为包含全局最优解的种群的集 合。阻f 是p 的次小于1 的最大特征值。迸一步，对陋 ，存在不依赖于变异率p 的常数a ，满足： 川1 一和5 ( 1 一) 。5 这里占= m a xm a x ，【 ，m a xd ( i ，朋，即个体f ，_ ，之间的最大海明距离， u s i s z iu 句“。i l 海明距离是指在二进制编码形式下，两个染色体( 个体) 之间的不同基因的数目。 文献 9 对选择，杂交，交异算子时齐和非时齐的遗传算法g a s l ，g a s - 2 分别估计出它们的收敛率的界。首先，要使g a s 收敛，必须满足全局最优集是可 达( 即从任何一个初始状态出发均可达到最优集) 和吸收的( 即一旦进入，便不 离开) 。 文献 9 的结论是： i 对g a s 一1 ，即选择，杂交，变异算子时齐的遗传算法，当满足文中的性质 1 ) - 4 ) 时： 一硎( 1 一回”卜 这里占为一大于0 的常数，f 0 是某一时刻。其中性质1 ) 一3 ) 保证：若当前种群 中含有全局最优解，则经变异、杂交、选择后仍然存在于种群中；性质4 ) 称为 可达性，即从任何初始种群开始，经有限步概率转移必可达到全局最优解集。 i i 对g a s 一2 。即选择，杂交，变异算子非时齐的遗传算法，当满足文中的性 质5 ) 一8 ) 时， ”丌忙糕 ( 1 - 8 ) 1 l e - i + z 。吼7 占) 这里f 。可看作全局最优集的首次访问时间，占可看成从任何初始分布开始对全局 最优集的首次访问概率，且 a t a s u p s u p p ( m + 七) 一p ( m 。+ i ) i i 。) om 。) 0 其中性质5 ) 一7 ) 除了保证：若当前种群申含有全局最优解，则经变异、杂 交、选择后仍然存在于种群中，还保证非时齐的变异、杂交、选择算子形成的非 上海交通大学硬士学位论文 时齐转移概率矩阵分别收敛到一个常矩阵；性质8 ) 与性质4 ) 类似。 文献 1 0 通过分析一种扩展串的g a ( e x t e n d e ds t r i n g sg e n e t i ca l g o r i t h m ， 简称为e s g a ) 的相应转移矩阵p 的特征值的方法，将达到全局最优解的平均次 数作为衡量算法收敛的指标，得出达到全局最优解的平均次数r 为 l 一l 辜卉，虻一“，这里- = o ，l ，z 为转移矩阵的模小于l 的特征值， j i oi 一2 1 ri - 0 旃，是使得p = 西a 市的m 中的元素，a 是由p 的特征值所形成的对角矩阵 “，i = 0 , 1 ，是种群的初始分布。显然t 1 。 文献 1 1 通过对遗传算法的m a r k e rc h a i n 分析，研究其转移概率矩阵p 的 小于l 的特征值，估计出 俐。阿弘删) 1 叫挣5 ( 嚣门， 从( 工) 一一+ ( z ) l ( h v 卅( x ) 邮一一( 带5 ( 等) 卜6 n 其中以，f 分别是种群序列的第k 代概率分布和最终概率分布，7 1 ，v 。是 对应于p 的特征值厶， ，“一。的右特征向量，厶= l ，限l 1 ，i = 2 , 3 ，n l ， a 。是满足方程胁= ( 1 0 y o + 码v 1 + + 口v 的复系数，a 为与变异概率无关的常 数，占= m 犁【m a xd “，)】。 0 q e 2 1 一l 叫s 27 一l ， j ) ，j ) 可以看出，目前的关于收敛率的文章也大都建立在m a r k o vc h a i n 模型的分 析上，依赖于对其转移矩阵的描述和研究，也有者类似于收敛率分析的局限性。 而且，这些文章在收敛率的形式表达上不够简洁明了，需要计算除算法本身具有 的参数之外的额外信息，如转移矩阵的特征值、特征向量等，从而限制了更好地 改进算法性能以促进实际应用。而且，目前有关的文章很少有关于遗传算法收敛 性的结论经过作者的多次文献检索，发现有关收敛率的文章数目远不及收敛性 的文章数目。 1 4 本文的工作 针对现有的关于遗传算法收敛特性不完善的情况，本文作了以下的工作： ( 1 ) 从鞅论方面来分析遗传算法的收敛性：在已有的用下鞅分析g a s 的理论基础 上进一步作出改进，给出g a s 几乎处处弱收敛的条件。用遗传算法求解一个 问题，总希望尽可能快地找到该问题的全局最优解，而我们在执行遗传算法 时，通常只要求在一个种群空间中有一个全局最优解就可以停止，不需要使 得种群的每一个解都为全局最优，因为这将大大增加执行的时间，在实践中 是不可行的。而几乎处处强收敛性就是要求种群中的每一个个体都收敛到全 局最优解。为了对实际操作有更大的帮助，本文给出算法几乎处处弱收敛的 条件。 上海交通大学硕士学位论文 ( 2 ) 讨论遗传算法的收敛率：研究了收敛性，我们自然希望讨论收敛率，以希望 能对实际应用有所帮助，一个算法若以很慢的速度收敛，在实践中是不可行 的，故我们希望能确定影响算法收敛快慢的参数，从而加快收敛，在给定的 精度下得出令人满意的结果。本文对于经典遗传算法c g a 和杰出遗传算法 e g a ，以第n + 1 代最佳解的期望值与全局最优解的差值对第h 代最佳解与全 局最优解的差值的比作为衡量收敛率的标尺，给出了遗传算法的般收敛率 的阶：对于整体退火遗传算法g a g a ，定义第n + 1 代解的平均值的期望与全局 最优解的差值对第疗代解的平均值与全局最优解的差值的比为收敛率。这两 种收敛率的定义只以概率形式来表示算法的收敛速度，因而比较简洁明了， 使在实际操作遗传算法中能直接对具体的概率参数进行调整来改进算法性 能，而不需要再计算或推导其它信息。在这两种收敛率的定义下，本文证明： 随着种群规模的扩太，选择强度的增大，以及杂交率和变异率的适度减小 算法能更快地收敛。此外，整体退火遗传算法的收敛率还与问题的目标函数 之间的最大差值有关。 ( 3 ) 用实验验证：对一个求函数最大值问题在m a t l a b 语言环境下编程，分别对 标准遗传算法，杰出遗传算法和整体退火遗传算法进行分析比较，验证所确 定的收敛率。实验证明了对于同一个问题，同一种遗传算法的参数性能好坏 决定了这种遗传算法收敛到全局最优解的快慢程度，较好地验证了本文第三 章所确定的收敛率的结果。 上海交通大学硕士学位论文 第二章收敛性分析 2 1 离散鞅的基础知识 本文从鞅论方面来分析遗传算法的收敛性。因为遗传算法的目标是寻求全局 最优解，而完成的过程是一个随机搜索过程，总希望这个过程在期望值意义下越 来越好，这样自然应当是一个下鞅序列，利用鞅收敛定理就可以证明遗传算法的 收敛性。由于该算法是在离散的时间序列上执行，故我们只考虑离散鞅的情况。 下面先给出条件期望与鞅的定义及性质。 定义2 1 i 1 2 1设q 是一个基本集合，, r 是q 上的部分子集构成的口一代 数，即满足： ( 1 ) o f ， ( 2 ) a c k - 时a f ， ( 3 ) o f ( v n = l ，2 ，) ，则u 。f h = i 则( q ，f ，p ) 构成概率空f a q ( q ，i f - ) 称为可测空间。若f 是可测空间( q ，f ，) 到 可测空间( q 2 ，f2 ) 的映射，且对于任意a f2 有，“( ) = x ；厂( 砷a ) e f ， 则称，为可测映射。若厂是实值可测映射，则称之为随机变量。 定义2 1 2 2 1 设f 为离散型随机变量，其分布列为 p f = 一 = p 。，i = 0 ，1 ，2 ，一，且p f o ，p ，= 1 r _ o 若k p ， o o ，记e ( 0 = 置只， j 1 0j - o 称e ( o 为f 的数学期望。 定义2 1 3 设，叩) 为离散型随机变量，其概率函数 p ( i ，k ) = p f = t ，叩= y t ) ，f ，k = 1 , 2 ， 1 4 上海交通大学硕士学位论文 条件概率函数 p ( k i f ) = p ( 玎= y t k = x 。) ，p ( i l 七) = p f = _ k = n ) ，i ，