（应用数学专业论文）改进的遗传算法求解tsp问题.pdf

重庆大学硕士学位论文 中文摘要 摘要 遗传算法是一种模拟自然界生物进化的搜索算法，由于它简单易行、鲁棒性 强，尤其是不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程，从 而使它的应用范围极为广泛，并且已在众多领域得到了实际应用，取得了令人瞩 目的成果，引起了广大学者和工程人员的关注。 t s p 问题是一个典型n p 难题，具有广泛的应用，多年来一直是学者们研究的 热点。由于大多数学者认为n p 问题不存在多项式时间内的完全算法，因此设计 t s p 问题的近似算法具有非常重要的意义。t s p 问题还成为了衡量近似算法效率 的主要标准。 本文对遗传算法的理论与应用进行了一些研讨。首先介绍了遗传算法的基本 原理及其应用，其次分析了t s p 问题的研究现状、数学模型、求解方法等，最后 在标准遗传算法的基础上提出了改进的遗传算法。针对t s p 问题的特点，在遗传 算法的交叉过程中对边的邻接状况采用了新的评价标准，结合顺序交叉算子和贪 婪策略，本文设计提出了两种新的交叉算子：顺序插入交叉算子与动态顺序插入 交叉算子，它们有效地利用了局部信息，并且能很好地继承父代的优秀基因段，实 例仿真表明了该算法的可行性和有效性。 关键词：t s p 问题，遗传算法，顺序插入交叉，动态顺序插入交叉 重庆大学硕士学位论文英文摘要 a b s t r a c t t h eg e n e t i ca l g o r i t h mi sak i n do fs e a r c h i n gm e t h o dw h i c hs i m u l a t e st h en a t u r a l e v o l u t i o n ri ss i m p l ea n de a s yt oi m p l e m e n t , e s p e c i a l l yi td o e s n tn e e dt h es p e c i a lf i e l d k n o w l e d g e , s oi th a sb e e nu s e di ne v e r yb r o a df i e l d s n o wt h eg e n e t i ca l g o r i t h mh a sg o t al o to f f i u l t sa n dm o r es c h o l a r sb e g i nt op a ya t t e n t i o nt oi t t r a v e l i n gs a l e s m a np r o b l e mi sar e p r e s e n t a t i v en p h a r dp r o b l e m i th a sv e r y i m p o r t a n ta c a d e m i cs i g n i f i c a n c ea n da c t u a la p p l i c a t i o nv a l u e s o i ti sar e s e a r c hh o t s p o t f o rs e v e r a ly e a r s m a n ys c h o l a r sb e l i e v et h e r ei sn op o l y n o m i a lt i m ec o m p l e t e n e s s a l g o r i t h mf o rt h en pp r o b l e m , t h e r e f o r et h ea p p r o x i m a t ea l g o r i t h mi sp r o v i d e dw i t h v e r y i m p o r t a n t m e a n i n g t h e t s p b e c o i r l e s a c h i e f c r i t e r i o n f o r m e a s u r i n g t h e e f f i c i e n c y o f t h ea p p r o x i m a t ea l g o r i t h m t h i sp a p e rh a sd o n es o m ew o r ki nt h er e s e a r c ha n da p p l i c a t i o no ft h eg e n e t i c a l g o r i t h m f i r s t ，t h ei n t r o d u c t i o no ng a st h e o r ya n di t sa p p l i c a t i o n s s e c o n d ，w es t a t e t h eh i s t o r ya n dt h ep r e s e n ts i t u a t i o n , m a t hm o d e l s ，a n dt h es o l u t i o n a tl a s t , w ep r e s e n t t h ed e v e l o p m e n to ng e n e t i ca l g o r i t h mt os o l v et s p a c c o r d i n gt ot h et s pc h a r a c t e r , t w o n e wc r o s s o v e ro p e r a t o r , o r d e ri n s e r tc r o s s o v e ro p e r a t o ra n dd y n a m i co r d e ri n s e r t c r o s s o v e ro p e r a t o ra r ed e s i g n e d , w h i c hc o m b i n eo l d e ri n s e r tc r o s s o v e ra n du s e st h e g r e e d ys e l e c t i o ns t r a t e g yi nt h ec r o s so ft h eg e n e t i ca l g o r i t h m t h e s eo p e r a t o ra r e c o n d u c t e du s i n gt h el o c a li n f o r m a t i o ne f f e c t i v e l ya n di n h e r i t i n ge x c e l l e n tg e n ef r o mt h e p a r e n t s i th a sb e e np r o v e de f f e c t i v et h r o u g ht h eo p t i m i z a t i o nc o m p u t i n go fs o m e e x a m p l e k e y w o r d s ：t r a v e l i n gs a l e s m a np r o b l e m ，g e n e t i ca l g o r i t h m ，o r d e ri n s e r to f o s s o v e r o p e r a t o r ，d y n a n l i co r d e r i n s e r tc r o s s o v e ro p e r a t o r 独创性：声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重麽太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：烈1 海荡 签字日期： 四7 年月乡日 学位论文版权使用授权书 本学位论文作者完全了解重麽太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重麽太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( v ) 。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名： 孙海器 签字日期： q7 年6 月尹日 导师签名：咖睁矜 签字日期： 0 7 年d 月够目 f 重庆大学硕士学位论文1 绪论 1 绪论 1 1 研究背景 1 1 1 遗传算法 近年来，随着人工智能应用领域的不断扩大，传统的基于符号处理机制的人 工智能方法在知识表示、信息处理和解决组合爆炸等方面所遇到的困难越来越明 显，从而使得寻求一种适合于大规模问题并具有自组织、自适应、自学习能力的 算法成为有关学科的一个研究目标。大自然为我们解决各种问题创造了灵感，遗 传算法( g a n c t i ea l g o r i t h m ，简称g a ) 就是jh o l l a n d 于1 9 7 5 年受生物进化论的 启发而提出的。 在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解 或准最优解，典型的n p 完全问题就是一例。在求此类问题时，若不能利用问题的 固有知识来缩小搜索空间，很容易产生搜索的组合爆炸。因此研究在搜索过程中 自动获取和积累有关搜索空间知识并自适应地完成搜索过程，从而得到最优解或 准最优解的通用搜索算法一直是令人瞩目的课题。遗传算法就是这种特别有效的 算法。它的主要特点是简单、通用、鲁棒性强，适用于并行分布处理，应用范围 广。尽管遗传算法本身在理论上和应用方面仍有待进一步地研究，但它在组合优 化问题求解、白适应控制、规划设计和人工生命等领域的应用中已展现出了自身 的特色。 随着应用领域的扩展，遗传算法的研究主要有几个新动向： 基于遗传算法的机器学习，它把遗传算法从离散的搜索空间优化搜索算 法扩展到具有规则生成功能的机器学习算法； 遗传算法正日益和神经网络、模糊推理及混沌理论等其他智能计算方法 相互渗透和结合； 并行处理的遗传算法的研究十分活跃； 遗传算法与人工生命的渗透结合，在生物的自适应、进化、免疫等方面 的研究将会发挥一定的作用； 遗传算法和进化规划以及进化策略等进化理论日益结合。 我国有关遗传算法、进化算法的研究，从2 0 世纪9 0 年代以来一直处于不断 上升的时期。特别是近年来，遗传算法、进化算法的应用在许多领域取得了令人 瞩目的成果。现阶段研究的几个主要方面： 优化搜索方向的研究； 学习系统的遗传算法的研究； 重庆大学硕士学位论文1 绪论 生物进化与遗传算法的研究； 算法的分布并行处理； 人工生命与遗传算法的研究。 遗传算法作为一种自组织、自适应的高性能计算和建模方法的研究渐趋成熟。 尽管如此，在使用遗传算法求解具体问题时，染色体群体规模、选择概率、交叉 概率、变异概率等参数的设置仍然较难控制，特别是适应度函数的设计对算法的 收敛性以及收敛速度的影响较大。同时，在利用遗传算法的优点来解决实际问题 方面虽然已经取得了不少成果，但还有待于更多的探索和交流。 1 1 2 旅行商问题 旅行商问题( 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 ) 是组合数学中一个古老而 又困难的问题，它易于描述但求解方法至今尚未彻底解决。 旅行商问题：有一个推销员，要到n 个城市推销商品，他要找出一个包含所有 n 个城市的具有最短路程的环路。t s p 的历史发展悠久，最早的描述是1 7 5 9 年欧 拉研究的骑士周游问题。t s p 由美国r a n d 公司于1 9 4 8 年引入，该公司的声誉以 及线性规划这一新方法的出现使得t s p 成为一个知名且流行的问题。 t s p 是一个典型的组合优化问题，并且是一个n p 难问题，因为h a m i l t o n 圈 的数目是顶点数目n 的指数函数，所以一般很难精确地求出其最优解。但是，首 先从应用上来说，很多实际应用问题，如印制电路板的电路设计、连锁店的货物 配送路线等，经简化处理后，均可转化为t s p 问题。由于旅行商问题的重要应用 价值，因而对旅行商问题的算法研究自然是一个无法回避的问题。其次，从理论 上来说，它的计算复杂性研究在形成n p 完全理论中起到了奠基作用。今天，由于 计算机科学技术的发展，给一些n p 难题的算法研究又重新注入了新的活力，旅行 商问题研究的新思路、新方法、新成果必将丰富n p 完全理论的内涵，促进n p 完 全理论的发展。 1 2 本文的研究内容 本文主要研究了改进遗传算法求解t s p 问题。分析了标准遗传算法和混合遗 传算法对t s p 的求解，尤其对求解t s p 问题的遗传算法的交叉算子进行了深入地 研究，设计出了两种新的交叉算子，采用多组典型数据对设计的算法进行了测试， 测试结果理想，说明了算法切实可行有效。本文共分六章论述了以上提出的问题。 第l 章，绪论。介绍本文的研究背景，对遗传算法和t s p 问题进行了简要的 概述。 第2 章，遗传算法概述。主要阐述了遗传算法( g a ) 的基本原理，以及g a 的 数学基础，给出了g a 的完整的框架，详细地分析了g a 的编码、适应度函数、遗 2 重庆大学硕士学位论文1 绪论 传操作、参数设置等步骤，并且简单介绍了遗传算法的应用。 第3 章，t s p 问题概述。首先介绍了旅行商问题的定义、分类、扩展形式、 研究难点和应用领域等，其次简介了旅行商问题的基本算法，其中重点介绍了目 前最有发展潜力的神经网络、遗传算法等。 第4 章，求解t s p 问题的遗传算法。主要介绍了基本遗传算法求解t s p 问题 的基本方法，同时还介绍了几种求解t s p 问题的改进遗传算法。 第5 章，改进交叉算子求解t s p 问题的研究。首先分析了常用的几种交叉算 子的主要缺陷，然后设计了两个新的交叉算子：顺序插入交叉算子与动态顺序插 入交叉算子。同时，进行了数值试验，从而验证了本文设计的算法切实可行有效。 第6 章，全文的总结。对本文的主要研究工作进行简要的阐述和说明，并对 t s p 问题的进一步研究进行了探讨和展望，同时对以本文提出的算法为基础求解 其它的优化组合问题提出了设想。 重庆大学硕士学位论文 2 遗传算法 2 遗传算法 2 1 遗传算法的起源与发展 6 0 年代，m i c h i g a n 大学的h o l l a n d 教授认识到生物的遗传和自然进化现象与 人工自适应系统的相似关系，提出在研究和设计人工自适应系统时，可借鉴生物 的遗传机制，以群体的方式进行自适应搜索。1 9 6 7 年，h o l l a n d 的学生b a g l e yj d 在他的博士论文中首次提出了“遗传算法”一词，发展了复制、交叉、变异、显性、 倒位等遗传算子。7 0 年代初，h o l l a n d 提出了遗传算法的基本定理一模式定理 ( s c h e m a t h e o r e m ) ，奠定了遗传算法的理论基础。 1 9 7 5 年，h o l l a n d 出版了第一部系统论述遗传算法和人工生命自适应系统的专 著自然系统和人工系统的适配。同年，d ej o n g 在其论文遗传自适应系统的 行为分析中结合模式定理进行了大量纯数值优化实验，将选择、交换和变异操 作进一步完善和系统化。同时又提出了诸如代沟等新的遗传操作技术，建立了著 名的d ej o n g 五函数测试平台，定义了评价遗传算法性能的在线指标和离线指标。 8 0 年代，h o l l a n d 实现了第一个基于遗传算法的机器学习系统一分类器系统， 建立了基于遗传算法的机器学习的新概念，为分类器的构造提出了一个完整的框 架。1 9 8 9 年，g o l d b c r g 出版了专著搜索、优化和机器学习中的遗传算法，系统 总结了遗传算法的主要研究成果，全面完整的论述了遗传算法的基本原理和应用。 1 9 9 2 年，k o z a 将遗传算法应用于计算机程序的优化设计即自动生成，提出了 遗传编程的概念。目前在遗传算法的研究中，尽管还存在一些有争议的问题，甚 至还有某些截然不同的学术观点和设计原则，一时尚难统一，整个遗传算法的理 论基础还比较薄弱，但是很多实例及应用充分表明，模拟自然进化的搜索过程往 往可以产生非常简单、通用和鲁棒性很强的计算方法。如今，无论是对遗传算法 的理论研究还是应用研究都分外活跃。 2 2 遗传算法的数学基础 遗传算法在机理方面具有搜索过程和优化机制等属性，数学方面的性质可通 过模式定理和积木块假设等理论加以讨论。 模式：模式表示一些相似的模块，它描述了在某些位置上具有相同结构特征 的个体编码中的一个子集。 以二进制为例，个体是由二值字符集v = o ，l 中的元素所组成的一个编码串， 而模式却是由三值字符集k = o ，l ，) 中元素所组成。其中“，表示通配符，它即可被 当作“l ”也可被当作“o 。 4 重庆大学硕士学位论文2 遗传算法 如模式1 1 * 1 描述长度为5 ，1 ，2 ，5 位置取为l 的所有字符申的集合 1 1 0 0 1 ， 1 1 0 1 1 ，1 1 1 0 1 ，1 1 1 1 1 。在进行遗传算法的理论分析时，在引入模式概念之后，遗 传算法的本质是对模式所进行的一系列运算，选择算子是将当前群体中的优良模 式遗传到下一代群体中，通过交叉算子进行模式的重组，通过变异算子进行模式 的突变。通过这些遗传运算，一些较差的模式逐渐被淘汰，而一些较好的模式逐 步被遗传和进化，最终就可以得到问题最优解。 模式阶：模式h 中确定基因值的位置数目称为该模式的模式阶记为d ( 日) 。例 如，o ( 0 1 1 + l = 4 。 模式的对应长度：模式h 中第一个确定基因值的位置和最后一个确定基因值 的位置之间的距离称为该模式定义长度，记为j ( 日) 。例如，6 ( 0 1 l + l ”) = 4 。 模式定理：具有短的定义长度、低阶、并且模式采样的平均适应度在种群平 均适应度以上的模式，在遗传算法迭代过程中将按指数增长率被采样。 积木块：模式定理说明了具有某种结构特征的模式在遗传进化过程中其样本 数将按指数级增长，这种模式就是具有低阶、短的定义长度且平均适应度高于群 体平均适应度的模式。这种类型的模式被称为基因块或积木块。 遗传算法的求解过程并不是在搜索空间中逐一地测试各个基因的枚举组合， 而是通过一些较好的模式，像搭积木一样，将它们拼接在一起，从而逐渐构造出 适应度越来越高地个体编码。 积木块假设：个体的基因块通过选择、交叉、变异等遗传算子的作用，能够 相互拼接在一起，形成适应度更高的个体编码。 隐含并行性：在算法的运行过程中，每代都处理了n 个体，但由于一个个体 编码串中隐含了多种不同的模式，所以算法实质上却处理了更多的模式，这种并 行处理过程有别于一般意义下的并行算法的运行过程，是包含在处理过程内部的 一种隐含并行性，通过这种隐含并行性，使得我们可以快速地搜索出一些比较好 地模式。 2 3 遗传算法的基本技术 遗传算法g a 把问题的解表示成“染色体”，并且在执行遗传算法之前。给出一 群t 染色体”，作为假设解，然后，把这些假设解置于问题的环境”中，并按适者生 存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉和变异过程产 生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适 应环境的一个“染色体”上，它就是问题的最优解。 2 3 1 遗传编码 按照遗传算法的工作流程，当用遗传算法求解问题时，必须在目标问题实际 5 重庆大学硕士学位论文2 遗传算法 表示与遗传算法的染色体位串结构之间建立关系，即确定编码和解码运算。 编码就是将问题的解用一种码来表示，从而将问题的状态空间与g a 的编码 空间相对应，编码的选择是影响算法性能与效率的重要因素。 对于给定的优化问题，由g a 个体的表现型集合所组成的空间称为问题空间， 由g a 基因型个体所组成的空间称为g a 编码空间。遗传算子在g a 编码空间中对 位串个体进行操作。 编码应该适合要解决的问题，而不是简单的描述问题，问题编码一般应满足 以下几个原则： 完备性；问题空间中的所有点( 潜在解) 都能成为g a 编码空间中的点( 染 色体位串) 的表现型。 健全性：g a 编码空间中的染色体位串必须对应问题空间中的某一潜在 解。 可扩展性：对于具体的问题，编码的大小确定了解码的时间，两者存在 一定的函数关系，若增加一种表现型，作为基因型的编码大小也应作出 相应的增加。 多重性：多个基因解码成一个表现型，即从基因型到相应的表现型空间 是多对一的关系，这是基因的多重性。若相同的基因型被解码成不同的 表现型，这是表现型的多重性。 个体可塑性；决定表现型与相应给定基因型是受环境影响的。 常用的编码方法有如下几种： 二进制编码：二进制编码将问题空间的参数表示为基于字符集 o ，1 g o 成 的染色体位串，是最常用的一种编码方式。 大字符集编码：除基于字符集 o ，1 ) 的二进制编码之外，可以结合实际问题 的特征采用d 进制数或字符集来表示长度为l 的位串。 序列编码：采用g a 求解t s p 问题时，用排列法进行编码似乎更为自然、 合理。 实数编码；实数编码具精度高、大空间搜索的优点。 树编码：树编码是一种非固定常用编码模式，其表示空间是开放的。在 搜索过程中树可以自由生长，但是不便于形成更具有结构化和层次性的 问题解，实际应用中往往可以加以限制。 自适应编码：实现选择合适的固定编码方式对潜在的遗传算法用户来说 是一个难题。事实上，提出合适的编码同解决问题本身一样困难。因此， 许多用户认为既然要用遗传算法解决问题，为什么不让它同时调整编码 呢? 一些专家就采用了自适应编码。 6 重庆大学硕士学位论文 2 遗传算法 乱序编码：g o l e b e r g 和他的同事提出了一种基于乱序编码的遗传算法， 用于提高函数优化和概念学习问题中g a 的搜索能力。其主要思想是促 进短距模式的检测和重组效率，降低模式被交叉算子破坏的概率。 2 3 2 选择 从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又称 为再生算子。选择的目的是把优化的个体( 或解) 直接遗传到下一代或通过交叉产生 新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。 在遗传算法中，目前常用的选择机制有以下几种： 适应度比例方法 适应度比例方法是目前遗传算法中最基本也是最常用的选择方法。它也叫赌 轮或蒙特卡罗选择。在该方法中，各个个体的选择概率和其适应度值成比例。 设群体大小为n ，其中个体i 的适应度值为z ，则i 被选择的概率为： 乳；t | 皂 ，1 = 1 ( 2 1 ) 显然，概率凡反映了个体i 的适应度在整个群体的个体适应度总和中所占的 比例。个体适应度越大，其被选择的概率就越高，反之则被选择的概率越低。 最佳个体保存方法 最佳个体保留进化策略的基本思想是当前群体中适应度最高的个体不参与交 叉运算和变异运算，而是用来替换掉本代群体中经过交叉、变异等遗传操作后所 产生的适应度最低的个体。 具体操作过程是： 1 1 找出当前群体中适应度最高的个体和适应度最低的个体。 2 ) 若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还 要高，则以当前群体中的最佳个体作为新的迄今为止的最好个体。 3 ) 用迄今为止的最好个体替换掉当前群体中的最差个体。 期望值方法 在赌轮选择机制中，当个体数不太多时，依据产生的随机数有可能会出现不 正确地反映个体适应度的选择，即存在统计误差。也就是说，适应度高的个体也 有可能被淘汰( 当然，适应度低的个体也有可能被选择) ，为克服这种误差，期望值 方法用了如下思想。 1 ) 计算群体中每个个体在下一代生存的期望数目： 肚笏。旌z 肛 q 2 2 ) 若某个体被选中并要参与配对和交叉，则它在下一代中的生存的期望值数 目减去0 5 ；若不参与配对和交叉，则该个体的生存期望数目减去1 。 7 重庆大学硕士学位论文2 遗传算法 3 ) 在2 ) 的两种情况下，若一个个体的期望值小于0 时，则该个体不参与选择。 排序选择机制 排序选择方法的主要着眼点是个体适应度之间的大小关系，对个体适应度是 否取正值或负值以及个体适应度之间的数值差异程度并无特别要求。排序选择机 制的主要思想是：对群体中的所有个体按其适应度大小进行排序，基于这个排序 来分配各个体被选中的概率。其具体操作过程是： 1 ) 对群体中的所有个体按其适应度大小进行降序排序。 2 ) 根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次 序分配给各个个体。 3 ) 以各个个体所分配到的概率值作为其能够被遗传到下一代的概率，基于 这些概率值用比例选择的方法来产生下一代群体。是指在计算每个个体 的适应度后，根据适应度大小顺序对群体中个体排序，然后把事先设计 好的概率表按序分配给个体，作为各自的选择概率。 联赛选择机制 联赛选择机制也是一种基于个体适应度之间大小关系的选择方法。其操作思 想是，从群体中任意选择一定数目的个体( 称为联赛规模) ，其中适应度最高的个体 保存到下一代，这一过程反复执行，直到保存到下一代的个体数达到预先设定的 数目为止。联赛规模一般取2 。 联赛选择机制的具体操作过程是： 1 1 从群体中随机选取n 个个体进行适应度大小的比较，将其中适应度最高 的个体遗传到下一代群体中。 2 ) 将上述过程重复m 次，就可得到下一代群体中的m 个个体。 2 3 3 交叉 遗传算法中的交叉运算是指：两个相互配对的染色体按某种方式相互交换其 部分基因，从而形成两个新个体。一般地，子代个体具有父母双方的优点，因而 表现出比父代更优秀性状。在g a 的运算过程中，交叉的作用也在于此，交叉的 结果使个体更趋近于最优解。所以人们认为，交叉算子是g a 中最重要的算子。 交叉算子也是遗传算法区别于其他进化算法的重要特征。 设计交叉算子的指导原则就是既不要太多地破坏表示优良性状的基因，又要 产生一些较好的新个体模式。交叉算子的设计与研究问题和编码方式有关，针对 不同的研究问题和编码方式人们进行了大量的研究。 二进制编码常用的交叉方法有单点交叉、两点交叉、多点交叉、均匀交叉。 单点交叉 单点交叉( s i m p l ec r o s s o v e r ) ，又称简单交叉，它是指在个体编码串中随机设置 重庆大学硕士学位论文2 遗传算法 一个交叉点，然后再交换配对个体在该点后的部分基因。其具体过程是：先对群 体进行随机配对；其次随机设置交叉点位置；最后按一定的交叉概率来交换配对 染色体在交叉点位置之后的部分基因座上的基因。单点交叉操作过程如图2 1 所示 囊笈点链赣 er o i l s o v e t 啼 i ； 0 ol翻 i t冉l 0豳 图2 1 单点交叉 f i 9 2 1s i m p l ec r o s s o v e r 单点交叉的重要特点是：若邻接基因座之间的关系能提供较好的个体性状和 较高的个体适应度的话，则这种单点交叉操作破坏这种个体性状和降低个体适应 度的可能性最小。 双点交叉和多点交叉 双点交叉( t w o - p o i n tc r o s s o v e r ) 是指在个体编码串中随机设置了两个交叉点， 然后再进行部分基因交换。双点交叉的具体操作过程是： 1 ) 在相互配对的两个个体编码串中随机设置两个交叉点。 2 ) 交换两个个体在所设定的两个交叉点之间的部分染色体。 例如，双点交叉操作的示例如下； 量p 芦一j 忡 五日珥一口聱蕾羽 受笑焱i 糍鬟赢2突鬟蕊1 燮义焱2 将单点交叉和双点交叉的概念加以推广，可得到多点交叉( m u l t i - p o i n t c r o s s o v e f ) 的概念。即多点交叉是指在个体编码串中随机设置了多个交叉点，然后进行基因 交换。多点交叉又称为广义交叉，其操作过程与单点交叉和多点交叉相类似。 需要说明的是，一般不太使用多点交叉算子，因为它有可能破坏一些好的模 9 重庆大学硕士学位论文 2 遗传算法 式。事实上，随着交叉点数的增多，个体的结构被破坏的可能性也逐渐增大，这 样就很难有效地保存较好的模式，从而影响遗传算法的性能。 均匀交叉 均匀交叉( u n i f o r mc r o s s o v e r ) 是指两个配对个体的每一个基因座上的基因都以 相同的交叉概率进行交换，从而形成两个新的个体。均匀交叉实际上可归属于多 点交叉的范围，其具体运算可通过设置一屏蔽字来确定新个体的各个基因如何由 哪一个父代个体来提供。均匀交叉的主要操作过程如下： 1 ) 随机产生一个与个体编码串长度等长的屏蔽字矿= w t w 2 m 其中， 为个体编码串长度。 2 ) 有下述规则从a ，b 两个父代个体中产生出两个新的予代个体a 、b ： a 若= 0 ，则a 在第f 个基因座上的值继承a 的对应基因值，b 在第f 个 基因座上的值继承b 的对应基因值； b 若= 1 ，则a 在第f 个基因座上的值继承b 的对应基因值，b 在第i 个 基因座上的值继承的a 对应基因值 均匀交叉操作的示例如下： 田田田= 。 图2 3 均匀交叉 f i 9 2 3u n i f o r mc r o s s o v e r 2 3 4 变异 遗传算法中的所谓变异运算，是指将个体染色体编码串中的某些基因座上的 基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。从遗传算法 运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方法，它 决定了遗传算法的全局搜索能力；而变异运算只是产生新个体的辅助方法，但它 也是必不可少的一个运算步骤，因为它决定了遗传算法的局部搜索能力。 在遗传算法中使用变异算子主要有以下两个目的： 改善遗传算法的局部搜索能力。遗传算法使用交叉算子已经从全局的角 度出发找到了一些较好的个体编码结构，它们已接近或有助于接近问题 的最优解。但仅使用交叉算子无法对搜索空间的细节进行局部搜索。这 时若再使用变异算子来调整个体编码串中的部分基因值，就可以从局部 i 0 重庆大学硕士学位论文 2 遗传算法 的角度出发使个体更加逼近最优解，从而提高了遗传算法的局部搜索能 力。 维持群体的多样性，防止出现早熟现象。变异算子用新的基因值替换原 有基因值，从而可以改变个体编码串的结构，维持群体的多样性，这样 就有利于防止出现早熟现象。 最简单的变异算子是基本位变异算子。为适应各种不同应用问题的求解需要， 人们也开发出了其他一些变异算子。下面介绍其中较常用的几种变异操作方法， 它们适合于二进制编码的个体和浮点数编码的个体。 基本位变异 基本位变异( s i m p l em u t a t i o n ) 操作是指对个体编码串中以变异概率n 随机指 定的某一位或某几位基因座上的基因值作变异运算，其具体操作过程是：先随机 确定个体基因型的变异位置，然后以某一概率将变异位置上的基因值取反 ( 对二进制编码而言) 。 基本位变异操作过程如图所示： 燮肄点蹙黯虑 图2 4 基本位变异示意图 f i 9 2 4s i m p l em u t a t i o n 基本位变异操作改变的只是个体编码串中的个别几个基因座上的基因值，并 且变异发生的概率也比较小，所以其发挥的作用比较慢，作用的效果也不明显。 均匀变异 均匀变异( u n i f o r mm u t a t i o n ) 操作是指分别用符合某一范围内均匀分布的随机 数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。 均匀变异的具体操作过程是： 1 ) 依次指定个体编码串中的每个基因座为变异点。 2 ) 对每一个变异点和变异概率从对应基因的取值范围内取一随机数来替 代原有基因值。 假设有一个体为x = x 。x 2 鼍而，若为变异点，其取值范围为【，盏，【，惫】， 在该点对个体x 进行均匀变异操作后，可得到一个新的个体x = 五为以而， 其中变异点的新基因值是： 。屹+ ，( 吃一吃) 式中，r 为 0 ，l 】范围内符合均匀概率分布的一个随机数。 重庆大学硕士学位论文 2 遗传算法 均匀变异操作特别适合应用于遗传算法的初期运行阶段，它使得搜索点可以 在个搜索空间内自由地移动，从而可以增加群体的多样性，使算法处理更多的模 式。 2 3 5 适应度函数及尺度变换 遗传算法在进化搜索中基本不用外部信息，仅以适应度函数为依据，利用种 群中每个个体的适应度值来进行搜索。因此适应度函数的选择至关重要，直接影 响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标 函数变换而成的。对目标函数值域的某种映射变换称为适应度的尺度变换。 适应度函数的设计主要满足以下条件： 单值、连续、非负、最大化：这个条件是容易理解和实现的。 合理、一致性：要求适应度值反映对应解的优劣程度，这个条件的达成 比较难以衡量。 计算量小：适应度函数设计应尽可能简单，这样可以减小计算时间和空 间上的复杂性，降低成本。 通用性强：适应度函数对具体问题应尽可能具有通用性，最好无需使用 者改变适应度函数中的参数。 适应度函数的尺度变换有线性变换法、幕函数变换法、指数变换法。 2 3 6 算法参数 在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数。这组 参数在初始阶段或种群进化过程中需要合理地选择和控制。主要包括染色体位串 长度l 、种群规模n 、交叉概率以以及变异概率以。 位串长度l ：位串长度l 的选择取决于待定问题的精度。要求的精度越 高，位串越长，但需要更多的计算时间。为提高运算效率，变长度位串 或者在当前所达到的较小可行域内重新编码，是一种可行的方法，并显 示了良好性能。 种群规模：大种群含有较多模式，为遗传算法提供了足够的模式采样容 量，可以改进g a 搜索的质量，防止早熟前收敛。但大种群增加了个体 适应性评价的计算量，从而使收敛速度降低。一般专家建议n = 2 肛- 2 0 0 。 交叉概率以：交叉概率以控制着交叉算子的应用频率，在每一代新的种 群中，需要对个体的染色体结构进行交叉操作。交叉概率越高，种群中 新结构的引入越快，已获得的优良基因结构的丢失速度也相应升高。而 交叉概率太低则可能导致搜索阻滞。一般改= 0 6 0 1 o o 。 变异概率以：变异操作是保持种群多样性的有效手段，交叉结束后，交 配池中的全部个体位串上的每位等位基因按概率随机改变，因此每代中 重庆大学硕士学位论文 2 遗传算法 大约发生n 次变异。变异概率太小，可能是某些基因位过早丢失的信息 无法恢复；而变异概率过高，则搜索将变成随机搜索。一般取= o 0 5 - - 0 2 。 2 3 7 算法的终止条件 g a 的收敛理论说明了g a 以概率l 收敛的极限性质，因此我们要迫求的是提 高算法的收敛速度，这与算法操作设计和参数选取有关。然而，实际应用g a 时 不允许它无休止的进化下去，而且通常问题的最优解也不一定知道，因此需要有 一定的条件来终止算法的进程。最常用的终止条件就是事先给定一个最大进化步 数，或者是判断最佳优化值是否连续若干步没有明显变化等。 应该认识到，g a 不是一个简单的系统，而是一种复杂的非线性智能计算模型， 纯粹用数学方法来预测其运算结果是很难的，而且这方面的研究工作也远远不够。 目前，为兼顾g a 的优化质量与效率，实际应用g a 时许多环节一般还只是凭经验 解决，这方面还有待更深入的研究和发展。 2 4 遗传算法的运行步骤和流程图 遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反 复将选择算子、交叉算予、变异算子作用于群体，最终可得到问题的最优解或近 似最优解。对于一个需要进行优化计算的实际应用问题，一般可按下述步骤来构 造求解该问题的遗传算法。 确定决策变量及其各种约束条件，即确定出个体的表现型和问题的搜索 空间( 解空间) 。 建立优化模型，即确定出目标函数的类型( 是求目标函数的最大值还是 求目标函数的最小值) 及其数学描述形式或量化方法。 确定表示可行解的染色体编码方法，也即确定出个体的基因型及遗传算 法的遗传空间。 确定解码方法，即确定出由个体基因型到个体表现型的对应关系或转换 方法。 确定个体适应度的量化评价方法，即确定出由目标函数值到个体适应度 的转换规则。 设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的 具体操作方法。 遗传算法实现的具体流程图如下： 重庆大学硕士学位论文2 遗传算法 图2 5 遗传算法实现的具体流程图 f i 9 2 5t h ec o n c r e t ef l o wc h a r to f g a si m p l e m e n t 2 5 遗传算法的特点 遗传算法是一种不同于以往任何一种寻优方法的具有鲁棒性的高效寻优方 法，具有一些显著的特点。 以决策变量的编码作为运算对象 传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算，而遗 传算法则是以决策变量的某种形式的编码作为运算对象。特别是对一些无数值概 念或很难有数值概念，只有代码概念的优化问题，编码处理方式更显出了其独特 的优越性。 直接以目标函数值作为搜索信息 传统的优化算法不仅需要利用目标函数值，而且往往需要其它些辅助信息 才能确定搜索方向。而遗传算法仅使用适应度函数值，就可以确定搜索方向和搜 索范围，无需目标函数的导数值等其它一些辅助信息。而且直接利用目标函数值 或个体适应度，也可把搜索范围集中到适应度较高的部分搜索空间，从而提高搜 索效率。 同时使用多个搜索点的搜索信息 传统的优化算法往往是从解空间的一个初始点开始最优解的迭代搜索过程， 所以搜索效率不高；有时甚至使搜索过程陷于局部最优解而停滞不前。遗传算法 从由很多个体所组成的一个初始种群开始最优解的搜索过程，而不是从一个单一 的个体开始搜索，这是遗传算法所特有的一种隐含并行性。隐含并行性是遗传算 法搜索最为突出而有用的特点。 使用概率搜索技术 很多传统的优化算法往往使用的是确定性的搜索方法，这种确定性往往有可 1 4 重庆大学硕士学位论文2 遗传算法 能使得搜索永远达不到最优点，因而也限制了算法的应用范围。而遗传算法属于 一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来 进行的，从而增加了其搜索过程的灵活性。 2 6 遗传算法的应用 遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体 领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗传算 法的一些主要应用领域。 函数优化 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用 算例。而对一些非线性、多模型、多目标的函数优化问题，用其它优化算法较难 求解，而遗传算法却可以方便地得到较好的效果。 组合优化 遗传算法对于组合优化问题中的n p 完全问题非常有效。例如，遗传算法已经 在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。 生产调度问题 遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水 线生产问调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。 自动控制 在自动控制领域中有很多与优化相关的问题需要求解。例如用遗传算法进行 航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊 控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的 学习、利用遗传算法进行人工神经网络的结构优化和设计，权值学习等。 机器人与机器学习 遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆 运动学求解、细胞机器人的结构优化和行为协调、学习模糊控制规则、调整人工 神经网络的连接权、神经网络的网络结构优化设计、学习式多机器人路径规划系 统中等方面得到研究和应用。 图像处理 在图像处理过程中，如扫描、特征提取、图像分割等不可避免的会存在一些 误差，这些误差会影响图像处理的效果。遗传算法在这些图像处理中的优化计算 方面找到了用武之地，目前己在模式识别、图像恢复、图像边缘特征提取等方面 得到了应用。 人工生命 重庆大学硕士学位论文2 遗传算法 人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工 生命现象的主要基础理论。虽然人工生命的研究尚处于启蒙阶段，但遗传算法已 在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能 力，并且必将得到更为深入的应用和发展。 遗传编程 k o z a 发展了遗传编程的概念，他使用了以l i s p 语言所表示的编码方法，基于 对一种树形结构所进行的遗传操作来自动生成计算机程序。 2 7 小结 本章首先介绍了遗传算法的起源与发展、数学基础，然后介绍了算法的基本 技术及实现步骤，最后介绍了遗传算法的特点和应用。 1 6 重庆大学硕士学位论文 3 旅行商问题 3 旅行商问题 3 1 旅行商问题概述 3 1 1 旅行商问题的定义和数学模型 定义 旅行商问题( 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 ) 是组合数学中一个古老而 又困难的问题，它易于描述但至今尚未彻底解决，现己归入所谓的n p 完全问题类， 经典提法为： 有一货物推销员要去若干个城市推销货物，从城市1 出发，经其余各城市一 次，然后回到城市l ，问选择怎样的行走路线，才能使总行程最短( 各城市间距离 为己知) 。 该问题在图论的意义下就是所谓的最小h a m i l t o n 圈问题，由于在许多领域中 都有着广泛的应用，因而寻找其实际而有效的算法就显得颇为重要了。遗憾的是， 计算复杂性理论给予我们的结论却是，这种可能性尚属未知。 若设城市数目为n 时，那么组合路径数则为( n - 1 ) ! 。很显然，当城市数目不多 时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈 指数级数规律急剧增长，以至达到无法计算的地步，这就是所谓的“组合爆炸问题”。 假设现在城市的数目增为2 0 个，组合