（应用数学专业论文）基于改进遗传算法的多目标tsp问题研究.pdf

摘要 t s p ( t r a v e l i n gs a l e s m a np r o b l e m ，旅行商问题) 是指给定n 个城市和各城市 间的距离，要求确定一条经过各个城市当且仅当一次的最短路线。它是一种典 型的组合优化问题，其最优解的求解代价是指数级的。已经证明t s p 问题是一 个n p h a r d 问题。基于智能优化算法求解t s p 问题，是近年来刚刚兴起的热门 课题。 然而在科学管理与经济决策的许多应用领域中，现实世界存在着大量的多 目标优化问题。对于旅行商问题( 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 h a r d 的数学 理论模型，它属于演化计算的一个新的研究领域。与经典的t s p 相比，多目标 t s p 更复杂，具有更大的挑战性。多目标t s p 的研究将推动一些实际问题的解 决，如投资问题。投资者一般希望所投入的资金量最少，风险最小，且获得的 收益最大。所以研究多目标t s p 具有重大的理论意义和应用价值。 关于多目标问题的研究在国内外都刚起步，鉴于以上研究现状，本文提出了 一种多目标遗传算法。主要包括以下工作： 1 介绍了t s p 的研究现状、基本知识和遗传算法的基础理论知识。 2 介绍了作者对多目标t s p 取得的研究成果：针对传统遗传算法求解的缺陷 及多目标t s p 问题解的特性，进行了一系列的改进，首先采用g r e f e n s t e t t e t 编 码对候选初始解进行编码，引进了一个线性函数来计算选择概率，提出了一种 改进的交叉和变异算子，建立多目标旅行商问题模型，设计出了一种能够较好 求解多目标t s p 问题的遗传算法计算机仿真实验验证了该算法的有效性 最后，本文对所做的工作以及进一步的研究方向做了总结和展望。 关键词：多目标t s p ，遗传算法，g r e f e n s t e t t e t 编码，适应度函数，选择算子， 变异算子 a b s t r a c t i nt h et r a v e l i n gs a l e s m a np r o b l e m ( t s p ) ，w ea r eg i v e nnc i t i e st o g e t h e rw i t ht h e p a i r w i s ed i s t a n e e sb e t w e e ne a c ht w oc i t i e s t h eg o a li st of i n dt h es h o r t e s tt o u rv i s i t s e v e r yc i t ye x a c t l yo n c ea n di nt h ee n dr e t u r n st oi t ss t a r t i n gc i t y t h et s p i so n eo f t h em o s tf a m o u sp r o b l e m si nc o m b i n a t o r i a lo p t i m i z a t i o n t h ec o s tt or e s o l v et s pi s e x p o n e n t i a la n di ti sp r o v e nt ob en p h a r d h o w e v e r i nm a n ya p p l i c a t i o na r e a so fs c i e n t i f i cm a n a g e m e n ta n de c o n o m i c d e c i s i o nm a k i n g ，t h e r ea r eal o to fm u l t i o b je c t i v e o p t i m i z a t i o n p r o b l e m s i na s p e c i f i c 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 ) ，o f t e nh a v et o c o n s i d e rs o m eg o a l s s i m u l t a n e o u s l y , s u c h a st h es h o r t e s t r o u t e ，t h em i n i m u mt i m e ，t h e l o w e s tr i s k ， t h em i n i m u mc o s ta n dm a n yo t h e rf a c t o r s h o wt og e taf a i ra n dr e a s o n a b l es o l u t i o n i sac o m p l i c a t e di s s u e m u l t i o b j e c t i v et s p ( m o t s p ) ，an e wr e s e a r c hf i l e do fe v o l u t i o n a r yc o m p u t a t i o n ， i sa nn p - h a r d p r o b l e m w h i c hc o m e sf i o mt h e a p p l i c a t i o n s o f c o m m u n i c a t i o n s ，1 0 g l s t i e s i ti sh a r d e rt h a nc l a s s i c a lt s er e s e a r c h i n gm o t s p w o u l dp r o m o t ead e v e l o p m e n to fs o m er e a l r i s t i cp r o b l e m ss u c ha si n v e s t m e n t p r o b l e m t h ei n v e s t o r su s u a l l yw a n tt oi n v e s tl e s sc a p i t a l ，h a v el e s sr i s k i n ga n dm u c h r e t u n s s or e s e a r c h i n gm o t s pi so fg r e a tt h e o r e t i c a ls i g n i f i c a n c ea n dr e s e a r c hv a l u e s o m er e s e a r c h e so nm o t s ph a v eb e e nd o n er e c e n t l y b a s e do nt h ea b o v e b a c k g r o u n d s ，w ed e s i g n e da ng e n e t i ca l g o r i t h mt h a tc a ns o l v et h eo p t i m a ls o l u t i o n s o fm o t s p w eh a v ed o n et h ef o l l o w i n gw o r k ： 1 i n t r o d u c et h eb a s i ck n o w l e d g eo ft s pa n dg e n e t i ca l g o r i t h m ，a n dt h er e s e a r c h s t a t u sf o r t s p 2 i n t r o d u c et h ea u t h o r sp r o d u c t i o n sa b o u tm o t s p ：b ya n a n l y z i n gt h ed e f i c i e n c yo f t r a d i t i o n a lg ai ns o l v i n gm o t s pa n dt h ec h a r a c t e r r i s t i co fm o t s p , w eh a v ea s e r i e so fi m p r o v e m e n tw h e nu s e dt os o l v et s p , i t f i r s t l y t o o ka d v a n t a g eo f g r e f e n s t e t t e tr e p r e s e n t a t i o nt oe n c o d e ，i n t r o d u c e dal i n e a rf u n c t i o nt oc a l c u l a t e s e l e c t i o nr a t e ，t h ec r o s s o v e ro p e r a t o ra n dt h em u t a t i o no p e r a t o r sw e r ei m p r o v e d ，a n d e s t a b l i s h e da na d a p t e dm o t s pm o d e l ，t h e nd e s i g n e da na l g o r i t h mt h a tc a ns o l v et h e o p t i m a ls o l u t i o n so fm o t s pb e t t e r t h ee m u l a t i o nr e s u l t sp r o v e dt h ev a l i d i t yi n s o l v i n gm o t s e f i n a l l y w es u m m a r i z eo u rw o r ka n ds t a t et h ef u t u r ew o r k 、en e e dt od o k e yw o r d s ：m u l t i o b j e c tt s p ；g e n e t i ca l g o r i t h m ；g r e f e n s t e t t ee n c o d i n g ；f i t n e s s f i u n c t i o n ；s e l e c t i o no p e r a t o r ；m u t a t i o no p e r a t i o n 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保 留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) ，、十户 签名：主：遣) 型导师签名： 武汉理丁人学硕一l - 论文 1 1 研究背景 1 1 1 最优化问题简述 第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 ) ，自1 9 3 2 年k m e n g e r 提出以来，已引 起各领域许多研究者的兴趣。它形式简单，难度却极大，但应用价值也很大， 例如在芯片设计、机器人控制、车辆选路，甚至在基因测序方面都有广泛的应 用。t s p 问题是组合数学中一个古老而又困难的问题，也是组合优化中研究最 多的问题之一，但至今尚未彻底解决，仍然有许多学者在孜孜不倦地研究解决 方案。然而当今社会科技水平日新月异，随着新技术新工具的出现，许多新的 问题随之而来。例如，高速、高效的网络让世界连成一个庞大的因特网，实时 的网络管理机制需要在短时间内对产生连接方案，这就对问题产生了实时需求， 即要求解决动态问题而在求解过程中，通讯距离跟通讯成本、通讯速度之问往 往产生一定的矛盾，不能同时兼顾，因而又产生了对多目标问题的需求，即要 求解决多目标问题，等等。对多目标问题提出高效的算法，将大大提高生产效 率，并将转化成实际的生产力，为国民经济的发展做出贡献也将推动科研水平 武汉理t 人学硕t ：论文 的发展，为更有效的算法提供基础，为问题的进一步研究提供参考。 1 2 研究现状及存在的问题 t s p 问题的求解，一直以来倍受人们的关注。对于这样一个典型的、易于 描述却难以处理的n p 难题，有效地解决它在可计算理论上有着重要的理论价 值。目前，对于求解t s p 问题，国内外都有相当好的进展。在国内，康立山教 授等研究用演化算法解决t s p 问题，提出的郭涛算子( i n v e r - o v e ro p e r a t o r , 1 9 9 8 ) ， e l k 算子等在用演化计算求解t s p 问题领域达到了国际先进水平。2 0 0 0 年， 周培德用点集凸壳的多项式时间算法解决了3 1 个顶点的中国货郎担问题。 关于多目标t s p 问题的研究在国内外都刚起步，例如，j o c h e n ，k a t h r i n 等人研究了多目标组合优化问题的多个解之间的联系：李军民等则提出了非 群体迭代型多目标遗传算法与局部阶段搜索算法相结合的混合遗传算法求解 多目标问题。这些研究都取得了一定的成果，但是离比较好地解决问题还有 一定距离，因此这些问题都还有很大的研究空间。本文将在多目标问题的研 究基础上，作粗浅的探索性研究。 1 3 本文采用的理论方法和主要研究内容 1 3 1 理论方法 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是一种通过模拟生物界自然选择和 遗传机制的随机搜索算法，其遗传操作和编码技术比较简单，主要操作有选择、 交叉和变异，并且它是一种基于种群的搜索算法，这一特点使得g a 成为解决多 目标问题的很自然的选择。对于问题，以刀个城市的一种排列作为一条染色体， 随机构造若干条染色体构成初始种群，然后根据适应度进行优胜劣汰的选择， 每次繁殖由两个双亲产生一个子代根据一定的交叉算子和变异算子进行交叉和 变异。以一定的迭代次数或某个到达条件作为算法终止的条件。 g a 的搜索过程从问题解的一个集合开始，具有隐含并行搜索的特性，可 大大减少陷入局部最小的可能。但是对于大规模的问题，其搜索空间大，时间 长，往往会出现早熟收敛的情况另外，对初始种群很敏感，初始种群的选择常 常直接影响解的质量以及算法的效率。 本文选用遗传算法进行问题研究，在实验中，针对算法的缺点进行改进， 对更好的求解多目标t s p 问题有一定的意义，也能进一步提高g a 算法的性能。 2 武汉理工人学顾i ：论文 1 3 2 主要研究内容 本文主要研究基于遗传算法的多目标t s p 问题，具体内容如下： ( 1 ) 首先简述了t s p 问题，介绍了t s p 问题的一般模型及研究意义，然后 详细总结与介绍了t s p 问题的传统解决方法。 ( 2 ) 简要介绍了遗传算法的基本思想，然后对遗传算法的具体实现技术进行 了阐述，最后针对遗传算法主要运行参数的使用做了说明。 ( 3 ) 对多目标t s p 问题进行了描述，介绍了多目标t s p 问题的国内外研究 现状，并对标准遗传算法进行改进来解决多目标t s p 问题，最后给出了计算机 仿真实验结果。 1 4 本章小结 本章简单介绍了多目标问题的概念及相关问题的研究状况。给出本文研究 所采用的理论方法。在总结前人研究经验的基础上，最后概括了本文所研究工 作的主要内容。 3 武汉理t 人学硕j j 论文 第2 章t s p 问题的简介 2 1t s p 问题的定义 2 1 1t s p 问题的一般性描述 t s p 问题可以简单地描述成：一名旅行商从一个城市出发，欲遍访n 个城 市推销商品，每个城市到一次且仅到一次后返回原出发城市，求总距离最短的 巡回路径。t s p 问题属于典型的组合优化问题，并且是一个n p 完全问题，其 可能的路径数目为( n - 1 ) ! 2 ，至今尚未找到有效的解决方法。在理论上一些方 法是可以解这一问题，但当刀较大时，解题的时间消耗会使这些方法显得没有 任何实际价值，所以设计一种有效算法以获得问题的最优解或近似解是具有重 要意义的他- 引。如可用来解决分配问题、路径问题、车辆调度问题等，以及算法 理论研究上的价值，所以它一直吸引着各个领域的研究人员去研究各种新的算 法。 2 1 2t s p 问题的数学模型 t s p 问题的数学模型如下：设有n 个城市，寻找一条巡回路径 t = ( f 。，f ：，t 。) ，使得下列目标函数最小： 型 厂( 丁) = d ( t f ，t “1 ) + d ( f 。，t 1 ) i = 1 其中t i 为城市号，取值为l 到船之间的自然数，d ( i ，_ ，) 为城市i 和城市j 之间的 距离，对于对称式t s p ，有d ( i ，j ) = d ( j ，f ) 。 除此之外，模型还有其它一些等价的书写形式，这旱不一一列举。 2 1 3t s p 问题的意义 可计算性理论研究证明，问题是一个完全问题。可计算性理论还告诉我们： 任何n p 完全问题都不能用任何已知的多项式时间算法求解；若任何一个n p 完全问题有多项式时间算法，则一切n p 完全问题都有多项式时间算法。然而， n p 完全问题是否有多项式时间算法，至今无人证明，也无人证伪。人们普遍认 为，不发展全新的数学技术就无法证明证伪这个猜想。但事实上，大多数人都 猜想它没有多项式算法。许多人相信，难计算是这样一类问题的固有性质，它 4 武汉理t 人学硕i ：论文 们不可能用有效算法求解，而所有能精确求解n p 完全问题的算法，在最坏情况 下都需要指数级的时间。 另外，t s p 问题是一个理想化的问题，大多数对于此问题的研究都不是为 了直接的实际应用，但这些研究可以经转化后用于许多现实的组合优化问题。 很自然地可以想到，t s p 问题的成果可以应用于运输和物流问题。t s p 问题最 早的应用是在上个世纪的四十年代，应用于校车路线的优化。现在，t s p 问题 在越来越多的方面得到应用： ( 1 ) 电路板钻孔进度的安排。在这个应用当中，电路板上的孔代表t s p 问 题中的城市，钻头从一个钻孔移动到另一个钻孔相当于t s p 问题中在城市间移 动。寻找最短路径变成了寻找最省时的外头移动时间。尽管目前钻机的工艺技 术发展很快，但钻头的移动时问仍然是一个令人头疼的问题。 ( 2 ) 基因测序。c o n c o r d e 是一种求解t s p 问题的程序。美国国家卫生机构 的研究人员利用这一程序来进行基因测序。在这一应用中，局部的基因图谱作 为城市，城市与城市的距离代表某张图谱与其它图谱相连的可能性。研究人员 试图寻找一种可能性最高的连接方式把主些局部的图谱合成为整张基因图谱。 ( 3 ) 半导体的线路设计。一家半导体生产厂家应用c o n c o r d e 程序来人优化 半导体的线路设计，这样可以节省刻制半导体的时间，也能减少半导体电路消 耗的能量。 ( 4 ) 光缆的线路设计。贝尔电话公司利用c o n c o r d e 程序来设计光缆的铺设 绕路，同样的方法也应用于电话和电力线路的铺设当中。 ( 5 ) 在机器人控制等其它方面，t s p 问题也有应用。 2 2t s p 问题的传统解决方法 几十年来对于求解t s p 问题出现了很多传统方法，其中有精确算法如线性 规划算法、动态规划算法、分枝定界法( b r a n c ha n db o u n d ) ；近似优化算法如最 近插入法( n e a r e s ti n s e r t i o n ) 、最近邻算法( n e a r e s tn e i g h b o r ) 、c l a r k & w r i g h t 算 法、双最小生成树法( d o u b l em i n i n gs p a n i n gt r e e ) 、贪婪法( g r e e d ya l g o r i t h m ) 、 k 一交叉法、混合算法、概率算法等。我们对这些方法进行简单的介绍。 2 2 1 精确算法 ( 1 ) 线性规划算法 这是求解t s p 问题的最早的一种算法，主要是采用整数规划中的割平面法， 即先求解模型中由- f i i j - - 个约束构成的松驰线性规划问题，然后通过增加不等式 约束产生割平面，逐渐收敛到最优解。 武汉理_ t 人学硕j j 论文 7 0 年代中期对于t s 多面体理论的研究，产生了一些比较有效的不等式约 束，如子回路消去不等式( s u b t o u r e l i m i n a t i o n ) 、梳子不等式( c o m bi n e q u a l i t i e s ) 、 团树不等式( c l i q u et r e ei n e q u a l i t i e s ) 等等。这些约束提高了搜索效率，但使得割 平面法相当复杂，用语言写大约需要1 0 0 0 0 行代码。而且，这个算法还相当耗 时，例如，求解2 3 9 2 个城市的t s p 问题，就要在一台强力计算机上用超过2 7 小时才计算出来i t s 。 目前，常用方法是先用近似算法来求得近似解，再将此近似解作为下限， 用线性规划方法来精确求解或证明此下限为最优解。 对于目前最大的己成功求解的例子s w e d e n ( 2 4 9 7 8 ) 城市数为2 4 9 7 8 ，它的求 解过程如下： 第一步，用l k h 算法求得近似解8 5 5 5 9 7 ， 第二步，用线性规划法求得解的下限为8 5 5 3 9 1 1 7 ， 第三步，证明在8 5 5 3 9 1 1 7 和8 5 5 5 9 7 之间不存在解。 整个线性规划求解( 不包括用近似算法求解) 的过程是在工作站上完成的， 折算成个人计算机( i n t e lx e o n 2 8g h zp r o c e s s o r ) 所耗费的时问为8 4 8 年。 ( 2 ) 动态规划算法 由于动态规划算法的时间复杂度为o ( 咒2 2 “) ，空间复杂度为o ( 刀2 ”) ，故一 般除了很小规模的问题外，几乎不予采用。 ( 3 ) 分支定界法 分支定界法是一种应用范围很广的搜索算法，它通过有效的约束界限来控 制搜索进程，使之能向着状态空问树上有最优解的分支推进，以便尽快找出一 个最优解。该方法的关键在于约束界限的选取，不同的约束界限，可形成不同 的分支定界法。 虽说分支定乔法对于较大规模的问题并不十分有效，可有时却被用来求解 近似解。而且，将分支定界法与一些启发式算法相结合，常常能获得一些意外 的成功。 2 2 2 近似算法 由于精确算法所能求解的问题规模非常有限，实际中使用的往往都是多项 式阶数的近似算法或启发式算法( h u e r i s t i c s ) 。算法的好坏用c c 。e 来表示， c 为近似算法所得到的总行程，c 为最优总行程，e 为最坏情况下，近似解与 最优解的总行程之比所不超过的上界值。 ( 1 ) 插入型启发式算法( i n s e r t i o nh e u r i s t i c s ) 6 武汉理t 人学硕上论文 插入型算法可按插入规则的不同而分为若干类，其一般思想为： 第一步，通过某种插入方式选择插入边( f ，) 和插入点尼，将k 插入f 和之 问，形成 ，f ，k ，j ，) ； 第二步，依次进行直至形成回路解。 具体实施中，可以将出发点取取遍犷中各点而得到多个解，从中选择最好的一 个，但此时的时问消耗增加了n 倍。常见的插入型算法有最近插入法、最小插 入法、任意插入法、凸核插入法等等。 ( 2 ) 最近邻算法( n e a r e s tn e i g h b o rh e u r i s t i c s ) 基本步骤为： 第一步，任取一出发点： 第二步，依次取最近的点加入当前解中直至形成回路解。 具体实施中，可以将出发点取遍矿中各点而得到多个解，从中选择最好的 一个。但时间消耗将增加刀倍。 ( 3 ) c l a r k & w r i g h t 算法 基本步骤为： 第一步，任取一出发点p ，计算= d 4 - d 一d 驴： 第二步，将各s 。由大到小排列： 第三步，将排好后的各配对顶点 f ，) 依次适当连接，形成回路解。 ( 4 ) c h r i s t o f i d e s 算法 基本步骤为 第一步，首先求出最小生成树： 。 第二步，对树中所有奇顶点解最小权匹配问题： 第三步，将匹配边添加入生成树并求出其e u l e r 回路： 第四步，在回路点序列中去除重复点，形成回路解。 ( 5 ) 双生成树启发式算法( d o u b l es p a n n i n gt r e eh e u r i s t i c s ) 基本步骤为 第一步，首先求出最小生成树： 第二步，将树中各边都添加一重复边并求出其e u l e r 回路： 第三步，在回路点序列中去除重复点，形成回路解。 ( 6 ) 神经网络算法( n e u r a ln e t w o r ka l g o r i t h m ) 八十年代中后期，美、日等国家出现了一股神经网络研究热溉许多从事 脑科学、心理学、计算机科学以及电子学等方面的专家都在积极合作，开展这 一领域的研究。其早期思想源于四十年代，由于受v o nn e u m a n n 串行处理体系 的限制，一直进展不大，直到八十年代，美国生物物理学家h o p f i e l d 提出人工 7 武汉理t 人学硕l 论义 神经网络( a n n ) 模型，才被认为是一个重大突破。 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) ，是由大量处理单元即神经 元( n e u r o n s ) 互相连接而成的网络，通过反映人脑的基本特性，对人脑进行抽象， 简化和模拟的一种工程系统。人工神经网络算法成为近年来的热点研究领域， 涉及到电子科学与技术、电气工程、控制科学与技术等诸多学科，其应用领域 包括了建模、时间序列分析、模式识别和控制等，并且仍然在一断扩展。 作为神经网络的基本单元，神经元模型具备三个基本要素。其一是有一组 突触或连接，常用表示神经元和神经元之间的联接强度，或称之为权值，取值 可在负值和正值之间其二是具有反映生物神经元时空整合功能的输入信号累加 器其三是具有一个激励函数用于限制神经元的输出。典型的人工神经元模型如 图2 1 所示： 图2 - 1 人工神经元模型 在图中，x ( = 1 , 2 ，刀) 为神经元，的输入信号，w o 为联接权，f , 表示输 入信号线性组合后通过激励函数厂，0 。表示神经元的输出，只表示神经元的闽 值。 根据信息流向和网络的拓扑结构，可以将神经网络模型分成以下几大类： ( a ) 前馈神经网络；( b ) 反馈神经网络；( c ) 随机神经网络；( d ) 竞争神经网络。 而h o p f i e l d 和t a n k ( 1 9 8 5 ) 用a n n 方法求解t s p 问题获得成功以来，更是 引起了极大的关注，国内也报导了求解数百个结点的t s p 问题的有关结果。该 方法的思想是确定神经元之间的连接权，随着网络状态的变化，其能量不断减 少，最后达到平衡时，即收敛到一个局部最优解。w i l s o n 和p a w l e y 曾研究了算 法的稳定性，当刀很大时，他们得出了相当悲观的绪论，即，求解过程很有可 能陷入在解空间中作无目标的周游的困境，或者落到许多局部最小点中的某一 点上。但是，t a k e f u j i i ( 1 9 8 8 ) 等发现，只要适当修正l i a p u n o v 函数，就可消除许 8 2 ， 行 x x x 武汉理丁人学硕i j 论义 多困难，他们的结论因此而显得比较乐观。 目前，前述的几种神经网络都有在t s p 问题的应用实例，且取得了一定的 成功，但还存在着严重缺点，而且就一般实际问题而言，无法与其它近似算法 相比。因此，该算法的适用范围很可能在于非欧空间或不可度量的问题方面。 ( 7 ) 模拟退火法( s i m u l a t e da n n e a l i n ga l g o r i t h m ) 这是一种源于五十年代、基于m o n t ec a r l o 迭代求解思想的随机搜索算法， 八十年代才开始应用于组合优化领域，其出发点是将组合优化问题与统计力学 的热平衡作类比，把优化的目标函数视作能量函数，模仿物理学中固体物质的 退火处理，先加温使之具有足够高的能量，然后再逐渐降温，其内部能量也相 应下降，在热平衡条件下，物体内部处于不同状态的概率服从b o l t z m a n n 分布， 若退火步骤恰当，则最终会形成最低能量的基态。这种算法思想在求解优化问 题时，不但接受对目标函数( 能量函数) 有改进的状态，还以某种概率接受使目 标函数恶化的状态，从而可使之避免过早收敛到某个局部极值点，也正是这种 概率性的扰动能够使之跳出局部极值点，故而得到的解常常很好。经典的模拟 退火法流程为： 第一步，选择初始状态日( 初始解) 、初始温度、降温次数； 第二步，生成日的邻域状态h ，并计算z ( h 7 ) 一z ( 日) ； 第三步，按接受概率置换h ； 第四步，重复第二步直至停机条件满足。 模拟退火法所得解的好坏与初始状态、温度函数等都有一定的联系，降温 较快的效果不一定很好，效果好的，其降温过程又极其缓慢。但由于该方法适 用范围广，并可人为控制迭代次数，反复求解，因此具有很强的实用性。 ( 8 ) 演化算法( e v o l u t i o n a r ya l g o r i t h m ) 这是一种( 或者说一类) 来自生物进化理论中“适者生存 的自然选择原则 的搜索算法，它基于生物学的自然选择原理和自然遗传机制模拟生命的进化， 这种新近发展起来的完全异于传统思想的搜索和优化方法自j o h nh o l l a n d 等 f 1 9 7 5 ) 提出以来，获得了广泛的应用。尤其是在人工智能领域，取得了极大的 成功，对于许多复杂困难问题的解决提供了强有力的处理办法。 遗传算法用于优化问题时，其最主要特征就是它不在单点上进行优化，而 是从整个种群( p o p u l a t i o n ) 中选择生命力强的个体产生新的种群它使用随机转 换原理而不是确定性规则来工作。遗传算法中常用的遗传操作有选择 ( s e l e c t i o n ) 、繁殖( r e p r o d u c t i o n ) 、交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 等四种。其 中，选择算子是种群优胜劣汰竞争机制的裁判员，繁殖算子用于从旧种群生成 新种群，交叉算子用于从父代生成子代，变异算子用于对子代作某种变异。这 里，繁殖和交叉操作是遗传算法的有效性所在，但有时会丢失一些重要的遗传 9 武汉理工人学硕i 二论义 信息，适当的变异操作可保证这些有用信息的引入。 遗传算法在整个遗传过程中的遗传操作是随机性的，但它所呈现出的特征 并不是完全随机搜索，它能有效的利用历史信息来推测下一代期望性能有所提 高的寻优点集，这样一代代的不断遗传，最后收敛到一个最适应环境的个体上， 求得问题的最优解。 ( 9 ) 厂o p t 算法 该方法是一种局部改进搜索算法，由l i n 等人( 19 6 5 ) 提出，后来经完善成 为l k 算法( 1 9 7 3 ) ，至2 0 0 0 年经k e l dh e l s g a u n 改进成为l k h 算法。l k h 算法是 当今除穷举法外精确度最高的t s p 问题搜索算法，而且收敛速度相当快。 ，o p t 算法基本框架如下： 第一步，根据一定的规则求出每个顶点的候选顶点集，人为地规定该顶点 只能和候选集中的顶点相连接； 第二步，产生初始路线； 第三步，对第一个顶点轮流进行，o p t 交换，直到无法改进当前解为止。 ( 1 0 ) 其它算法 除了前面提及的一些典型的旅行商问题算法之外，还有其它许多方法可供 使用，如n o r b a c k 等人的何图解法( 1 9 7 7 ) 、我国学者提出的极小代数算法 ( 1 9 9 0 ) 、归约算法( 1 9 9 1 ) 、从模拟退火法引申而来的均场退火法、遗传退火法、 源于神经网络并本质上作为并行实现的弹性网法、自组织映射法等等。还有一 种使用效果也相当不错的禁忌( t a b u ) 搜索法，它采用了类似爬山法的移动原理， 将最近若干步内所得到的解储存在禁忌列表中，从而强制避免再次重复搜索表 中的解，该方法在九十年代曾求解过儿十万个顶点的大型t s p 问题 2 3 本章小结 本章介绍了t s p 问题的基本概念，包括般性描述和数学描述，还简单说 明了t s p 问题的难度之大，以及应用之广。然后主要介绍了当代对t s p 问题的 几个有代表性的算法。其中重点介绍了较有研究潜力的演化算法、神经网络算 法和，o p t 算法。 本章引出的遗传算法，是下一章重点描述的内容。 l o 武汉理t 人学硕 ：论文 第3 章遗传算法的基本理论 遗传算法的基本思想是基于d a r w i n 进化论的m e n d e l 的遗传学说。d a r w i n 进化论的最重要的是适者生存原理，它认为每一物种在发展中越来越适应环境。 物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变 化。当环境变化时，只有那些能适应新环境的个体特征能留下来。m e n d e l 遗传 学说最重要的是基因遗传原理。它认为遗传以密码方式存在于细胞中，并以基 因形式包含在染色体内，每个基因有特殊的位置并控制某种特殊性质，所以每 个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应 于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 遗传算法是根据生物进化思想启发而得出的一种全局优化算法。它将问题 的解集看作一个种群，通过不断的选择、交叉、变异等遗传操作，让解越来越 好。遗传算法的概念最早是由b a g l e yj d 在1 9 7 6 年提出的啪1 。而开始遗传算法 的理论和方法的系统性研究是1 9 7 5 年，这一开创性工作是由m i c h i g a n 大学的 完成的乜。当时，其主要目的是说明自然和人工系统的自适应过程。 h o l l a n d 所提出的算法称为标准遗传算法，简称g a 、c g a 或s g a ；而将 其它的“g a 类 算法称为g a s ，可以把g a 看成g a s 的一种特例。 遗传算法在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模 式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物 科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传 算法、自适应系统、细胞自动机制、混沌理论与人工智能一样，都是对今后十 年的计算技术有重大影响的关键技术 。 3 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 y j 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 实现了第一个基于遗传算法的机器学习系统一分类器系 统( c l a s s i f i e rs y s t e m ) ，建立了基于遗传算法的机器学习的新概念，为分类器的 构造提出了一个完整的框架。1 9 8 9 年，g o l d b e r g 出版了专著( ( g e n e t i ca l g o r i t h m s i ns e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a r i n g ) ) ，系统总结了遗传算法的主要研究 成果，全面完整的论述了遗传算法的基本原理和应用 3 0 o1 9 9 2 年，m i c h a l e w i c z 出版了另一本很有影响力的著作( ( g e n e t i ca l g o r i t h m + d a t as t r u c t u r e s = e v o l u t i o n p r o g r a m s ) ) ，对遗传算法应用于最优化问题起到了推波助澜的作用口。 1 9 9 2 年，s t a n f o r d 大学的j r k o z a 将遗传算法应用于计算机程序的优化设 计即自动生成，提出了遗传编程( g e n e t i cp r o g r a m m i n g ) 的概念。 3 2 遗传算法的基本思想 遗传算法的思路和自然进化的思路是同出一辙的。遗传算法主要借用生物 进化中“适者生存 的规律：最适合自然环境的群体往往产生了更大的后代群 体。在进化过程中，每个种群所面临的问题是寻找一种对复杂和变化着的环境 最有利的适应方式。每个种群所获得的“知识”都被嵌入其成员的染色体组成 当中。 遗传算法的思想正是做自然界想做的事情。我们以兔子作为例子h 叭：在一 给定时间里，有一群兔子，其中一些比另外一些兔子跑得快，而且更加聪明， 这些兔子被狐狸吃掉的可能性比较小，因此它们中的多数就存活下来并繁殖更 多的兔子。当然，一些慢而愚笨的兔子也会活下来，只是因为它们比较幸运。 这些存活的兔子群体开始生育。生育的结果是兔子遗传材质的充分融合：一些 慢的兔子生出快的兔子，一些快的兔子生出更快的，一些聪明的兔子生出愚笨 的兔子，等等。在最顶层，自然界时不时地变异一些兔子的基因材质。所产生 的小兔子平均来说要比原始的群体更快更聪明，因为从狐狸口中生存下来的父 代多数是跑得更快也更聪明的兔子。同样，狐狸也经历相似的过程否则兔 子可能跑得太快又太聪明以致狐狸根本抓不到了。可见，遗传算法遵循着和兔 子的故事极相似的过程。， 3 2 1 遗传算法的构成要素 基本遗传算法的构成要素有以下几个1 ： ( 1 ) 染色体编码方法。基本遗传算法使用固定长度的二进制符号串来表示群 1 2 武汉理t 大学硕 ：论文 体中的个体：初始群体中的各个个体的基因值可用均匀分布的随机数来生成。 ( 2 ) 个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当 前群体中每个个体遗传到下一代群体中的机会多少。 ( 3 ) 遗传算子( g e n e t i co p e r a t o r s ) 。基本遗传算法只使用下述三种遗传算子： 选择算子( s e l e c t i o no p e r a t o r ) 使用比例选择算子，交叉算子( c r o s s o v e ro p e r a t o r ) 使用单点交叉算子，变异算子( m u t a t i o no p e r a t o r ) 使用基本位变异算子或均匀变 异算子。 ( 4 ) 基本遗传算法的运行参数。基本遗传算法的运行参数有：群体大小m ， 终止进化代数丁，交叉概率( c r o s s o v e rr a t e ) p 。，变异概率( m u t a t i o nr a t e ) p ，。 这4 个运行参数对遗传算法的求解结果和效率都会有一定的影响，在遗传算法 的实际应用