《平面问题的一种新型神经网络算法》由会员分享，可在线阅读，更多相关《平面问题的一种新型神经网络算法（46页珍藏版）》请在金锄头文库上搜索。
1、1 0 7 0 1T P 3 9 l学号一塑磐型j 碧密级公开士学位论文j 曼匝凰避鳆= 赞新墨竖申暨盟缘霉堡一上! 婴；n 删9 卫- o ! 蔓! 运；曲一塑i 也一一曼地艘H 剑咖g 卿然蹦g 虹蚀虹 ，里强指导教师姓名、职务壁至墓熬竖三抖学科、专业一盟篓妞鏖用蛙墨一三旦Q 盎生= 且摘要摘要平面问题是一个典型的组合优化问题。平面问题在印制电路板的设计和大规模集成电路( v L s I ) 的布线方面有着重要的应用，对于很多可视化问题，例如基因调控网络的可视化也有着蘑大的意义。平面问题包括两部分：平面性测试和平面嵌入。虽然很多研究人员针对该问题的两部分已经提出了一些算法，但它们都存在着一
2、些缺陷。本文将该问题的两个部分统一对待，指出了可平面图的平面嵌入是有条件的，只有在特定的顶点顺序情况下才是可直线嵌入的，并通过给出既满足直线嵌入条件又实现正确布线的能量函数，进而用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 tA b s t r a c tP l a l l 州z a t i o
3、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 ti 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
4、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 也cp 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
5、ym a l l yr 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 wH 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 lo I l l yb ee m b e d d e do m oas i n g l
6、el i l l ew h e ni t sv e m c e sa r ei ns p e c i a lo r d e Lna l s op r e s e m sa ne n e r g yf U n c t i o nt h a tc a nm 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 el 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
7、 l i e df o rd 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 yg 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 oe m b e dt h es u b g r a p ho n t oas i n g l el
8、 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 sh 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
9、 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 gA l g o r i t h mY8 5 8 9 2 5独创性( 或创新性) 声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，
10、论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：埠j 塾日期翌! 车2 目兰堕关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内
11、容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解密后遵守此规定)本学位论文属于保密在一年解密后适用本授权书。 本人签名：导师签名：日期竺! ! 盘! 旦塑 日期竖垒丛塑等一第一章绪论第一章绪论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 网络是一类应用十分广泛的人工神经网络，在组合优化方面有着广泛的应用。但是，在实际的应
12、用中，这种经典的网络存在着诸多缺陷，例如局部极小点，网络进入极限环等。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
13、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 网络在当前权值的学习过程中陷入到个局部极小点时，开始模拟退火的
14、梯度上升学习过程，从而使网络的能量以一定概率暂时增加，增强了网络摆脱局部极小点的能力。我们知道图论中的平面问题是个典型的组合优化问题。平面问题在印制电路版的设计和大规模集成电路的布线上有重要作用【l 】。它对应完成两个任务，一个是平面测试，一个是平面嵌入。平面测试问题是判断一个电路图是否是可平面的，并从非平面的电路图中提取出其最大的可平面部分。1 9 8 9 年J a y k I l I l l a r 等人给出了解决这一问题的0 ( 起2 ) 复杂度平面测试算法【l 】，其中H 为电路中顶点数目。平面嵌入问题是将一个可平面图或一个不可平面图的最大可平面子图嵌入到平面上，并实现在该平面上的平面
15、布线。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
16、 a k e f u j i 等首先引进了H o p f i e l d 网络的并行智能化算法。但 2 中在进行平面嵌入时采用的是直线嵌入方法，而这会出现一种情况：顶点与直线上的位置对应顺序不同时所得的结果是不一致，这样会导致可平面图由于网络运行结果表明其是不可直线嵌入的而得出是不可平面的结论，从而无法实现可平面图的直线嵌入和布线；对于不可平面图则会发生无法真正找出其最大的可平面子图，从而未能彻底的解决平面问题。本文针对该算法的不足之处，提出了新型高阶反馈神经网络求解平面问题的方法，并改进了网络的结构和能量函数。整个算法由两个阶段组成，分别是H o p f i e l d 网络的梯度下降运行阶段和模拟退火算法逃离局部极小阶段。该算法用梯度下降算法来进行局部搜索，当算法陷入局部极小点后便开始用模拟退火算法来逃离局部极小点。因此该算法兼备了梯度下降算法的效率和模拟退火算法的稳定性。另外该算法还具有单调收敛的良好特性。大
