（计算机系统结构专业论文）回复式神经网络及其在组合优化问题中的应用.pdf

摘要 摘要 人工神经网络研究从8 0 年代初复苏后一直是科学与工程研究的一个热点学 科。2 0 多年来，神经网络的研究取得了大量的研究成果。在工程应用上，神经网 络的应用越来越广泛。其应用已经深入到经济、军事、工程、医学、以及科学的 许多领域，并在信号处理、智能控制、模式识别、机器视觉、非线性优化、自动 目标识别、知识处理、遥感技术等领域取得重要成果。神经网络独特的性质及其 强大的计算能力已为科学工作者和工程师们所肯定。 神经网络是解决组合优化问题的一种重要的工具，本文主要研究回复式神 经网络以及其在组合优化问题中的应用，主要包含以下四方面的内容： ( 1 ) 研究利用h o p f i e l d 模型解决t s p 的参数设置问题：利用比h - t 更有效的 能量函数，从几何学角度分析网络权值矩阵的特征值所对应的子空间，从而得 出网络参数的设置标准，模拟结果显示，新的参数能保证网络收敛到有效解。 ( 2 ) 研究回复式网络( 带非饱和激励函数) 的多稳定性：从分区角度给出了 网络单稳定和多稳定的条件，并对二维网络在各个象限的动力学行为进行了详 细讨论，明确地给出了二维网络收敛到不同平衡点的条件，同时提出了一种具 有w i n n e r - t a k e - a l l 特征的带有非饱和激励函数的回复式神经网络模型，并成功 地将其运用到方向选择中。 ( 3 ) 研究行竞争网络( c c m ) 在优化问题中的应用：从理论上分析了利 用c c m 模型解决t s p 问题时，网络很难逃离局部最小值问题，然后提出了一种 利用改进的能量函数的方法对模型进行改进，从而一定程度上解决了c c m 模 型的局部极小值问题，改善了解的质量。同时，提出并分析了多推销员售货问 题( m t s p ) ，并成功地将c c m 模型应用于解决m t s p 问题中。 ( 4 ) 研究p c n n s 模型在优化问题中的应用：对p c n n s 模型进行了一定的改 善，并提出了m - p c n n s 模型，利用此模型，提出了一种计算最短路径的算法，实 验结果证明，在网络规模较大的时候，此算法的效率明显高于其它算法：同时， 将m - p c n n s 模型应用于网络路由协议中的s p t 计算的问题中，提出了静态和动 态计算s p t 的算法，大大地提高了路由算法的效率。 摘要 关键词：回复式网络，多稳定性，推销商问题，网络路由，最短路径问题。 a b s t r a c t a b s t r a c t s i n c e1 9 8 0 s ，a r t i f i c i a ln e u r a ln e t w o r k s h a v eb e e na t t r a c t i n gt h es t u d yo fm a n y r e s e a r c h e r si ns c i e n c ea n de n g i n e e r i n gf i e l d s ，a n dm a n yi n t e r e s t i n gr e s u l t sh a v e n b e e no b t a i n e di nt h et w od e c a d e s m o r ea n dm o r er e s e a r c h e r ss t a r tt os t u d yt h e n e u r a ln e t w o r k sw h i c ha i ma ts o l v i n gt h ep r o b l e m so fe c o n o m i c a l ，e n g i n e e r i n g ， m i l i t a r y , m e d i c a l ，a n do t h e rf i e l d so fs c i e n c e ，s u c ha ss i g n a lp r o c e s s i n g ，i n t e l l i g e n t c o n t r o l s ，v i s i o no f m a c h i n e s ，o p t i m i z a t i o n s ，o b j e c td e t e c t i n g ，m i n i n g o f k n o w l e d g e ， r e m o t es e n s i n ga n ds oo n s o m eu n i q u ec h a r a c t e r sa n dc a p a b i l i t yi nc o m p u t i n g o ft h en e u r a ln e t w o r k sh a v eb e e nr e c o g n i z e db ys c i e n t i s t sa n de n g i n e e r s i ti sw e l lk n o w nt h a tn e u r a ln e t w o r k sh a v eb e e nc o n s i d e r e da sa l li m p o r t a n t t o o lt os o l v ec o m b i n a t i v eo p t i m i z a t i o np r o b l e m s t h i 8d i s s e r t a t i o ns t u d i e st h e c h a r a c t e r i s t i c so fr e c u r r e n tn e u r a ln e t w o r k sa n da p p l i e st h e ms o l v es o m eo ft h e c o m b i n a t i v eo p t i m i z a t i o np r o b l e m s 甄em a i nt o p i c sw ew i l ld i s c u s sa r el i s t e d 嬲 f o l l o w i n g ： ( 1 ) s t u d y i n gt h es e t t i n go fp a r a m e t e r si nh o p f i e l dn e t w o r k sw h e na p p l i e d t os o l v et s p s b ya n a l y z i n gt h eb e h a v i o ro fh o p f i e l dn e t w o r k s 嬲am e t h o d o fs o l v i n gt 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 i t ha ne n h a n c e df o r m u l a t i o n o fe n e r g yf u n c t i o n ，w es h o wt h a tt h i sm o d e li sm o r ee f f e c t i v et h a nt h a to ft h e h o p f i e l d - t a n k sf h - t ) t h ea n a l y s i si sb a s e do nt h eg e o m e t r yo ft h es u b s p a c e s e tu pb yt h ed e g e n e r a t ee i g e n v a l u e so ft h ec o n n e c t i o nm a t r i x as e to fc r i t e r i o n f o rp a r a m e t e rs e t t i n g si sd e r i v e d t h en e wp a r a m e t e r sp e r f o r m e dw e l li nt h e s i m u l a t i o n s ( 2 ) s t u d y i n gt h em u l t i - s t a b i l i t yo ft h en e u r a ln e t w o r k sw i t hl i n e a rt h r e s h o l d ( l t ) t r a n s f e rf u n c t i o n d i f f e r e n tc o n d i t i o n sa r ed e r i v e de x p l i c i t l yt og u a r a n t e e t h em o n o - s t a b i l i t ya n dm u l t i - s t a b i l i t yo ft h en e t w o r k ，r e s p e c t i v e l y d y n a m i c a l p r o p e r t i e s o f t h e e q u i l i b r i a o f t w o - d i m e n s i o n a i n e t w o r k s a r e a n a l y z e d t h e o r e t i c a l l y w es h o wt h a tt h eg i v e nc o n d i t i o n sc a nd r i v et h en e t w o r k ( t w o - d i m e n s i o n a l ) o f c o n v e r g i n gt od i f f e r e n tg l o b a ls t a b l ep o i n t s ，o rd i f f e r e n tm u l t i - s t a b l ep o i n t s a n i m p o r t a n ti m p l i c a t i o no ft h ep r o p o s e dm o d e l ：w i n n e r - t a k e - a un e t w o r k ，i ss t u d i e d i n d e t a i l ( 3 ) s t u d y i n gt h ea p p l i c a t i o no fc c mt ot h eo p t i m i z a t i o np r o b l e m s u s - i a b s t r a c t i n gs o m em a t h e m a t i c a lt o o l s w ep r o v et h a tc c m i sh a r d l yt oe s c a p ef r o ml o c a l m i n i m u ms t a t e si ng e n e r a l a na l t e r n a t ec c mi sp r e s e n t e db a s e do nam o d i f l e de n e r g yf u n c t i o na n di te n h a n c e st h ec a p a b i l i t yo ft h eo r i g i n a lc c m an e w a l g o r i t h mi sp r o p o s e db yc o m b i n i n gt h ea l t e r n a t i v ec c mw i t ht h eo r i g i n a lo n e ， w h i c he n a b l e st h en e t w o r kt oh a v el o w e re n e r g yl e v e lw h e nt r a p p e di nl o c a lr a i n - i m a ，a n dm a k e st h en e t w o r kt or e a c ht h eo p t i m a lo rn e a r - o p t i m a ls t a t eq u i c l d y a n o t h e ro p t i m i z a t i o np r o b l e m ：m u l t i t r a v e l i n gs a l e s m a np r o b l e m ( m t s p ) ，a l l e x t e n s i o no ft h ew e l lk n o w nt s pi sp r o p o s e da n ds t u d i e di nd e t a i l c c mi se m - p l o y e dt os o l v et h em t s p s t a b i l i t yc o n d i t i o n so fc c mf o rm t s pa r ee x p l o i t e d b ym a t h e m a t i c a la n a l y s i s ( 4 ) s t u d y i n gt h ea p p l i c a t i o no fp c n n s t ot h eo p t i m i z a t i o np r o b l e m s s t u d - i e so ft h ep e r f o r m a n c eo ft h ea u t o - w a v ei np c n n 8a i ma ta p p l y i n gt h e mt oo p - t i m i z a t i o np r o b l e m s ，s u c ha st h es h o r t e s tp a t hp r o b l e m am u l t n o u t p u tm o d e l o fp u l s ec o u p l e dn e u r a ln e t w o r k s ( m - p c n n s ) i ss t u d i e d an e wa l g o r i t h mf o r f i n d i n gt h es h o r t e s tp a t hp r o b l e mu s i n gm p c n n si sp r e s e n t e d s i m u l a t i o n sa r e c a r r i e do u tt oi l l u s t r a t et h ep e r f o r m a n c eo ft h ep r o p o s e dm e t h o d as t a t i ca l g o - r i t h mi sp r e s e n t e dt oc o m p u t et h es p tm o r ee f f i c i e n t l yf o rl a r g es c a l ec o m p u t i n g p r o b l e m s ad y n a m i ca l g o r i t h mt oc o m p u t es p ti sp r o p o s e da l s o ，f r o mw h i c h t h ee f f i c i e n c yo ft h ea l g o r i t h mi si m p r o v e dg r e a t l y k e y w o r d s ：r e c u r r e n tn e u r a ln e t w o r k s ，m u l t i s t a b l e ，t r a v e k n gs a l e s m a np r o b - i e m ( t s p ) ，r o u t i n g ，s h o r t e s tp a t hp r o b l e m i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特另, j j j n 以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：医塑 日期酗年f 1 , 9 趵e t 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：醴导师签趣 日期：k ( 1 年切k 日 第一章引言 第一章引言 人是万物之灵，区别人与其它动物的是其发达的大脑及进化的智慧。研究 人工神经网络，特别是神经学习的机理，对认识和促进人自身发展有特殊的意 义。人工神经网络是由大量简单的神经元互联而成的自适应的非线性动力系统。 它建立在现代神经科学研究成果的基础上，是对人脑的某种抽象和模拟。随着 它与多门学科的相互渗透，人工神经元已发展成为一种信息存储和处理的计算 单元，人工神经网络则发展成为种信息处理系统。网络的信息处理由各个神 经元之间的相互作用来实现，知识与信息的存储表现为网络元件互连间分布式 的物理联系，网络的学习和识别取决于各神经元连接权的动态演化过程。 1 1 研究意义 神经网络理论是巨量信息并行处理和大规模平行计算的基础，神经网络既 是高度非线性动力学系统，又是自适应组织系统，可用来描述认知、决策及控制 的智能行为。它的中心问题是智能的认知和模拟。从解剖学和生理学来看，人脑 是一个复杂的并行系统，它不同于传统的n e u m a n n 式计算机，更重要的是它具 有“认知”、“意识，和“感情”等高级脑功能。我们以人工方法摸拟这些功能，毫 无疑问，有助于加深对思维及智能的认识。8 0 年代初，神经网络的崛起，已对认 知和智力的本质的基础研究乃至计算机产业都产生了空前的刺激和极大的推动 作用。 人工神经网络在模式识别、自动控制、地球物理等许多领域都有着广泛的 应用前景，并且已取得了很多丰硕的成果。当前神经网络理论研究的一个重要 的特点就是越来越紧密地和数学等其它学科结合起来，利用这些学科的最新成 果来解决神经网络中的理论问题。例如模糊神经网络就是神经网络和模糊理论 相结合的产物，它吸收了两者的最新成果，是一种既具有学习、联想、自适应性， 又能进行模糊思维的信息处理系统。 目前，神经网络的理论研究日益深入。许多严格的基本理论正在逐步被建 立起来，其研究成果不断在许多国际一流学术刊物，如( s c i e n c e ) ，( n a t u r e ) 等 上发表。关于神经网络的研究无论在国外还是国内都深深地吸引了许多优秀的 科学家和一流的学术研究机构，如m i t ，h a r v a r d 大学，b o s t o n 大学等，其在科学 上的地位不言而喻。 1 电子科技大学博士学位论文 近十年来，神经网络实践也有了引人注目的进展，它拓展了计算概念的内 涵，使神经计算、进化计算成为新的学科，神经网络的软件模拟得到了广泛的 应用。科技发达国家的主要公司对神经网络芯片、生物芯片的研发进行了大量 的投入，并取得了令人振奋的研究成果。例如i n t e ! 公司、i b m 公司、贝尔实验室 和h n c 公司等已取得了多项专利，已有产品进入市场，被国防、企业和科研部门 选用，公众手中也拥有神经网络实用化的工具，其商业化令人鼓舞。尽管神经计 算机、光学神经计算机和生物计算机等研制工作的艰巨性和长期性，但有一点 可以使人欣慰：它现在还只是初露锋芒，有巨大的潜力与机会，前景是美好的。 关于脑的计算原理及其复杂性，关于学习、联想和记忆过程的机理及其模 拟等方面的研究已受到人们的关注，它未来的发展必将是激动人心的。神经网 络理论的前沿问题将渗透在2 l 世纪科学的挑战性问题中，一定会取得重大的突 破。回复式网络，作为神经网络中的一个重要的模型，从理论上分析其特性并研 究其在组合优化中的应用，无论是理论上还是实践上都具有十分重要的意义。 1 2 回复式神经网络模型 根据网络结构的不同，人工神经网络大致可以分为：前馈式神经网络、回复 式神经网络和竞争网络三大类。回复式网络模型主要有以下几种： 1 2 1 h o p f i e l d 神经网络模型 1 9 8 2 年，h o p f i e l d 提出了一种离散随机神经网络模型【1 】，给沉寂己久的神经 网络研究注入了新的活力。同时也引起了科学界，工程界等的极大兴趣。在离散 型l l o p f i e l d 神经网络的基础上，1 9 8 4 年，h o p f i e l d 又提出了连续型h o 曲e l d 神经网 络模型【2 l 并且证明，这两种模型的许多重要性质是紧密相关的，连续型神经网 络模型在硬件实现时更为方便。 在如图1 1 所示的连续型神经网络模型中，每个放大器就是一个神经元，其 输出用一个非线性动力方程描述。若第i 个放大器的输入为t “，那么非线性动力 方程如下： g 筹一一尝+ 吩+ 五 ( “) j = i 放大器即神经元的输出巩满足 巩= ( 啦)( 1 2 ) 2 第一章引言 7 7 _ 口jo l ；d ； ：p 翌 1 琢1 - e 卧 茹i玛 岛 曝鞋日两矗遍一 - 嚼”筠7 c 钦7 瓦j 一 i i 图1 1 ：连续型h o p f i e l d 网络模型。 其中g 是放大器的输入电容，是第j 个放大器输出到第i 个放大器输入的连接 图1 2 ：s 型神经元的特征曲线。 权值，五( ) 是第i 个放大器的输出特性，即神经元特性，它的形状为如图1 2 所示 的s 形曲线。厶为放大器的外部输入，n 为神经元的个数。 在h o p f i e l d 神经网络中，连接权值是对称的，即马= 此外，在网络中 同时采用放大器的正向和反向输出，使得的值可正可负，并且i 乃i = 南，其 中如是第j 个放大器的输出和第i 个放大器的输入之间的电阻值。 3 电子科技大学博士学位论文 在公式( 1 ，1 ) 中，t 的值由下式给出： 去= 去+ 善壶 q 3 ， 一= 一+ i( 1 ) 瓦a 暑坞 。 其中皿是放大器的输入阻抗。一般情况下可以把- r 和g 取为常数，如q = i 由几个神经元的输出和公式( 1 1 ) 以及公式( 1 2 ) ) 一起可独立地描述h o p f i e l d 神 经网络的运行状态，所以称这n 个输出所组成的向量为系统的状态向量。同时， 为了描述h o p f i e l d 神经网络的稳定性，引入如下能量函数： e 。：莩莩酞一莩厶砍+ 莩毫z “，1 c 州v c q 在高增益的情况下，上式的第三项可省略。考虑到五f 的对称性，于是有： 筹= 一莩警( 一尝+ 莩码岣+ 五) c ，s ， 再根据式( 1 2 ) ，即有： d 。e 。= _ e c t 掣( 警) 2 ( 1 。) 因为，( ) 是s 形函数，故，1 ( ) 单调增加，上式右边的每一项都是非负的，从而 i d e o ( 1 7 ) 并且仅当警= o 时，上式的等号成立。警对应的是状态空间中能量函数e 的稳定 平衡点，表示的是网络最终可能的输出值的集合。因为能量函数e 是有界函数， 所以( 1 7 ) 式表明网络总是收敛到能量函数引拘局部极小点上。 对于最优化问题，通过适当地选取连接权t q 的值以及外部输入信号五， 可将其匹配到神经网络上。经过这样的构造后，给定一组输入电压的初始 值，h o p f i e l d 神经网络会收敛到极小化目标函数e 的稳定状态，从而求得目标函 数e 的局部极小值。 1 2 2带非饱和激励函数的回复式神经网络 常见的带非饱和激励函数的回复式网络可以用以下方程来描述： 觑= 一戤+ 盯( 蛳+ 垃) ( 1 8 ) 4 第一章引言 其中，z 表示神经元i 的当前活动状态。让b 表示神经元j 到神经元i 突触间的连接 强度。当神经元j 通过突触刺激神经元t 时，w i j h i e ；当神经元j 通过突触抑制神 经元i 时，札b 为负。口( ) 是神经元i 的激励函数，风为外部输入 a ) s i g m o l db ) l l m l t e rc l i n e a rt h r e s h o l d 图1 3 ：激励函数的形式。 激励函数口( ) 的形式x g f 潞( 1 8 ) 的有界性具有非常重要的影响，如图1 3 所 示。如果激励函数有上下界，比如a 盯( z ) b ，那么显然，当x i o 时，血0 ， 当以6 时，血0 ，即网络是有界的。这类激励函数包括f e r m i i 函数 盯( z ) 2 南 ( 1 9 ) 以及线性函数 i a ，i f z 6 近年来，对以生物模型为背景的神经网络的研究层出不穷，如【3 l ， 4 】， 【5 1 ，【6 】，f 7 】。其中，一种非常重要的网络是具有非饱和激励函数( 也被称为切? 函 数) 的网络模型，在这个网络模型中网络的激励函数是非饱和的，表示如下： 巾) = 他。卅巍嚣 ( 1 1 1 ) 可以简化为： 盯( z ) = m a x o ，) ， ( 1 1 2 ) 其中，p 为神经元的阀门值，k 0 是激励函数的增益常数。可以肯定的说，当用 来模拟大脑皮层神元的功能时，这种网络模型比具有s i g m o i d 激励函数的网络模 型，如i s ，【9 】，【1 0 1 中研究的模型，更具有生物意义【1 l 】。 5 电子科技大学博士学位论文 1 2 3 行竞争网络神经模型 h o p f i e l d 指出，如果连接矩阵是一个对称矩阵，那么以下能量函数 e = 一妻v 狮v 一( i b ) t v ( 1 , 1 3 ) 可以通过连续型的h o p 丘e l d 网络收敛到一个极小值【8 】。这里，w = ( 睨j ) 为网络 的连接矩阵，t ，j = l ，佗，n 是神经元的个数，v = ( 如，i ) 表示神经元( z ， ) 的输出 状态，i 6 表示偏置输入向量。 行竞争网络模型( c c m ) 是对h o p f i e l d 网络模型中迭代方式的一种变形，在 这种模型中，每列的神经元之间使用w i n n e r - t a k e - a l l ( w t a ) 的竞争规则相互 竞争，输入最大的神经元输出为“l ”，其余的输入为“0 ”。利用这个模型可以成功 解决规模较小的t s p 问题。假如模型对应t s p 问题的能量函数为 e ( = ；( 。) + ；锄( t h + “) ( 从) 其中，k 0 为网络的参数，也。是城市z 和城市口之间的距离。将式子( 1 1 4 ) 整理成 式子( 1 1 3 ) 的形式，可得出 - p 幺卅= 一 1 越2 2 ) 其它 、7 ( 1 2 3 ) 其中， ) 神经元( f ，刃的阈值，劬为时间常数k 为正规常数。当以f 大于当前 阈值时，神经元( i ，j ) 点火，即= 1 ，此后在，反馈作用下，鼠，立即增大，并超 过的值，神经元( ，j ) 的输出又立刻变为0 ，这样便形成了一次点火过程，并产 生了脉冲输出。 与传统的反馈型神经网络相比，p c n n s 神经元在神经元构成上有自己 独有的特点：变阈值、内部行为和积分耦合、分支树的漏电容积分，从而使 得p c n n s 模型具有两个显著的特点；同步脉冲发放和自动波。 1 3主要研究内容 本文主要研究回复式神经网络，包括h o p f i e l d 罔j 络，带非饱和激励函数的网 络。行竞争网络( c c m ) 以及脉冲耦合网络( p c n n s ) 的一些基本理论，以及其在 组合优化问题中的应用。研究内容包括： ( 1 ) 研究利用h o p f l l e d 模型解决t s p 问题时网络参数的设置问题：采用 比h - t 模式更有效的能量函数，从几何学角度分析网络权值矩阵的特征值所对 应的子空间，从而获得设置网络参数得的标准，模拟结果显示，新得网络参数能 保证网络收敛到有效解。 ( 2 ) 研究带非饱和激励函数的回复式网络的多稳定性：从分区角度给出了 网络单稳定和多稳定的条件，并对二维网络的在各个象限的动力学行为进行了 详细分析，明确的给出了二维网络收敛到不同平衡点的条件，同时提出了一种 8 第一章引言 具有w i n n e r - t a k e - a l l 特征的带有非饱和的回复式神经网络模型，并将其成功地 运用到方向选择中。 ( 3 ) 研究行竞争网络( c c m ) 在优化问题中的应用：从理论上分析了c c m 模 型在解决t s p 问题时很难逃离局部最小值问题，然后提出了一种利用改进的能 量函数对模型进行改进的方法，从而一定程度上解决了c c m 模型的局部极小值 问题，改善了解的质量。同时，提出并分析了多旅行商问题( m t s p ) ，并成功地 将c c m 模型应用于解决m t s p 问题中。 ( 4 ) 研究p c n n s 模型在优化中的应用：对p c n n s 模型进行了一定的改变， 并提出了m p c n n s 模型，利用此模型，提出了一种计算最短路径的算法，实验 结果证明，在网络规模较大的时候，此算法的效率明显高于其它算法；同时， 将m p c n n s 模型应用于网络路由协议中的s p t 计算的问题中，提出了静态和动 态计算s p t 的算法，大大地提高了解决路由问题算法的效率。 1 4 特色和创新 目前，回复式神经网络是众多学者研究的热点之一，对它的改进、提高、补 充、变形不断地进行着，我们从理论角度出发，研究回复式神经网络的特性，对 其性能进行优化，是对其的改进和提高，对神经网络发展起一定的促进作用。 t s p 是一个经典的组合优化问题，这个问题吸引了众多领域( 人工智能、生 物、数学、物理等) 研究者的兴趣，它在工程方面具有十分重要的应用价值，比 如：v l s i 电路设计、机器人设计以及通讯中的网络路由等。我们以t s p 为中心， 以回复式神经网络为主线，结合t a b us e a r c h 等局部搜速算法，对其进行全面的 研究和优化，具有很强的应用价值。 在理论研究的基础上，我们对回复式神经网络的应用加以推广，提 出m t s p 问题，并寻求利用回复式神经网络解决一般组合优化问题的普遍方 法，从而扩展了研究范围，提高了研究的实用性。 1 5 章节安排 第一章引言部分，概述本文的研究意义，研究内容以及所涉及的网络模型。 第二章介绍利用h 0 p 丘e l d 网络模型解决t s p f , 题时网络参数的设置问题。 第三章研究带非饱和激励函数的回复式网络的多稳定性分析，同时提出了 一种具有w t a 特性的网络模型。 9 电子科技大学博士学位论文 第四章介绍利用行竞争模型解决t s p f 司题时局部极小值的问题。 第五章介绍m t s p 问题以及如何利用行竞争模型来解决m t s p 问题。 第六章介绍p c n n s 在优化问题中的应用，提出了利用p c n n s 求解最短路径 的算法，以及利用p c n n s 求解路由协议中s p t 的算法。 第七章为结束语。 第二章利用h o p f i e l d 模型解决t s p 问题 第二章利用h o p f i e l d 模型解决t s pf 司题 本章以t s p 问题入手，采用比h - t 模式更有效的能量函数，从几何学角度分 析网络权值矩阵的特征值所对应的特征子空间，从而获得网络参数设置的标准， 模拟结果显示，新得网络参数标准能保证网络收敛到有效解。 2 1 研究背景 利用h o p f i e l d 神经网络解决t s p ( 旅行商问题) 已经引起了广泛的兴趣【8 】，然 而，网络参数设置的难度导致了网络经常收敛到无效的状态或者局部最优状 态。a i y e r 等通过分析网络权值矩阵的特征值，取得解决t s p 问题时网络参数的 一种设置方法f 17 1 。t a l a v a n 等通过分析系统l y a p u m o v i 弱数的一阶导数，同样获 得了网络参数设定范围f 1 8 1 。但是在他们的研究中，系统的能量函数都是采用最 初的h _ t 表达式f 8 1 。众所周知，h - t 表达式对t s p 问题来说并不是一种非常理想 的能量函数 1 9 】，因此，寻找一个能够更好地映射t s p 问题的能量表达式和寻找 能够保证网络收敛到最优解的参数设置方法，成为利用h o p f i e l d 络解t s p 问题 的两种十分重要的途径。这两种方法的混合使用，往往能取的更好的结果。 为了避免采用h t 表达式所带来的不良的特性，寻找一个有效的方法来获 得网络参数的最佳设置，可以把以上的这两种方法结合起来。本章通过研究一个 基于加强的能量表达式的权值矩阵的特征值，分析了h o p f i e l d 网络的行为特征， 最终得到一个能保证网络收敛到有效状态的参数的设置方法，见参考文献f 2 0 1 。 2 2c h n 模型到t s p 的映射 连续的h o p f i e l d 模型是一个具有佗个连续变化的神经元的相互全连接的网 络，如果用正j 表示神经元i 到神经元，的连接强度，用砖表示神经元i 的偏置输入， 用毗表示神经元i 当前输入，用讧表示神经元i 的当前输出，那么连续的h o p f i e l d 模 型可以用以下微分方程来描述： 坐：一竺+ i 、，+ i 6 一d t t 十上v 十1 1 1 ( 2 1 ) 电子科技大学博士学位论文 并且 在这里，输出函数为： 札，= j 1 ( 1 + t a n h ( 等) ) 咖 。 h o p f i e l d 模型的离散形式可以描述为 矿+ 1 = t v 扣) + i b h o p f i e l d 指出，如果矩阵t 是对称的，则存在如下的l y a p u n o v 函数 ( 2 2 ) e = 一互1 v t t v 一( i 6 ) t v ( 2 3 ) 这个函数可以保证c h n 收敛到平衡点。 h o p f i e l d 解决t s p 问题时，采用以下表达式来映射t s p 问题的能量，这个表 达式通常被称为h - t 表达式。 曰；告v z # v z j + 导 。il 判 。i 。f 和 + 罢( 一) 2 + d 9 一一一d ；地；v y , i + 1 i - i ) y , i _ 1 ) ( 2 4 ) zt o 停z 在这里，面表示城市善到城市可的距离，a ，b ，g ，d 为正的常数。把这个能量表达 式转化为形如( 2 3 ) 形式的能量函数，就可以得出相应的连接权值和偏置输入，如 下所示： ，酊= 一 瓴，f ( 1 一盈j ) + b 盈j ( 1 一瓦，v ) + c + d ( ( 文j + i + 文j 一1 ) 5 ) 屯= c n ( 2 6 ) 然而，这个能量表达式经常导致网络收敛到一些无效的解空问。h o p f l e l d 和t a n k 采用修改偏置输入的方法，即将神经元的偏置输入i 6 = c n 用i b = g 来 代替【8 】，来保证网络收敛到稳定的有效解空间，其中是一个比大很多的常 数。但是这种方法对解的优化程度是十分有限的，并没有达到理想的结果。 第二章利用h o p f i e l d 模型解决t s p 问题 2 3利用加强的能量表达函数来描述t s p 问题 b k a m g a r - p a r s i 等人在【2 1 】中说明，在解决t s p 问题时，h - t 能量表达式是 不稳定的。所以，我们使用以下加强的能量函数，如式( 2 7 ) 所示。这个能量函数 由四部分组成：当网络的输出矩阵的每行中有且仅有一个神经元的输出为1 其 余的都为0 时，第一部分的能量值为0 ：当输出矩阵的每列中有且仅有一个神经 元的输出为1 ，其余的都为0 时，第二部分的能量值为0 ；第三部分用来保证网络 的输出能不断地向系统超立方体的顶点( 有效解) 运动；第四部分用来表示路径 的长度。 = 鲁( j 一1 ) 2 + 詈( j 一1 ) 2 一z 一 i + 萼( i - j ) j + d 2 - - - d 哳( + 1 + 蛳_ 1 ) ( 2 7 ) 一 $ 一 p $ 通过计算，可以得出网络的连接矩阵t 和神经元的偏置输入i 6 ，如下所示： 2 驯= 一 a 瓦，”+ b 文j c 6 = 国j + d c ( 文j + l + 盈j 1 ) ( 2 8 ) t ：j = a + b 一寻 ( 2 9 ) 这个能量函数具有比h - t 函数更好的性质，关于这点，见参考文献【2 2 】 和f 2 3 】。就像他们描述的那样，这个新的加强的能量函数中的神经元之间的连接 数黄j ( 4 n 一3 ) n 2 ，而h t 能量函数中的神经元连接数为4 ，从而减少了计算量， 尤其是当问题规模很大时，这种简化对网络的性能有很大的影响。 2 4 连接矩阵的特征值 公式( 2 7 ) 中的头三项用以保证网络能收敛到有效状态，因此，除去d 项来 考虑是合理的，同时，假定a = b ，则第一项和第二项具有相同的权值，这样t 可以简化为： 2 新= 一a 以廖一a 盈j + ( 了疋盈j ( 2 1 0 ) 为了简化问题，我们考虑离散型的迭代方程，如式( 2 2 ) 所示，也就是u = t v 接下来，我们计算网络连接矩阵的三个不同的特征值a 1 = c 一2 n a ，a 2 = g 和a 3 = c n a 。 1 3 电子科技大学博士学位论文 2 4 1 计算第一个特征值 定义v = e 1 ，则对于所有的和j 来说，有j = 1 成立，并且u e = t v = t e l 可以推出以下等式： e ，；= 黾栅= 瓦枷e 品= 一a 翰一a 如 口jvj护1j = 1y = lj = 1 n nn + g 锄奶= 一a 1 一a 1 + c = 一2 n a + c ( 2 1 1 ) 这表明， r e l = f c 一2 n a ) e 1 = a l e l 很明显，a l = c 一2 n a 是矩阵t 关于特征向量e 1 = ( 1 ，1 ，1 ) 的特征值。 2 4 2 计算第二个特征值 假定v 是网络的一个有效解，则存在向量v ，使得v = v 一1 成立。因此， 从式( 2 1 0 ) ，可以得出： t 耐= ， u = 一 t v = w ( v 一6 1 、 t v t 6 1 = t v a 1 e 1 u a 1 色1 ( 2 1 2 ) 一a 一a 幻+ g 锄如 既然v 是一个有效解，所以有邑v 巧= 1 和。v y ，l = 1 ，因此有 u 科：= 一- 。a 2 a 。+ + c 伪v = ( 2 1 3 ) ， f 卜 ， a一 ， ， a一 = 第二章 利用h o p f i e l d 模型解决t s p f , 题 将式( 2 1 3 ) 和a 1 = 一2 a + c 代入式( 2 1 2 ) ，可以得到： u = t v = - 2 a e l + c v 一( 一2 n a + c ) 6 1 = c ( v 一1 1 = c v = a 2 v r ( 2 1 4 ) 这说明a 2 = c 是矩阵t 的一个特征值。 2 4 3 计算第三个特征值 在计算第三个特征值时，我们采用与f 1 7 j 中使用的相同的方法。设口( 8 ) 是口一 个有效部分，并且 s ：f 口( a ) 。( 口) 。 o ，酊= 选彰 o 分以下几种情况来考虑： ( 2 1 5 ) ( 2 1 6 ) 1 i = j 且z 如此时 是一个有效的路径，和不可能为l ，因此，s 中所 有i = j 且z g 的元素的值都为o 。 2 i = j 且。= p ：此时，一个城市的位置有( 一1 ) ! 中可能，因此，s k 一= ( 一1 ) ! 。 3 i j 且z = ：这种情况下，= 1 和不可能为l ( 因为i j ) ，所 以s 中所有$ = 掣且i j 的元素都为o 。 4 t j 且z ：这种情况下，在一个路径中，两个城市的位置可以固定， 因此，其他( 一2 ) ! 个城市位置的取法有( 一2 ) ! 种。可以得出，当i j f i z 时，别= ( n 一2 ) ! 由上可知，矩阵r 可以由s 表示成： t = 订f 兰研s + ( g n a ) j a e l e ” ( 2 1 7 ) 1 5 电子科技大学博士学位论文 显然，和矩阵s 的有效子空间对应的特征值必须为0 。注意到，式( 2 1 7 ) 的 第一部分反映s 特征值的大小，第三部分仅仅反映s 在方向e 1 上的特征值的大 小，因此，( c 一a ) j 必须反映与t 的有效子空间部分对应的特征值一n a ) ， 即，k = c n a 。 2 5 网络参数设置 a i y e r 等在【1 7 】中指出，在方程( 2 1 ) 中，式一( 詈) 不会对网络的特性带来本质的 影响。因此，为了简化分析，我们假设： 搴：t v + i 6 ( 2 1 8 ) 面2 1 7 十1 1 训 另外，