（计算机应用技术专业论文）平面问题的一种新型神经网络算法.pdf

摘要 摘要 平面问题是一个典型的组合优化问题。平面问题在印制电路板的设计和大规模 集成电路( v l s i ) 的布线方面有着重要的应用，对于很多可视化问题，例如基因调控 网络的可视化也有着蘑大的意义。平面问题包括两部分：平面性测试和平面嵌入。 虽然很多研究人员针对该问题的两部分已经提出了一些算法，但它们都存在着一 些缺陷。本文将该问题的两个部分统一对待，指出了可平面图的平面嵌入是有条 件的，只有在特定的顶点顺序情况下才是可直线嵌入的，并通过给出既满足直线 嵌入条件又实现正确布线的能量函数，进而用h 叩f i e l d 神经网络实现了对可平面 图的直线嵌入和不可平面图的最大可平面子图的寻找和布线：另外本文用模拟退 火算法来帮助网络摆脱局部极小点。大量实验结果表明我们的混合算法具有帮助 h o 两e l d 网络摆脱局部极小点的能力并能得到较好的结果。 关键字：平面问题h o p f i e l d 神经网络模拟退火算法 a b s t m c t a b s t r a c t p l a l l 州z a t i o np r o b l e mi sar 印r e s e n t a t i v ep r o b l e mmc o m b i n a t i o no p t i m i z a t i o n i t i sw i d e l yu s e di nd e s i g i l i n gp r i n t e dc i r c l l i tb o a r d s ，r o u t i n gv e r ) r - l a r g e s c a l ei 1 1 t e 孕a 廿o n ( v l s l ) c i r c u 沁a n dv c r yi m p o r t a n t 幻协ev i s m m t yo ft h eg c n er e 刚a t o r yn e 柳o r k t h ep l a n a r i z a t i o np r o b k mc o n s i s t so f 铆op a n s ：也ep l a l l a r i z a t i o nt e s t i n ga i l d 也c p l a i l e e m b e d 函n g m a i l ya l g o r i t l l 】咂sa b o u tt l l i sp r o b l e mh a v eb e e np r o p o s c db ym a l l y r e s e a r c h e r sb u tm e r ee x i g tb u g si nm e m t bs e m et l l e s et v v os u b _ p r o b l e m s ，an e w h o p f i e l dn e t 、v o r ka l g o r i t l l 】mi sp r o p o s e d 1 m sp a p c rp o i n t so u tm a tt h ep l a n a r 铲印hc a i l o i l l yb ee m b e d d e do m o as i n g l el i l l ew h e ni t sv e m c e sa r ei n s p e c i a lo r d e lna l s o p r e s e m sa ne n e r g yf u n c t i o nt h a tc a n m e e tt l l en e e do fe m b e d d i n gag r a p ho n t oas i i 培l e l i n c a i l dm u t i n gt h e 伊a p hc o r r e c t l y t h e nah o p 矗e l dn e m a ln e t w o r ki sa p p l i e df o r d e c r e a s m gt 1 1 ee n e r g yo f 也en e t w o r k 、】l r i 也r c s p e c to ft i m e ，s u c h 也a tw ec a nn o to i l l y g e n e r a t eam a ) ( i m a lp l a n a rs u b g r a 曲厅o man 0 印l 趾a rg r 叩ho rap l a l l a rg r a p hb u ta l s o e m b e dt h es u b g r a p ho n t oas i n g l el i n e i na d d i t i o n ，s i m u l a t e da n n e a l i n ga l g o r i m m 哪 u s e dt oh e l pt l l en c i c 、】l ，o r ke s c a p ef b mt h el o c a lm i n i m 乱p l e n t yo fe x p e r i m e n t a lr e s u l t s h a v ep r o v 司t h a to l l rh y b 谢a l g o r i 缸nh 髂t h ea b i l 埘t 0h e l ph o p f i e l dn e t 、r ke s c a p e 丘o ml o c a lm “m aa n dg e tb e t t e rr e s u l t s k e y w o r d ：p l a a d 疆t i o np m b l e m ，h o p 靠e mn e u m in e t w o r l 【 s i m u l a t e da n n e a l i n g a l g o r i t h m y8 5 8 9 2 5 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 埠j 塾日期翌! 车2 目兰堕 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名： 导师签名： 日期竺! ! 盘! 旦塑 日期竖垒丛塑 等一 第一章绪论 第一章绪论 1 1 本文的研究背景及现状 人工神经网络( a n i f i c i a ln e u r a ln e t w o r k ) 是一门近年来再度兴起并得到 迅速发展的前沿交叉学科，它是一种在对人脑组织结构和运行机理的认识理解基 础之上模拟其结构和智能行为的工程系统。其中的h o p f i e l d 网络是一类应用十分 广泛的人工神经网络，在组合优化方面有着广泛的应用。但是，在实际的应用中， 这种经典的网络存在着诸多缺陷，例如局部极小点，网络进入极限环等。h o p 丘c l d 网络的基本思想是沿着梯度下降的最优路径到达离初始点最近的极小点，一旦网 络进入局部极小点，系统的运行便失败了，必须重新运行网络；而这种情况是经 常发生的。为了摆脱局部极小点，使系统运行得到全局最优解，一般采用随机处 理和网络动力学方程进行优化设计。目前存在很多种改进h o p f i e l d 网络进而解决 局部极小点问题的方法。其中比较著名的如b o l t z m 趾机，该方法通过对离散型 h o p f i e l d 网络加以扰动，使其以概率的形式表达，而网络的模型方程不变，只是输 出值以类似于b o l t z m a l l 分布的概率分布取值。另外还有随机h o p 丘e l d 网络模型， 在每个输入上加上扰动，从而可以使网络摆脱局部极小点。这些解决方案的基本 思想都是在模型中引入随机因素来避免陷入局部极小点，这不可避免地增加了额 外的大量的搜索时间。因而在实际的应用中，效果还不尽如人意。在本文中，我 们提出了一种新型的h o p 丘e l d 神经网络的学习算法，即混合梯度下降学习算法。 整个算法由两个阶段组成，分别是h o p f i e l d 网络的梯度下降运行阶段和模拟退火 算法逃离局部极小阶段。当h o p 丘e l d 网络在当前权值的学习过程中陷入到个局 部极小点时，开始模拟退火的梯度上升学习过程，从而使网络的能量以一定概率 暂时增加，增强了网络摆脱局部极小点的能力。 我们知道图论中的平面问题是个典型的组合优化问题。平面问题在印制电路 版的设计和大规模集成电路的布线上有重要作用【l 】。它对应完成两个任务，一个是 平面测试，一个是平面嵌入。平面测试问题是判断一个电路图是否是可平面的， 并从非平面的电路图中提取出其最大的可平面部分。1 9 8 9 年j a y k i l i l l a r 等人给出了 解决这一问题的0 ( 起2 ) 复杂度平面测试算法【l 】，其中h 为电路中顶点数目。平面嵌 入问题是将一个可平面图或一个不可平面图的最大可平面子图嵌入到平面上，并 实现在该平面上的平面布线。1 9 7 1 年1 铡a n 给出了平面嵌入算法 3 ，1 9 8 9 年t 址e f i l j i 和l e e 【2 j 在s c i e n c e 上的论文首先用h o p f i e l d 反馈网络给出了求解平面问题的并行 智能化算法。 2 平面问题的一种新型神经网络算法 1 2 本文的工作 本文的研究工作是在国家自然科学基金项目( 编号：6 0 5 7 4 0 3 9 和6 0 0 7 1 0 2 6 ) 和国家留学基金项目支持下进行的。本文所研究的平面测试问题和平面嵌入问题 在1 9 8 9 年9 月t a k e f u j i 和l e e 的论文。3 发表之前一直是分开处理，t a k e f u j i 等 首先引进了h o p f i e l d 网络的并行智能化算法。但 2 中在进行平面嵌入时采用的 是直线嵌入方法，而这会出现一种情况：顶点与直线上的位置对应顺序不同时所 得的结果是不一致，这样会导致可平面图由于网络运行结果表明其是不可直线嵌 入的而得出是不可平面的结论，从而无法实现可平面图的直线嵌入和布线；对于 不可平面图则会发生无法真正找出其最大的可平面子图，从而未能彻底的解决平 面问题。本文针对该算法的不足之处，提出了新型高阶反馈神经网络求解平面问 题的方法，并改进了网络的结构和能量函数。整个算法由两个阶段组成，分别是 h o p f i e l d 网络的梯度下降运行阶段和模拟退火算法逃离局部极小阶段。该算法用 梯度下降算法来进行局部搜索，当算法陷入局部极小点后便开始用模拟退火算法 来逃离局部极小点。因此该算法兼备了梯度下降算法的效率和模拟退火算法的稳 定性。另外该算法还具有单调收敛的良好特性。大量的实验结果表明了本文提出 的混合算法不仅保持了梯度下降的收敛速度，算法还在一定程度上解决了局部极 小点问题并能较好的求解平面测试问题和平面嵌入问题。 苎三童旦哩垒! ! ! 塑丝旦堑! ! 塑型! 笪尘 第二章h o p f i e i d 神经网络( h 州) 概述 2 1 神经网络概述 神经网络也称为人工神经网络( a n n ) ，它的研究起始于对人脑的研究，它是人 工智能领域的一个分支。目前人工智能的发展主要有两个方向：符号智能和人工 生命。人工神经网络便是人工生命的模型。 人工神经网络的研究已经有近5 0 年的历史，它的发展表现在它的模型的构造 上；其推动因素来源于对神经科学研究的突破以及计算机科学和人工智能发展的 需要和v l s i 技术、生物技术、超导技术等的发展。下表2 1 和表2 2 分别列出了 人工神经网络的研究历史和神经网络与人工智能的主要历史“3 。 表2 1人工智能( a n n ) 的研究历史 时间贡献者a n n 模型 1 9 5 7r o s e n b l a t t感知器 1 9 6 1s t e i n b u c h学习矩阵 1 9 6 2w i d r o w 自适应线性元件 1 9 6 8 g r o s s b e r g大系统模型 1 9 6 9w i l l s m 布尔a m 1 9 7 1a a r i 布尔网络理论 1 9 7 2a n d e r s o n线性a i i 1 9 7 2a l b u s雪崩网络理论 1 9 7 2 1 9 8 4f u k u s h i m a 认识机、神经认识机 1 9 7 2v o n d e rm a l s b u r g自组织理论 1 9 7 2k o h o n e n 埘理论 1 9 7 5f r e e m a n删网络设计 1 9 7 7h e c h t n i e l s e n 自适应大系统 1 9 7 7a n d e r s o n b s b 一盒中脑 1 9 7 8 1 9 8 6 g r o s s b e r g自适应共振理论( a r t l 和a r t 2 ) 1 9 8 0k o h o n e n自组织映射 1 9 7 4 1 9 8 5r u i e l h a r t ，w e b b 等b p 理论 1 9 8 2 h o p f i e l d m j n 1 9 8 2p s a l t i s ，h i n t o n 等联想网络 1 9 8 2 c r u z y o n g 学习网络 1 9 8 5 眦n t o n 等b 0 1 t z n 机( 跚) 、c a u c h y 机 1 9 8 6h e c h t n i e l s e n c o u n t e r p r o p 8 9 a t i o n 1 9 8 6m a r k si i 交替投影n n ( a p n n ) 1 9 8 6 p s a l t i s 等光学n n 1 9 8 8 c h u a y a n g细胞n n ( c n n ) 平面问题的一种新型神经网络算法 表2 2 神经网络与 i 的主要历史 | 时间主要发展 1 9 4 3 肝模型 1 9 5 0 s 由m p 模型激励了n n 的硬件、软件模拟，机器智能的早期开发，人工智能 诞生 1 9 5 6d a r t m o u t h 夏季a i 研究计划 1 9 6 0 s黑箱法和n n 方法迅速发展 1 9 7 0 s n n 研究被抛弃，专家系统诞生 1 9 8 0 s 专家系统迅速发展，a i 再度陷入困境，n n 再度获得新生 。 人工神经网络模拟人类部分形象思维的能力，是模拟人工智能的条途径。特 别是可以利用人工神经网络解决人工智能研究中所遇到的一些难题。人工神经网 络理论的应用已经渗透到多个领域，在计算机视觉、模式识别、智能控制、非线 性优化、自适应滤波相信息处理、机器人等方面取得了可喜的进展。 人工神经网络模型发展至q 今日已有酉余种模型，建造的方法也是多种多样，有 出自于热力学的、数学方法的模糊以及混沌方法。对于有规则的网络结构比较适 合我们习惯的简洁分析方法。由于网络拓扑结构的规则性，限制了系统的自由性 和无序运动，因而可以采用非效力学的其它方法。如对于前馈拓扑结构的人工神 经网络，可使用感知器算法、误差反传递算法、竞争学习算法等。 1 9 8 2 年美国加州州立理工学院物理学家h o p f i e l d 教授提出了可用作联想存储 器的互连网络，这个网络称为h o p f i e l d 网络模型，也称h o p f i e l d 模型。他将能 量函数的概念引入人工神经网络，并给出了稳定性的判据，开拓了人工神经网络 用于联想记忆和优化计算的新途径。p f i e l d 神经网络模型是一种循环神经网络， 从输出到输入有反馈连接。h o p f i e l d 网络有离散型和连续型两种。 反馈神经网络由于其输出端有反馈到其输入端，所以h o p f i e l d 网络在输入的 激励下会产生不断的状态变化。当有输入之后，可以求出h o p f i e l d 的输出，这个 输出反馈到输入从而产生新的输出，这个反馈过程一直进行下去。如果h o p f i e l d 网络是一个能收敛的稳定网络，则这个反馈与迭代的计算过程所产生的变化越来 越小，一旦到达了稳定平衡状态；那么h o p f i e l d 网络就会输出一个稳定的恒值。 对于一个h o p f i e l d 网络来说，关键是在于确定它在稳定条件下的权系数。 应该指出：反馈网络有稳定的，也有不稳定的。对于h o p f i e l d 网络来说，还 存在如何判别它是稳定网络，或者是不稳定的问题：而判别依据是什么，也是需 要确定的。 另一方面，如果反馈网络是稳定的，那么网络是否能收敛到全局极小点，用什 么方法来避免陷入局部极小点，这也是本文在理论和实际问题中要探讨的问题。 第二章h o p 蠡e l d 神经网络( 玎州) 简介 2 2 神经网络的基本结构和基本原理 神经网络是由大量处理单元( 神经元、处理元件、电子元件、光电元件等) 广 泛互连顽成的网络。网络的信息处理由神经元之间的相互作用来实现；知识与信 息的存储表现为网络元件互连间分布式的物理联系：网络的学习和识别决定于各 神经元连接权系数的动态演化过程。神经网络计算机就是模拟人脑的这一信息处 理系统的一种新型计算机体系，其中心由类似于人脑神经元的简单处理器组成， 而处理器之间的联结则与神经元之间的突触联系相似。 神经网络是一个具有高度非线性的超大规模连续时间动力系统，其最主要特性 为：连续时间非线性动力学、网络全局作用、大规模并行分布处理及高度的鲁棒 性和学习联想能力。同时它又具有一般非线性动力学系统的共性，即不可预测性、 吸引性、耗散性、非平衡性、不可逆性、高维性、广泛联结性与自适应性等。因 此它实际上是一个超大规模非线性连续时间自适应信息处理系统。 神经元是神经网络的基本处理单元，它一般是一多输入、单输出的非线性器件， 其结构模型如图2 1 所示。其中五，五，以是神经元的输入，即是来自前级n 个 神经元的轴突的信息，岛是f 神经元的阀值；彤，彬：，呒分别是f 神经元对 五，五，z 的权系数，也即突触的传递效率；z 是f 神经元的输出：厂【】是激发函 数，它决定f 神经元受到输人墨，五，以的共同刺激达到阀值时以何种方式输出。 图2 。l 神经元结构模型 如图2 1 所示，常用的神经元非线性特征可描述如下： 1 阀值型：在这种模型中，神经元没有内部状态，而且函数厂为一阶阶跃函 数，如图2 2 ( a ) 所示。 2 分段函数型：如图2 2 ( b ) 所示。 3 s i g m o i d 函数：它一般是没有内部状态并连续取值，其i o 特性常用对数 或正切等一类的s 状曲线来表示，如图2 2 ( c ) 所示。 平面问题的种新型神经网络算法 r u i j i u 。 lh u d l _ 。 o u j 【f t h ) t厂 o 5 玎j ( a )( b )( c ) 圈2 2 神经元的i o 特性 根据人工神经网络对生物神经系统的不同组织层次和抽象层次的不同模拟，神经 网络模型可分为： 神经元层次模型 组合式模型 网络层次模型 神经系统层次模型 智能型模型 神经网络的信息处理能力包括：a 网络的信息存储能力b 网络的计算能力。 时至今日，神经网络已经能够处理下列任务： 数学逼近映射 概率密度函数的估计 从二进制数据中提取相关知识 形成拓扑连续及统计意义上的同构映射 晟近相邻模式分类 数据聚集 最优化问题的计算 神经网络的互连结构形态可分为一下几种： 不含反馈的前向网络 从输出层到输入层有反馈的前行网络 层内有相互结合的前向网络 相互结合型网络 神经网络的分类： 按网络的性能分类：连续型与离散型网络；确定性与随机性网络。 按网络的结构分类：反馈网络与前向网络。 按学习方式分类：有教师学习与无教师学习。 按连接突触性质分类：一阶线性关联网络与高阶非线性关联网络。 第二章h o p f i c l d 神经网络( m 州) 简介 2 3 离散型h o p f i e l d 网络 h o p f i e l d 最早提出的网络是二值神经网络，神经元的输出只取1 和o 这两个 值，所以，也称离散h o p f i e l d 神经网络。在离散h o p f i e l d 网络中，所采用的神 经元是二值神经元：故而，所输出的离散值1 和0 分别表示神经元处于激活和抑 制状态。 首先考虑由三个神经元组成的离散h o p f i e l d 神经网络，其结构如图2 3 所示。 龋o 朦 蔫绺l 罄 y p扣 图2 3 三神经元组成的网络 在图中，第0 层仅仅是作为网络的输人，它不是实际神经元，所以没有计算功 能；而第一层是实际神经元，故而执行对输人信息和权系数乘积求累加和，并由 非线性函数厂处理后产生输出信息。，是一个简单的阀值函数，如果神经元的输 出信息大于阀值口，那么神经元的输出就取值为l ；小于阀值口，则神经元的输出 就取值为0 。 对于二值神经元，它的计算公式如下 u ，= z + ( 2 一1 ) 黼置为外部输入。并且有：e = 髓雄磊。 对于一个离散的h o p f i e l d 网络，其网络状态是输出神经元信息的集合。对于 一个输出层是，z 个神经元的网络，则其f 时刻的状态为一个n 维向量： y ( f ) = k o ) ，艺( r ) ，( r ) 】7 。 故而，网络状态有2 “个状态：因为f p ) ( ，= 1 ，玎) 可以取值为1 或o ；故玎维向 量y ( r ) 有2 “种状态，即是网络状态。 对于三个神经元的离散h o p f i e l d 网络，它的输出层就是三位二进制数；每一 平面问题的一种新型神经网络算法 个三位二进制数就是一种网络状态，从而共有8 个网络状态。这些网络状态如图 2 4 所示。在图中，立方体的每一个顶角表示一种网络状态。同理，对于九个神经 元的输出层它有2 “个网络状态，也和个玎维超立方体的项角相对应a b0 1 0 图2 4三神经元输出层的网络状态 i 】l 1 1 d 如果h o p f i e l d 网络是一个稳定网络，那么在网络的输入端上加入一个输入向 量，则网络的状态会产生变化，也就是从超立方体的一个项角转移向另一个顶角， 并且最终稳定于一个特定的顶角。 对于一个由，2 个神经元组成的离散h o p f i e l d 网络，则有胆押的权系数矩阵缈： 缈= 呢) f ，j = 1 。，珂。同时，有n 维阀值向量口：口= 【嘿，岛，包r 。 一般而言，和侈可以确定个唯一的离散h o p f i e l d 网络。考虑离散h d p f i e l d 网络的一般节点状态：用t ( 哆表示第，个神经元，即节点，在时刻f 的状态，则节 点的下一个时刻o + 1 ) 的状态可以求出如下： w + 1 ) = 删f ) 】i 凇三： ( 2 - z ) u ( ，) = o ) + 一哆 ( 2 3 ) 当彬，在j = ，时等于0 ，则说明神经元的输出并不会反馈到它自己的输入；这时， 离教的h o p f i e l d 网络称为无自反馈网络。 当形。在i = 7 时不等于0 ，则说明神经元的输出会反馈到它自己的输入；这时， 离散的h o p f i e l d 网络称为有自反馈的网络。 离散h o p f i e l d 网络有两种工作方式：同步方式和异步方式。 在时刻f ，所有的神经元的状态都产生了变化；则称并行工作方式。并且有 l 一( f + 1 ) = ，( ：既鬈( f ) + 一q 】j 2 1 ，2 ，n ( 2 4 ) 第二章h o p n e l d 神经网络( m 州) 简介 在不考虑外部输入时，则有 o + 1 ) = 九r ( f ) 一b 】 f = l 在时刻f 时，只有某一个神经元，的状态产生变化， 态不变这时称串行工作方式。并且有 ( f + 1 ) = 厂【i ( f ) + 与一9 】 l = 1 巧( f + 1 ) = ( f ) ，f 在不考虑外部输人时，则有 o + 1 ) = i 一够】 f = i ( 2 5 ) 而其它 一1 个神经元的状 ( 2 6 ) ( 2 7 ) 对于一个网络来说，稳定性是一个重大的性能指标。 对于离散h o p f i e l d 网络，其状态为y ( f ) ：y ( f ) = 哺( r ) ，墨( f ) ) 一，( f 炉。 如果，对于任何f 0 ，当神经网络从f = o 开始，有初始状态】，( o ) ；经过有限 时刻f ，有：】，8 + f ) = y ，则穗网络是稳定的。 在串行方式下的稳定性称之为串行稳定性。同理，在并行方式的稳定性称之为 并行稳定性。在神经网络稳定时。其状态称稳定状态。 从离散的h o p f i e l d 网络可以看出：它是一种多输入，含有阀值的二值非线性 动力系统。在动力系统中，平衡稳定状态可以理解为系统的某种形式的能量函数 在系统运动过程中，其能量值不断减小，最后处于最小值。 对h o p f i e l d 网络引入一个l y a p u n o v 函数，即所谓能量函数： e = ( 一去) i 一一巧+ g 巧 ( 2 8 ) tiij 即有： e = ( 一习r 弓卜以弓+ g 巧= 【( _ 专誓弓卜五i + e 巧) ( 2 9 ) 对于神经元j ，其能量函数可表示为：( 一去) r 巧一玛r + q 巧 也即是有：e = 易 神经元_ ，的能量变化量表示为丝： 屿2 考q2 考2 ( - 争喜暇r 每+ 嘧卜考+ 曰爿蟛c z l 。， 1 0 平面问题的一种新型神经网络算法 如果存在条件睨= o ，f = 】，2 ，n ，= ，f ，7 = l ，2 ，以， 则有： 弓= f _ 誓一+ g 】巧= - 【r + x ，一q 1 ( 2 1 1 ) ，= i，= l l ie j 其中ie ，为神经元，的能量； 业，为神经元，的能量变化： 彬，为神经元f 到神经元，的权系数： f 为神经元，的输出； x 为神经元，的外部输入； 秽为神经元，的阀值； y ，为神经元，的输出变化。 如果，令= 巧+ 爿，则蟑的值根据如下两种情况而定： 1 如果u ，占，即神经元，的输入结果的值大于阀值，则v ，矽，刚从二值 神经元的计算公式知道：f 的值保持为1 ，或者从o 变到l 。这说明y j 的变化y ，只 能是0 或正值。这时很明显有e ，：墟o 。 这说明h o p f i e l d 网络神经元的能量减少或不变。 2 如果u ，岛，即神经元歹的输入结果的值小于阀值，则移，s 彰，则从二值 神经元的计算公式可知：f 的值保持为o ，或者从1 变到o 。这说明f 的变化一只 能是零或负位。这时则有e ：丝，0 。 这也说明h o p f i e l d 网络神经元的能量减少。 上面两点说明了h o p f i e l d 网络在权系数矩阵形的对角线元素为o ，而且矽矩 阵元素对称时，h o p f i e l d 网络是稳定的。 c o b e n 和g r o s s b e r g 在1 9 8 3 年给出了关于h 。p f i e l d 网络稳定的充分条件，他 们指出： 如果h o p f i e l d 网络的权系数矩阵矿是一个对称矩阵，并且，对角线元素为0 则 这个网络是稳定的。即是说在权系数矩阵矽中，如果f = 歹时，o ；j 歹时， 彤，= 既，则h o p f i e l d 网络是稳定的。 应该指出：这只是h o p f i e l d 网络稳定的充分条件而不是必要条件。在实际 中有很多稳定的h o p f i e l d 网络，但是它们并不满足权系数矩阵是对称矩阵这一 条件。 篁三童型! ! ! 翌塑丝塑堕! 坠型! 堕坌旦 上面的分析可知：无自反馈的权系数对称h o p f i e l d 网络是稳定的网络a 它如 图2 5 ，图2 6 所示。 t ly ln 图2 5 对角线权系数为o 的对称h o p f i e l d 网络 - w 1 1 -臀n f w 2 冒割 - 1- ) i ) o 。 同时容易知虬 o j ( 华2 砒很明显，在警时，必定有警s 。 平面问题的一种新型神经网络算法 而且当，仅当兰警盟：o 时，有鱼警：o 。 d fn l 至此，则定理证明完毕。 这个定理说明h o p f i e l d 网络的能量函数e ( f ) 是单调下降的：如果e ( ，) 有下界， 即有确定的极小值；那么网络必定是稳定的。而且，可以知道稳定点对应于能量 函数的下界，即极小值。 下一步工作，只需证明能量函数有下界，那么就可以证明网络是稳定的。 可以证明，如果h o p f i e l d 网络的传递函数g 是连续而且有界的，那么，能量 函数e ( f ) 是有界的。 最后，有如下结论： 当h o p f i e l d 网络的神经元传递函数是连续且有界的，例如s i g m o i d 函数，并 且网络的权系数矩阵对称，则这个连续h o p f i e l d 网络是稳定的。 在实际应用中，任何个系统，如果其优化问题可以用能量函数e ( f ) 作为目标 函数，那么，总可以用连续h o p f i e l d 网络对其进行求解。 由于引入能量函数e ( f ) ，h 0 p f i e l d 使神经网络和问题优化直接对应；这种工 作是具开拓性的。利用神经网络进行优化计算，就是在神经网络这动力系统给 出初始的估计点，即初始条件；然后随着网络的运动传递而找到相应极小点。这 样，大量的优化问题都可以用连续的h o p f i e l d 网来求解。这也是h o p f i e l d 网络 用于神经计算的基本原因。 第三章工程组合优化问题中h o p f i e l d 网络的稳定性及局部极小点问题 第三章工程组合优化问题中h o p f i e i d 网络的稳定性及局部极 小点问题 由于本文的工作是组合优化问题，所以我们从组合优化的角度来谈一下 h o p f i e l d 网络的稳定性及局部极小点问题。 3 1 稳定性分析 美国物理学家h o p f i e l d 提出h o p f i e l d 网络时用了一组微分方城表达，如下： c f 罢= 姜毛巧一景+ ，p 。) 【= g ( “) 式中：毛= 0g 一一可微的严格单调上升的函数； q ，足 o ，同时h o p f i e l d 构 造了一个能量函数 e ：一专兰羔乃巧巧一凳+ 笔去r g 。1 ( r 渺 ( 3 国 e = 一寺乃巧巧一+ 【g 。1 ( f ) 面 ( 3 2 ) j = 1j = ll = l扛l1 、 h o p 触d 严格证明了警艄且仅当警= o 时警北 基于h o p f i e l d 网络总是朝着能量e 减少的方向运行，而且网络的稳定平衡点就 是e 的极小点这一事实，许多学者提出了许多用于工程优化问题的广义的h o p f i e l d 网络【5 1 。这些网络的共同特点是将优化目标函数与约束条件利用罚函数建立一个能 量函数，然后在利用这一能量函数给出一个神经网络动态演化方程岩= ， ) 使式 ( 3 2 ) 成立。表面上看网络的解就是优化问题的一个解，但是许多数值模拟结果却 失败了。 下面的定理说明当仅满足( 3 2 ) 式是不能保证所构造的神经网络是稳定的。 定理l 【9 】连续自治系统的稳定性判据：对于由微分方程岩= 厂) 所表示的系统 ，：彤斗r ”是连续的，它是完全稳定的条件：存在一个标量函数y ( x ) ：f _ r 1 ， 矿( z ) 有一阶连续导数并且( a ) 孚o 且y ( f ) ；o ，当且仅当譬：o ；( b ) x ：，( x ) 的 d r讲 所有的解都是有界的。可见如果要使构造的网络是稳定的，x = 厂( x ) 的解必须有 界。而在实际应用中，许多网络都没有考虑到这一点。而h o p f i e l d 网络在满足式( 3 - 3 ) 的条件下是稳定的，是因为已经证明h o p f i d d 网络在h o 西e l d 严格的假设条件下， 竺 平面问题的一种新型神经弼络算法 网络的解是有界的【1 0 】。一旦这些条件被破坏，网络就可能不稳定。举例： y ：g ( “) ：“，对于简单的一维问题婴：肖来说，方程的解是x ( f ) ：( o ) ，可知 该鹪是无界的，因而网络是不稳定的1 计算机模拟也不能够到达系统的平衡态的 解。 文献 1 1 】中指出：即使根据优化问题的目标函数与约束条件而构造的神经网络 是稳定的，网络的平衡态也不一定对虚能量函数的极小点。它还指出了对于工程 组合优化问题，当目标函数满足极小点的一阶必要条件时，一般能得到一个极小 点。因此，对于如下利用罚函数形成的优化问题：m i n e ( 彳) 和它的网络动态演化 方程x = 厂( 柳应该满足如下几条准_ 贝| j ：( a ) 警o 且鲁= o 当且仅当警= o ； 譬= ，( 柳的解有界：( c ) 罢可以表达成塞= 琢) 警，m ) 是任一函数。则满足烈厦dd f 以上3 个准则的神经网络一般可以得到工程优化问题的极小解。 3 2 局部极小点问题与解决方法 应用h o p f i e l d 网络来解决组合优化问题时，我们通过稳定性分析设计了能量 函数，一般情况下，它是高维的非线性多元函数。而这种函数一般情况下只能找 到局部极小点，而在实际情况中很多这样的局部极小点是没有用处的。和全局极 小点相比，这种极小点的搜索不单代价高而且并没有价值。对于全局优化问题， 怎样才能找到全局极小点。主要有以下两种方法： 随机优化方法 解析方法、即梯度方法 一般来说，一个好的全局优化技术应该能够避免陷入局部极小，而且具有较好 的收敛到稳定点的速度。对于连续变量的情况，随机优化方法很好地解决了逃离 固定点，但由于存在编程复杂的原因而没能得到应用。其中一个原因也是因为它 地下降到稳定点的速度太慢了。另一方面，基于梯度信息地解析方法能有效地找 到稳定点。理想的结果是，我们希望保持随机优化方法的鲁棒性和全局最小化算 法的速度，当我们的系统运行到接近稳定点时，在本文中，针对平面问题的特点， 我们采取了混合梯度下降和模拟退火的方法( 下一章中有具体介绍) ；实验证明了 在寻优和逃离两个过程中它都具有有效的收敛速度。 出现陷入局部极小问题来源于能量函数的固有特性，是不可克服的。那么，我 第三章工程组合优化问题中h 叩f i e l d 网络的稳定性及局部极小点问题 旦 们要逃离局部极小点就必须由能量函数入手。勰析地寻找极小点可以采用梯度法， 原理是显然的，这在我们论证h o p f i e l d 网络地稳定性的时候就已经讲明。我们在 这里采用的是在陷入局部极小点时模拟退火，造成能量函数的暂时上升，从而使 系统具有了逃离的能力。 下面分别介绍解决局部极小的两种方法： 模拟退火算法： 模拟退火算法基于以下几点事实“”： 1 在温度t 下分子停留在状态r 满足波尔兹曼概率分布： 叩趔力 2 去酬一i 禹 p 3 ， 其中e ( ，) 为状态r 的能量，k o 为波而兹曼常量；面为分子能量的一 个随机变量；z 口) 为概率分布的标准化因子。 2 在同一温度下，分子停留在能量小的状态的概率比停留在能量大的状 态的概率大。 3 p r e = e ( 。) 关于温度t 单调下降： p r 乒娟心m 以2 击2 忑i 毒阿p 4 )s e d e 筇e ( k ) 一 z 当丁j o 时晨斗o ，即p r 面= e ( ，m 。) 斗1 。p r 面= e ( ) 的图形如下： 【a ) 在能量低的状态 ( b ) 在非能量低的状态 图3 1 分子停留状态和温度的关系 模拟退火算法的步骤如下： 1 任选一个初始解；t ；：= o ；f 等f m a ) 【( 初始温度) 。 2 若在该温度达到内达到那循环停止条件则转步骤3 ；否则从邻域( 蕾) 中随机选一，计算蜕= 厂( ) 一，( 耳) ；若蜕o ，则：= x ，否则若 平面问题的一种新型神经网络算法 e x p ( 一三鲨) ，鲫玉删( 0 ，1 ) 时则五：= x ，；重复步骤2 。 f k 3 + 。= d ( ) ；七：= 七+ l ；若满足条件，终止计算：否则回到步骤2 。 参数空间梯度上升算法： 图3 2 是h o p f i e l d 网络寻优及逃离局部极小的流程图。 框i 是用学习后的新参数( 第一次用初始给出的参数值) ，使h n n 在状态空间 里进行状态更新至平衡状态，r 是状态更新次数，被定义为时间。框i i 是网络到 达平衡状态后，在参数空间里进行学习，s ( 离散值) 是学习次数。 图3 2 学习算法的流程图 档 ( 由 图3 3 含两个极小值的h n n 学习过程 为了简明起见，举个只含二个极小值的h n n 为例，说明其学习过程。图3 3 是能量和状态的关系，属概念性图示，横坐标表示状态，纵坐标表示与之对应的 能量( 为了便于理解，用一维表示) 。网络的初始状态和所对应的能量可以被定义 第三章工程组合优化问题中h o p f i e l d 网络的稳定性及局部极小点问题旦 为“山岳地形”上的某一点，这个点在特定“山谷”的斜面上。在状态空间里， 由h n n 的收敛特性可知，随着h n n 状态的更新，这个点将滑向谷底。如初始状态 是图3 3 ( a ) 上的点a ，随着h n n 状态的更新，将向谷底滑去，最终陷入谷底b 点 ( 极小值) 。 h n n 能量函数的形状是由各种参数值决定的。因此，对于一旦陷入极小值的点， 在参数空间里，让参数向着使能量函数最速上升的方向学习。为此，用参数对能 量函数进行微分，在它的最速上升方向( 能量函数的微分系数更大的方向) ，即正 的梯度方向上对参数进行修正，这里我们称之为最速上升法。下面就此作进一步 阐述。 首先，考虑一个含有许多参数的系统，把这些参数归纳起来用向量i 表示，在 参数空间里，矿将按照式( 3 6 ) 进行学习，这里设s 是正的常数，旷的修正量，。可 以由式( 3 7 ) 求得， 丘“= 丘+ 丘 ( 3 5 ) k = f v e ( k ) ( 3 - 6 ) v 日是e 关于p 的梯度。如果能使s 取得足够小，随着学习，能量函数e 是上升的。 因此，学习后上升了的b 点，又成为“山谷”斜面上的一点b7 。这时，在状 态空间里，使h n n 进行状态更新，点b7 将向谷底c 滑去，最后陷入谷底c 点( 图 3 3 ( b ) ) 。如此使网络在状态空间和参数空间里，按照洲n 的收敛特性及最速上升 法，反复地进行状态更新、参数学习，h 州能量函数能够从陷入的极小值中逃脱出 来，最终收敛于最优解或满意解( 图3 3 ( b ) ) 。 2 0 平面问题的种新型神经网络算法 第四章模拟退火与梯度下降相结合的混合算法 4 1 引言 h o p f i e l d 网络的基本思想是沿着梯度下降的最优路径到达离初始点最近的极 小点，所以整个学习过程是一个非线性优化过程，有可能产生局部最小值和震荡， 使学习结果变差，即有可能得不到全局极小值，于是我们引入了模拟退火法，对 其进行改良，形成了一种新的混合下降算法。在上一章中我们已经分别讨论了模 拟退火算法和梯度下降算法的特点，在本章中我们主要给出由这两者组成的混合 下降算法，大量实验结果验证了该混合算法的有效性和可行性。 4 2 混合算法的分析与设计 用一般的随机优化算法解决全局最优化问题时，往往会因为算法的效率太低 而使得算法变得难以应用；而用般的下降算法解决全局最优化问题时，又往往 会因为算法的结果与初始点的选取关联过大而使得算法的通用性大大下降【1 7 j 。因 此许多混合算法被提出来用于解决全局最优化问题。 比较常用的一种混合算法是利用梯度下降算法和某些辅助函数来不断的从一 个局部极小点跳到另外一个更好的局部极小点。这种算法包括n l 柏e l l i n g 算法【1 8 】 和b r i d g i l l g 算法i l 州。这些算法必须依靠构造相当准确的t u 加e l l i n g 函数或者 b r i d g i n g 函数来帮助目标函数从个局部极小点跳到另外一个更好的局部极小 点。对于一些维数很低的全局最优化问题，这些算法确实能较好的找到相应的全 局极小值b o j 。但是对于些高维的全局最优化问题，它们却不能有效的找出相应 的全局极小值。 一般来说，一个好的全局最优化算法应该既能保证有效的避免陷入局部极小 点，又能较快地收敛到个稳定的值。随机优化算法是一个逃离局部极小点的很 好的方法，但是它的运行速度过于缓慢。其中一个原因就是这种方法在试图找到 一个稳定的收敛点的时候速度过慢。而对于基于梯度的分析性方法来说，找一个 稳定的收敛点的速度很快。因此我们希望找到一种算法，它既能拥有随机优化算 法的优点，又能以较快的速度运行到一个稳定的值。在本章中，我们根据这种思 路提出了由梯度下降法和模拟退火算法组成的