（运筹学与控制论专业论文）神经网络在tsp问题中的应用研究.pdf

大连理工大学硕士学位论文：神经网络在t s p 问题中的应用研究刘乃文2 0 0 2 1 摘要 t s p 问题一直是组合优化中极富活力的研究课题之一。七十年代中 期，计算复杂性理论的出现和数学规划的发展大大推动了组合优化的前 进。计算复杂性理论表明，被称作n p 完全问题的旅行推销员问题以及其 它类似的组合优化问题在计算上是等价的。也就是说，不能用任何已知 的多项式算法求解这种问题。从这个新发现可以看出：最优化方法的能 力是有限的，这使得研究人员不得不寻求更好的解决办法。 神经网络的发展为这一问题的解决提供了一种新的思路。h o p f i e l d 神经网络算法是解决这一问题的经典算法，这一算法最初具有的不足之 处也得到了不断的改进。 本文所做的工作： 给出了t s p 问题的描述及数学模型 介绍了神经网络应用于t s p 问题的相关理论知识 h o p f i e l d 算法在求解t s p 问题中的应用分析 在已有的改进算法基础上，对h o p f i e l d 算法进一步改进 提出了大规模t s p 问题的基于分层聚类思想的解决方案 本文的创新之处： 分析了h o p f i e l d 神经网络算法解决t s p 问题的理论过程，在 已有改进算法的基础上，提出了新的改进，使得构造神经网 络的神经元数目由 2 个减少到( m 一1 1 2 个，简化了网络结构， 提高了算法效率，对于神经网络的硬件实现有重要的意义； 提出采用分层聚类的方法来解决大规模t s p 问题的方案。基 本思想是利用聚类神经网络先把地理位置上相互靠近的城市 划分为一个集体单位( 一个物理区域) ，用改进的h o p f i e l d 神经网络算法求解各个区域间的最优( 或近似最优) 路径， 然后再在每一个区域内部用同样的方法来求解其局部的最优 ( 或近似最优) 路径，这样可以最终得到全局的最优( 或近 似最优) 解。描述如下： 设有城市集合s ，按城市的地理位置把s 划分为若干子 t h e s i so f m a m 盯d e g r e e ，ms o , u o r c t d e p to f a p p t i e dm a t h e m a t i c s d a l i a nu n i v e r s i t yo f t e c h n o l o g y 摘要 集，得s = u s 。，其中s ，n o = 矿，i 。求得集合 = 1 s = 5 ；l i = 1 , 2 ， 的t s p 最优路径，再依次求得子集s ，内部 的t s p 最优路径，即得最终优化路径 ( s ，一s ，- - - ) , 一- - - s kl f ，j ，k ( 1 ，2 ，一，” f ，k ) a 这一思想的具体实现可以使得神经网络有效地用于大规 模t s p 问题的求解，同时也为用神经网络解决其它大规模组 合优化问题提供了一种可参考的思路。 关键词：t g p 问题最优路径人工神经元网络聚类神经网络学习 h o p f i e l d 神经网络 t h es t u d yo f n e u r a ln e t w o r k a p p l i e di nt h et r a v e l l i n gs a l e s m a np r o b l e m m r l i u n a i 呲n m2 0 0 2 大连理工大学硕士学位论文：神经网络在t s p 问题中的应用研究刘乃文2 0 0 2 3 a b s t r a c t 1 1 1 e t r a v e l l i n g s a l e s m a np r o b l e m ( t s p li s a l w a y s o n eo ft h em o s t i n t e r e s t i n gt o p i ci nc o m b i n a t o r i a lm a j o r i z a t i o n 。 i nt h em i d d l es e v e n t i e s t h e a p p e a r a n c eo ft h ec o m p l e x i t yt h e o r yo fc a l c u l a t i o na n dt h ed e v e l o p m e n to f m a t h e m a t i c a l p r o g r a n l m i n g h a v e g r e a t l yi m p r o v e d t h ea d v a n c e m e n to f c o m b i n a t o r i a lm a j o r i z a t i o n t h ec o m p l e x i t yt h e o r yo fc a l c u l a t i o nh a sp r m 7 e d t h a tt h es o c a l l e dp r o b l e mo fn pa n do t h e rs i m i l a rp r o b l e m sa r ee q u a li n c a l c u l a t i n g t h a ti st os a y , w ec a n n o tu s ea n yp o l y n o m i a la l g o r i t h mt os o l v e t h i sk i n do fp r o b l e m sf r o mt h i sn e wd i s c o v e r yw ef i n dt h a tt h ea b i l i t yo f o p t i m i z a t i o nm e t h o d i sl i m i t e da n dt h i sm a k e si tn e c e s s a r yf o rt h er e s e a r c h e s t of i n do u tb e t t e rs o l u t i o n s t h e d e v e l o p m e n t o fn e u r a ln e t w o r ko f f e r san e ws o l u t i o nt ot h i sp r o b l e m h o p f i e l dn e u r a ln e t w o r k ( h n n ) a l g o r i t h mi s at y p i c a lo n ei n s o l v i n gt l l i s p r o b l e m ，a n dt h ee a r l ys h o r t c o m i n g s o ft h i ss o l u t i o nh a v eb e e ng r e a t l y i m p r o v e d a g e n e r a li n t r o d u c t i o nt ot h em e s i s ： a d e s c r i p t i o no f t s p a n di t sm a t h e m a t i c a lm o d e l a ni n t r o d u c t i o no ft h et h e o r i e so fn e u r a ln e t w o r ka p p l i e dt ot h e t s p a n a p p l i c a t i v ea n a l y s i so f h n n i ns o l v i n gt h et s p t h ei m p r o v e m e n to f h n n t h ep r e s e n t a t i o no ft h es o l u t i o n so f l a r g es c a l et s p b a s e d0 1 1t h e i d e ao f s o r t i n g t h ei n n o v a t i o n so ft h i st h e s i s ： t h e a n a l y s i so ft h et h e o r e t i c a lp r o c e s so fh n n i ns o l v i n gt h e t s p p r o b l e m t h en e wi m p r o v m e u t o fi n no nt h eb a s i so f e a r l y i m p r o v e m e n t ，w h i c hm a k e st h en u m b e ro fn e u r a lr e d u c ef r o m 门2t o( n 1 ) 2a n d i m p l i f i e s t h ea r c h i t e c t u r eo fn e u r a l n e t w o r k a l s oi m p r o v e st h ee f f i c i e n c y n l i sh a sg r e a ts i g n i f i c a n c e i nr e a l i z i n gh a r d w a r eo f t h en e u r a ln e t w o r k t h e s i so f m a s t e rd e g r e e ，ms c ，u o r c t d e d to f a p p l i e dm a t h e m a t i c s d a l i a n u n i v e r s i t yo f t e c , h n o l o g y 摘要 d t h ep r e s e n t a t i o no f t l ei d e no f s o r t i n gb a s e do nd e l a m i n a t i o ni n s o l v i n gl a r g es c a l et s r t h eb a s i ct h o u g h ti st od i v i d et h ec i t i e s w h i c ha r ec l o s et oe a c ho t h e ri n t oag r o u pf p h y s i c a la r e a ) b y a p p l y i n gs o r t i n gn e u r a ln e t w o r k ，f e n do u tt h eo p t i m a lp a t hb yt h e i m p r o v e dh n n a n dt h e nc a l c u l a t et l l e 1 0 c a l o p f i m a lp a t hb y u s i n gt h es a l i l em e t h o d ，a n df i n a l l yg e tt h ew h o l eo p t i m a lp a t h ， w h i c ha r ed e s c r i b e da sf o l l o w i n g ： aa s s e m b l yso fc i t i e s i s g r o u p e d i n t os o m es u b s e t s a c c o r d i n gt ot h e i rp h y s i c a ll o c a t i o na n dw ec a ng e t s = u 墨， 泞l s j n s ? = 审，i 章j a n d t h e n g e t t h e o p t i m a l 。p a t h o ft s po f s = b 。l i = 1 ，2 ，”jt h r o u g h t h eg i v e n m e t h o d ，a s w e l la s t h e s s ow ec a r lg e tt h eu l t i m a t eo p t i m a l p a t h ： ( s ，。j ， 一j 女】f ，_ j ( 1 ，2 ，一， l f ，七) t h er e a l i z a t i o no ft h i si d e nm a ym a k en e u r a ln e t w o r kb e w i d e l ya p p l i e d i nt h e s o l v i n g o fl a r g es c a l et s p p r o b l e m ，a n d p r o v i d e ar e f e r a b l e w a y o f r e s o l v i n g o t h e r 1 a r g e s c a l e c o m b i n a t i o no p t i m a lp r o b l e m b y n e u r a ln e t w o r k k e y w o r d s ：t r a v e l l i n gs a l e s m a np r o b l e m ，o p t i m a lp a t h ，a r t i f i c a ln e l l a l n e t w o r k ，s o r t i n g ，s t u d yo f n e u r a ln e t w o r k ，h o p f i e l dn e u r a ln e t w o r k t h es m a yo f n e u r a l n e t w o r k a p p l i e d i n t h e t r a v e l l i n gs a l e s m a np r o b l e m m r l i un a t w e a f e b2 0 0 2 大连理工大学硕士学位论文：神经网络在t s p 问题中的应用研究刘乃文2 0 0 2 5 1 1 问题简述 第一章t s p 问题概述 旅行销售员问题( 简称t s p ) ，亦称邮递员路径问题，是典型的组合 优化问题。由于t s p 问题在实际应用中所具有的典型意义，比如可以用 于车辆调度、切割问题、分配问题和网络问题等，因而自从该问题被提 出以来，一直被各个领域的研究人员所关注。该问题的数学描述如下： 有n 个城市c = b ，c ：，“ ，给定其中任意两个城市之间的距离： ，( c ，c ，) = f ( f ，) ，1 f ， 现在要找出一个城市的排列 扛。( 1 1 c 。( 2 1 c 。( 3 1 一，c 。0 v ) ， 1 n n 使得闭合路径y 水。( f ) c 。( ( f + 1 ) m o d ) 】为最小。 i ：1 t s p 一直是组合优化中极富活力的研究课题之一。从最初的研究t s p 的离散模型到现在，几代组合学数学家和运筹学家对这个问题进行了广 泛而且深入的研究，并取得了很大的成就。例如：在整数规划求解中首 先引入了问题分割和分解技术，创立了与树列举方法有关的几个重要思 想，包括“分枝定界”等。动态规划的应用以及对组合优化启发式方法 的评价都已证明这些技术是富有成效的。 组合优化方法在五、六十年代应用于生产计划、机器调度和人员安 排等问题，以动态规划和一般整数规划方法为依据，设计优化算法。其 中最具有代表性的是c o n w a y 、m a x w e l l 和m i l l e r i l l 的调度理论以及用动态 规划方法设计库存管理和生产管理。同时，网络流理论的广泛应用也促 进了组合优化的发展。 七十年代中期，计算复杂性理论的出现和数学规划的发展再一次推 动了组合优化的前进，而且引起了社会的广泛关注。计算复杂性理论表 明，被称作n p 完全问题的旅行推销员问题以及其它类似组合优化问题在 t h e s i so f m a s t e rd e g r e e ，ms e ，u o r c t d e p lo f a p p l i e d m a t h e m a t i c s d a l i a nu n l v 盯s i t 3 o f t e c h n o l o g y 第一章t s p 问题概述6 计算上是等价的。也就是说，不能用任何已知的多项式算法求解这种问 题，如果任何一个这样的问题有多项式算法，那么所有这样的问题都有 多项式算法。从这个新发现可以看出：最优化方法的能力是有限的，这 使得设计和分析有效启发式方法成为研究的重点。于是，旅行推销员问 题又一次成为关注的焦点，对t s p 算法的最坏情况、统计以及概率等方 面的研究为启发式方法的分析方法奠定了基础。l e n s t r a 和r i r m o o yk a n 2 1 指出：这类问题绝大多数是n p 完全的，且有很多局部优化解。因此当城 市数目较多时，求解t s p 问题的全局最优解是十分困难的，通常的图论 解法显得无能为力。 1 2 已有的解决算法 解决t s p 问题的算法有局部搜索算法、直接树搜索法、动态规划法、 遗传算法及最近邻居算法等多种。下面简单介绍两种算法。 1 2 1 遗传算法6 l 遗传算法是建立在生物进化论基础上的算法，人们利用生物进化论 的观点发展了遗传算法。j o h nh o l l a n d 在1 9 7 5 年首先提出了遗传算法 ( g e n e t i c a l g o r i t h m ，简称g a ) 。他认为，许多复杂问题都可以用二进制 串编码表示，而且通过一些简单的变换规则可以逐步改进这些用二进制 编码串表示的结构，使之往“好”的方向“迸化”。遗传算法就是用来完 成这一“进化”过程的算法。j o h nh o l l a n d 已经证明峭】，在一定条件下遗 传算法可以在搜索空间中收敛到全局最优解。8 0 年代以来，基于进化论 观点的遗传算法进一步发展，并主要应用于优化计算。 1 2 1 1 。遗传算法的基本原理 遗传算法是一种基于自然选择和群体遗传机理的搜索算法。它模拟 了自然选择和自然遗传过程中发生的繁殖、交配和变异现象。对于复杂 的优化问题，遗传算法无需建模和进行复杂的运算，只要用遗传算法的 三种算子就能寻找到优化解，这三种算子就是复制、交叉和变异。 复制 复制就是依据每个兮体的适用度值来复制新个体的过程。根据不同 的问题，当适用度值越大或越小时，个体被复制的可能性就越大。适用 m t “u n a i w e n f e b2 0 0 2 大连理工大学硕士学位论文：神经网络在t s p 问题中的应用研究刘乃文2 0 0 27 度值是由适用度函数( 即评价函数) 转化而来的。适用度函数是根据不 同问题和目标而制定的目标函数，它是每个个体生存或淘汰的最终仲裁 者。 交叉 首先在新复制个体的群体中随机选择两个个体，然后沿着两个个体 均匀随机地取一个位置，最后二者互换该位置到末尾的部分。 变异 变异就是以很小的概率随机地改变字符串某个位置的值，它本身是 一种随机搜索，与复制和交叉算子结合在一起，保证了遗传算法的有效 性。 图1 就是建立在遗传机理基础上的遗传算法流程图 9 。遗传算法是 利用基因形成的各种基因组进行竞争，继而进行优生繁殖，得到下一代 的基因组的过程。在这个过程中使那些对应于符合要求的基因组获得更 多的生存机会，经过反复繁殖和进化得到一个较优的基因组。这个基因 组表现出的显性与要求的特性相符。整个算法要求确定“基因”、“基因 组”、评判标准( 评价函数，即适用度函数) 、删除的数目、复制的数目、 执行变异的算法以及子孙繁殖的数目。只要这些参数确定了，那么对于 任何问题都可以用图1 的算法进行计算。 用遗传算法解决一个实际的问题通常包括5 个方面： 问题解的基因表示 初始解的生成 从数值上表示解的优劣的评价函数 改变基因组成的遗传操作 遗传算法中的各个参数，如解组的大小和实行遗传操作的概率等 图1 遗传算法流程图 遗传算法的具体形式随着遗传操作的不同而有所不同，但其重要步 骤就是：在搜索的每一步，从解组中随机抽取两个解做为父母；通常对 t h e s i so f m a s t e r d e g v e ems c u o r c t d e p to f a p p l i e dm a t h e m 砒t c s d a l i a nu n i v e r s i t yo f t e c h n o l o g y 一茎二童! ! ! 塑望塑垄 ：! ： 父母解实行遗传操作后产生一个后代解；把此解加入解组，并根据某个 原则将原解组中的一个解替换出来；这一过程一直持续到解组中的各个 解都相同时，则算法就收敛了。 1 2 1 2 t s p 问题的遗传优化算法 t s p 问题的遗传优化算法中，各个基因组是按照一定顺序排列的城 市号码的组合。在计算过程中，只取部分的基因作为初值，然后沿着进 化方向繁殖子代。这样，计算量减少，速度也较快，问题的适用度是以 基因组合的最短路程为结果，所以算法也只能得到一个近似最优解。 算法的具体步骤如下： 1 随机组成m 个基因组，每个基因组是由n 个基因组成，他们表 示一条t s p 路径； 2 计算每个基因组的路径( 长度) ，作为他们对应的评价函数值； 3 比较评价函数值( 即路径长度) ，并且排序，进入选择阶段； 4 在选择阶段中，对于路程最优的那些基因组进行复制，对于差的 基因组进行删除； 5 进行交叉和变异，即可从亲代变异到子代，交叉和变异的方法是： 1 ) 可以将某个基因组代表的路径城市次序进行颠倒，每次只颠 倒一部分； 2 ) 对换两个城市之间的位置。 所有交叉和变异方法因为改动不大，所以计算量是不大的，对这些 子代再进行步骤2 的计算，这样新的一轮进化又开始了，因此子孙的增 加使输入样本面逐步扩大。但计算的量并不因为迭代的次数而增加，因 为在程序中对子代进行了删除和优化，每次迭代的计算量是固定的，最 后即可得到要求的解。 1 2 2 模拟退火算法 模拟退火算法是实现全局优化的一种基本途径，它是8 0 年代出现的 寻求全局极小的非线性优化算法，t s p 问题是这一算法在状态空间离散 时的典型应用。 7 “”“曲“”“”咄却m “”岫“”“s 骂雷魏器凛 f e b2 0 0 2 大连理工大学硕士学位论文：神经网络在t s p 问题中的应用研究刘乃文2 0 0 2 9 1 2 2 1 算法分析与步骤 模拟退火方法是n m e t r o p o l i s 等人在1 9 5 3 年研究二维相变时提出来 的。1 9 8 3 年g e h i n t o n ，t j s e j n o w s k i 和d h a c k l e y 把这种方法用于神 经网络，提出了波耳兹曼机。1 9 8 4 年s g e n m a n 和d g e m a n 给出了退火 t ，+ 、 率( 温度随时间变化率) 为二型o cl i n t 。其中t o 是初始温度。这个退火 o 过程太慢，因而效率很低，难以实用。1 9 8 5 年h a r o l dhs z u 提出一种快 速模拟退火方法，称为柯希机( c a u c h y m a c h i n e ) ，使这种方法有了实际应 用的可能性，因为退火率为r ( f ) r 0 1 t 。 模拟退火算法基本上由三部分组成 4 1 ： 1 以定的概率密度跃迁到新的状态，这个概率密度函数称为生成 函数； 2 以定概率密度容忍评估函数的偶然上升，这个概率密度函数称 为容忍函数： 3 以定的冷却程式降低温度，这个等效温度是生成函数和容忍函 数中的控制参量，确定所引入的随机扰动( 噪声) 的强度。 经典的模拟退火算法中采用了高斯型的生成函数，即 g 。( x ) “e x p - x 2 r o ) l ，其中t ( t ) 是温度，决定了概率密度分布的特征宽 度，这种分布函数远处是指数型衰减的，因而代表一种局域型搜寻过程， 为了能找到全局极小，温度要下降很慢，g e m a n 兄弟证明了它所要求的 退火方式为r ( 0 r o = 1 i n t ，其中t o 为初始温度，要求t o 取足够高的值。 该算法的过程大致如下：从一个随机选取的状态出发，依据生成概 率在每一步产生一个新的状态，如果这个新状态的评估函数值比原来的 状态低，则令它为系统的新状态；如果它比原来状态的评估函数高，则 它成为新状态的概率由容忍函数确定，若系统不进入这个新状态，则它 仍保持原先的状态，生成函数与容忍函数按照规定的冷却方式变化。 下面给出这一算法的具体步骤： 设x = 1 ，2 ，3 ， 是一有穷集合，称为状态空间。e 0 是定义在x 上的 t h e s i so f m a s t e rd e g r e e ，ms c ，u o r c t d e p to f a p p t i e dm a t h e m a t m s d n i a nu n i v e r s i t yo f t e c h a o l o g y 第一窜t s p 问题概述 非负实函数，称为能量。问题是：求i x ，使e ( f ) = r a i n me ( j ) 。求解 这一问题的模拟退火算法步骤表示如下【7 j ： 1 选择初始状态i o ，称之为当前状态。选择一个初始温度值t 0 ， 此时为第一个循环； 2 设处于第k 次循环，当前状态为f ；，按照某种规则，例如由首先 给定的状态转移概率矩阵进行抽样，随机选取一个状态j ，称之 为预选态； 3 计算血= ( ，) 一e 也) ；如果a e 0 ，因此 d e 0 为常数。巨保证当矩阵v 的每一行不多于一个1 时，置达 到最小e 。m m = 0 。 同理构成列约束条件为 e 。：昙宝宝窆v ， ( 3 2 7 ) 其中_ 8 0 为常数。e ：保证当矩阵f 的每一列不多于一个l 时，e ：达 至u 最0 、e ：。二0 。 构成全局约束 ，1 l n n i e ，= 等l v 。一”1 ( 3 2 8 ) o | z = 】i = ll 其中c 0 为常数。e 保证当矩阵v 中的1 的个数恰好为，2 时，即整 个矩阵有n 个1 时，易达到最小毛m m = 0 。 式( 3 2 6 ) 、( 3 2 7 ) 和( 3 2 8 ) 之和达到最小时，能保证网络输出状态矩阵v 构成换位阵。 考虑路径的合理性，此项定义中应包含有效路径的长度信息，此项 t h e b 口o f m 勰xd e 管e 巴，ms c ，u o k c t ：裟揣黜黑麓装科 第三章h o p f i e l d 神经网络算法分析与改进 定义为 其中d 0 为常数。下标运算定义为类似于以下的取模运算 忙+ ，) 。 丘+ ， 咒+ 席+ r n + 定+ r r 3 2 9 ) ，为模式平移量。表示一维模式平移，位，往左移r 为正，往右移r 为 负。原模式x 中的元素x ，札现在移动为x ，x 。 这样从路径最后一个城市到第一城市的距离也包括在式( 3 2 9 ) 中。e 。 实际数值就是一次有效路径总长度的倍数。若路径为最佳时，e 。达到最 小点。若路径为较好时，e 。达到极小点。式( 3 2 6 ) 、( 3 2 7 ) ( 3 2 8 ) 这三项 适用于一般t s p 问题，式( 3 2 9 ) 是路径最短，与具体问题有关。 所以，构成用h o p f i e l d 神经网络求解t s p 问题的能量函数为： e = e 、+ e 2 + e 3 + e 4 ( 33 0 ) 把式( 3 3 0 ) 与标准能量函数( 3 2 5 ) 比较可得到神经元x 。与y 之间的导 纳值( 相当于权系数) 为： t 。：一彳岛【1 一西) 一占毛( 1 一如) 一c d 1 。蛾，。+ 乃，。x 1 一屯) ( 3 3 1 ) 其中占。，占，；9 3 ( n t ) e t 工2 ： ，f 1i = ， d ”2 j o其它 而偏流( 外加激励) 为 i 一：c n ( 3 3 2 ) 用计算机模拟时，把网络结构( 3 3 1 ) ，t ! i ( 3 3 2 ) 代入网络的运行方程中可 得 m r l j u “m w + h k 乱惘 。rl d 一2 = b n o 辨 “ 甜 l o r，l【 | | r 塑三茎! 塑生塑塑墨堕竺竺些坌堑皇垦垄 ：! ! ： 姆唧1 从超空间的角度解释了h o p f i e l d 网络求解t s p 问题时经常陷入无 效解的原因，并将能量函数修改为： e = 鲁芝窆宝吒+ 鲁窆窆窆k 。_ ，+ “， 圪+ 詈吒：nj - l 半) 喜喜砉喜圪，屹+ 了d 刍n 刍n 善n ，。+ + ，) 从上式可以看出，a i y e r 是以复杂的能量函数为代价来保证网络收敛到有 效解的。 文献通过对( 3 3 0 ) 式的分析，提出了以下改进措旖并给出了理论的