（计算机软件与理论专业论文）遗传算法在数值优化中的应用.pdf

摘要 本文包括两部分。 第一部分介绍遗传算法的理论和它在函数极值优化问题中的 应用。首先，本文通过对不同参数遗传算法在t s p 问题的数值仿 真结果的比较和分析，找出了影响遗传算法稳定性和收敛性的重要 因素。其次，文章提出了几种改进办法，提高遗传算法的性能。 第二部分中，文章提出了改进s g a 不足的h g a 算法。通过 两种算法分别在函数优化中的应用，结果证明h g a 性能优异，可 以克服s g a 的不足。 关键词： 遗传算法，简单遗传算法，分层遗传算法，n p 完全f q 题，函数 优佗，组合优钯_ ：旅行商问题丫 a b s t r a c t t h i sp a p e rc o n s i s t so ft w op a r t s t h ef i r s ts e c t i o ni st h ei n t r o d u c t i o no ng a s t h e o r ya n di t sa p p l i c a t i o n so nl i m i tv a l u eo ff u n c t i o no p t i m i z a t i o n f i r s t l y ，t h ep a p e r f i n d so u ts o m ei m p o r t a n te f f e c t i v ef a c t o r so nt h eg a ss t a b i l i t ya n d c o n v e r g e n c es p e e db yc o m p a r i n gs e v e r a lt s p n u m e r i c a le x p e r i m e n t s w i t hd i f f e r e n tp a r a m e t e r s t h e n ，t h ep a p e rp r o p o s e ss e v e r a ln o v e l t e c h n i q u e so ni m p r o v i n gt h ec o n v e r g e n c es p e e do fg a s i nt h es e c o n ds e c t i o n ，t h ep a p e ra l s op r o p o s e san e wh i e r a r c h i c g e n e t i ca l g o r i t h m s ( h g a ) ，w h i c ho v e r c o m es o m ed r a w b a c k so n s i m p l eg e n e t i ca l g o r i t h m s ( s g a ) t h ep a p e rc o m p a r e sh g a a n d s g a b ys e v e r a lf u n c t i o nn u m e r i c a le x p e r i m e n t s t h es i m u l a t i o nr e s u i t ss h o wt h a tt h eh g ai sb e t t e rt h a ns g a k e yw o r d s ： g e n e t i ca l g o r i t h m s ，s i m p l eg e n e t i ca l g o r i t h m s ，h i e r a r c h i cg e n e t i ca l g o r i t h m s ，n o n d e t e r m i n i s t i cp o l y n o m i a lc o m p l e t e n e s s ，f u n c t i o n o p t i m i z a t i o n ，c o m b i n a t o r i a lo p t i m i z a t o n ，t r a v e l i n g s a l e s m a n p r o b l e m ( t s p ) 第一章绪论 第一节遗传算法的发展及研究概况 近代科学技术发展的显著特点之一是生命科学与工程科学的 相互交叉，相互渗透和相互促进，而遗传算法( g e n e t i ca l g o r i t h m s g a ) 与智能化计算的蓬勃发展体现了学科发展的这一特点和趋势。 近年来这些新的计算智能理论和方法正在迅速发展。并且广泛地 适应于研究与工程的各个领域，取得了显著效果。 遗传算法的的内涵和哲理乃是启迪于自然界生物从低级简单 到高级复杂乃至人类这样一个漫长绝妙的进化过程和借鉴于达尔 文的物竞天演，优胜劣汰，适者生存的自然选择和自然遗传的机理。 其本质是一种求解问题的高效并行搜索方法。能在搜索过程中自 动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求 得最优解或较优解。 使用遗传算法求解科学研究和工程技术中各种组合搜索和优 化计算问题的这一基本思想，是早在6 0 年代初期由美国密西根 ( m i c h i g a n ) 大学的j h o l l a n d 教授的名著自然- 9 人工系统的 自适应中予以系统的介绍，到了8 0 年代中期，遗传算法研究蓬勃 发展，吸引了大批的科学研究者和工程技术人员，从事该领域的研 究和开发应用工作，由于遗传算法的整体搜索策略和优化搜索方法 在计算时不依赖于梯度信息，所以它的应用范围非常广泛，尤其是 适合于处理传统搜索方法难以解决的高度复杂的线性f s j 题。如背 包问题，旅行商等问题，在组合优化，优化数值，机器学习，智能控 制，人工生命，模式识别等领域应用中，展现了它特有优越性和魅 力。随着计算机速度的提高，进行遗传算法和进化计算时计算机速 度的要求已不在是制约其发展的要素。遗传算法在很多方面取得 了广泛应用。 遗传算法的两大主要特点是群体搜索策略和群体中个体之间 的信息交换，它实际上是模拟由个体组成群体的整体学习过程，其 中每个个体都是给定问题搜索空间的一个解点。遗传算法从任一 初始化群体出发，通过随机选择( s e l e c t i o n ：使群体中优秀个体有更 多机会传给下一代) 交叉( c r o s s o v e r ：体现了自然界e e 群体内个体间 信息交换) 和变异( m u t a t i o n ) 在群体中一代一代地进入到搜索空间 中越来越好的区域，直至抵达优解点。遗传算法与其它搜索方法相 比，其主要优越性表现在： 首先，遗传算法在搜索过程中不易限入局部最优，即使所定义 适度函数非连续，不规则和伴有噪声的情况下也可能以极大概率找 到全局最优解；其次由于遗传算法固有的并行性，使得它非常适合 于大规模并行分布处理。主要内在并行方式表现在i 搜索一个种群 数目的点而不是单点，其内在并行性表现在多台计算机对各自独立 的种群的深化计算，甚至不用通信，等到运行结束才通信，选取最佳 个体。还包含有内含并行性，于由于遗传算法采用种群搜索，因而 可同时搜索解空间多个区域。并相互交流信息。遗传算法优越性 还表现在其智能性，即自组织，自适应和自学习性，此外遗传算法易 于和别的技术结合，形成更优的问题求解方案。 目前遗传算法的研究，尽管还存在一些有争议的问题，某些截 然不同的甚至鲜明对照的学术观点和设计原则，一时尚难统一，而 且整个遗传算法的理论基础还比较薄弱，但是很多实例及应用充分 表明，模拟自然进化的搜索过程往往可以产生非常简单，通用和鲁 棒性能很强的计算方法。 第二节本文研究目的和研究内容 本文旨在研究遗传算法及其在数值优化与组合最优化中的应 用，尤其注重遗传算法及采用分层方法改进后的算法在n p 完全问 题中的应用。 因此本论文在对遗传算法和组合最优化及数值优化方面进行 了基本研究和分析的基础上进行了以下各方面研究。 1 、研究s g a 在组合优化中的应用，具体内容是： ( 1 ) 分析遗传算法原理，以及使用它解决问题的方法。 ( 2 ) 提出组合优化中的典型n p 完全问题，用及现有数学解决 方法，以实际的例子t s p 问题作为样本，具体的分析使用这一方法 在优化组合方面具有的优越性。 ( 3 ) 将该问题转化为用s g a 解决的目标问题，并用该算法来实 现它。 ( 4 ) 实现该算法，并在t u r b oc 2 0 中调试其结果，分析该 结果，从中发现其存在的问题和可以改进的地方。 ( 5 ) 多次试验对其收敛速度和克服未成熟收敛进行分析，为基 本遗传算法改进打基础。 ( 6 ) 系统的研究了分层遗传算法，并对它在应用中避免过快收 敛和收敛缓慢以及局部收敛的的等方面同简单遗传算法作了对比。 2 、本文讨论了遗传算法改进方法，比较多种方法之后，采用分 层遗传算法处理上述问题，注体进行了以下几方面有意义的工作： ( 1 ) 分析改进算法的优势，并且提出改进后可能出现的问题。 ( 2 ) 实践分层遗传算法，解决组合优化和数值优化问题，对比 改进前后二者收敛速度和抗未成熟收敛性能。 ( 3 ) 为了避免过快收敛和收敛缓慢以及局部收敛的情况，可以 在分层遗传算法中引入交互式遗传算法和其它有效的方法，而且可 以有非常高的程序并行计算的能力。 第三节本文研究的所需软硬件工作环境 本文研究的算法实现是在c 语言为版本的数据结构基础之 上，在d o s 3 0 以上版本上运行，其实现程序由t u r b oc 2 0 上编 写及运行调试。 第二章遗传算法的基本原理和方法 第一节遗传算法的基本概念 遗传算法( g e n e t i ca l g o r i t h m s ) ，简称g a s ，是一类借鉴生物界 自然选择和自然遗传机制的随机优化搜索算法，是一种近似算法。 众所周知，在人工智能领域中，有不少问题需要在复杂而庞大 的搜索空间中寻找最优解或准最优解，典型的n p 完全问题就是一 例。在求此类问题时，若不能利用问题的固有知识来缩小搜索空 间，很容易产生搜索的组合爆炸。因此研究在搜索过程中自动获取 和积累有关搜索空间知识并自适应地搜索过程，从而得到最优解或 准最优解的通用的搜索算法一直是令人瞩目的课题。遗传算法就 是这种特别有效的算法。它主要特点是简单、通用、鲁棒性强，适用 于并行分布处理及应用范围广。尽管g a 本身在理论和应用方法 上仍有很多有待进一步研究的问题。但它在组合优化问题求解，自 适应控制，规化设计，机器学习和人工生命等领域的应用中展现了 其特色。 达尔文的自然选择学说认为：所有的生物发展都是经历了从低 级简单逐渐到高级复杂的过程，生物要生存下去就必须进行生存斗 争。在生存斗争中，具有有利变异( m u t a t i o n ) 的个体容易存活下 来，并且有更多机会将有利变异传给后代；具有不利变异的个体就 容易淘汰。产生后代的机会也少的多。因此在生存斗争中获胜的 个体都是对环境适应性比较强的。达尔文把这种生存斗争中适者 生存不适者淘汰的过程称之为自然选择。达尔文的自然选择学说 表明，遗传和变异是决定生物进化的内在因素。遗传指的是父代与 子代之间，以及予代的个体之间，在性状上或多或少的存在变异现 象。在生物体内，遗传和变异关系十分密切，一个生物体的遗传性 状往往会发生变异，而变异的性状有的可以遗传。遗传能使生物的 性状不断的传递给后代，因此保持了物种的特性，变异能使生物性 状发生改变，从而产生新个体，适应新环境，不断向前发展。 既然遗传算法效法基于自然选择的生物进化，是一种模仿生物 进化过程的随机方法。那么认知生物遗传学上的基本概念与术语 对于理解遗传算法是非常重要的。 染色体( c h r o m o s o m e ) ：是遗传物质的主要载体，由多个遗传因 子基因( g e n e ) 组成。 遗传因子( o e n e ) ：染色体中一定位置的基本遗传单位，也称基 因。 基因型( g e n e t y p e ) ，遗传因子组合的模型，是性状染色体的内 部表现。 表现型( p h e n o t y p e ) ，由染色体决定性状的外部表现。 基因座( l o c u s ) ，遗传基因在染色体中占据的位置。 等位基因( a l l d e ) ，同一基因座它可能有的全部基因称为等位 基因。 个体( i n d i v i d u a l ) ，指染色体带有特征的实体。 种群( p o p u l a t i o n ) ，染色体带有特征的个体组成了种群。 群体中个体数目大小称为群体大小( p o p u l a t i o n s i z e ) ，也叫群体 规模。 适应度( f i t n e s s ) ，各个体对环境适应程度。选择( s e l e c t i o n ) ， 指决定以一定概率从种群中选择若干个体的操作。一般而言，选择 过程是一种基于适应度的优胜劣汰的过程。交叉( c r o s s s o v e r ) 两个 染色体之间通过交叉而重组形成新的染色体。变异( m u t a t i o n ) 染 色体的某一基因发生变化，产生新的染色体，表现出新的性状。 编码( c o d i n g ) ：遗传编码可看成是从表现型向基因型的映射， 而解码( d e c o d i n g ) 是基因型向表现型的映射。 引用了这些术语，可以更好的描述遗传算法，遗传算法也就是 从代表问题的可能潜在解集的一个种群( p o p u l a t i o n ) 出发，而一个 种群则由基因( o e n e ) 编码( c o d i n g ) 的一定数目个体( i n d i v i d u a l ) 组 成。每个个体其实是染色体( 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 ) ，可 以作为问题的近似最优解。 第二节、遗传算法的实现 遗传算法是具有“生成+ 检测”( g e n e r a t i o na n dt e s t ) 的迭代过 程的搜索算法。它基本处理流程图是如图2 1 所示： 图2 、1g a 的基本流程 由基本处理流程图表示可见，遗传算法是一种群体型操作，该 操作以群体中的所有个体为对象。选择( s e l e c t i o n ) ；交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 是遗传算法的三个主要遗传算子( g e n e t i c o p e r a t o r ) ，它们构成了所谓的遗传操作，使遗传算法具有了其它传 统方法所没有的特性。由流程图可知，遗传算法中包含如下五个基 本要素： 1 、参数编码 2 、群体设定 3 、适应度函数设计 4 、遗传操作设计 5 、控制参数设定( 主要指群体大小和使用遗传算子的概率) 。 这五个要素构成了遗传算法核心。 一、编码 遗传算法主要是通过遗传操作对种群中具有某种结构形式的 个体施加结构重组处理，从而不断地搜索出群体中个体间的结构相 似性，形成并优化积木块以逐渐逼近最优解。所以遗传算法不能直 接处理问题空间的参数，必须把它们转换成基因型串结构数据，这 个转换操叫作编码。 1 、定义 问题空间指由g a 表现型个体( 有效候选解) 集所组成的空间。 g a 空间是指由基因型个体所组成的空间。 由1 7 题空间向g a 空间的映射称作编码( c o d i n g ) 由g a 空间向问题空间的映射称作译码( d e c o d i n g ) 2 、编码技术 g a 采用的编码方法很多，二值编码，实数表示和格雷码表示 等。其中二值编码是目前常用的编码方法。它具有以下特点： 1 、简单易行 2 、符合最小字符集编码原则 二、初始种群生成 遗传操作是对多个个体同时进行，这众多个体组成了群体，在 遗传算法处理流程中，继编码设计后的任务是初始群体设定，并以 此为起点，一代代进化直到按某种进化准则终止进化过程，由此得 出最后一个种群。在种群初始生成过程中，种群大小对遗传算法效 能发挥有重大影响。 一般来说，遗传算法中初始群体中的个体均为随机产生，群体 规模的设定既要保种群中个体多样性，又要考虑到计算量问题。 三、适应度函数 遗传算法在搜索进化过程中一般不考虑其它外部信息，仅用评 估函数值即适应度函数来评估个体或解的优劣，并作为以后遗传操 作的依据，评估函数值又称作适应度( f i t n e s s ) ，遗传算法的适应度 函数不受连续可微的约束，定义域为任一集合。对适应度函数唯一 要求是输入可计算出能加以比较的非负结果。 适应度函数基本以下三种： 1 、直接以待求解目标函数转化为适应度函数中： 若目标函数为最大化问题：f i t ( f ( x ) ) = f ( x ) 若目标函数为最小化问题：f i t ( f ( x ) ) = 一f ( x ) 这种适应度函数简单直观，但存在两个问题： 其一是可能不满足常用的轮盘赌选择中概率非负要求； 其二是某些代求解函数在函数值分布上相差很大，由此得的平 均适应度可能不利于体现种群的平均性能，影响算法性能。 2 、界限构造法：若目标函数为最小问题，则： r ( ，( z ) ) ：c 一- ，z ，f ( x c 砌b ”2 1o ，其他 3 、若目标函数为最小问题 f i t ( 厂( 圳= 再南c o ，c + 厂( z ) o 若目标函数为最大问题 f i t ( 厂( 圳= 再南c o ，c - f ( z ) o 四、遗传操作 遗传操作是模拟生物基因遗传的操作，在遗传算法中，通过编 码组成初始群体后，遗传操作的任务就是对群体的个体，按照它们 环境适应程度施加一定操作，从而实现优胜劣汰的进化过程，从优 化搜索而言，遗传操作可使问题的解，一代又一代地优化，并逼近最 优解。 遗传操作包含三个基本遗传算子( g e n e t i co p e r a t o r ) 选择( s e l e c t i o n ；) 交x ( c r o s s o v e r ) ；变( m u t a t i o n ) 这三个遗传算子有如下特点： ( 1 ) 这三个遗传算子的操作都是在随机扰动情况进行，换句话 说，遗传操作是随机操作，因此群体中个体向最优解迁移的规则是 随机的。 ( 2 ) 遗传操作效果和上述三个遗传算子所取操作概率、编码方 法、群体大小、初始群体以及适应度函数设定，密切相关。 ( 3 ) 2 个基本遗传算子的操作方法或操作策略随具体求解问题 不同而异，更具体地讲，是与个体的编码方式直接相关。 1 、选择( s e l e c t i o n ) 从群体中选择优胜个体，淘汰劣质个体的操作- 1 选择。选择算 子有时又称为再生算子( r e p r o d u c t i o no p e r a t o r ) 。选择的目的是把 优胜的个体直接传到下一代或通过交叉配对再遗传到下一代。选 择操作是建立在群体中个体适应度评估的基础之上，即个体适应度 越高，其被选择的机会就越多，目前常用的选择算子有：适应度比例 方法、最佳个体保存方法、期望值方法、排序选择方法、联赛选择方 法、排挤方法。这里主要介绍常见的两种方法，本文采用的是第一 种方法。 ( 1 ) 适应度比例方法 适应度比例方法是目前遗传算法中最基本也是最常用的选择 方法。它也叫赌轮或蒙特卡洛选择。在该方法中个体被选择概率 与其适度成比例。 ( 2 ) 最佳个体保存方法( e l i t i s tm o d e l ) 该方法的思想是把群体中适应度最高的个体不进行配对，直接 复制到下一代中，此种选择操作也称复制( c o p y ) 。 设到时刻t ( 第t 代) 时，群体中a ( t ) 为最佳个体，又设a ( t + 1 ) 为新一代种群，若其中不存在个体a ( t ) ，则把a ( t ) 作为a ( t + 1 ) 的 第n + 1 个个体。( 其中，n 为群体大小) 。 采用此选择方法的优点是，进化过程中某一代的最优解可不被 叉交和变异操作所破坏。但是隐含着一种危机，使局部最优个体的 遗传基因会急速增加而使进化有可能限于局部解。也就是说该方 法全局搜索能力差，它更适合单峰性质的搜索，而不是多峰性质的 空间搜索，所以此方法一般与其它方法结合使用。 2 、交叉( c r o s s o v e r ) 在自然界生物进化过程中起核心作用的是生物遗传基因的重 组( 加上变异) 。同样，遗传算法中起核心作用的是遗传操作的交叉 算子。所谓交叉又是指把两个父代个体的部分结构加以替换重组 而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提 高。各种交叉算子( 对二值编码而言) 一般都包含两个基本内容： ( 1 ) 从由选择操作组成的配对库中，按照预先设定的交叉概率来 决定每对是否需要进行交叉操作。 ( 2 ) 设定配对个体的交叉点( c r o s ss i t e ) ，并对这些点前后配对个 体部分结构( 或基因) 进行相互交换。 基因的交叉算子有：一点交叉，两点交叉，多点交叉，一致交叉， 二维交叉，树结构交叉，顺序交叉，周期交叉等等；这里主要讨论一 下一点交叉( o n ep o i n tc r o s s o v e r ) 。 一点交叉又叫简单交叉，具体操作是：首先对配对库中个体进 行随机配对，然后在个体中随机设定一个交叉点( 配对库中的竖线 表示交叉点) ，实行交叉时，该点前或后的两个个体的部分结构进行 互换，并生成两个新个体，下图给出一点交叉的例子： 父个体1 1 0 0 1i 1 1 1 安x 1 0 0 1 11 1 1 子个体1 配对个体父个体f + 0 0 1 112 0 0 1 10 0 0 0 0 1 1 i0 0 0 子个体2 ， 父个体 f 亍个谇 其中交叉点在第4 、第5 基因座之间交叉时，两个个体的部分 码串互相交换，得到两个新个体1 、2 。交叉点是随机设定的，当 染色体长为n 时，可能有n 一1 个交叉设置，所以，一点交叉可能实 现n 一1 个不同交叉结果，交叉是遗算法最为重要的算法之一。 3 、变异( m u t a t i o n ) 变异算子的基本内容是对群体中个体串的某些基因座上的基 因值作变动。就是基于字符基0 ，1 的二值码而言，变异操作就是把 某些基因座上的基因值取反，即0 1 或1 0 。变异操作同样也是 随机进行的，变异概率一般都取得很小，变异的目的是为了挖掘群 体中个体多样性，克服有可能限于局部解的蔽病。一般说来变异操 作基本步骤如下： ( 1 ) 在群体中所有个体的码串范围内随机的确定基因座； ( 2 ) 以事先设定的变异概率p m 来对这些基因座的基因值实行 变异； 遗传算法引入变异的目的有两个：一是遗传算法具有局部的随 机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用 变异算子这种局部随机搜索能力可以加速向最优解收敛。显然这 种情况下的变异概率应取较小值，否则接近最优解的积木块会因变 异而遭到破坏。二是使遗传算法可维持群体中个体多样性，以防止 出现未成熟收敛现象，此时收敛概率要取较大值。 遗传算法的基本变异算子是指对群体中的个体码串随机挑选 一个或多个基因座并对这些基因座的基因值做变动( 以变异概率 p m 做变动) ，0 ，1 二值码串中的基本变异操作如下例i 个体a 101 1011 堑11 1001 1 变异基因座 基中变异点在第2 ，第4 基因座两处，变异使个体的该两处基 因值取反，形成了一个新个体。 另外还有一些其它的变异算子：逆转算子，自适应变异算子等。 遗传算法中，交叉算子因其具有全局搜索能力而作为主要算 子，变异算子因其具有局部搜索能力而作为辅助算子，遗传算法通 过交叉和变异这一对相互配合又相互竞争的操作而使其具备兼顾 全局和局部的均衡搜索能力。所谓相互配合，是指当群体在进化中 陷入搜索空间中某个超平面而仅靠交叉不能解脱时，通过变异操作 有助于这种摆脱。所谓相互竞争，是指当通过交叉已形成所期望积 木块时，变异操作有可能破坏这些积木块。 在问题求解过程中，遗传算法是这样不断的进行选择，交叉，变 异操作，不断的进行迭代处理，也就是说群体继续不断的一代代进 化下去，那么最终可以得最优或近似最优解。 第三节、遗传算法的基本定理 ( 一) 、模式定理( s c h e m a t et h e o r e m ) 1 、模式的定义 模式( s c h e m a ) 是一个描述字符串集的模板，该字符串集中的串 的某些位置上存在相似性，因此也可解释为相同的构形，它描述的 是一个串的子集。 定义2 ，3 1 ：基于三个字符集( 0 ，1 ，* ) 的字符串称为模式，其 中符号“* ”代表任意字符，即0 或1 。 例如模式* 1 * o 描述四个之的字符集 0 1 0 0 ，0 1 1 0 ，1 1 0 0 ， 1 1 1 0 。对于二进制编码串，当串长为l 时，共有2 1 个不同模式。遗 传算法串的运算实质为模式运算； 2 、模式阶( s c h e m ao r d e r ) 和定义距( d e f i n i n gl e n g t h ) 定义2 3 2 ：模式h 中确定位置的个数称为h 的模式阶。 记为o ( h ) 虫口o ( 0 * 1 * 0 1 ) = 4 模式阶用来反映不同模式间确定性差异，模式阶数越高，模式 确定性越高，所匹配的样本个数就越少。 定义2 3 3 ：模式h 中第一个确定位置和最后一个确定位置之 间距离称为定义距，记作6 ( h ) ： 例虫口6 ( 1 0 1 * 0 1 * 1 ) = 7 3 、模式在遗传操作下的变化 令a ( t ) 表示第t 代中串的群体，以a j ( j - 1 ，2 ，n ) 表示一代中 第j 个个体串。 ( 1 ) 选择操作对模式的作用 假设在第t 代，种群a ( t ) 中模式h 所能匹配的样本数为m ，记 作m ( h ，t ) ，一代中群体大小( 群体中个体的总数) 为n ，且个体两两 互不相同，由于一个串是以概率p i 2 恭进行选择的，其中f i 是个 体a i ( t ) 的适应度，所以模式h 在第t + 1 代中的样本数为m ( h ，t + 1 ) 为： m ( h ，t + 1 ) = 趔掣( 2 1 ) 其中f ( h ) 是模式h 所有样本的平均适应度，令群体平均适应 度为i ，其- _ g n f i j , j ： ”：( h ，+ 1 ) ：丛旦4 型( 2 2 ) f 现在假设模式h 的平均适应度一直等于群体平均适应度，且 设高出部分为c f ，c 为常数，则有： m ( h ，+ 1 ) = 丝堕上二= 7 7 2 ( h ，f ) ( 1 + f ) f 假设t = 0 开始，c 保持为常值，则有： ；9 ( h ，t + 1 ) = m ( h ，0 ) ( 1 + f ) 可见，在选择算子作用下，平均适应度高于群体平均适应度的 模式将呈指数级增长，而平均适应度低于群体平均适应度模式将呈 指数级减少。 ( 2 ) 交叉操作对模式的作用 为了说明这一点可有如下示例，采用的是单点交叉情形： a = 0 1 0 1 1 0 b = 1 0 1 0 0 1 其中b 为a 的配偶。 有模式：h 1 = * 1 * l* * o h 2 = * * *l 11 * 则a 个体既同h 1 匹配，又同h 2 匹配。 设a b 交叉点在3 ，则有： a = 0 1 00 0 1 b = 1 0 11 1 0 结果是a ，b 都不是h 1 的样本，而h 2 样本确依然存在，由于 交叉点是等概率产生，模式h 1 遭破坏( 在位置2 ，3 ，4 ，5 交叉都遭 破坏) 大大超过模式h 2 ( 只在位置4 交叉破坏) ，h 2 生命力要强于 h 1 。 一般说来，模式h 只有当交点落在定义距之外才能生存。在 单点交叉情形下，h 的生存概率为p s = 弋1 - 丁= 6 可( h ) ，而交叉本身也是 以一定的概率p c 发生的，所以模式h 的生存概率为： p s = l 胖 ( 3 ) 变异操作对模式的作用： 假定串的某一位置发生改变的概率为p m ，模式h 在变异算子 作用下，若要不受破坏，则其中所有的确定位置( 为“0 ”或1 的位) 必须保持不变。因此模式h 保持不变概率为( 1 一p m ) * o ( h ) 其 中o ( h ) 为模式h 的阶数。当p i n k 1 时，模式h 在变异算子作 用下的生存概率为： p s = ( 1 一p m ) 0 ( h ) 1 0 ( h ) p m( 2 5 ) 综合( 2 3 ) ，( 2 4 ) ，( 2 5 ) 则有： m ( h ，t + 1 ) m ( h ，t ) ( f ( h ) “) 1 一p c 6 ( h ) ( 1 1 ) 一0 ( h ) - p r a ( 2 6 ) 其中忽略了极小项( p c 6 ( h ) ( 1 1 ) o ( h ) p m ) 4 、模式定理 由公式( 2 6 ) ，可以得到下面模式定理： 定理2 1 ：模式定理( s c h e m at h e o r e m ) ：在遗传算子选择，交叉 和变异的作用下，具有低阶，短定义距以及平均适应度高于群体平 均适应度的模式在子代中将得以指数级增长。 模式定理保证了较优的模式( 遗传算法的较优解) 的样本数呈 指数级增长，从而给出了遗传算法的理论基础，其定义是深远的。 ( 二) 积木块假设： 具有低阶，短定义距及高适应度的模式称作积木块( b u i l d i n g b l o c k ) 。 正如搭积木一样，这些“好”的模式在遗传操作中，相互拼搭，结 合产生适应度更高的串，从而找到更优的可行解，这正是积木块假 设所揭示的内容。 积木块假设( b u i l d i n gb l o c kh y p o t h e s i s ) 低阶，短距，高平均适应 度的模式( 积木块) 在遗传算子作用下，相互结合，能生成高阶，长 距，高平均适应度模式，可最终生成全局最优解。积木块假设则指 出，遗传算法具备寻找到全局最优解的能力，即积木块在遗传算子 作用下，能生成高阶，长距，高平均适应度的模式，最终生成全局最 优解或近似最优解。 遗憾的是上述结论没有得到证明，所以称之为假设，但很多实 践支持积木块假设，在许多领域内应用都取得成功。 ( 三) 隐并行性( i m p l i c tp a r a l l e l i s m ) 对于一个长度为l 的串，其中隐含着2 1 个模式。对于群体规模 为n ，则其中隐含的模式个数介于2 1 和n 2 之间。 考虑由长度为l 的串所构成的规模为n 的群体。我们只考虑 那些生存概率大于p s 的模式( 其中p s 为一常数) ，即在单点交叉和 低概率变异情况下，那些丢失概率为 1 p s 的模式，因此我们考 虑那些定义距为l s ( 1 1 ) + 1 的模式。 考虑到重复计算和模式数目分布，经过数学推导可得到遗传实 际处理模式数目为：n s = ( 1 一l s + 1 ) n 3 1 4 即有n s = e n 3 = o ( n 3 ) ，其中c 为常数，由此得出结论： 遗传算法有效处理模式总数正比于群体数n 的立方，即为o ( n 3 ) 。 显然，尽管具有高阶，长定义距的模式在交叉算子和变异算子 作用下遭到破坏，尽管遗传算法实际上只对几个串个体进行运算， 但遗传算法仍然隐含处理了大量的模式，命名这一性质为隐并行 性。 第四节、遗传算法的特点和优点 遗传算法是一个利用随机化技术来指导对一个被编码的参数 空间进行高效搜索的方法，遗传算法具有十分顽强的鲁棒性，与传 统的搜索方法不同，它采用了许多独特的方法和技术，归纳起来主 要有以下几个方面： 1 、遗传算法处理对象不是参数本身，而是对参数进行编码的个 体，此编码操作，使得遗传算法可直接对结构对象进行操作。所谓 结构对象泛指集合，序列，矩阵，树，图，链表等各种一维或二维甚至 三维结构形成的对象，这一特点使得遗传算法具有广泛的应用领 域n 2 、许多传统搜索算法都是单点搜索算法，对于多峰分布的搜索 空间，常常会陷于局部的某个单峰的优解，而遗传算法是采用同时 处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评 估，更形象的说，遗传算法是并行的爬多个峰。这一特点使遗传算 法具有较好的全局搜索性能和良好的全局收敛性能。减少了陷入 局部最优解的风险，同时这使遗传算法本身也十分易于并行化。 3 、在标准遗传算法中，基本上不用搜索空的知识或其它辅助信 息，而仅用适应度函数来评估个体，并在此基础上进行遗传操作，犹 其是适应度函数不受连续可微的约束，而且其定义域可以任意设 定，对适应度函数唯一要求是，对于输入可计算出加以比较的非负 结果，这一特点使得遗传算法应用范围极为广泛。 4 、遗传算法采用概率的变迁规则来指导它的搜索方向，而不采 用确定性规则，因而能搜索离散的有噪声的多峰值复杂空间。遗传 算法采用概率规则来引导其搜索过程朝着搜索空间的更优化解区 域移动，实际上有明确搜索方向。 5 、遗传算法在解空间内进行充分的搜索，但并不是盲目的穷举 和瞎碰，适应度函数评估，为选择提供了依据，因此其搜索时耗和效 率往往优于其它优化算法。 上述这些特点使得遗传算法和其它搜索方法相比有着很多优 越性，使用简单，鲁棒性强，良好的全局搜索性，易于并行化，易于和 别的技术相融合等。从而应用范围非常广泛。 第三章遗传算法在组合最优化中的应用 第一节概述 组合优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 是遗传算法最基本的也 是最重要的研究领域之一。所谓组合优化问题是指在离散的、有限 的数学结构上，寻找一个满足给定约束条件，并使其目标函数达到 最大或最小的解。一般来说，组合优化问题通常存有大量的局部极 值，往往是不可微的，不连续的，多维的，有约束条件的，高度非线性 的n p 完全问题，因此，精确地求解组合优化问题的全局最优解一 般是不可能的。遗传算法作为一种新型的，模拟生物进化过程的随 机搜索和优化方法，近些年来在组合优化问题上显示了良好的性能 和效果，在本章中，首先介绍了基于遗传数法的组合优化方法，其次 通过旅行商( t s p ) 问题，阐述了g a 在排序这类问题上的应用，和 该算法与其它算法的比较，通过实例来分析遗传算法应用于组合优 化问题上的搜索能力。 一、基于遗传算法的组合优化的一般方法： ( 1 ) 确定群体规模n ( 参数) ，使用随机方法或其它方法产生n 个 可能解，x ；( k )( 1 i n ) 组成初始解群。 ( 2 ) 对于每一个体x 。( k ) ( 变量k 称作“代”数，初始的k = 1 ) ，计 算其适应度f ( x ；( k ) ) 。 ( 3 ) 对于每一个体x j ( k ) ，计算其生存概率p ，( k ) ： p i ( k ) ：o ! 盟 ( 厂( x ：) )z j 、j 然后设计一个随机选择器，依据p i ( k ) 以一定的随机方法产生 配种个体x ( k ) 。 ( 4 ) 产生下一代解群。选取两个配种个体x 。( k ) ，x z ( k ) ，并依 据一定的组合规则( 如交叉、变异、逆转等) 将x ，( k ) ，x z ( k ) ) 结合 成两个新一代的个体x 。( k + 1 ) ，x ：( k + 1 ) 直至新一代n 个个体形 成完毕。 ( 5 ) 重复( 2 ) 一( 4 ) 步，直至满足程序终结条件，( 如时间上的限 至) ，或解的质量达到满意的范围。 上述算法在合适条件下，其目标函数会逐代增加，并收敛到某 一最大值。 二、遗传算法关键参数确定 遗传算法参数主要包括以下参数： 1 、群体规模n ： 群体规模影响遗传优化的最终结果，以及遗传算法的执行效 率，当群体规模太小时，遗传算法的优化性能一般不会太好，而采用 较大的群体规模可以减少遗传算法陷入局部最优解的机会，但较大 规模，意味着计算机复杂度提高。一般n 从1 0 到1 0 0 之间较好。 2 、交叉概率p c ： 交叉概率p c 控制着交叉操作被使用的频度，较大的交叉概率 可增强遗传算法开辟新的搜索区域的能力，但高性能的模式遭破坏 的可能性较大；若选用交叉概率太低，遗传算法搜索可能陷入迟钝 状态，一般选取概率是从0 2 5 到1 0 0 之间。 3 、变异概率p m ： 变异在遗传算法中属于辅助性搜索操作，其主要目的是维持群 体多样性，一般，低频度的变异可防止群体中重要的单一的基因可 能丢失，高频度变异将使遗传算法趋于纯粹的随机搜索，通常取变 异概率p m 为0 0 0 1 左右。 4 、代沟g ( g e n e r a t i o ng a p ) ： 代沟g 控制着每一代群体构成中个体被更新的百分比，即在t 代有n ( 1 一g ) 个个体结构选择复制到t + 1 代解群体中。“代沟”方 式的选用为遗传算法利用优化过程的历史信息提供了条件，加速了 遗传算法的收敛过程；当代沟g 过小时，可能导函遗传算法不成熟 收敛。 三、目前常用的选择机制 在组合优化过程中，选取合适的选择机制也是有效解决组合优 化问题的关键技术之一。目前流行有以下几种选择机制： 1 、赌轮选择( v o u l e t t ew h e e ls e l e c t i o n ) 机制 该方法又称为蒙特卡洛选择机制，这是最简单，最常用的一种 选择方法，在这种机制下每一个体被选中的概率与其在环境中适应 度成正比。 j个体 l234567891 0 1 1 l 适应度 2 0o1 81 61 4121 o080 6040 20 1 | 选择机率0 1 80 1 6 o 1 501 30 1 l00 900 70 0 6o0 30 0 2o l 累计概率0 1 803 40 4 90 6 20 7 3 o 8 208 90 9 50 9 81 0 01 ，0 0 表3 1赌轮选择法的选择概率计算 上表3 1 是计算1 1 个个体的适应表，选择概率和累积概率为 了选出交配个体，需要进行多轮选择，每轮产生一个 0 ，1 的随机 数，根据该数来确定被选个体，如表3 2 所示： 轮数 123 456 随机数 0 8 103 20 9 600 10 6 5 0 4 2 表3 2 各轮的随机数 2 、最佳保留选择机制 首先按赌轮选择机制执行遗传算法的选择功能，然后把其中适 应度最高个体完整复制到下一代中去，其主要优点在于能在该算法 终止时，得到最后结果是历代出现的高适应度个体。 3 、期望值模型选择机制 这种选择机制主要要为了克服赌轮选择机制所产生的随机选 择错误而提出的，在赌轮选择控制中，由于群体规模有限等原因，使 得个体实际被选中的次数与它应选中的期望值( n f ( x ) 2 f ( x i ) ) 1 2j 之间与能存在一定误差，在期望值值模型选择机制中，先按期望值 ( n f i x ) f ( x ) ) 的整数部分安排个体被选中次数，而对其期望值 1 2j ( n f ( x ，) 2 f ( x ，) ) 的小数部分可按下述几种方式进行处理： h ( 1 ) 确定方式 将期望值( n f i x i ) 2 f i x 、) ) 小数部分按值的大小进行列表，然 后自大到小依次选择。直到选满为止。 ( 2 ) 赌轮方式 将期n n ( n f ( x i ) 2 “f ( x 。) ) 的小数部分按上述赌轮3 - 式进行 选择，直到选满为止。 ( 3 ) 贝努利试验方式 将期望值( n f ( x ) f ( x ，) ) 的小数部分作为概率进行贝努利 试验，若试验成功选择该个体，如此反复操作，直到选满为止。 4 、排序选择机制 上述几种选择机制，均以适应度为基础，个体被选择的次数与 其适应度大小成正比。但也潜伏着以下两个问题： ( 1 ) 群体中出现个别或极少数适应度相当高的染色体，这类机制 可能导致个别或极少数染色体基因在群体中迅速的遗传，造成不成 熟收敛。 ( 2 ) 另一方面，群体内个体适应度非常接近时，优化过程很容易 陷入迟钝状态。而排序选择机制，首先按个体适应度高低编号，然 后，基于所排序号，按某种规则进行的选择，排在前面的个体有较多 的选择机会。 第二节基本遗传算在t s p 中的应用 、问题提出 t s p 问题是典型的组合优化中的n p 完全问题，也就是给定几 个城市和它们两两之间直达距离，寻找一条闭合的旅程，使得每个 城市刚好经过一次，并且总的旅行距离最短。 用图论语言描术t s p ，给出一个图g = ( v ，e ) ，每边e e e 上有 非负权值w ( e ) ，寻找g 的h a m i l t o n 图c ，使得c 的总权w ( c ) = w ( e ) 最小。简言之，就是找一条最短的遍几个城市的路径，或 e l cj 者记整数子集x = 1 ，2 ，n ( x 的表示对几个城市的编号) 的一个 排列丌= v 。，v 2 ，v 。 使 ，? 一1 t d = d ( v i ，u ) + d ( u ，) i = 1 取最小值。式中d ( v i ，v ) 表示城市v i 到城市v 的距离。 二、问题实现 1 、编码与适应度函数： ( 1 ) 在求解t s p 问题的多种遗传算法中，多采用以遍历城市次 序排列进行编码。 如：串3 1 4 5 8 7 6 2 是指从城市3 开始；依次经过