（管理科学与工程专业论文）降幂编码遗传算法及其在旅行商问题中的应用研究.pdf

武汉科技大学 研究生学位论文创新性声明 本人郑重声明：所呈交的学位论文是本人在导师指导下，独立进行研究 所取得的成果。除了文中已经注明引用的内容或属合作研究共同完成的工作 外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名：呈查坚 日期： 7 1 0 1 0 2 研究生学位论文版权使用授权声明 本论文的研究成果归武汉科技大学所有，其研究内容不得以其它单位的 名义发表。本人完全了解武汉科技大学有关保留、使用学位论文的规定，同 意学校保留并向有关部门( 按照武汉科技大学关于研究生学位论文收录工作 的规定执行) 送交论文的复印件和电子版本，允许论文被查阅和借阅，同意 学校将本论文的全部或部分内容编入学校认可的国家相关数据库进行检索和 对外服务。 论文作者签名： 指导教师签名： 武汉科技大学硕士学位论文第1 页 摘要 旅行商问题是一个实用背景广泛，并且有着重要理论价值的组合优化难题，该问题的 一个显著特点是描述简单，但很难得到最优解。因为旅行商问题在工程技术领域的应用十 分广泛，所以具有很高的研究价值。 由于旅行商问题的时间复杂度很大，精确算法只能求解规模很小的旅行商问题，所以 当求解规模较大的旅行商问题时，常常采用近似算法，遗传算法是一种常见的求解旅行商 问题的近似算法。 因为字符编码在求解旅行商问题时，拥有信息表达简单、直观的特点，所以目前在解 决旅行商问题时，一般使用的都是字符型编码的遗传算法。但是字符型编码由于其自身的 特点，在求解旅行商问题时存在会产生非法染色体、计算效率低的缺点，其效果并不是很 理想。本研究提出了一种新的求解旅行商问题的遗传算法编码方式，将其与字符型编码进 行比较，证明其在交叉的时候不会产生非法的染色体，并且实验结果表明其能更快的找到 最优解，这两个优点足以证明这种新的编码方式更适合求解旅行商问题。 关键词：旅行商问题遗传算法二进制编码字符编码降幂编码 第1 i 页武汉科技大学硕士学位论文 a b s t r a c t t s pi su s e di n8 1 1e x t e n s i v ep r a c t i c a lb a c k g r o u n d w h i c hi st h ec o m b i n a t i o n a lo p t i m i z a t i o n p r o b l e mw i mi m p o r t a n tt h e o r e t i c a lv a l u e ，t h eo b v i o u sf e a t u r ei st h ed e s c r i p t i o ni sv e r ys i m p l e ， b u td i f f i c u l tt og e ta l lo p t i m a ls o l u t i o n i ti sh i g hr e s e a r c hv a l u ea st s pu s e di nt h ea p p l i c a t i o no f e n g i n e e r i n gt e c h n o l o g ye x t e n s i v e l y a st h eg r e a tt i m ec o m p l e x i t yo ft s p , e x a c ta l g o r i t h m sc a no n l ys o l v es m a l l - s c a l et s p , s o a p p r o x i m a t i o na l g o r i t h mi su s e da l o tt os o l v el a r g e s c a l et s p , g e n e t i ca l g o r i t h mi sac o m m o n s o l u t i o no f a p p r o x i m a t i o na l g o r i t h mf o rt s e b e c a u s et h ei n f o r m a t i o ni ss i m p l ea n di n t u i t i v ew h e nc h o o s et h ec h a r a c t e re n c o d i n gf o rt s p , t h eg e n e t i ca l g o r i t h mf o rc h a r a c t e r i s t i c se n c o d i n gi sac o m m o ns o l u t i o nn o w a d a y s h o w e v e ra s i t so w nc h a r a c t e r i s t i c so fc h a r a c t e re n c o d i n g , i ti sn o tt h e b e s te f f e c ta si tm a k e si l l e g a l c h r o m o s o m ea n da l s oc a l c u l a t ew i t hl o we f f i c i e n c y t h i sr e s e a r c hg i v e san e wc h a r a c t e r i s t i 鹪 e n c o d i n go fg e n e t i ca l g o r i t h mf o rt s p , c o m p a r e dw i 廿1o t h e rc h a r a c t e r i s t i c s ，i ti sp r o v e dt h a ti t d o e s n tp r o d u c ei l l e g a lc h r o m o s o m e sw h e nc r o s s e d ，a l s ot h ee x p e r i m e n t a lr e s u l t ss h o wt h a ti t c a nh e l py o ut of i n dao p t i m a ls o l u t i o nm u c hf a s t e r , 、) l ，i t l lt h e s et w oa d v a n t a g e s ，t h i sn e wc o d i n g m e t h o di sp r o v e dt h a ti ti sam o r es u i t a b l es o l u t i 0 1 1f o rt s e k e yw o r d ：t s p g e n e t i ca l g o r i t h m b i n a r ye n c o d i n g c h a r a c t e re n c o d i n g d e s c e n d i n ge n c o d i n g 武汉科技大学硕士学位论文第1 页 摘要 目录 i a b s t r a c t i i e j 录l l i 第一章绪论 l 1 1 选题背景及研究意义1 1 2 国内外研究现状1 1 3 遗传算法概述2 1 3 1 遗传算法的基本原理2 1 3 2 遗传算法的基本概念2 1 3 3 遗传算法的基本数学理论3 1 3 4 遗传算法求解问题的步骤4 第二章遗传算法编码方式5 2 1 遗传算法编码的特性5 2 2 数值编码5 2 2 1 二进制编码5 2 2 2 格雷码编码6 2 2 3 十迸制编码8 2 3 符号编码8 2 3 1 字符编码8 2 3 2 基因编码8 第三章旅行商问题概述1 0 3 1t s p 的发展历史1 0 3 2t s p 的数学描述1 0 3 3t s p 的数学分类1l 3 3 1 按对称性分类l l 3 3 2 按问题限制条件分类l l 3 4t s p 的应用价值1 1 3 5t s p 的计算复杂性1 2 3 6 求解t s p 的方法1 3 3 6 1t s p 的精确计算1 3 3 6 2t s p 的近似计算1 4 第四章三种编码方式求解t s p 1 5 4 1 问题描述1 5 4 2 使用字符编码求解t s p 。1 6 4 2 1t s p 字符编码1 6 第页武汉科技大学硕士学位论文 4 2 2t s p 字符解码1 6 4 2 3 染色体有效性分析16 4 2 4 遗传算子设计1 6 4 2 5 计算结果1 7 4 3 使用二进制编码求解t s p 18 4 3 1t s p 二进制编码1 8 4 3 2t s p 二进制解码2 0 4 3 3 染色体有效性分析2 l 4 3 4 遗传算子设计2 3 4 3 5 计算结果2 4 4 4 使用降幂编码求解t s p 2 5 4 4 1t s p 降幂编码2 5 4 4 2t s p 降幂解码2 5 4 4 3 染色体有效性分析2 6 4 4 4 遗传算子设计。2 7 4 4 5 计算结果2 9 4 5 实验结果对比分析3 0 第五章结论及展望3 2 5 1 结论3 2 5 2 创新点。3 2 5 3 进一步的研究方向。3 2 参考文献3 3 致谢 附录 3 6 3 7 武汉科技大学硕士学位论文第1 页 第一章绪论 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 ) 是一个有重要理论价值的组合优化难 题，该问题的一个显著特点是描述简单，但很难得到最优解。旅行商问题在工程技术领域 的应用十分广泛，所以具有很高的研究价值【l 】。由于旅行商问题的时间复杂度很大，精确 算法只能求解规模很小的旅行商问题，所以当求解规模较大的旅行商问题时，常常采用近 似算法，遗传算法( g e n e t i ca l g o r i t h m , g a ) 是一种常见的求解旅行商问题的近似算法【2 1 。 编码在g a 中是用染色体的形式描述问题的可行解的过程，即把一个问题的可行解从其 解空间转化到能被g a 处理的搜索空间的过程【3 】。编码是使用g a 时的第一个步骤。当我们 面对一个问题的时候，根据问题怎样选择一个合适的编码方式，是g a 应用中的难点之一， 也是g a 的一个重要研究方向。 由于字符编码在求解t s p 时，拥有信息表达简单、直观的特点，所以目前在解决t s p 问题时，一般使用的是字符型编码的g a 4 1 。但是由于字符型编码由于其自身的特点存在会 产生非法染色体、计算效率低的缺点，所以在求解t s p 时效率并不是很理想【5 】。本文研究 提出了一种新的求解t s p 的g a 编码方式，将其与字符型编码进行比较，结果证明确实比字 符型编码更适合求解t s p 。 1 2 国内外研究现状 h o l l a n d 首先使用模式定理解释g a 的搜索行为，奠定了g a 的数学理论基础【6 】。并得出 每一代中能处理有效模式下限是o ( n 3 ) ，其中n 为群体大小，这是g a 能够有效搜索的根苯 原因之所在【_ 7 1 。b e r t o n i 和d o r i g o 推广了这项研究，并获得了n = 2 归，给出为任意值时处 理多少有效模式的表达式【引。恽为民和席裕庚给出了每代至少产生0 ( 2 。1 ) 数量级的新模式 【9 】 o 马丰宁通过对r i e m a n n 函数的测试，修正了模式定型1 0 】；为了克服二进制编码的早熟 问题，s c h r a u d o l p h 等提出了动态变量编码，通过对d e j o n g 拘5 个函数进行测试，发现动态 变量编码比普通二进制编码的优化效果好得多【l l 】。g o l d b e r g 和s m i t h 通过对动态背包问题进 行比较研究，实验表明双倍体比单倍体的跟踪能力强【1 2 】。q i 和p a l m i e r i 基于m a r k o v 链，用 数学方法严密地分析了浮点数编码的g a 1 3 】。张晓缋等研究了二进制和十进制编码在保持 群体稳定性和搜索能力上的差异，结果二进制编码比十进制编码的搜索能力强【1 4 1 。v o s e 等 扩展了h o l l a n d 的模式概念，揭示了不同编码之间的同构性【1 5 1 。 g a 中的编码在许多问题的求解中，对算法性能的影响是十分重要的。简单二进制编码 的采用得到了h o l l a n d 早期理论结果的支持，但它仍有许多不足之处【1 6 l 。动态参数编码的能 克服搜索效率与精度之间的矛盾，同时对克服早熟纤细有有所帮助。此外，多值编码、实 值编码、区间值编码、d e l t a 编码、对称编码以及将以往的合成编码分解成多个相对独立编 第2 页武汉科技大学 硕士学位论文 码的独立编码策略等多种编码方法也都被证明各有优缺点【1 7 l 【1 8 】。但是这些编码方法的提出 是启发式的，缺乏一个理论基础来判断各种编码方法的好坏并指导它们的设计【1 9 1 。 李韪韬，王惠南，钱志余提出了一种新的基于n 进制分部编码算子的g a z 0 。该编码算 子首先将每个基因值用n 迸制的浮点数表示，然后将其分为整数部分和小数部分，对整数 和小数部分分别编码【2 。在开始阶段，现对染色体进行整数部分和小数部分的遗传操作， 使得g a 在早期的全局搜索能力很强，避免过早地找到全局最优值；在后期进行小数部分的 遗传操作，对染色体进行微调，使得遗传在后期具有很强的局部搜索能力，能够有效地搜 索到全局极值。 目前，采用何种编码策略仍然存在很多争议。一种观点是要求根据模式定理，尽量用 少的符号进行编码【捌；另一种观点要求首先满足数值优化计算的方便和精度，用一个基因 设置一个参数，并把相应的基因操作变成适合实数操作的形式【2 3 】。b o s w o r t h 等是后一种观 点的开创者。近年来，许多学者发现在有些问题上，采用大符号集编码比采用小符号集编 码的g a 的性能要好【2 4 1 。a n t o n i s s e 从理论上证明t h o l l a n d 在推导最小字符集编码规则时存 在的错误，指出大符号集编码的设计可提供更多的模式【2 5 】。 1 3 遗传算法概述 1 3 1 遗传算法的基本原理 g a 是模仿生物学里的适者生存的机制的迭代搜索算法【2 6 1 。g a 主要通过遗传操作对中 群内个体的进行结构重组，不断搜索出群体内的优良个体，从而逐渐接近最优解。因为g a 具有鲁棒性强、适于并行处理、简单通用等特点，现在在优化调度、组合优化、运输问题、 机器人足球、计算科学等领域应用十分广泛【2 刀。 1 3 2 遗传算法的基本概念 g a 来源于生物学，所以它沿用了很多生物学概念。要想研究g a ，理解这些概念是必 不可少的前提【2 引。 ( 1 ) 基因，基因是生物学中最基本的遗传物质。在g a 和生物学中，基因都是构成染色 体的基本元素。 ( 2 ) 染色体，通常一条染色体是由多个基因以某种排列组成的，染色体是生物细胞中的 遗传物质的重要载体。在生物界中，通常一个生命的性状是由很多染色体共同表现的，而 在g a 中，通常只是通过一条染色体表现。 ( 3 ) 个体，个体是在某个物种类别中，具体的一个实体。个体之间的性状差异性的原因 是它们的染色体各不相同。 ( 4 ) 适应度，生物学中适应度指某个物种对所生活的环境的适应能力。对环境适应力强 的物种更容易存活下来，反之对环境适应力差的，就会走向灭绝。g a 中使用适应度函数用 来衡量个体的适应水平。适应度越大的越接近最优解，适应度越小的与最优解差别越大。 武汉科技大学 硕士学位论文第3 页 ( 5 ) 遗传算子，遗传算子是在染色体上的进行的遗传操作的泛称。几乎所有g a 都需要 三种基本遗传算子：选择、交叉和变异算子。从g a 起源到现在，还产生了一些特殊的遗传 算子，例如免疫算子。 a ) 选择算子，选择算子的作用就是把对环境适应能力较强的染色体保留遗传到下一代。 目前常见的选择方法有轮盘赌、最佳个体保留值、期望值法等方法。 b ) 交叉算子，交叉算子通过两条染色体交叉组合会形成两个新的染色体。 c ) 变异算子，变异算子以很小的概率产生某些复制差错，出现新的染色体，从而表现 出新的性状。变异算子的能使g a 具有局部的随机搜索能力，同时还能使g a 有机会跳出局 部最优解，全局优化能力更强。 ( 6 ) 编码与解码，编码是将问题的解转换成染色体的表现形式的一个过程。反之， 将染色体的表现形式转换成问题的解的过程称为解码。在g a 中，编码是要做的第一项工作， 在选择的时候，再将其解码到解空间进行评估。不同的问题，会有不同的编码方案，因此 染色体的表现形式也各不相同，染色体的编码方案还可能直接影响到g a 的求解效果。因此， 使用何种编码方案是g a 的一个重要因素。 ( 7 ) 种群，对生物遗传进化等行为发生的群体。个体为种群中的元素。种群中的每个个 体都代表g a 的一个解。 ( 8 ) 代，在生物学中表示个体从出生到死亡的过程，在g a 中，代表示为迭代的次数。 1 3 3 遗传算法的基本数学理论 在g a 的搜索过程中，g a 是通过适应度的值来选择个体的，为什么适应度能指导遗传 搜索向不断改进的方向前进? 模式定理和积木块假设回答了这个问题。模式定理和积木块”一 假设同时也奠定了g a 的数学基础【2 9 】。 定义一：模式( s c h e m a ) 是种群中的个体即基因串的相似模板，表示基因串中某些特征 位相同的结构，因此模式也可以解释为相同的构形【3 0 l 。 模式描述的是一个串的子集，例如在二进制编码的串中，模式是基于三个字符集( 0 ， l ，奎) 的字符串，符号叶表任意字符，即o 或l 。例如：模式 l 宰描述了一个四个元的子集 r d 甜= 4 0 0 ，i ，j v ) 。t s p 要求g 的哈密尔顿( h 锄i l t o n ) 回路上的消耗达到最小值，并 设吻= 托蜥旌警棚上 则t s p 的数学模型可写成如下的线性规划形式【5 2 】： m i n z = d y 。嘞 为= 1 ， 嘞= 1 ， 嘞 l 时，可将t s p 的动态规划方程写成 c ( s ，k ) = m i n e ( s 一 足) ，) + 批l _ ，s k 】，再逐步迭代求解。 因为动态规划算法的时间复杂度为o ( n 2 2 “) ，空间复杂度为o ( n 2 “) ，所以也只能解 第1 4 页武汉科技大学硕士学位论文 决规模很小的t s p 。 3 6 2t s p 的近似计算 上述精确算法虽然能精确的找出最优解，但都由于太繁琐而没有得到广泛的应用，特 别是当问题规模很大的时候，精确算法几乎无法求出最优解，正因如此，在实际求解t s p 中往往使用的都是启发式算法或进似算法，从而求解t s p 的近似算法才不断受到重视。近 似算法顾名思义只能得到近似的解，因为它不会搜索问题的全部解空间，因此近似算法也 不能保证一定能找到最优解，但近似算法与精确算法比较起来却具有运算时间上的巨大优 势，因为近似计算的时间复杂度都只是多项式，不会随着输入规模的扩大而使计算时间产 生“组合爆炸 的现象。这类算法是通过启发式的策略来指导搜索，普遍比精确算法要快 捷。 判断一个近似算法的好坏用c c 占来衡量，c 为通过近似算法所得到的总行程，c 。 为全局最优总行程，g 为最坏情况下，近似解与最优解之比不超过的上限。 目前，有很多近似优化算法，如神经网络方法、模拟退火、最近邻算法、以及g a 。 ( 1 ) 最近邻算法 最近邻算法首先任取一出发点，然后依次取最近的点加入当前解中直至形成回路解。 适用范围于对称型t s p 。最近邻算法的时间复杂度为o ( n 2 ) ，在具体实施过程中，可以 将v 中每个点都当做出发点计算一次，从而得到n 个解，从中选择最好的一个，但此时算 法的时间复杂度会变为o ( n 3 ) 。 ( 2 ) 神经网络算法 神经网络的思想是通过对神经网络引入适当的变化，其能量不断减少，最后达到平衡 时，收敛为一个局部最优解。 ( 3 ) 模拟退火算法 模拟退火算法是将组合优化问题和统计力学中的热平衡作类比，把目标函数看成是能 量函数，模仿物理学中固体物质的退火过程。首先加温使其具有足够高的能量，然后再逐 渐降温，因此其内部能量也相应会下降。在热平衡条件下，物体内部处于不同状态的概率 服从b 0 1 t 珊姐分布，如果退火步骤恰当，最终会形成最低能量的基态。模拟退火算法在求 解、组合优化问题时，不但接受对目标函数有改进的操作，而且还会以某种概率接受让目 标函数变坏的操作，因此能够避免过早收敛到某个局部最优值，正是有这种概率性的扰动 能够使之跳出局部最优解，故而一般都能得到比较优秀的可行解。 武汉科技大学硕士学位论文第1 5 页 第四章三种编码方式求解t s p 本章先给出一个t s p ，然后分别用二进制编码的g a 、符号编码的g a 以及降幂编码 g a 求解该t s p ，然后通过对三种编码方式求解t s p 的结果进行比较分析，以确定在使用 g a 求解t s p 时，更适合的编码方式。 4 1 问题描述 现给定平面直角坐标系中的1 2 个点( 分别命名为a 、b 、c 、k 、l ) ，每个点在平 面直角坐标系中的坐标如表4 1 所示。要求从a 点出发，试求出遍历这1 2 个点的最优路径， 要求每个点只经过一次，使所用的总路线最短。 表4 1 初始点坐标 点名称x 坐标y 坐标点名称x 坐标y 坐标 a 3 0 8 2 g 3 2 7 7 b7 33 6h6 06 5 c2 08 0i3 08 9 d5 70j1 09 0 e59 0k3 46 9 f9 41 6l7 7 6 5 根据表4 1 中各城市的坐标，反映到直角坐标中如图4 1 所示。 图4 1 各城市散点图 本研究的目的是使用不同编码方式的遗传算法求解该t s p ，希望能克服字符编码在交 叉时产生“非法一染色体的缺陷，再进一步通过该编码方式的遗传算法在求解t s p 时的效 第1 6 页武汉科技大学硕士学位论文 率与字符编码的遗传算法相比较，得出何种编码方式更优的结论。 4 2 使用字符编码求解t s p 4 2 1t s p 字符编码 对于本文中的t s p ，点集 a ，b ，c ，d ，e ，f gh ，i j ，kl ) 中每个城市都有一个字母与之 对应，所以可以很方便的以城市的名称来编码。 如假设一条路径为a b c d e f g h i j k l a ，则可以将这个解编 码为a b c d e f g h i j k l a 。 4 2 2t s p 字符解码 解码是编码的一个逆向过程，假如有一个染色体串为a b c d e f g h i j l a ，则表示的路 径为a b c d e f g h i j k l a ，此时这条路径的总长度为1 5 0 5 6 6 9 8 。 4 2 3 染色体有效性分析 假设有这样一条染色体a b d e f g u l k h c ，表示的路径为a b d e f g i j l k h c a ，能够行程回路，则说明这条染色体是有效的染色体。 假设有这样一条染色体a b d e f g u l k h i ，其中点a 、b 、d 、e 、f 、g 、j 、l 、k 、h 这1 0 个点出现的次数为l ；i 出现的次数为2 ；c 出现的次数为0 。点c 没有出现表示城市c 没 有被遍历，则这条染色体是一条无效的染色体。 所以对于字符编码的该t s p ，其编码有效性的充要条件为：除a 之外在染色体中每个字 母出现的次数为l 。 4 2 4 遗传算子设计 如有以下两条染色体： a cgbhdkfl ej ia afbcd e lhkgija 将第4 和第5 位上的基因交叉，得到如下两条染色体： a cgcddkf lej ia afbbhelhkgija 交叉之后两条染色体中有重复的点，此时需要将非交叉位上重复的基因用另一条染色 体上相对应的交叉基因替换。如图4 6 所示。 武汉科技大学硕士学位论文第1 7 页 替换 囚回曰曰回曰曰曰日曰曰曰囚 囚曰日回国曰日曰国曰田田困 图4 6 染色体交叉示意图 变异算子操作如下：在染色体中取第2 和第1 2 之间任意两位进行变换。如下染色体： agbcd i eflk jha ，进行变异操作变为： a gbckiefldjha 。 4 2 5 计算结果 与4 2 5 中一样，设置初始种群规模为2 0 ，如下： adblh k iegcfja 1 abdeihcf lgjka 1 adehc bg if ljka ，f aelkdcfl bghja ， ac gb hdkflejia ，f adcefhilgjkb a ， ah jglbikecdfa ，f ajbfgih dl ceka ， aefjbgchdilka ，f ac bh d ijkel fga ， ae fb cd g hjkila ，f ag ke lcfd h jiba ， afb cdeh k g ijla ，f aedjk hifl cgba ， agfh ijldekbca ，f afbcde lh k g ija agcekbh dfijla f acidejbfkglha adfbiceg h jkla ，f ab cde fg hijkla ， 选择概率只= 0 5 ，交叉概率= 0 4 ，变异概率己= 0 1 。编程实现该最终结果为 d = 5 5 0 6 0 1 4 ，最优路径为a j h b f g i c e l l a ，计算代数为4 6 7 1 5 代。如图4 7 所示。 第1 8 页武汉科技大学硕士学位论文 睦。缀鬟鍪黧笼z = = 黧髦2 z 鍪豳l 国 p s =0 5p c =0 4h = o 1 | c t c a t ei 代数： p 7 1 5 最短路径值： 嚣驹豹蜡钙l 豸7 l 瞒 最短路线：| 弼辫g i 沈鹚强 图4 7 实验结果示意图 4 3 使用二进制编码求解t s p 4 3 1t s p 二进制编码 编码是g a 中最初始的工作，针对不同问题，染色体的编码方式可能有会有很大的主 所以在使用g a 解决问题时要根据问题本身的特点选择适当的编码方式，只有适合问题 的编码方式才能在解决问题的时候起到良好的效果。 针对本问题中1 2 个城市 a ，b ，c ，d ，e ，f gh ，i ，j ，kl ) ，其中任意两点可确定一 段，如a b 两点之间可确定一条线段a b 。推广开来，如果有n 个城市，则可确定的线 为：c ：刀( n ，- n 。所以该问题中1 2 个城市可以确定的线段数为