（计算机软件与理论专业论文）最优化问题混沌神经网络算法的研究与应用.pdf

原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 强；o ；t e 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论文及送交 论文复印件，允许论文被查阅和借阅；学校- j - 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：日期：州 。 易 竺 叠f 獬聊 雌 摘要 2 0 世纪8 0 年代由j j h o p f i e l d 和d wt a i l l 【提出的h o p f i e l d 神经网络模型在 很大程度上促使了人们对神经网络的重新关注。至今，该模型已被成功应用于各 类与优化相关的问题，其中著名的要数旅行商问题。尽管，h o p f i e l d 模型的性能 要优于大多数的启发式算法。然而，它也有不足之处。其中最明显的缺陷在于采 用梯度下降的动态系统导致其容易陷入局部最优。不过，通过对混沌非线性系统 的探究，人们提出了几种混沌神经网络从而克服了这一缺陷。本文首先应用其中 的一种混沌神经网络，即暂态混沌神经网络，来解决一个经典的并具有许多现实 应用领域的n p 难的组合优化问题最大团问题，并对其优化性能作了深入的 研究。然后，对该算法进行改造，使其适用于模式识别和大规模集成电路设计等 领域。在研究过程中，我发现暂态混沌神经网络的运算速度相对较慢。因此在本 文最后，我通过调整该算法的退火机制对该算法进行了改进，改进后的算法能够 迅速地收敛并保持很好的优化性能。1 关键词；神经网络；最优化问题；混沌；最大团问题；模式识别；大规模集成电路 设计 本课题得到上海市科委自然科学基金的资助( n o 0 0 j c l 4 0 5 2 ) a a b s t r a c t m u c ho ft h er e s u r g e n c eo fi n t e r e s ti nn e u r a ln e t w o r k sd u r i n gt h ee a r l y1 9 8 0 s c a l lb ea t t r i b u t e dt ot h ee m e r g e n c eo ft h eh o p f i e l dn e u r a ln e t w o r k ，w h i c hi sp r o p o s e d b yj j h o p f i e l da n dd wt a n k u pt on o w , t h eh o p f i e l dn e u r a ln e t w o r km o d e lh a s b e e ns u c c e s s f u l l ya p p l i e di nv a r i o u so p t i m i z a t i o nr e l a t e dp r o b l e m s ，a n d o n ef a m o u so f w h i c hi st h et r a v e l i n gs a l e s m a np r o b l e m a l t h o u g ht h ep e r f o r m a n c eo ft h eh o p f i e l d m o d e li sb e t t e rt h a nt h a to f m o s th e u r i s t i ca l g o r i t h m ，t h eh o p f i e l dn e u r a ln e t w o r ka l s o h a ss o m ed r a w b a c k s ，a n do n es e r i o u so fw h i c hi st h a tt h eh o p f i e l dn e u r a ln e t w o r k m a yg e ts t u c ki nl o c a lm i n i m ad u et oi t sg r a d i e n td e s c e n td y n a m i c s f o r t u n a t e l y , b y p r o b i n gi n t ot h ec h a o t i cb e h a v i o ro fn o n l i n e a rd y n a m i c s ，s e v e r a lc h a o t i cn e u r a l n e t w o r k s ( c n n ) h a v eb e e np r o p o s e dw h i c hc a no v e r c o m et h i sd i s a d v a n t a g e a n di n m yp a p e r ，if i r s t l ya p p l i e do n ek i n do ft h e s ec h a o t i cn e u r a ln e t w o r k s ，t h et r a n s i e n t l y c h a o t i cn e u r a ln e t w o r k ，t os o l v et 岫m a x i m u mc l i q u ep r o b l e m ，w h i c hi sac l a s s i c n p - h a r dc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e ma n dh a sm a n yr e a l - w o r l da p p l i c a t i o n ， a n dt h ep e r f o r m a n c eo ft h i sa l g o r i t h mi ss t u d i e di nd e t a i l a n dt h e n ，t h i sa l g o r i t h mi s a d a p t e df o rs o m ea p p l i c a t i o n ss u c ha sp a t t e r nr e c o g n i t i o na n dv l s id e s i g n i nt h e p r o c e s so fr e s e a r c h ，if o u n dt h a tt h es p e e do ft h i sa l g o r i t h mi sr e l a t i v e l ys l o w , s o f i n a l l yi nt h i sp a p e rip r o p o s e da ni m p r o v e da l g o r i t h mt h a tc a i lc o n v e r g eq u i c k l ya n d m a i n t a i ne x c e l l e n to p t i m i z a t i o np e r f o r m a n c eb ya d j u s t i n gi t ss i m u l a t e da n n e a l i n g m e c h a n i c s 1 k e y w o r d s ：n e u r a ln e t w o r k ；o p t i m i z a t i o np r o b l e m ；c h a o s ；t h em a x i m u mc l i q u e p r o b l e m ；p a t t e r nr e c o g n i t i o n ；v l s ic i r c u i td e s i g n s u p p o r t e db y t h es c i e n c e f o u n d a t i o n o f s h a n g h a i m u n i c i p a l c o m m i s s i o n o f s c i e n c ea n d t e c h n o l o g yu n d e r g r a n tn o0 0 j c l 4 0 5 2 6 第1 章最优化问题的相关知识 1 1 最优化问题的提出与定义 1 1 1 最优化问题的提出 最优化问题的理论及算法是一个重要的数学分支，它所研究的是在众多的方 案中什么样的方案最优以及如何找出最优方案。这类问题普遍存在于社会生活的 各个方面。例如产品设计、城市规划、农业生产等等。最优化问题这一数学分支， 正是为这些问题的解决提出理论基础及求解方法。 1 1 2 最优化问题的定义 下而给出最优化问题的一般定义： 定义1 1 ：给定一对元素( f ，c ) ，其中f 是一个集合或可行点的定义域，c 是费 用甬数或映射( c ：f 叶尺】。摄优化问题是求个f f ，使得 b f ：f ( 厂) c ( y ) ，则f 被称为给定最优化问题的全局最优解。 1 2 最优化问题的基本分类 按照其变量的性质，最优化问题可以自然地分为两类：一类是离散变量的问 题，另一类是连续变量的问题。 1 2 i 组合最优化问题 具有离散变量的优化问题称之为组合优化问题，其定义如下： 定义1 2 ：给定q = “，s ：，一，晶 为所有状态构成的解空间，c ( 黾) 为状态对应 的目标函数值t 组合优化问题是求一个5 + q ，使得q ：c ( s + ) c ( ) e 典型的组合优化问题有最大团问题( m a x i m u mc l i q u ep r o b l e m ，m c 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 ) 以及图着色问题( g r a p hc o l o r i n g p r o b l e m ，g c p ) 等等。 p r o b l e m g c p ) 等等。 9 1 2 2 函数最优化问题 变量在定义区间内连续的优化问题成之为函数优化问题，其定义如下： 定义1 3 ：令s 为r ”上的有界子集，f ：s 呻r 为n 维实值函数，函数最优化问 题是寻求点z + s ，使得v y s ：z ( x ) ，( z ) 。 1 3 一些典型的最优化问题 在本节中，我们将介绍两个经典的最优化问题一最大团问题和二次规划问 题。它们分别属于上一节所讲的组合最优化问题和溺数最优化问题。 1 3 1 最大团芦】题 最大团问题是经典的组合优化问题，它是一个n p h a r d 问题 1 3 。它在各 个领域都有广泛的应用。例如：信息检索、机器视觉、电路设计等等。另外，它 也是研究许多图论问题的基础，如图着色问题。 在给出最大团问题的定义之前，我们首先需要了解团、极大团和最大团的定 义。 定义1 4 ：对于一个无向图g = ( 矿，e ) ，矿v 称为一个团，如果v u ，v ，ep ，1 ， ( v , _ ) e e 。 定义1 5 ：对于一个无向图g = ( v ，e ) ， y 矿称为一个极大团，当且仅当v 。是 一个团并且v 不是其他团的子集。 定义1 6 ：对于一个无向图g = ( y ，e ) ， y 矿称为一个最大团，如果v 的顶点 数最大。 由此可见，最大团必定是一个极大团，极大团必定是个团。但反之不然。 图1 - 1 ：具有5 个顶点的无向图 如图1 - l ，顶点集 b ，c ，d ，e ) ， a , b ，e ) ， a ，b ) 分别是最大团、极大团和团。而 顶点集 a ，b ，c ，e ) 由于顶点a 和c 之间没有边相连，所以不是一个团。 而最大团问题就是在给定的无向图中搜索最大团的问题。 1 3 2 二次规划问题 若j ( x ) 是x 的二次函数，函( x ) ( f - 1 ，2 ，m ) ，啊( x ) ( f - m + l ，n ) 都是x 的 线性函数，则： r a i ni ( x ) j t g ，( x ) 0 ，f = 1 ，2 ，m 囊( x ) = o ，f _ m + l ，p 称为二次规划问题a 其中，厂( x ) 为目标函数，岛 ) ， ( x ) 为限制条件。 1 4 求解最优化问题的一般方法及其缺陷 解决实际优化问题的手段大致分为三种：一是靠经验的积累，凭主观作判断； 二是做试验选方案，以优劣定决策；三是建立数学模型，求解最优策略。目前对 一些常用问题的模型已经研究和设计了相应的标准求解算法，这些算法可有效解 决很多实际问题，但多局限与良性结构问题，即问题结构比较清晰、所含元素之 间关系明确、边界清楚、有明确的最优判定准则、能拟定求解的程序步骤、所要 求的计算量不至于过大等。然而实际中的许多问题不具有良性结构，套用传统方 法处理难以得到满意的结果。这时，与其偏离事实或忽略修正重要条件勉强套用 传统标准方法，还不如保持问题的本来面目建立符合实际的非标准模型。前者虽 然可简化求解，但得到的解由于偏离了实际而难以付诸实施；后者则由于模型涉 及因素多，难以套用传统方法求解。 为了克服传统算法的这些不足，并在不明显降低优化效果的前提下，为实际 问题提供计算步骤简单、易于实现、运算量小、节约开支与时间的新算法，2 0 世纪8 0 年代以来，一些新颖的优化算法应运而生 4 ，5 。这些算法通过模拟或 揭示某些自然现象或过程而得到发展，其思想和内容涉及数学、物理学、生物进 化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供了新的思路和 手段。这些算法独特的优点和机制，引起了国内外学者的广泛重视并掀起了该领 域的研究热潮，并在诸多领域得到了成功应用。在优化领域，由于这些算法构造 的直观性与自然机理，因而通常被称作智能优化算法( i n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m s ) ，或称现代启发式算法 ( m e t a - h e u r i s t i c a l g o r i t h m s ) 。其中最具代表性的就是h o p f i e l d 神经网络。 第2 章h o p f i e l d 神经网络的相关概念 2 1h o p f i e l d 神经网络的发展 2 1 1h o p f i e l d 神经网络的提出与发展 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 dn e u r a ln e t w o r k ) ，证明在 高强度连接下的神经网络依靠集体协同作用能自发产生计算行为 6 - 9 。h o p f i e l d 网络是典型的全连接网络，通过在网络中引入能量函数以构造动力学系统，并使 网络的平衡态与能量函数的极小解相对应，从而将求解能量函数极小解的过程转 化为网络向平衡态的演化过程。尤其是通过对t s p 问题的成功求解，开辟了神 经网络模型在计算机科学应用中的新天地，动态反馈神经网络从而受到广泛的研 究和关注，被广泛应用与优化问题中，且已设计出了专用的硬件电路。 2 1 2h o p f i e l d 神经网络的应用 除了在优化领域中取得了巨大的成功，h o p f i e l d 神经网络的应用研究也渗透 到控制工程、机器学习、信号处理、模式识别和经济等领域。 2 2h o p f i e l d 神经网络的基本结构 2 2 1 离散型h o p f i e l d 神经网络 离散型h o p f i e l d 神经网络的输出为二值型，网络采用全连接结构。 x ix ：，x 。为各神经元的输出，y l ，儿，儿为各神经元的中间状态， c o i 。，q 一，q ，为各神经元与第i 个神经元的连接权值，为第i 个神经元的阀值， 则有 葺= ，l 毛n ，_ 一 叫咒卜1 , y i 0 。， 能量函数定义为： 1 ” hn e 一i 善善1 蕾_ + 善t ( 2 卢】户l _ l 、7 2 22 连续型h o p f i e l d 神经网络 连续型h o p f i e l d 神经网络的动态方程可简化描述如下 ( 2 3 ) 其中，m ，分别为第i 个神经元的中间状态和输出，g ( ) 为具有连续且单 调增性质的神经元激励函数，为第i 个神经元到第，个神经元的连接权，为 施加在第i 个神经元上的偏置。 能量函数定义为 e 一j 1 智n 智n0 3 “蕾。一喜耳+ 喜f gj - i ，一1】- lf - 1 2 3 连续型h o p f i e l d 神经网络在最大团问题上的应用 从最大团问题的定义可以容易的得到如下结论 对于一个简单无向图g ( v ，e ) ，其中v = 1 , k ，n ) 是顶点的集合，e 互v x v 是 边的集合，在g ，e ) 中搜索最大团等价于求解如下的= 次优化问题 m a x f ( x ) = i x 7 艇( 2 5 ) 其中a = ( a u ) u x w ，是图g ( v ，e ) 的邻接矩阵。与连续型h o p f i e l d 神经网络的 能量函数形式一致。 2 3 1 最大团问题的连续型h o p f i e l d 神经网络算法 由上述结论可以得到最大团问题的连续型h o p f i e l d 神经网络算法。其迭代公 r 缸一 毗百 式如下 h = g ( ”) 协叫嚆 =一；善n蔷ne薯_ 一z 薹i g x j + 羹；f g = 一；薯_ 一+ f g i = l ，= lf _ 1i = l ( 2 - 6 ) 1 ( ”) 如 其中蛳= 0 ；当顶点i 和，相连时卿= l ；当顶点i 和，不相连时，卿：a ( p o ) 。 当p = 一4 n 时，该算法收敛于一个极大团。 2 3 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 神经网络会陷入局部最 小，从而影响优化性能，其证明如下： 因为 塑d = 羔詈生(27)td t 鲁融 ” 并且 嚣一蔷nw + g - i ( 一) - z j x j i ? + y 奶 = 一一 出 由式2 7 和2 8 ，可以得到： ( 2 8 ) ( 2 9 ) 由于_ = g 伊d 单调递增，所以y i - - g - 7 扛d 也单调递增因此，矗e 出 0 ) 3 3 暂态混沌神经网络的优化性能分析与研究 本节中，我们将使用前面提到的暂态混沌神经来解决最大团问题，以研究暂 态混沌神经是否适用于最大团问题。我们将分别分析该算法的优化性( 是否能够 搜索到最大团) ；效率( 算法收敛的迭代步数) ：鲁棒性( 算法是否对参数敏感) 和可扩展性( 算法是否对不同的问题规模数适用) 。最后，我们将给出该算法的 实验结果。 3 3 1 用暂态混沌神经网络解决最大团问题 为了使用暂态混沌神经网络来解决最大团问题，我们对该算法进行了改造。 算法的伪代码表示如下所示： t c n nf o rt h em c p i n i t i a l i z e w ，一( o ) a n d 毛( 0 ) d o f o ri - - lt o n ( 小= 1 ( 1 + e 州) “川) 卅心) + a 陡酬吵 吲f ) ( 巾) 训 = ，( t + 1 ) = ( 1 - p ) z ，( t ) i n c r e a s e t b y1 u n t i le c o n v e r g e s 从理论上说口和z ( 0 1 的值可以任意选择。但是，基于大量的实验，我们发 现当口【o ，o6 】和= ( o ) 1 0 ，2 0 时，该算法能够得到最优结果。 我们同样将t c n n 应用于图1 - 1 中的那个无向图实验共进行了1 0 0 次每 次使用不同的初始值。我们惊喜地发现所有实验的结果都是 b ，c ，d ，e ，即最大团 由此可见该算法明显优于h o p f i e l d 神经网络算法。 很明显，t c n n 对于求解最大团问题是一个很有希望的方法。在下一节中， 我们将具体分析该算法的有效性、效率、鲁棒性和可扩展性，并探究使t c n n 避免陷于局部最优解的主要原因。 3 3 2 算法的性能分析 在这一节中我们将在二维变量空间内就t c n n 算法的各项性能进行研究， 包括有效性、效率、鲁棒性和可扩展性。具体到最大团问题而言，有效性指的是 在一次实验中算法是否能够搜索到最大团；效率指的是算法收敛所用的迭代步 数：鲁棒性是指有效区域的分布；而可扩展性则考察算法是否对不同结点数的无 向图都适用。 各参数具体设景如下：p ：- 4 ，峨：_ i p l ，s ：1 ：0 0 0 1 ，r ：0 9 。其中参数 q 和z ( o ) 控制最速下降速度和非线性反馈强度最主要的两个参数。基于大量的变 验，我们发现当参数口设置在0 和0 6 之间，参数z ( o ) 设置在1 0 和2 0 之间， 算法最容易得到最优解。因此，参数空间的参数分别为口和z ( o ) 。图3 - 1 ( a ) ( c ) 分别显示了算法对于结点数为2 8 、6 4 和2 5 6 的无向图的有效性。而图3 - 1 ( d 1 显 示了算法对于结点数为6 4 的无向图的收敛迭代步数。在图3 - 1 ( a ) 一( c ) 中，黑色的 区域表示算法在此参数设置下搜索到了最大团。很明显，在参数空间内有效区域 占了相当大的部分，这就意味着算法在选择参数时有着很好的鲁棒性。此外，随 着结点数的增多，有效区域并没有明显减少，从而显示了很强的可扩展性。在图 3 - 1 ( d ) 中，我们用灰度的强弱来表示不同的效率，颜色越深意味着收敛的迭代步数 越少，换言之，就是较高的效率。由于图3 - 1 ( b ) 和( d ) 所设计的问题规模数相 同，即结点数为6 4 ，我们发现当参数口和z ( o ) 分别设置为0 6 和1 3 时t c n n 通过5 2 次迭代就在一个6 4 结点的无向图中收敛到了最大团。而h o p f i e l d 在该图 上用了6 4 次迭代才收敛。这就表示t c n n 拥有较好的效率。通过比较图3 - 1 ( b ) 和( d ) ，我们还发现在对有效性的影响中，参数口较之参数z ( o ) 起着更为重要 的作用。而随着参数z ( o ) 减小，效率明显提高。 图3 - 2 显示了当1 v i = 6 4 ，d = o 0 5 和z ( 0 ) = 1 5 时，能量函数e 的演化过程。 从中，我们可以清楚地观察到神经元的全部动态过程。当t c 2 3 0 时，系统具有丰 富的混沌行为。然后能量函数的值逐渐减小，最后达到一个全局最小值。该图清 楚地表明，与传统的h o p f i e l d 算法不同，t c n n 始于确定性的混沌动态，随着参 数z 的减小经历了一个逆分岔过程，最终达到一个稳定的平衡状态。t c n n 这 一区别与h o p f i e l d 神经网络的特性改善了其求解最优化问题的性能。在此基础 上，我们改变变量口的值来观察其对神经元动态的影响。图3 - 3 ( a ) 和( b ) 分别 描述了d = 0 0 5 和口= 0 6 时t ( t ) 的动态过程。图3 - 3 ( a ) 中，神经元的混沌动态 过程持续了较长的时间；而另一方面，图3 - 3 ( b ) 中。神经元的混沌动态过程随时 间迅速消失。因此，我们可以清楚地看到该参数对混沌的分岔速度起着一定的作 用。而从图3 - 1 ( a ) ，我们很容易发现当参数a 被设置在0 0 5 和0 1 0 时，算法无法 搜索到最大团。这表明混沌状态持续时间过长将有可能降低算法的性能。 鲷4 飘 z ( o ) 伯 z ( o ) t 噼 5 0 蜘 m 猢 0 t d j 罄罄毒簿i i 毫爆最 。 z ( o ) 锄 图3 - 1 ：用暂态混沌神经网络求解最大团问题的有效性和效率分析图。( a ) ，0 0 ) 和( c ) 分别为 l v l = 2 8 ，6 4 和2 5 6 时的有效性分析图；( d ) 为i v l = 6 4 时的效率分析图。 潍眦蹲耀滞瑚耀 图3 - 2 ：用哲态混沌神经网络求解最大团问题能量函数值的演变 图3 - 3 ：不同口值情况下，单个神经元的数值演变l ( a ) 口t 0 0 5 ；( b ) a = o 6 3 3 。3 实验结果 d i m a c s ( t h ec e n t e rf o rd i s c r e t em a t h e m a t i c sa n dt h e o r e t i c a lc o m p u t e r s c i e n c e ) 在1 9 9 3 年曾举办了一次“i n t e r n a t i o n a li m p l e m e n t a t i o nc h a l l e n g e ”， 用于寻求在最大团问题、图着色问题( g r a p hc o l o r i n g ) 和可满足性问题 ( s a t i s f i a b i l i t y ) 上的有效的优化算法和近似算法。而我们使用的实验数据则取 自此。实验结果如表3 - 1 所示。第一栏( g r a p h ) 表示实验数据的名称：第二栏 ( i v i ) 则是结点数：第三栏( t c n n ) 给出了使用t c n n 对最大团进行搜索的结果， 如果用粗体显示则表示给结果与第四栏给出的最优结果一致，而第四栏( b e s t r e s u l t ) 则提供了目前为止其他算法所得到的最优值。 表3 - 1 ： 在d i m a c 8 数据上进行实验的结果 g - r a p h ( v , e ) v it c n nb e s tr e s u l t t a m m i n 9 6 2 ；4 2；2 + a m m i n 9 6 4 弭 i + a m m i n 9 8 2 1 5 62 82 8 * t a m m i n 9 8 - 4 1 5 661 6 + a m m i n 9 1 0 - 2 【0 2 4；1 25 1 2 ) h a t 3 0 0 一1；0 0j + ) h a t 3 0 0 2 0 0：5z 5 + ) h a t 3 0 0 3；0 01 63 6 * ) h a t 5 0 0 15 0 0 i+ ) h a t 5 0 0 25 0 01 63 6 * ) h a t 5 0 0 35 0 01 75 0 ) h a t 7 0 0 17 0 001 l + ) m a t 7 0 0 27 0 0 1 4 4 4 * ) h a t 7 0 0 37 0 0；96 2 * o h a t l 0 0 0 11 0 0 0【01 0 d h a t l 0 0 0 21 0 0 01 64 6 o h a t l 0 0 0 31 0 0 0；86 8 j o h n s o n 8 2 42 8i d j o t m s o n $ 4 47 0l 41 4 j o h n s o n l 6 2 41 2 0 b8 4 c f a t 2 0 0 12 0 01 21 2 c ：- f a t 2 0 0 2 2 0 0z 42 4 * c f a t 2 0 0 52 0 05 85 8 * c f n 5 0 0 25 0 02 62 6 * c f a t 5 0 0 55 0 06 46 4 * s a n r 2 0 0 0 72 0 01 71 8 + s a n r 2 0 0 0 92 0 04 l4 2 * s a n r 4 0 0 0 5 4 0 0 1 2 1 3 + s a n r 4 0 0 0 74 0 02 l2 1 第4 章暂态混沌神经网络在工程中的应用 4 1 暂态混沌神经网络在模式识别中的应用 4 1 1 模式识别中的关系结构匹配问题 在模式识别研究领域中，关系结构是用于对象表示的一个重要的数据结构。 一般来说，一个对象上的各个组成部分由一组单元集合与一组属性集合表示。而 这些组成部分之间的关系，诸如：地理关系、空间关系和时间关系，由一组关系 集合表示。因此，关系结构成为模式识别研究中十分受欢迎的一种表示方法。 对象相似度的判定是许多模式识别应用中的关键问题。给定一组已知对象以 及一些需要分类的输入对象，模式识别的任务就是从已知对象中确定一个对象使 其与输入对象的相似度最大。如果采用关系结构来表示对象的话，那么这个问题 就转变成确定关系结构之间相似度的问题，该问题被称为关系结构匹配问题 ( r e l a t i o n a ls t r u c t u r em a t c h i n gp r o b l e m ，r s m p ) 1 4 ，1 5 。 目前，有各种算法来解决关系结构匹配问题。而这些算法基本上可以分为两 大类。其中，第一类是将匹配问题看作为一个在状态空间中的搜索问题，第二类 是将该问题作为一个能量最小化问题。在属于第一类的那些算法中，由a m b l e r 提出的算法经验证十分有效并应用在各个领域。a m b l e r 的方法基于这样一个思 想，即关系结构匹配问题等同与在结合图中搜索最大团的问题，其中结合图是从 关系结构中导出的一个辅助图。该方法的吸引人之处在于它将匹配问题转换成一 个组合优化问题即最大团问题。因此，所有那些能够有效解决最大团问题的算法 亦能有效解决关系结构匹配问题 1 6 - 1 8 】。 4 1 2 问题求解 为了使用暂态混沌神经网络来求解关系结构匹配问题，我们对该算法进行了 改造。算法的伪代码表示如下所示： t c n n f o r t h er s m p g e n e r a t i n gt w or e l m i o n a ls t r u c t u r es 岍ta n ds 咖 c o n s t r u c t i n gt h ea s s o c i a t i o ng r a p hp r o d u c e df r o mb o t hs t w ia n ds 归 i n i t i a l i z e ，”( 0 ) a n dz ( 0 ) f _ 0 d o f o ri - - 1t o n ( f ) = 1 ( 1 + b 一“) y i 0 + 1 ) = 职( f ) + 口1 n 峨_ ( f ) + 1 厂、 l = 1 一( f ) ( ( f ) 一l ) z ，( t + 1 ) = ( 1 一卢) z ，( t ) i n c r e a s et b y1 u n t i lec o n v e r g e s m e a s u r i n gs i m i l a r i t yb yc o u n t i n gt h en u m b e ro f v e r t i c e so f t h em a x i m u mc l i q u e 4 1 3 实验结果 我们用该算法对圈的同构问题进行了一系列的试验，该问题被广泛被应用于 评价关系结构匹配问题算法的性能。以验证该算法的效果。在实验中，我们生成 1 0 0 个结点的随机图，其联接度从l o 到9 0 。对每一种联结度，共生成1 0 0 个 图，然后将其结点随机地进行重排，从而获得一对同构图。每一对同构图作为该 算法的输入，算法收敛后，如果搜索到的最大团的结点数等于输入图的结点数， 则作为匹配成功。表4 - 1 列出了t c n n 和h o p f i e l d 神经网络对于这些随机图的 实验结果。第一栏( c o n n e c t i v i t y ) 表示随机图的联接度；第二栏( h n n ) 给出了使用 h o p f i e l d 神经网络进行匹配的成功率；第三栏( t c n n ) 给出了使用t c n n 神经网 络进行匹配的成功率。 从实验结果中我们可以清楚地发现，使用t c n n 算法，匹配的成功率界于 8 8 与9 8 之间。因此，这验证了t c n n 用于结构匹配问题是十分有效的。与 使用h o p f i e l d 神经网络进行匹配的成功率相比，t c n n 在不同的联接度匹配的成 功率都优于h o p f i e l d 神经网络。 表4 - 1 ： 对随机图分别用h n n 和t c n n 进行仿真的结果 c o r m e c t i v i t yh n nt c n n o 19 3 9 8 0 28 7 9 7 0 - 3 9 0 9 1 o 4 9 0 9 5 0 57 7 9 0 o 68 1 8 8 o 7 8 3 9 2 0 88 8 9 5 0 99 2 9 2 4 2 暂态混沌神经网络在v l s i 设计中的应用 随着大规模集成电路( v l s i ) 的日益普及，提高集成电路的性能、降低其成本 已成为生产中的两个主要问题。因此，目前有诲多研究人员正致力于v l s i 芯片 物理设计的研究之中，以期在改善芯片的性能同时降低其成本 1 9 ，2 0 。 4 2 1v l s i 设计中的通道排线问题 在v l s i 芯片物理设计中，通道排线问题( c h a n n e lr o u t i n gp r o b l e m ，c r p ) 是 一个十分重要的问题，这是因为该问题对于芯片的性能和生产成本起着重要的作 用。因此，有许多用于解决这个问题的算法。下面对该问题做一个简要的介绍。 通道是v l s i 芯片中的一个重要组成部分，其中排放了几百乃至几千条电子 线路。从此通道是有上、下两层组成的。在每一层上，均匀分布着线路的引脚并 由数字标注。而上下两层的引脚中如果有一对必须在芯片内部相连的话，则被成 为一个网络，如图所示。在通道排线问题中，通常有个通道的规格说明来具体 表明需要建立哪些网络。如图4 1 所示，该通道规格说明中包含有6 条双引脚类 型的网络。网络1 将上层的引脚7 与下层的引脚1 0 相连。同样网络6 将上层的 引脚8 与下层的引脚1 1 相连。在上、下两层之间，有一些水平的轨道用于放置 网络连线的水平部分。 12j4057目q1d1 1c o l t mn o i：i !：1 1。o 6 。m i n 3 1n o j-。_ 。l 三一1 - 乞已j l _ j ) _ 王已j l 旦l 三- t e r m i n a l n o 123466780101 1c 0 1 u 孙n o 图4 - 1 ；通道规格说明 给定一个通道及其规格说明，通道排线问题就是将在实现规格说明要求的同 时使各网络连线的水平部分不相互重叠。图4 - 2 给出了针对图i 的两个可行的解 决方案。但是，很明显图4 - 2 ( b ) 中的芯片比图4 - 2 ( a ) 中的芯片多了一条水平轨道， 这就意味着图4 - 2 ( b ) 中的芯片比图4 - 2 ( a ) 的芯片性能更优、成本更低。因此， 通道排线问题不仅仅只是提供一个可行的解决方案，而且要使芯片中的水平轨道 尽可能得最少。 日gg2iej212 ii34 56t 0 1 01 1 ( a ) 叶- 乩 2 ( b ) 图4 - 2 ： 对应图5 中通道说明的两个可行解 为了使通道排线问题从实际问题中抽象出来，我们采用了一个数学模型来描 述这一问题，即水平限制图( h o r i z o n 协ic o n s t r a m tg r a p h , h c g ) 。在水平限制图中， 每个结点与通道中相应的网络所对应。也就是说，结点i 与网络i 相对应。并且， 结点i 与结点相连，如果网络i 与网络，连线的水平部分在同一水平上重叠。 而图4 - 3 给出了对应与图1 中芯片的水平限制图。回忆上面提到的通道排线问题， 我们可以清楚地发现通道排线问题就等价与将水平限制图中的结点分割成数量 尽可能少的部分，使得每一部分中的任意两个结点互不相连。因此，我们可以通 过在水平限制图进行这样的优化工作来解决通道排线问题。 图4 3 ：对应图5 中通道说明的水平限制图 巧合的是，这种优化思想与一个经典的优化问题相似，即图着色问题( g r a p h c o l o r i n gp r o b l e m ，g c p ) 。其定义如下： 定义：给定一个图g ，图着色问题就是用尽可能少的颜色对各个结点进行着色， 使得相邻两个结点的着色不同。 由此定义，我们可以清楚的看到图着色问题实际上与通道排线问题等价。因 此，那些能够有效解决图着色问题的算法，也必定能够有效地解决通道排线问题。 4 2 2 问题求解 为了使用暂态混沌神经网络来求解图着色问题从而解决v l s i 设计中的通道 排线问题，我们对该算法进行了改造。算法的伪代码表示如下所示： c n n f o rt h eg c p i n i t i a l i z ew ，y f ( 0 ) a n d ( 0 ) t4 - - 0 d o f o ri 卜1t o n ( t ) = l ( 1 + e 一删) ，( f + 1 ) = r o y ( f ) + a l nq _ ( f ) “1 f、 = 1 f j 一z j ( f ) h ( ) 一i o ) z 。( t + 1 ) = ( 1 - p ) z , ( t ) i n c r e a s et b y1 u n t i le c o n v e r g e s 4 2 3 实验结果 我们从d i m a c s 中选取了若干实验数据来验证该算法的性能。实验结果如 表4 - 2 所示。第一栏( g r a p h ) 表示实验数据的名称；第二栏( iv1 ) 则是结点数； 第三、第四栏( h n n ) * 口( t c n n ) 分别给出了使用h o p f l e l d 神经网络以及t c n n 算法对图进行着色的最少着色数，如果用粗体显示则表示给结果与第五栏给出的 最优结果一致，而第五栏( b e s tr e s u l t ) 则提供了目前为止其他算法所得到的最 优值。 表4 - 2 ：对d i m a c s 数据进行实验的结果 b e s t g r a p h ( v , e )i v l h n nt c n n r e s u l t h u c k7 41 2l ll l m y c i e l 3 1 1 44 4 m y c i e l 4 2 3555 m y e i e l 5 4 7666 m v c i e l 6 9 5777 m v e i e l 71 9 198 8 q u e e n 5 - 5 2 5665 q u e e n 6 - 6 3 67 7 7 该表显示，t c n n 的优化结果较h o p f i e l d 神经网络要好。在8 个实验数据中 的7 个，t c n n 算法得出的结果与最优结果一致。 第5 章暂态混沌神经网络的改进 5 1 暂态混沌神经网络的速度缺陷 尽管暂态混沌神经网络能够有效地避免陷入局部最优解，然而从图3 中我们 可以看到暂态混沌神经网络在4 0 0 多次迭代后才收敛。可见该模型在收敛过程中 所花费的时间过多。因此在一些实时应用中，该模型就不是很实用了。 5 2 快速收敛混沌神经网络 为了克服t c n n 的速度缺陷，人们提出了一些新的算法，这些算法主要通 过加入新的模拟退火机制来提高运算速度 2 1 - 2 3 。而我们在此基础上通过调节 t c n n 原有的模拟退火机制提出了一种新的算法名为快速收敛混沌神经网络 ( s p e e d yc o n v e r g e n tc h a o t i cn e u r a ln e t w o r k ，s c c n n ) 。其基本结构如下。 薯( t ) = l ( 1 + e 一删5 ) m ( ) ，( r ) + a f n t + l = t o yq x 足) + 一刁( f ) ( ( f ) 一厶) m () ，( r ) + a i q x 足) + l 一刁( f ) ( ( f ) 一厶) l j = 1 f o ， ( 5 1 ) 其中， a 岛是两个常数 算法刚开始时，使用较小的声常数即届，这与t c n n 一致。然而，当逆分 岔过程结束以后，算法采用较大的常数即岛，这样就能加速收敛的速度。 图s 1 显示了当届= o 0 0 1 ，岛= 0 1 时，能量函数随时间的变化过程。我们 可以从中观察到其神经员的动态过程。 图5 - 1 ：用快速收敛混沌神经网络求解最大团问题能量函数值的演变 从这张图中，我们可以清楚地看到，s c c n n 在3 0 次迭代后就开始收敛，这 要比t c n n 快了许多。因此，s c c n n 的运算效率要高于t c n n 。 5 - 3 - 陛能分析及实验结果 我们同样从d i m a c s 中选取了若干实验数据，通过对t c n n 和s c c n n 的 运算效率和优化效果进行比较来验证该算法的性能。实验结