（计算机应用技术专业论文）以小边为基因解tsp问题遗传算法研究.pdf

j 匕京1 ：商人学硕士学位论文 摘要 组合优化是运筹学的重要分支，主要通过对数学方法的研究寻找离散事件的最优 编排、分组、次序或筛选等。大多数这类问题通常在多项式时间里无法求解，属于 n p 问题。随着问题规模的扩大，问题空间呈现组合爆炸特征，无法用常规的方法求 解。旅行商问题( t s p ) 就是一个经典的组合优化问题，属于n p 完全问题。 遗传算法是一种新兴的搜索寻优技术，它模拟达尔文的进化论，根据“优胜劣汰 的原则，借助选择、交叉、变异等操作逐步逼近最优解。具有隐并行机制和自适应性， 因此他非常适合于多维，非线性和具有多峰值的问题。遗传算法早在六十年代由j h h o l l a n d 等人提出，并在八十年代得以完善，发展成为标准式的遗传算法，从九十年 代中期得到广泛研究与应用。遗传算法具有全局优化性和易操作性。最初应用于非数 值计算方面，直到近几年才转向于t s p 问题，并取得了一定的成果，吸引了越来越多 的研究者，逐渐成为人工智能领域的一个研究热点。 本文以近年来国内外学者提出的遗传算法为基础，分析了基本遗传算法易于出现 收敛缓慢现象的主要原因，并针对此引入导师证明的一个重要结论作为指导思想，在 遗传算法中初始化、交叉和变异算子上进行了改进，有效地加快了收敛速度。并将改 进后算法应用于求解t s p l i b 中的两个问题，实验结果表明，改进后算法加快了算法 的收敛速度，改善了求解的性能。 关键词：遗传算法，旅行商问题 i 以小边为基冈解t s p 问题遗传算法研究 a b s t r a c t c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e mi sa ni m p o r t a n tb r a n c hi no p e r a t i o n a lr e s e a r c h t h e s em a t h e m a t i c a lm e t h o d sc a l lb eu s e dt os o l v eo p t i m i z a t i o n a r r a n g i n g , g r o u p i n g ， s e q u e n c i n g o r r i d d i n g o fm o s td i s c r e t ee v e n t s t h e s ep r o b l e m s b e l o n g t ot h e n o n p o l y n o m i a l - c o m p l e t e ( n p c ) p r o b l e m s ，w h i c hc a nn o tb es o l v e di np o l y n o m i a lt i m e w i t ht h ee n l a r g e m e n to ft h ep r o b l e m ss c a l e t h ep r o b l e ms p a c ee n d su pe x p l o d i n gu p i ti s u n l i k e l yt ob es o l v e dw i t hg e n e r a la l g o r i t h m s 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 ) i ss u c ha c l a s s i c a lc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m o nt h eo t h e rh a n d ，g e n e t i c a l g o t i t h m ( g a ) i so n eo fn e wt e c h n o l o g i e s f o r o p t i m i z a t i o n w h i c hi st h ei m i t a t i o no fd a r w i n se v o l u t i o n s i m g e to p t i m a ls o l u t i o n t h r o u g hr e p r o d u c t i o n ，c r o s s o v e ra n dm u t a t i o n o p e r a t i o n s w i t hi m p l i c i tp a r a l l e l m e c h a n i s ma n da d a p t a b i l i t y s oi ti sf i tf o rt h o s ek i n d so fm u l t i d i m e n s i o n a ln o n l i n e a r p r o b l e m sw i t hm u l t i p l ep e a kv a l u e s g aw h i c hw a sp r e s e n t e db yh o l l a n di n 19 6 0 sa n d g e n e r a l i z e dt os t a n d a r dg ai n19 8 0 si sb e c o m i n gap o p u l a rd o m a i ni n c r e a s i n g l yi nt h e m i d d l eo f19 9 0 s t h e n ，m a n yr e s e a r c h e r sf o c u s e do nt h ei m p r o v e m e n ta n dt h ea p p l i c a t i o n o fg a g ai sa b l et os e a r c hg l o b a l l ya n di s e a s yt oi m p l e m e n t i n i t i a l l y , i ti su s e df o r n o n n u m e r i cc o m p u t i n ga n dt h e ni no p e i m i z a t i o nd o m a i nr e c e n t l y h o w e v e r , g ai s b e c o m i n gah o ta r e ai n a r t i f i c i a li n t e l l i g e n c ea n di n t e r e s t e di nb ym o r ea n dm o r e t h i sp a p e ri sb a s e do nt h ei d e a so fb u n c ho fc l a s s i cg a st h a th a sb e e np r o p o s e db y s c h o l a r s i ta n a l y z e st h er e a s o n sw h yc l a s s i cg a sh a sas l o wc o n v e r g e n c es p e e d i n s p i r e d b ym ya d v i s o r , t h i sp a p e rp r e s e n t se i g h ti m p r o v e dg a si nw h i c hw ei n v e n t e das e to f i n i t i a l i z a t i o no p e r a t o r s ，c r o s s o v e ro p e r a t o r so rm u t a t i o no p e r a t o r s e x p e r i m e n t a lr e s u l t so f2 p r o b l e m si nt s p l i bw i t hb o t hc l a s s i cg a sa n dt h ei m p r o v e da l g o r i t h m sh a v es h o w ng r e a t e f f e c t i v e n e s sa n de f f i c i e n c yo ft h el a t t e ro n e s k e y w o r d s ：g e n e t i ca l g o r i g h t m ，t r a v e l i n gs a l e s m a np r o b l e m 北京工商大学学位论文原创性声明 本人郑重声明：所呈交的学位论文是本人在导师指导下进行的研究工作所 取得的研究成果。除了文中已经注明引用的内容外，论文中不包含其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本声明的法律后果完全由本人承担。 学位论文作者签名：糌日期：汐。驴年。6 月z 。日 北京工商大学学位论文授权使用声明 本人完全了解北京工商大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属北京工商大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以采用影印、缩印或其它复 制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 学位论文电子版同意提交后，可于以年口一年口二年后在学校图 书馆网站上发布，供校内师生浏览。 学位论文作者签名：导师签名： 菇未书 日期：o 彦年6 月，绍 北京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 ) 是一个既古老、又有广泛实际 应用价值的问题。当今许多实际领域的问题都可以归结为t s p 问题，例如网络通讯、 电气布线、管道铺设、货物运输、加工调度等等。特别是它在算法理论研究上的价值， 一直吸引着各个领域的研究人员去研究新的算法。 由于t s p 问题在理论上已经被证明是n p 完全的问题，于是近年来兴起了用遗传 算法求解其近似解。目前，已经有很多文献研究和改进了求解t s p 问题的遗传算法。 但是，对于仞始种群的选择和种群的更换，大多数都是基于随机函数来实现的，有一 定的随机性和盲目性。 t s p 问题实质上是寻找最短的h a m i l t o n 回路。此回路中所有边的权值平均数当然 也是最小的。这就引发了权值小的边( 简称小边) 是t s p 问题求解过程中的一个关键 点。 我的导师刘书家教授和姜同强老师证明了下面的结论： 在边权值非负的无向图中，将每条边按权值由d , n 大排序，则最小h a m i l t o n 回路 必至少含有前p ( n ) 个小边之一。p ( 1 1 ) 定义为 p ( 雅) ： 研：一4 ”+ 8 ) 4 , ，l 为偶数且玎 4 b r j - i 2 4 n + 7 ) 4 ，n 为奇数且，l 5 时 n 为无向图中点的个数。 遗传算法是一种随机算法，通过代的不断更替来逼近最优解，具有很强的随机性， 如果能在经典的遗传算法过程中引入一些启发式搜索策略，则遗传算法的效率会大大 提高。 本课题以上述结论作为启发知识，引入到解t s p 的遗传算法中，以提高其搜索质 量。 以小边为基冈解t s p 问题遗传算法研究 3 研究内容及研究设想 和其它的优化算法一样，遗传算法自身存在着一定的局限性，主要表现在：( 1 ) 全局搜索能力相对较强而局部寻优能力较差；( 2 ) 对搜索空间编号的适应能力较差；( 3 ) 因为种群中的多样性过早的减少，易出现早熟现象；( 4 ) 算法在交叉、变异的进化过程 中随机性较强，到目前为止有关遗传算子控制参数值的选择上还没有理论上的指导， 往往得依靠实验或经验来确定。 本论文研究如何设计算法来实现以小边为基因的思想，以求达到对经典遗传算法 的改进。我们考虑的主要问题是小边为基因的思想在遗传算法的各个环节中怎么来设 计和体现。 为此，我们打算在遗传算法的整个过程中保留住一些以小边为基因的个体。为了 达到这个目的，我们通过初始化生成一些含有小边的个体，然后在代的更替中不去破 坏这些小边。由此我们对遗传算法的两个交叉算子进行了改进，同时对一个变异算子 进行了修改，使得在遗传算法不断迭代的过程中个体中的小边不会丢失。 4 研究意义 t s p 是最优化方法理论研究中很重要的一环，有着很重要的理论价值。t s p 源于 h a m i l t o n 回路问题，它们都是图论中的经典问题。t s p 又是n p 完全问题，大量的理 论问题都可以多项式归约到它。因此，寻找有效的近似算法早已成为学者们的研究方 向。而遗传算法是最近二三十年提出的，是一种比较有效的近似算法。 t s p 问题可以广泛地应用于许多领域，而且问题的规模( 城市数日) 都很大。如： 电路板钻孔问题，x 一射线结晶问题，v l s i ( 超大规模集成电路) 制造问题等等。t s p 问 题的n p 难度使得求解这些问题的最优解非常困难。而且t s p 问题由于其典型性已经 成为各种启发式的搜索、优化算法的间接比较标准。 而另一方面，遗传算法的兴起有两个背景。其一是工程领域，特别是人工智能与 控制领域，不断涌现出超大规模的非线性系统，这些系统的研究中存在大量的经典优 化方法所不能有效求解的优化问题。其二，遗传算法本身就是一种模拟自然演化这一 学习过程求解问题的方法。它能以独立的或与其它方法相结合的形式应用到智能机器 学习系统的设计当中。一般来说，任何难解的任务都可以被看成是要解决的一个问题。 反过来，它也可以被看成是对潜在解空间的一种搜索。因为我们的最终目的是要获得 2 北京：l 商人学硕+ 学位论文 最优解，所以可以把这种任务看成是一个优化过程。对小空间，经典的穷举法就足够 用了，而对于大空间，则需要使用特殊的人工智能搜索技术。 通过遗传算法解t s p 问题已经有很多的人在研究，但是效果并不十分理想。算法 的每一步随机性强。如果能在其中加入一些启发性的知识，则会加快算法的收敛速度。 本文在关于小边的结论基础上提出的算法能保证每个个体中均含有小边，而且每个小 边均被群体中的个体所含有。实验结果表明，本文提出的算法对于经典算法有了很大 改进。充分体现出其理论价值和应用价值。 3 以小边为基冈解t s p 问题遗传算法研究 第二章遗传算法的数学理论 遗传算法是一种仿生算法，即模拟生命演化的算法。它是从一个初始种群出发， 不断重复执行选择、杂交和变异的过程，使种群进化越来越接近某一目标。如果视种 群为超空间的一组点，选择、杂交和变异的过程即是在超空间中进行点集之间的某种 变换，通过信息交换使种群不断进化。 1 遗传算法的基本概念 遗传算法被认为是对人类自然演化过程的模拟。人类的自然演化过程是进化过 程，这种进化过程发生在染色体上；自然选择使适应值好的染色体比那些适应值差的 染色休有更多的繁嫡机会；变异可以使子代染色体不同于父代染色体；通过两个父代 染色体的结合与重组可以产生全新的染色体。染色体的选择、变异与重组进程是无记 忆的。将这些概念反映在数学上就形成了遗传算法的基本概念。 4 j 匕京j ：商人学硕+ 学位论文 问题域( 表现型) 遗传算i 去的过程 遗传算法的操作过程非常简单，从一个1 1 个串的初始群体出发，不断循环地执行 复制、杂交和变异过程。尽管遗传算法按这种简单的方式直接作用，在一个串的群体 上，但是我们已经开始认识到，在每代中，这种串的显式操作过程实际蕴含了大量模 式的隐含操作。本节讨论复制、杂交和变异算子对模式的影响。 不失一般性，考虑由二元字母表v 0 ，1 ) 编码的串( 依据生物术语，有时称串为 染色体) ，每个串可以用带下标的字母来形式地表示。其中下标代表位置，例如，一 个7 位串a = 0 1 1 1 0 0 0 可以记成 a 。a l a 2 a 3 a 4 a 5 a 6 a 7 5 以小边为基冈解t s p 问题遗传算法研究 这里每个a ，表示一个二元特征( 依据生物术语，有时称a 。为基因) ，可取值l 或 0 ( 有时称a 。的值为等位基因) 。在特定的串( 0 1 1 1 0 0 0 ) 中，a 。为0 ，a 2 为l ，a 3 为1 等等。 遗传算法通过一个串的群体来演化搜索，用a ( t ) 表示在时间( 或代) t 时的群体， 其中包含n 个串a i ，j = l ，2 ，n 。 除了描述串和群体的记号外，我们还需要简便的记号来描述包含在各个串和群体 中的模式。考虑由三元字母表v = 0 ，1 ，木) 表示的模式。如上一章所述，所谓模式就 是一个相同的构形，它描述的是一个串的子集，这个集合中的串之间在某些位上相同。 添加的符号半代表不确定字母，即在一特定位置上与0 或1 相匹配。 例如，考虑串长为7 的模式h = 木1 l 术o 料，则上面的串a = 0 1 1 1 0 0 0 是模式h 的个 表示，这是因为串a 与模式 i 在确定位置2 ，3 和5 上相匹配。 由上面的结果，定义串长为，的二进制串上的模式共有3 7 个。一般地，对于基数 为k 的字母表，共有( k + 1 ) 个模式。在n 个二进制串的群体中至多有，l 木2 7 个模式包 含在其中，这是由于每个串是它自身包含的27 个模式中的一个表示。 所有的模式并不是以同等机会产生的。有些模式比起其它的要更确定，例如，与 模式1 串1 料半术相比，模式1 木料木l 半在相似性方面是更明确的表示。某些模式的跨度要 比其它的长，例如，与模式1 水l 料术牢相比，模式l 术木料l 牢要跨越整个串长更大的部分。 为了定量地描迷模式，我们介绍两个概念：模式阶和定义长度。 一个模式h 的阶就是m 现在模式中确定位置的数目，记为o ( h ) 。在二进制串中。 一个模式的阶就是所有1 或0 的数目。以上面的模式为例，模式0 1 1 1 * 的阶为4 ， 可记为o ( 0 11 牢1 料) = 4 ，模式0 木木术水料的阶为i 。 一个模式的定义长度是模式中第一个确定位置与最后价确定位置之间的距离， 记为艿( 日) 。例如，模式0 1 l 木1 料韵定义长度为万= 4 ，这是因为第一个确定位置为1 ， 最后一个确定位置为5 ，它们之间的距离6 ( 日) = 5 一l = 4 ；由于另一个模式噼料木：l ：i ：仅有 一个固定位置，即第一个和最后一个确定位置是同一个，因此其定义长度万= 0 。 2 模式定理 模式、模式阶以及定义长度对于严格地讨论和区分串的相似性是有用的记号，并 6 北京ji ：商人学硕士学位论文 且它们提供了一个基本的方法来分析遗传算子对包含在群体中的基因块的作用效果。 下面分别考虑复制、杂交和变异算子对包含在串群体中的模式作用的单独效果和联合 效果。 模式定理在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平 均适应度高于群体平均适应度的模式在子代中将得以指数级增长。 模式定理是遗传算法的理论基础，其意义是深远的。 3 隐含并行性 在串长为，、规模为n 的二进制串群体中，包含有2 7 到以幸2 7 个模式，但是萨如模 式定理所表明的，并不是所有的模式都以较大的概率被进行处理，这是由于杂交算子 会破坏那些定义长度相对长的模式。本节讨论那些按有效的方式被处理的模式，即按 指数增长率采样的模式，并计算出这些模式数目的下界。 假如在n 个串长为，的二进制串中，我们仅考虑包含在其中的按大于某一常数p ， 的概率存活的模式，也就是说，假设在简单一点杂交算子和较小的变异率作用下，其 出错率e 小于( 卜鼽) 的模式，从而这些模式的定义长度要满足 f ( 0 0 ) ，f ( 11 ) f ( 0 1 ) ，f ( 11 ) f ( 1 0 ) 现在，设法引入迷惑遗传算法的条件。考虑4 个一阶模式的适应度，即f ( ：l c o ) ， f ( 木1 ) ，f ( o ：i ：) 以及f ( 1 术) 。一阶模式的适应度等于其包含的所有二阶模式的适应度的 平均值。即有 f ( 水o ) = f ( 0 0 ) + f ( 1 0 ) 2 f ( 木1 ) = i f ( 0 1 ) + f ( 1 1 ) 2 f ( o 木) = f ( o o ) + f ( 0 1 ) 2 f ( 1 宰) = f ( 1 0 ) + f ( 11 ) 2 令包含全局最优解f ( 11 ) 的一阶模式的适应度小于不包含最优解的一阶模式的适 应度，从数学上讲，就是 f ( o 术) f ( 1 ：l c ) f ( 木o ) f ( 木1 ) 有 f ( o o ) + f ( 0 1 ) 2 f ( 1 0 ) + f ( “) 2 f ( 0 0 ) + f ( 1 0 ) 2 f ( 0 1 ) + f ( 1 1 ) 2 上面二式给出了所谓的“欺骗”条件，下面我们将看到欺骗条件会迷惑遗传算法。 使得遗传算法偏离全局最优值f ( 11 ) 。同时可以看出，上面二式并不能同时成立，否 则就有，f ( o o ) f ( 1 1 ) ，从而违背了f ( 1 1 ) 是全局最优值的假定，不失一般性，不妨假 定第一式成立。由此，通过一个全局条件( f ( 1 1 ) 为全局最优值) 和一个“欺骗”条件 ( f ( 0 木) f ( 1 牢) ) ，就确定了一个欺骗问题。 将上述各适应度值按f ( o o ) 进行规一化如下； r = f ( 1 1 ) f ( 0 0 ) ，c = f ( 0 1 ) f ( 0 0 ) ，c = f ( 1 0 ) f ( o o ) 则全局条件可以表示为 1 0 北京i ：商人学硕士学位论文 r ) l ，r k c ，r c 则“欺骗”条件可以表示为 r l + c - c 可推出 c d ( t 2 ，t 3 ) + d ( q ，t 4 ) 成 立，则把f i t 2 和t 3 t 4 断开，把点t l 和点t 4 相连为t i t 4 ，把点t 2 和点t 3 相连为t 2 t 3 。如此不 断下去，到没有可断开的边为止，可以得到一个更短的回路。2 - o p t 算法最坏情况下 时间复杂度为o ( n 2 ) 。 2t 1 1 8 t 4t 3 北京l ：商人学硕十学位论文 第四章以小边为基因的遗传算法设计 在前几章中，我们了解了什么是遗传算法以及什么是旅行商问题。在这一章里面， 我们着重介绍以我们怎么样使用以小边为基因，把小边的思想结合到遗传算法之中解 t s p 问题。 1 遗传编码 我们已知道，遗传算法主要是通过遗传操作对群体中具有某种结构形式的个体施 加结构重组处理，从而不断地搜索出群体中个体间的结构相似性，形成并优化积木块 以逐渐逼近最优解。由此可见，遗传算法不能直接处理问题空问的参数。必须把它们 转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作就叫做编 码，也可以称作( 问题的) 表示( r e p r e s e n t a t i o n ) 。 一般来讲，由于遗传算法的健壮性，它对编码的要求并不苛刻。实际上，大多数 问题都可以采用前面所见过的基因呈一维排列的染色体表现形式，尤其是基于 0 ，l 符号集的二值编码形式。然而，正如我们将在后面的论述中所见到的那样。编码的策 略或方法对于遗传操作，尤其是对于交叉操作的功能有很大影响。在很多情况下，编 码形式也就决定了交叉操作，编码问题往往称作编码一交叉问题。因此，作为遗传算 法流程中第一步的编码技术是遗传算法研究中需要认真考虑的课题。本节主要介绍编 码评估准则以及各种编码技术。 1 1 编码问题 问题空间和g a 空间存在着对应关系。所谓问题空间是指由g a 表现型个体( 有效 的候选解) 集所组成的空间；所谓g a 空间是指由基因型个体所组成的空间。在g a 空 间中，个体的迁移是由交叉和变异所决定的。个体因一次变异所能迁移的局部空间叫 做变异近邻( m u t a t i o nn e i g h b o r h o o d ) ；由两个个体进行一次交叉所能迁移的局部空 间叫交叉近邻( c r o s s o v e rn e i g h b o r h o o d ) 。在g a 空间中。由于交叉近邻是由两个个 体所决定的，所以它比变异近邻迁移要大些。这也反映了遗传算法由于其核心操作一 交叉所具有的全局搜索性。 定义由问题空间向g a 空间的映射称作编码( c o d i n g ) ，而由g a 空间向问题空间 的映射称作译码( d e c o d i n g ) 。 需要指出的是，如果编码( 包括译码) 和交叉处理不当，在g a 空间中因交叉而生 1 9 以小边为基冈解t s p 问题遗传算法研究 成的个体逆映射到问题空间时，有可能成为无用解。这里称形成无用解的染色体为致 死基因。同时，即使逆映射到问题空间的是有用解，但也可能是和双亲完全无缘的解。 毫无疑同，我们不希望在问题空间中有这些不适当的解个体形成，这里，编码要发挥 一定的作用。 1 2 编码技术 下面，我们将介绍解t s p 问题的遗传算法的两种编码技术。由于编码设计往往不 能与交叉设计分开，所以在重点介绍编码技术的同时须简单地介绍相应的交叉技术。 有关这些交叉的详细介绍请参阅以后相关章节。 1 路径表示法 所谓路径表示法是指搜索空间的参数转换到遗传空间后，其相应的基因呈一维排 列构成染色体。具体地说，在遗传空问中，用以表示个体的字符集中的要素构成了字 符串。如4 个城市t s p 问题中的某个可行解可编码成： ( a ，b ，c ，d ) 或( 1 ，2 ，3 ，4 ) 其中a ，b ，c ，d 为城市名，l ，2 ，3 ，4 为相应的城市编号。 2 顺序表示法 该方法将所有城市依次排列构成一个顺序表( o r d i n a ll i s t ) 。如c = ( 1 ，2 ，3 ，4 ，5 ， 6 ，7 ，8 ，9 ) 一条旅程，以其经过的城市在c 中的位置标记，注意每处理完一个城市，便从c 中删除该城市，下一城市以其在当前c 中的位置标记。 例如旅程：卜2 - 4 - 3 - 8 5 - 9 - 6 - 7 当前c = ( 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ) ，1 号城市在c 中的位置为l ； 删除1 号城市，当前c = ( 2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ) ，2 号城市在c 中的位置仍为 1 ； 删除2 号城市，当前c = ( 3 ，4 ，5 ，6 ，7 ，8 ，9 ) ，4 号城市在c 中的位置仍为2 ； 删除4 号城市，当前c = ( 3 ，5 ，6 ，7 ，8 ，9 ) ，3 号城市在c 中的位置仍为1 ； 删除3 号城市，当前c _ ( 5 ，6 ，7 ，8 ，9 ) ，8 号城市在c 中的位置仍为4 ； 删除8 号城市，当前c = ( 5 ，6 ，7 ，9 ) ，5 号城市在c 中的位置仍为l ； 删除5 号城市，当前c - ( 6 ，7 ，9 ) ，9 号城市在c 中的位置仍为3 ： 删除9 号城市，当前c = ( 6 ，7 ) ，6 号城市在c 中的位置仍为1 ； 2 0 北京j ：商人学硕十学位论文 删除6 号城市，当前c = ( 7 ) ，7 号城市在c 中的位置仍为1 ； 该旅程表示为：( 1 1 2 1 4 1 3 1 1 ) 由于路径表示法很简单，很自然。所以在本文实验中，我们选择的是路径表示法。 2 适应度函数 遗传算法存进化搜索中基本上不用外部信息。仅用目标函数即适应度函数为依 据。对目标函数的唯一要求是，针对输入可计算出能加以比较的非负结果。这特点使 得遗传算法应用范围很广。 ， 在解t s p 问题时，适应度函数的设计要结合求解问题本身的要求而定。适应度函 数评估是选择操作的依据。适应度函数设计直接影响到遗传算法的性能。 本文采用的适应度函数如下： n - i 们) = d ( c c f 小1 ) + d ( c ，o ，c i 扩1 ) = o 其中，f 0 ，1 ，2 ，m 1 ) 为个体的编码( m 为个体总数) ，以为城市个数，d ( c 。，c ：) 表示城市c l 到c ：的距离。 显然，个体适应度越小说明结果越好。 3 以小边为基因的初始化策略 在第一章的“研究内容与研究设想 一节中，我们曾经提到过我的导师证明的一 个结论。 由这个结论，自然而然地，我们可以想到一种初始化策略。首先，对所有的n ( n - 1 ) 2 条边进行由小到大排序。称其中前p ( n ) 条边为小边。第二步，初始化时先把第一条小 边对应的两个点放入第个个体，再随机地把后面的点放入这第一个个体。第三步， 取第二条小边按此方法生成第二个个体。如此这般，可以生成p ( n ) 个个体。这里做一 个大小为p ( n ) 的数组r e p r e s e n t a t i v e s 来记录这p ( n ) 个个体在当前群体中的位置。在生 成过程中，小边的位置都保持不动。例如，设a b 边和c d 边为前p ( n ) 条边中的两条 小边，在生成个体时，把这两条边分别放入对应的两个个体，而且让这两条边始终是 这两个个体的第一条边，即作为个体的特征而存在。这种方法要求群体中个体的个数 大于等于p ( n ) ，否则会有小边不会被取到。 2 1 以小边为基冈解t s p 问题遗传算法研究 对于群体中除前p ( n ) 个个体以外的个体，可以按下面的方式来生成： 继续按照取第( 个体编号m o dp ( n ) ) 条小边来生成第( 个体编号) 个个体，直到个体 数达到群体规模为止。生成完毕以后更新r e p r e s e n t a t i v e s 数组，使其指向当前代中所 有小边对应的最优个体。这种方式可以保证交叉操作的简单性。即可以每次以小边为 中心，在小边以外的部分进行交叉，如下图。图中，a b 边和c d 边为小边，每次交 叉时并不把它