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

摘要 p 3 1 3 6 3 8 本文首先介绍了遗传算法和模拟退火算法的发展历史，然后分 析了简单遗传算法和模拟退火算法的基本思想。着重就压缩遗传算 法和基因表达这两种新型的遗传算法进行讨论，分析了返两种新型 遗传算法的结构性能，并将模拟退火思想引入到这两种算法，提 了两种混合遄l j ；- 算法。结合实际- j 不同的应用问题，文q j 分别j i 上述 算法建立了求解模型，并进行了大量的仿真实验。实验结果表明， 混合算法具有较好的性能。 关键词：遗传算法模拟退火算法压缩基因 a b s t r a c t t h i s p a p e r i n t r o d u c e st h e p r i n c i p l e o f s i m p l e g e n e t i ca l g o r i t h ma n ds i m u l a t e da n n e a l i n ga l g o r i t h m t h em a i nf o c u si so nd i s c u s s i o no f t h en e w c o m p a c t g e n e t i ca l g o r i t h ma n dg e n eg e n e t i ca l g o r i t h m b a s e do n t h es t r u c t u r a lf e a t u r e so ft h o s et w o a l g o r i t h m s ，t w o m i x e dg e n e t i ca l g o r i t h m sa r ep r o p o s e d t h ee x p e r i m e n t s s h o wt h a tt h em i x e d g e n e t i ca l g o r i t h m s h a v eb e t t e r p e r f o r m a c e k e yw o r d s ：g e n e t i ca l g o r i t h m ，s i m u l a t e da n n e a l i n g a l g o r i t h m ，c o m p a c t ，g e n e 第一章概述 1 1 遗传算法的历史回顾 遗传算法早期的研究工作始于本世纪6 0 年代。5 0 年代末6 0 年 代初，一些生物学家开始利用计算机对遗传系统进行模拟。在此期 间，h o ll a n d 正在从事自适应系统的研究，受生物学家们模拟结果的 启发，他首次应用模拟遗传算子来研究适应性中的人工问题。 6 0 年代中期，h o l l a n d 开发了一种编程技术遗传算法，其基 本思想是利用类似于自然选择的方式来设计计算机程序。在软件设 讣。h 适应性足基丁监督程序的不同选择，通过不断剔除效果刁i 佳的 程序，让那些求解问题好的程序越来越占据优势，从而使系统最终 能适应任意的环境。在随后的1 0 年中，h o l l a n d 致力于创建一种能 表示任意计算机程序结构的遗传码，以拓广遗传算法的应用领域h 。 1 9 6 7 年，b a g l e y 发表了关于遗传算法的第一篇沦文，并且首次 提到了“遗传算法”这个名词。他构造的遗传算法是用来搜索下棋 游戏评价函数中的参数数集，它与我们现在应用的遗传算法很相似 其中利用了复制、杂交和变异算子。他提出在遗传算法的开始和结 束阶段需要有适当的选择率，为此，他引入了适应值比例机制，在 算法执行的起始阶段减小选择的强制性，在算法执行的后阶段增加 选择的强制性，因而，当接近群体收敛时，在类似的高适应值的串 之间保持了适当的竞争。 1 9 7 0 年，c a v i c c h i o 应用遗传算法解决了人工搜索中的两个问 题：子程序选择问题和模式识别问题。 1 9 7 1 年，h o l l a n d 完成了关于遗传算法在纯数学优化应用方面 的第一篇学术论文，主要研究了五种不同的选择方法和八种交配策 略。 1 9 7 5 年，d ej o n g 完成了他的博士学位论文a na n a l y s i so ft h e b e h a v i o ro fac l a s so fg e n e t i ca d a p t i v es y s t e m s d ej o n g 把 h o l l a n d 的模式定理和他自己细致的计算结果成功地结合在一起，他 的研究成果至今仍是遗传算法发展史上的里程碑。 到8 0 年代早期，遗传算法已在更广泛的领域中得到应用。1 9 8 3 年，g o l d b e r g 将遗传算法应用于管道系统的优化和机器学习问题，其 系统不仅用与实际系统相当的成本满足了供气要求，而且也发展了 一套分层次容错规则，它能够对管道漏洞采取适当的反应。1 9 8 4 年， f i t z p a t r i c k ，g r e f e n s t e t t e 和v a ng u c h t 利用遗传算法处理了医学 图象变换问题。 遗传算法除在数学和工程设计中有广泛的应用外，还用于处理 社会科学中的问题。8 0 年代中期，a x e l r o d 和f o r r e s t 合作研究了 一个从政治学和对策论中得出的问题一一囚犯困境游戏。 从1 9 8 5 年到1 9 9 3 年，国际上已经召开了五届遗传算法学术会 议。1 9 8 9 年，美国亚拉巴马大学的d a v i dg o l d b e r g 出版了搜索、优 化和机器学习中的遗传算法一书，为本领域研究奠定了坚实的科学 基础。1 9 9 1 年，l a w r e n c ed a v i s 出版了遗传算法手册，对有效地应 用遗传算法具有重要的指导作用。 进入g o 年代后，遗传算法作为一种实用、高效、鲁棒性强的优 化技术，得到了极为迅速的发展，在各种不同的领域如机器学习、 模式识别、神经网络、控制系统优化及社会科学等领域得到了广泛 的应用，引起了许多学者的关注。在最近的人工生命、遗传编程、 进化策略、进化计算等领域都是将遗传算法与计算机技术相结合， 试图模拟自然界的自适应、自组织和再生能力，设计出具有“生命” 的人工系统。 国内对于遗传算法的研究也比较多，集中在基本遗传算法及其 改进方面做了许多工作，已开发出许多应用系统【1 2 】 ”】 测。 1 2 遗传算法的描述和特点 在应用遗传算法求解问题之前，要完成以下四个步骤： 1 确定表示方案； 2 确定适应值度量； 3 确定控制算法的参数和变量： 4 确定指定结果的方法和停止运行的准则。 在常规的遗传算法中，表示方案是把问题的搜索空间中每个可能 的点表示为确定长度的特征串。表示方案的确定需要选择串长i 和 字母表规模k 。二进制串是遗传算法中常用的表示方法，在染色体串 和问题的搜索空间中的点之间建立映射。 适应值度量为群体中每个可能的确定长度的特征串指定一个适应 值，适应值度量必须有能力计算搜索空间中每个确定长度的特征串 的适应值。 控制遗传算法的主要参数有群体规模n 和算法执行的最大代数目 m ，次要参数有复制概率p r 、杂交概率p c 和变异概率p m 等参数。 一旦这些准备步骤完成，就可以执行遗传算法，主要步骤如下： 1 编码，将待求解问题的变量按某种方式编码成一个定长的字 符串，每个字符串分剐代表原问题的一个解。 2 随机产生一个由确定长度的特征串组成的初始群体。 3 对串群体迭代地执行下面的步a 和步b ，到满足停止准则： a 计算群体中每个个体的适应值：一般取目标函数作为适应 度函数。 b 遗传操作。应用复制、杂交和变异算子产生下一代群体。 复制：将已有的优良个体复制后添入新群体中，删除劣质 个体； 杂交：将选出的两个个体进行交换，所产生的新个体添入 ， 新群体r 一| = l ； 变异：随机地改变某一个体的字符后添入新群体中。 4 把在任一代中出现的最好的个体串指定为遗传算法的执行结 果，这个结果可以表示为问题的一个解或近似解。 从数学角度看，遗传算法是一种搜索寻优技术，它从某一初始 群体出发，遵循进化规则，不断迭代计算，逐步逼近最优解。遗传 算法具有如下特点： 1 搜索过程不直接作用在变量上，而是作用在将变量编码后的 字符串上； 2 智能式搜索。遗传算法的搜索策略，既不是盲目式的乱搜索， 也不是穷举式的全面搜索，它是有指导的搜索。其指导依据是其适 应度，利用适应度，使遗传算法逐步逼近目标值； 3 逐步优化。遗传算法利用复制、杂交、变异等操作，使新一j 代的群体优于旧一代，通过不断迭代，逐渐得出最优解，其优化过 程具有渐进性； 4 全局优化。遗传算法由于采用杂交、变异等操作，产生新的 个体，扩大了搜索范围，使得搜索得到的优化解是全局最优解； 5 隐含并行性，遗传算法从初始群体出发，经过复制、杂交、 变异等算子，产生新的群体，其每次迭代计算，都是针对一组个体 同时进行，而不是针对某个个体进行，由于采用这种并行计算机理， 故其搜索速度较高； 6 通用性强。遗传算法对搜索空间没有特殊要求，它只研究输 入与输出的数量关系，并不深究造成这种关系的原因，也不要求求 解问题有明确的数学方程及导数表达式，因此便于处理各利，因果关 系复杂的问题，算法通用性强，可应用于离散问题及函数关系不明 确的复杂问题。 7 可扩展性。遗传算法利用随机规则而不是确定性规则来引导 搜索，而且遗传算法易于同别的技术结合使用，容易介入到已有的 模型中，具有可扩展性。 1 3 遗传算法的研究概况 遗传算法是多学科结合与渗透的产物，它已发展成一种自组织、 自适应的综合技术，广泛应用在计算机科学、工程技术和社会科学 等领域。遗传算法的研究工作主要集中在如下几个方而： 1 、基础理论 研究遗传算法进一步发展的数学和生物学基础，从理论和实验 上研究它们的计算复杂性，更深入地探讨遗传算法的机理。 在基础理论方面，人们根据算法的适用性对问题的类型进行了 划分。尽管遗传算法不能保证在多项式时间内找到n p 完全问题的最 优解，然而它经常能找到组合问题很好的次优解。w i l s o n 比较了遗 传算法易解函数与可通过每次改变一位来优化的函数之间的不同。 m a s o n 将遗传算法不容易处理的函数定义为“欺骗”函数。v o s e 利 用模式的扩展形式分析了遗传算法“欺骗”函数。 2 、性能分析 在遗传算法中，群体规模、遗传算子的概率等控制参数的选取 是必不可少的，但实验往往也非常困难，同时遗传算法还有一个过 早收敛问题，研究群体规模和遗传算子的控制参数的选取，怎样阻 止遗传算法的过早收敛问题是目前遗传算法研究的内容之一。 在遗传算法模型方面，人们为了提高遗传算法的搜索能力，提出 了几个扩展的遗传算法模型。关于遗传算子，s y s w e r d a 提出了一致 杂交算子，它是随机地交换位序列来保持群体的多样性。e s h e l m a n 提出通过阻止类似的个体之间的杂交来防止过早的收敛。w h i t l e y 提 出了“6 编码”方法，通过对远离一些先前的局部解的距离进行编 码来找到更精确的解。 3 并行遗传算法 遗传算法在操作上具有高度的并行性，许多人都在研究在并行 机和分布式系统上高效执行遗传算法的策略。对并行遗传算法的研 究表明，只要保持多个群体和恰当地控制群体间的相互作用来模拟 并行执行过程，即使不使用并行计算机，我们也能提高算法的执行 效率。 4 、结构优化设计 通常，工程技术的优化设计包括结构优化及参数优化，对于结 构优化，还缺乏成熟、有效的方法。近年来，人们应用遗传算法， 成功地解决了房屋桁架结构、飞机结构组成、电力通讯网络结构等 结构性问题。 5 、人工智能 专家系统、人工神经网络、遗传算法已成为人们处理人工智能 问题的三个有力工具。遗传算法在博弈对策、机器人控制、自动程 序设计、知识工程等方面正发挥越来越重要的作用。 6 、复杂问题优化和复杂系统分析 由于遗传算法不要求有明确的数学表达式，因此它是解决非线 性、多目标、不确定性问题的一种重要方法。多年来，人们应用遗 传算法从事聚类分析、模式识别、图像处理、高度组织等工作，将 表面上杂乱无章的问题条理化。 7 、分类系统 分类系统属于基于遗传算法的机器学习中的一类，它包括一个 简单的基于串规则的并行生成子系统、规则评价子系统和遗传算法 子系统，它是遗传算法研究中的一个非常活跃的领域。 另外，遗传算法在优化神经网络的连接权系数和网络的空间结 构、机器学习中的程序设计等方面也有着广泛的应用。 但是，任何一种算法都是有其优缺点的，遗传算法在下面这些 方面还有待于进一步完善： 1 编码技术和程序表达技术的改进； 2 遗传算子及遗传操作的改进： 3 适应度的表达和计算的改进； 4 与其它算法的结合应用。 1 4 模拟退火算法描述及特点 模拟退火算法( 简称s a ) 的思想及其在组合优化问题上的应用是 由k i r k p a t r i c k ( 3 】等人首先提出的。在算法中，利用一个称为温度的 控制参数控制最值搜索过程。在此过程中，成本函数的均值和方差要 随温度的递减而递减，为了避免限于局部最小值，当成本函数值比 原来还大时，则以概率p 来决定是否接收。在理论上，s a 随温度的 递减生成一系列马尔可夫链，在每一温度下，算法重复执行，直到 整个体系的概率分布达到了波尔兹曼分布。如果温度的递减足够慢， 那么波尔兹曼分布将收敛于均匀分布。可以证明当马尔可夫链是无 限长时，算法最后能以概率1 得到最优解，但由于实际中马尔可夫 链是有限长的，所以收敛过程只能近似。由此，模拟退火算法不能 保证以1 的概率找到全局最小值。近年来，许多研究人员致力于设 计一种性能较优的退火模型或一种并行模拟退火算法，在要求的误 差内以合理的时问求得近似最优解，但实际上，很难设计出这样的 在质量和时问上同时优化的退火模型。 模拟退火算法有如下优点： 1 、高效性 之所以讲模拟退火算法有高效性，是由于它与局部搜索算法相 比，模拟退火算法可望在较短时间里求得更优近似解，另外，模拟 退火算法允许任意选取初始解和随机数序列，又能得出较优近似解， 因此应用算法求解组合优化问题的前期工作量大减少。 7 2 、健壮性 模拟退火算法的实验性能不因优化问题实例的不同而蜕变，具有 一定的健壮性。 但模拟退火算法也有不足之处，主要有：返回一个高质近似解的 时间花费较多，当问题规模不可避免地增大时，难于承受的运行时 间将使算法丧失可行性。这些都有待进一步改进。 1 5 本文的主要工作 近年米，以h o l l a n d 提出的基本遗传算法为框架，不少学兹都在 探索新型的遗传算法。一个明显的趋势是研究基于基因表达的遗传 算法悖i ；与之相关联的另一趋势是寻找压缩群体规模的遗传算法，分 析这种算法求解问题的可能性 2 。本文的主要工作是讨论这两类算法 与模拟退火算法结合的性能。 本文分析了压缩遗传算法及基因表达遗传算法，f ：将模拟遐火 算法引入压缩遗f 譬算法和基因表达遗传算法，提i l _ j 了新的结合算法， 为遗f 譬算法的研究提供了新的途径和方法。研究这些混合算法的应 用，对求解非线性、多模型、多目标函数的优化问题和组合优化问 题部有积极意义。 本文结合基本的遗1 0 算法，在以下儿个方面做了。些工作： l 、分析了压缩遗传算法的性能； 2 、提i 【 了基丁模拟退火的压缩遗传算法； 3 、分析了基冈表达遗传算法： 4 、提出了模拟退火和基因表达结合的遗传算法； 5 、利用上述算法，对o n e m a x 测试问题和图划分问题进行了实 验和分析。 上述研究分析与实验_ l i 4 = 对混合遗传算法的研究具仃一定的理论 r 和实际应用意义。 第二章遗传算法和模拟退火算法分析 2 1 遗传算法的基本结构与运行机理 2 1 1 基本遗传算法概述 遗传算法( 简称为6 a ) 是1 一釉自适应启发式群体型迭代式的全局 搜索算法，它模拟了自然进化过程，应用适者生存的原理，使优胜 个体的遗传信息能够复制綮衍下来。算法中引入了“个体”的概念 ( 也称为解或染色体) ，一个解空间是由许多个体组成的，称之为“群 体”。g a 是个反复执行一系列遗传操作的过程，包含随个步骤，即 评价适应度和生成下一代群体。评价过程是对每个个体对应的评价 函数的计算，求得对应的适应度值来评价个体的性能。生成下1 一代 群体的过程中有选择和杂交、变异等操作，选择较好适应度的个体， 进行这些遗传操f 4 ：后，生成的新个体将组成下一代群体，且j f 均适 应j 叟要优丁| 。代，经过多次这样的繁衍过程，最后得到的群体一1 卜 终会钶较好的个体存在。 进行遗传操作的基本对象是染色体。每个染色体是一个知识结 构，代表所要求解问题的一个可能解，染色体通常用字符串或位串 表示，若干长度的串称之为构成染色体的基因。 通常用遗传算法解决问题的主要过程为：( 1 ) 编码表示刚题； ( 2 ) 初始化，构造初始群体；( 3 ) 计算群体中每个个体的适应值： ( 4 ) 对每个个体讨算其生存概率，然后设计一个随机选择策略；( 5 ) 进行复制、杂交、变异等操作；( 6 ) 停止准则。遗传算法循环执行 计算适应值、选择复制和应用杂交和变异算予这几个步骤，直到满 足某个停止准则。例如算法已找到了一个可以接受的解，或已迭代 了预置的次数。 g a 中常用的遗传算子说明如下： a 选择( s e l e c t ) g a 中一般采用的是淘汰赛法选择，按序选择固定个数的个体， 比较它们的适应度值，选择其中具有最大适应度的个体作为双亲中 的一个，同样方法再选取另一个，为了使选择有较大的随机性，可 在每个个体都参加过竞赛后对群体进行两次随机排序。 b 杂交( c r o s s o v e r ) 随机产生一个交叉点，此交叉点把两个被选双亲都分成两个子串， 交叉交换子串可得到俩个子体。杂交操作只交换了双亲的部分遗传 信息，并没有产生新的因子。 c 变异( m u t a t i o n ) 随机产生几个变异点，改变变异点的遗传信息，在二进制编码 中，即把0 变为1 ，把1 变为0 ，此变化可产生新的因子，由此产生 新的个体。 d 倒置( i n v e r s i o n ) 这个操作改变串的排列顺序也即改变了个体结构。 2 1 2 遗传算法的运行机理分析 遗传算法的运行过程较为简单，但它的整体行为是复杂的，e 主要问题是：遗传算法的全局收敛性、全局收敛的概率不稳定性、 以及遗传算法的搜索效率。目前，这些问题都是由h o l l a n d 提出的 模式定理来解释的。 在进化系统理论的的形式模型中，基因定义基因型空间g s ，表 现型定义表型空间p s 。 g s = g = ( a l ，a 2 ，) ，a i a i p s = p = ( p 1 ，p 2 ，p 。) ，p i i r 其中g 是基因型，p 是表型，基因g i 的可能值称为等位基因， 在m e n d e l 遗传学中，假设每个基因有有限数的等位基因，进化的过 程图如下： 遗传操纵子后生环境选择环境 假设给定后生环境：e p = e p l ，e p 2 ，e r ) 和变换函数f ：g s e p - - p s p = ( g 。e p ) 这个变换函数说明表型的发展是通过基因与环境的交互作用， 且变换过程是高度非线性的。质量函数q 给出了具体选择环境e s i 下 表型的质量，其定义如下： q ( p ，e s i ，t ) - * i r + 下面，我们以m e n d e l 遗传学的选择模型为例说明遗传算法的寻 优原理 1 。 为简明起见，假设一个基因具有n 个等位基因，a 。，a 2 ，a 。 定义p ；j 为总群体中基因型( a 。，a j ) 的频度，同时假定基因型与表型 相等，质量函数给每个表现型赋值 q ( a i ，a j ) = q i j 其中q 。；可以理解为出生率减去死亡率。 假设q ，j 是下一代表型( a i ，a 3 ) 的频度，然后达尔文选择依据 选择方程调整型的分布 上式中q 是群体的平均适合度。设p i 是群体中等基因的频率。 如设p i , j = p j j ，那么，我们得到在g s 中的一个选择方程： m = p , q 。而 1 9 = q 毋 l ， 这个离散的选择方程可以用连续方程近似 粤= ，】，( 9 一一q ) q d f 如果q 。i = q j i ，那么 掣= p ( 9 一百) c l t 这个方程可以证明以下结果 警= 2 ( 地2 ) 一百2 ) = 2 v a r ( o ) 2 0 这就是遗传算法中称为f i s h e r 的基本定理。它充分说明s f 均适 合度随着适合度的差别成正比例增加，而平均适合度的增加就意味 着解的优良性能在不断提高。 2 2 1 概述 2 2 模拟退火算法 芋 p。 = 一一 在已知的求解大规模组合优化问题的近似算法中，除局部搜索 算法外，这些算法都是仅适用于某类组合优化问题的专用算法，如 最近邻法只适用于货郎担问题。此外，这些算法得到的近似解的质 量通常较差，算法的时间复杂性也往往是指数阶的。局部搜索算法 虽然是一种通用的实用近似算法，但算法终止在某个局部最优解上， 而且最坏情况下的时间复杂性是未知的。因此，依据纯数学思维已 不可能构造出求解大规模组合优化问题的高质通用的近似算法。 对固体退火过程的研究给人们以新的启示。1 9 8 2 年，k i r k p a t r i c k 等首先意识到固体退火过程与组合优化问题之间存在的类似性， m e t r o p o l i s 等对固体在恒定温度下达到热平衡过程的模拟也给他们 以启迪：应该把m e t r o p o l i s 准则引入到优化过程中来，最终他们得 到一种对m e t r o p o l i s 算法进行迭代的组合优化算法，这种算法模拟 固体退火过程，称之为“模拟退火算法”。 设组合优化问题的一个解i 及其目标函数f ( i ) 分别与固体的一 个微观状态i 及其能量e i 等价，令随算法进程递减其值的控制参数 t 担当固体退火过程的中的温度t 的角色，则对于控制参数t 有每一 取值，算法持续进行“产生新解一判断一接受舍弃”的迭代过程就 对应着固体在某恒定温度下趋于热平衡的过程，也就是执行了一 次m e t r o p o i i s 算法。与m e t r o p o l i s 算法从某一初始状态出发，通 过计算系统的时间演化过程，求出系统最终达到的状态相似，模拟 退火算法从某个初始解出发，经过大量解的变换后，可以求得给定 控制参数值时组合优化问题的相对最优解。然后减小控制参数t 的 值，重复执行m e t r o p o l i s 算法，就可以在控制参数t 趋于零时，最 终求得组合优化问题的整体最优解。由于固体退火必须“徐徐”降 温，才能使固体在每一温度下都达到热平衡，最终趋于能量最小的 基态，控制参数的值也必须缓慢衰减，才能确保模拟退火算法最终 趋于组合优化问题的整体最优解集。 模拟退火算法用m e t r o p l i s 算法产生组合优化问题解的序列， 并由与m e t r o p o l i c 准则对应的转移概率p 。 f1 ! 扩( f ) ，( 氓 p 2 7 2 e x p ( 2 ：垡l ：j z 盟) ， 否则 2 2 - 1 确定是否接受从当前解i 到新解j 的转移。上式中的t r + 表示 控制参数。开始让t 取较大的值( 与固体的熔解温度相对应) ，在进 行足够多的转移后，缓慢减小t 的值( 与“徐徐”降温相对应) ，如 此重复，直至满足某个停止准则时算法终止。因此，模拟退火算法 可视为递减控制参数值时m e t r o p o l i s 算法的迭代。 假定存在邻域结构和产生器，再设t k 表示m e t r o p l i s 算法第k 次迭代时控制参数t 的值，l k 表示m e t r o p li s 算法第k 次迭代时产生 的变换个数，则模拟退火算法可以用类p a s c a l 语言描述如下： p r o c e d u r es i m u l a t e d a n n e a l i n g ： b e g i n i n i t i a l i z e ( i 0 ，t o ，l o ) ： k ：= o i ：= i o r e p e a t f o r1 ：一t o l k d o b e g i n g e n e r a t e ( j f r o ms i ) ： i ff ( i ) f ( i ) t h e ni ：- - j e s e 产 盟 c a l c u l a t e l e n g t h ( l k ) ： c a l c u l a t e c o n t r o l ( t k ) u n t i1 s t o p c r i t e r i o n e n d ： 模拟退火算法依据m e t r o p o l is 准则接受新解，因此除接受优化解 外，还在一个限定范围内接受恶化解，这正是模拟退火算法与局部搜 索算法的本质区别所在。开始时t 值大，可能接受较差的恶化解； 随着t 值的减少，只能接受较好的恶化解；最后在t 值趋于零值时， 就不再接受任何恶化解了。因此，对大多数组合优化问题而言，模 拟退火算法要优于局部搜索算法。 此外，模拟退火算法的收敛速度显然取决于参数t 。和 k ( k = o ，1 ，2 ) 的选择，保证算法收敛于整体最优解集分布，参数值 的控制非常重要。 2 2 2 模拟退火算法的特性 2 。2 2 1 模拟退火算法的统计特性 运用平衡态统计理论，可以分析模拟退火算法的总特性 1 引。 假设2 2 1 给定组合优化问题的某个实例( s ，f ) 和一个适当的邻 域结构，则在固定t 值时产生足够多的变换，运用式( 2 2 1 ) 的转移概 率后，模拟退火算法将找到一个解i s 的概率是 p - x - - i 兰州t ) - 志e x 砰) ， 其中x 是表示模拟退火算法所得当前解的随机变量，而 n o ( t ) 2 e x p ( 一半) ( 2 2 3 ) 表示归一化因子。 ( 2 2 3 ) 式的概率分布称为平衡分布，等价于g i b b s 正则分 布，归一化因子n o ( t ) 等价于系统的配分函数z 。 推论2 2 1 给定组合优化问题的某个实例( s ，f ) 和个适当 的邻域结构，并设平稳分布由式( 2 2 2 ) 给定，则 ( t ) 2 南k 】( f ) ， ( 2 - 2 4 ) 义为 其中s 。，表示整体最优解的集合，x ( 。o p t ) ( i ) 是i 的特征函数，定 s _ 0 ，1 ) ，k ) 2 器胬 这个推论的涵意是：若在每个t 值都达到( 2 2 2 ) 式的平衡分布， 则模拟退火算法渐近收敛于整体最优解集。下面给j i ；沦2 1 的证 明。 证明因为对v a 0 ，有 。x ：l 幸钿= o ”萨 1 0 若口 。= _ 1 厂( 嘎 1 6j ，e 8 t = f 。 ( 2 2 1 1 ) ( 2 2 1 2 ) m l i r a 口；兰盯o l ；善( 巾h ，( 2 2 1 3 ) o2 - o s t 岂s 。= l n l s 。l i l r 。s t 兰s o = l n s 。 ( 2 2 1 4 ) ( 2 2 1 5 ) ( 2 2 1 6 ) 推论2 2 2 和2 2 3 的证明与推论2 2 1 的类似。推论2 2 2 和2 2 3 的涵义是：若在t 的每个值都达到( 2 2 2 ) 式的平稳分布， 则在模拟退火算法执行期间，期望目标函数和熵分别单调减少至其终 值f 州和l n k f 推论2 2 4 设( s ，f ) 表示组合优化问题某个s 。s 的实例，并设 q 。( t ) 表示与模拟退火算法相关并由( 2 3 2 ) 式给定的平稳分布，则 ( 1 ) v f 5 。，有晏吼( f ) f ；啪) o ； ( 3 ) v ，( d “厂 。，贝, j 3 t ， o 使 0 若， t = 0f = t f ( 2 2 1 7 ) ( 2 2 1 8 ) ( 2 3 1 9 ) 推论2 2 4 给出( 2 2 2 ) 式的平稳分布对控制参数t 的依赖关系。 2 0 ，liui【 由推论2 2 4 可知，模拟退火算法找到一个整体最优解的概率随t 的减小而单调增大；且对于每个非整体最优解，都存在控制参数的 一个确定值t 。，使得t 时找到该非最优解的概率值t 的减小而单调 减小。 综上所述，模拟退火算法的总特性可以归结为： ( 1 ) 若在每个t 值都达到( 2 2 2 ) 式的平稳分布，则模拟退火算 法渐近收敛于整体最优解集； ( 2 ) 在模拟退火算法执行期间，随着控制参数t 值的减小，算法 返回某个整体最优解的概率单调增大，返回某个非最优解的概率单 调减小。 2 2 2 2 模拟退火算法的典型性态 期望目标函数 ；和目标函数方差砰的某些特性： a 对于大的t 值，目标函数的平均值和分布几乎是不变的，分别 等于 。与d 。，这正是( 2 ，3 。1 3 ) 式所描述的特性在大的t 值时， 目标函数的平均值和分布被预期为常数： b 。可以看出，存在控制参数的一个阈值t 。使得 t l z 2 1 ( 。+ 岛) ， ( 2 2 2 3 ) 一艇等i ( 2 2 2 4 ， 而且t 大致上是x ( t ) = 0 5 时的t 值。 2 2 3 性能分析 a 在退火过程中，我们不是通过一系列测试来优化参数，而是动 态改变参数，所以设计出的解决n p 难题的退火模型有很大的灵活性， 不仅增大了找到近似最优解的可能性还减少了运行时间，也就是说， 它在解的质量和时间耗费上进行了折衷，得到了较好平衡。另外，运 2 l 行时间还受温度下降比率的影响。 b 如果温度下降得太急速，则很容易陷入局部最优解。 c 在每一温度下检测系统是否平衡并不容易，由此马尔可夫链 的长度较能控制。 d 初始温度对算法的重复执行数有影响，如果在低温度区域内 重复执行算法的次数太少，有可能得不到最好解。 e 由于每次只对一个点进行操作，搜索过程较缓慢。 模拟退火算法可看作是对局部搜索算法的一种改进。这鼹种算 法在算法描述、邻域结构以及局部性态方面，有很多类似之处；它 们的执行过程可以构造成相同的随机搜索模式，面当模拟退火算法 中的控制参数取为零值时，两者的搜索过程就完全一致了。因而在 分析模拟退火算法的实验性能时，以局部搜索算法为参照系是最为 恰当的。此外，鉴于局部搜索算法在求解组合优化问题中的成功， 这种选择理应成为模拟退火算示实验性能的试金石。 由从局部搜索算法可知，局部搜索算法从初始解i = i 。开始，在 当前解i 的邻域s ：按接受准则f ( j ) f ( i ) 搜索一个更优解j 。如果在 s 。中找不到更优解，则算法终止。反之，只要找到一个更优解j ，就 使之成为新当前解并从这个新解出发重复邻域搜索过程。算法返回 的近似最优解是当前解邻域中的局部最优解。 在模拟退火算法中，对t 的每一取值进行的所有迭代过程构成 一个马尔科夫链，l k 是m e t r o p o l i s 算法第k 次迭代时的马尔科夫链 的长度。控制参数t 的初值t o 和衰减函数a 饥= 口) ，k 以及停止 准则所规定的控制参数的终值构成控制算法有限时执行的冷却进度 表。在实际应用中，停止准贝l j 常简化为：在相继的若干个马尔科夫 链中解无变动时终止算法。因此，模拟退火算法从初始解i = i 。开始， 在当前i 的邻域s i 中按m e t r o p o l i s 接受准则搜索取代当前解的新 解j 。在每个马尔科夫链中搜索过程是在m ( 1 m l 。) 个解的邻域 中的进行的。算法返回的近似最优解在最后一个马尔科夫链的l 。个 解中是最优的。 对照两种算法不难发现，两者的本质差异是不同的接受准则和 停止准则。由于算法的整体性态被算法进程的始点、方向和终点唯 一界定：在邻域结构和随机数序列给定的前提下，初始解确定始点， 接受准则控制方向，而停止准则限定终点。因此设两种算法采用同 一邻域结构，在同一随机数序列的同一起点上以同一初始解开始算 法进程，但进程方向和终点却会迥然不同。 局部搜索算法的接受准则使算法进程方向单驱直入，即从初始 解开始，沿逐次更优的方向直至停止准则限定的某个局部最优解。 除进程方向将初始解导引到整体最优解的极特殊情况外，最终解的 质量与初始解的质量间存在某种相依关系。在随机选取初始解的情 况下，最终解的质量是无从保证的。 而在模拟退火算法中，m e t r o p o l i s 接受准则引入了新的随机因 素，使算法进程方向呈现跳跃性而可能跳离局部最优的“陷井”。最 终解对初始解的依赖性化解了，最终解的质量也因而趋于稳定。停 止准则则将最终解限定为最后一个马尔科夫链中k 个解的最优解。 此外，由随机数序列、接受准则和停止准则确定的搜索范围及 其分布对算法最终解的质量也有重要影响。局部搜索算法的搜索范 围在蚓一训m 个解之间，这些解可能分布在卜h 个解的邻域中。而 模拟退火算法的搜索范围是厶个解，这些解可能分布在i - e l , 个 解的邻域中。冷却进度表确跫模拟退火算法的迭代次数k 以岌马尔 科夫链的长度k ，直接影响最终解的质量。 算法的时间复杂性可用算法执行的比较次数确定。对于局部搜 索算法的平均情况，时间复杂性以问题规模n 的多项式为界，面最 坏情况的时间复杂性是未知的。由于冷却进度表的控制作用，模拟 退火算法的时间复杂性是0 ( k l 。t ( n ) ) ，其中k 为迭代次数，l 。是k 个马尔科夫链中的最大长度，t ( n ) 是问题规模1 - 1 的多项式函数。 综上所述。模拟退火算法无论在最终解的质量及其对初始解的 依赖上，还是在时问复杂性上都要优于局部搜索算法。 2 3 小结 遗传算法是一种遵循进化规则的搜索寻优技术，它的搜索过程不 直接作用在变量上，而是作用在编码字符串上，具有通用性强，可扩 展，智能搜索的特点。但是当问题的规模不可避免地增大时，遗传 算法的优势就不明显了，特别是在编码的长度增长上，因此编码技 术是个有待进步研究的问题。另外，遗传算法最后的解的质最 也有待进一步改进。 模拟退火算法具有高效、健壮、通用、灵活的特性。与局部搜 索算法相比，模拟退火算法可望在较短时间里求得更优近似解。模 拟退火算法允许任意选取初始解和随机数序列，又能得出较优近似 解，因此应用算法求解组合优化问题的前期工作量大大减少。 在可能影响模拟退火算法实验性能的诸因素中，问题规模n 的 影响最为显著：i 1 的增大导致搜索范围的绝对增大，会使c p uh , j 问增 加相对于解空间而言，搜索范围又因i 2 的增大而相对减小，将引 起解的下降，但s a 的解和c p u 时间均随f i 增大而趋于稳定，且不受 初始解和随机数序列的影响。 模拟退火算法能应用于多种组合优化问题，为一个问题编制的 程序可以有效地刚r r 其它问题。 模拟退火算法也存在不足之处，主要是：返回一个高质近似解 的时间花费较多，当问题规模不可避免地增大时，难于承受的运行 时间：i j _ 使算法丧失可行忭。| 天| 此，必须探求改进算法实验性能、提 高算法执行效率的可行途径，它可能有： 1 选择适当的邻域结构和随机数序列可以提高解质并缩减运行 时间，这需要大量试验。 2 4 2 选择合理的冷却进度表可使算法的执行过程更为有效。 3 模拟退火算法的执行过程是一系列“产生新解判断 接受舍弃”的迭代过程，提高各个环节的时效可以缩减运行时间而 不会影响最终解的质量。 4 改变算法进程的各种变异方法，如有记忆的s a a ( 记取算法进 程中的最优近似解) 、回火退火法( 在解质不能改进时使控制参数值 增大以跳离“陷井”) 、加温退火法( 先升温后退火) 等。 5 大规模并行计算能够真正缩减算法运行时间。 6 建立与其它算法相结合的混合算法 下面我们讨论的就是将模拟退火算法引入到几种遗传算法后的混 合算法，实验分析表明，混合算法具有较好的性能。 第三章基于模拟退火的压缩遗传算法研究 3 1 压缩遗传算法 3 1 1 概述 压缩遗传算法( 简称c g a ) 的概念最早