（通信与信息系统专业论文）混沌神经网络组合优化技术及其在路由算法中的应用.pdf

混沌神经网络组合优化技术及其 在路由算法中的应用 摘要 科学技术上面的许多问题与优化组合问题有关。在这个领域研究的目 的在于建立一种有效的方法，使之能够求出目标函数在一定约束条件下的 。 最大值和最小值。大量有趣的组合优化问题很难解决或根本无法解决，因 为它们属于一类很难的问题：n p 难度( n o n d e t e r m i n i s t i cp o l y n o m i a l ) 问 题。寻找n p 难度问题最优解所需要的计算步数是巨大的。 因此人们开始研究寻找n p 问题接近最优解的算法，其中神经网络方法 是比较成功的模型。这一模型解决了传统的数字计算方式由于串行处理面 临着的严重速度瓶颈。神经网络的主要特性在于异步并行处理、连续时间 动力学和网络单元的总体互连。自从h o p f i e l d 提出用人工神经网络 h n n ( h o p f i e l dn e u r a ln e t w o r k ) 来解决推销员问题t s p ( t r a v e ls a l e s m a n p r o b l e m ) 问题以来，h n n 成为解决许多优化组合问题的强大的工具。但h n n 仍然有一些缺点：它容易陷入局部最小值，可能收敛到不合理的点等。广 混沌系统是一种确定系统，同时可以产生看似随机的信号，由于这个 原因，使得混沌得以与神经网络结合并且成功的应用于组合优化问题，它 充分利用混沌的丰富动态特性，从局部最小值的陷阱中跳出，得到比单纯 神经网络更加准确的优化解。 i 通信网络中的很多具体问题可以通过数学建模，最终归结为组合优化 问题，例如a t m 中的路由问题就是其中的一个例子。a t m 网络被设计成能承 载各种有不同性能要求的业务类型，如话音，数据，视频等。因此a t m 中 的路由算法也应该反映各种服务请求的具体要求，在优化标准条件下做出 最优或接近最优的路由决策。而其中很多优化条件或者服务需求是互相冲 突的，必须做出折衷的安排，以达到整体性能的优化。 a t m 中的路由问题主要考虑的两个问题是网络的开销和路由有效性。网 络的开销也就是路由算法所耗赀的网络资源，根据不同的要求，可以是嘲 络_ q 4 - 矗1 。间的距离，选路表的处理时间，网络带宽等。 。 a t m 中另一个重要的问题就是网络路由的有效性。在充分利用网络资源 的情况下，经常会出现网络的瓶颈问题，也就是在某些关键的节点和链路 汇集了大多数的网络通信，导致后面的路由请求阻塞甚至失败。所以给定 网络的一种业务模式，应合理地确定信息流在网络中的分配，不仅对当前 v c ( v i r t u a lc o n n e c t ) 请求考虑使用带宽比较大的链路，同时应尽量使网络 、 带宽负荷比较均匀。彳 ， 本文主要贡献是通过分析混沌神经网络模型，针对优化组合问题作出 各种改进，将噪声加入混沌神经网络的随机噪声模拟退火方法( s c s a ) ，自 适应混沌神经网络方法。进一步通过分析模型中的自反馈连接权值对优化 性能的影响，比较了两种常用的退火方案，并提出利，新的分段指数退火 方案，使得该方法从性能和速度方面都得到了改善。 另外，本文将混沌神经网络方法应用于a t m 路由，在v p 拓扑网络中解 决v c 路由选择的问题，折中的解决网络的开销和路由有效性。完成了其它 算法很难实现的复杂路由要求。 关键词：混沌，神经网络，组合优化，网络路由算法 a p p l i c a t i o no fc h a o t l cn e u r a ln e t w o r ki n c o m b i n a t i o no p t i m l z a t i o na n d r o u t i n ga l g o r i t h m a b s t r a c t m a n y s c i e n t i f i cp r o b l e m sr e l a t e dt oc o m b i n a t i o n o p t i m i z a t i o n t h ep u r p o s e o fr e s e a r c hi nt h e s ef i e l d si st ob u i l da ne f f e c t i v ea p p r o a c ht h a tc a nc a l c u l a t et h e m a x i mo rt h en l i n i m a lr e s u l tu n d e rc e r t a i nc o n s t r a i n ag r e a td e a lo f i n t e r e s t i n g c o m b i n a t i o no p t i m i z a t i o na r eh a r do re v e nc a n tr e s o l v e da t a l l ，f o rt h e ya r e b e l o n gt oo n ek i n do fv e r yd i f f i c u l tp r o b l e m ：n p ( n o n d e t e n n i n i s t i cp o l y n o m i a l ) h a r dp r o b l e m s t h ec o m p u t e s t e p st of i n dt h ee x a c tr e s u l to ft h o s ep r o b l e m si s v a s t s op e o p l eb e g i nt ol o o kf o rt h e c l o s e l yo p t i m i z a t i o na l g o r i t h m ，a n dt h e n e u r a ln e t w o r ki sas u c c e s s f u lm o d e la m o n gt h e m i tr e s o l v e dt h ep r o b l e mo f s l o w l ys p e e dt h a tt r o u b l e dt h et r a d i t i o np a r a l l e ld i g i t a lc o m p u t e s i n c eh o p f i e l d r a i s et h en e u t r a ln e t w o r k m o d e l ( h n n ) t o s o l v et h et s p p r o b l e m ，h n nb e c o m e t h em o s t p o w e r f u lt o o lt os o l v em a n yc 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 m s b u t h n ns t i l ln o t p e r f e c t ，i tv e r ye a s yt og e ti n t ol o c a lm i n i m a la n ds o m e t i m e c o n v e r g e t oi n f e a s i b l ep o i n t h i c h a o t i cs y s t e mi sak i n do fd e t e r m i n e ds y s t e ma n da tt h es a m et i m ei tc a n p 1 1 0 d u c es o m es i g n a lw h i c hs c c i t i sr a n d o m b e c a u s eo f t h i sf e a t u r ei tc o m b i n e d w i t hn e u r a ln e t w o r ka n ds u c c e s s f u l l yu s e di nt h eo p t i m i z a t i o np l o b l e m i tc a n f u l l yu s et h er i c hd y n a m i co fc h a o sa n dg e to u tf r o ml o c a lm i n i m a lt h u sr e a c h b e t t e rr e s u l t m a n yp r a c t i c a lp r o b l e m si nc o m m u n i c a t i o nc o m ed o w nt oo p t i m i z a t i o n p r o b l e mb y b u i i tm a t h e m a t i c sm o d e ls u c ha st h er o u t i n gi na t mn e t w o r k a t m i s d e s i g n e d t o c a r r y d i f f e r e n tk i n d so fs e r v i c e st h a t r e q u i r e d d i f f e r e n t p e r f o r m a n c es u c ha sv o i c e ，d a t a ，v i d e oa n ds oo n s ot h er o u t i n ga l g o r i t h mi n a t ms h o u l dr e f l e c tt h em a t e r i a lr e q u i r e m e n to fe a c hs e r v i c e ，a n dm a k et h eb e s t r o u t i n gd e c i s i o n u n d e rt h e o p t i m i z a t i o nr e q u i r e m e n t m a n yr e q u i r e m e n t s a r e c o n f l i c ts ot r a d eo f fm u s tb e a r r a n g e dt og e tt h ew h o l eo p t i m i z a t i o n t h ep r i m a r yp r o b l e m ss h o u l db ec o n s i d e ri na t m r o u t i n g a r en e t w o r k s p e n d i n g a n dt h e v a l i d i t y t h e n e t w o r k s p e n d i n g i st h en e t w o r kr e s o u r c e r e q u i r e db yr o u t i n ga l g o r i t h m a c c o r d i n gt od i f f e r e n tr e q u i r e m e n ti tc a l lb et h e d i s t a n c eo f n o d e ，t h ep r o c e s st i m em a dt h en e t w o r kb a n d w i d t h i ft h en u m b e ro f h o p s b e t w e e nt w on o d e si ss m a l l e s t ，i t sw i l lc o n s u m em i n i m a l r e s o u r c e ，s ob u i l t v c r e q u i r e m e n t w i t hl e a s th o p sc a nu s et h en e t w o r kr e s o u r c e se f f e c t i v e l y a n o t h e ri m p o r t a n ti s s u ei na t mi sv a l i d l y u n d e rt h ec o n d i t i o nt h a tf u l l y u s e st h en e t w o r kr e s o u r c e ；t h ei s s u eo fn e t w o r kb o t t l ew i l lo f t e n a p p e a r i n a n o t h e rw o r d ，t h e r o u t i n gr e q u e s ti nt h ef u t u r em a y b eb l o c k e dw h e ns o m ek e y n o d eo rl i n kh a v et o om a n yt r a f f i c g i v e nas e r v i c ep a t t e r n ，w em u s tc a r e f u l l y r e s e r v ec e r t a i nb a n d w i d t ha v a i l a b l ef o rf u t u r eu s e s ow es h o u l dn o to n l yu s e m o s tf r e el i n kf o rc u r r e n tv c r e q u e s t ，b u ta l s ob a l a n c e t h et r a f f i ca sw ec a l l t h em o s tc o n t 】i b u t i o no ft h i sp a p e ri s t h r o u g ht h ea n a l y s i so ft h ec h a o t i c n e u r a ln e t w o r k m o d e l ，p u t t i n g f o r w a r d m a n yi m p r o v e m e n t sa c c o r d i n g t o s p e c i f i co p t i m i z a t i o np r o b l e m s i t si n c l u d i n ga d dn o i s et ot h ec h a o t i cn e u r a l n e t w o r ka n d p u tf o r w a r dt h en e wa d a p t i v ew a y f u r t h e rm o r e ，w ea n a l y z e dt h e i n f l u e n c eo fs e l ff e e d b a c kw e i g h tt ot h e o p t i m i z a t i o np e r f o r m a n c e ，c o m p a r e d t w o f i e q u e n t l yu s e da n n e a l i n gs c h e m e sa n dr a i s e d an e wk i n do fa n n e a l i n g s c h e m et h a tb o t hi m p r o v et h ep e r f o r m a n c ea n dd e c r e a s et h et i m eu s e d t h e a p p l i c a t i o no f c h a o t i cn e u r a ln e t w o r ki na t m r o u t i n ge f f i c i e n ts o l v e d t h ev c r e q u e s ti nt h ev pt o p o l o g i c a ln e t w o r k ，a n dm a d et r a d eo f fb e t w e e nt h e r e s o u r c es p e n d i n ga n d r o u t i n gv a l i d l y k e y w o r d s ：c h a o s ，n e u r a ln e t w o r k ，c o m b i n a t i o no p t i m i z a t i o n ，r o u t i n g v 街交通人学坝l + 学位论史 第一章绪论 1 1 混沌神经网络组合优化技术 1 1 1 混沌系统介绍 本世纪初的1 9 0 3 年，美国数学家jhp o i n c a r e 在科学与方法一1 翊，提出了 p o i n c a r e 猜想。他把动力学系统和拓扑学两火领域结合起来，指出了混沌存在的可能性， 从而成为世界上最先了解存在混沌可能性的人。 从6 0 年代开始，人们开始探索科学上的那些莫测之迷，使混沌科学得到了飞速的 发展。美国气象学家e l o r e n z 取得了很大的成功。他使用一台原始计算机研究气候的 变化。1 9 6 3 年，l o r e n z 在大气科学杂志上发表了“决定性的非周期流”一文，指 出在气候不能精确重演与长期天气预报者无能为力之间必然存在着一种联系，这就是非 周期性与不可预见性之问的联系。他还认为一串事件可能有一个临界点，在这一点上， 小的变化可以放大为大的变化。而混沌的意思就是这些点无处不在。这些研究清楚的描 述了“对初始条件的敏感性”这一混沌的基本性态。因此，可以说，是天气预报和气象 学的研究叩丌了混沌科学的大门。 7 0 年代，科学家们开始考虑在许许多多不同种类的不规则之间有何联系。生理学家 发现，在人类的心脏中存在着混沌现象，这其中有惊人的有序性。生态学家在探索着树 蛾群体的减少与增多的规律。经济学家研究股票价格上升下降的数据，尝试求出一种全 新的分析方法。对于事物发展的内部规律的探求，则直接把人类引向自然界云彩的 形状，雷电的径迹，血管在显微镜下所见的交叉缠绕，星星在银河中的集簇等等。7 0 年代是混沌科学发展史上光辉灿烂的年代。在这一时期，作为一门新的科学混沌学 _ i _ f 式诞生。科学家们对混沌做了大量的研究与发展。如1 9 7 5 年，中国学者李天岩和美 国数学家j y o r k e 在 | 、 图2 2 源，宿和鞍的相图示意 f i g2 2 t h e p h a s ei m a g e o f s o u r c e ，d e s t i n a t i o nm a ds a d d l e 流是考虑混沌系统时经常使用的概念，数学的流的描述为：作为一个定义于一个子 集“r 上的平滑函数厂：“一r “，产生了一个流办：“斗r ”。在这里办g ) = 妒g ，t ) 。它 定义在所有x “，任意间隔f ，q ，b ) 和任意一个连续系统上，并且满足方程： 妄吼。= 厂，) ) ，眠叫川 c z a ， 海交通人学倾 1 学位论文 流描述了系统随时问变化的总体行为。有- - t 0 ，典型的流：源、宿、鞍和吸引子。他 们山局部轨道的行为米定义。这些行为周围的的点可以是稳定和不稳定的。稳定性也可 以山后面的l y a p u n o v 指数来度量。 下面是一个混沌吸引子图( l o r e n z 系统) ： 图23l o r e n z 系统吸引子图 f i g 2 3t h ea t t r a c t o ro f l o r e n zs y s t e m 很明显，吸引子周围的轨道是受限的并且不是周期的。同时它也不是拟周期的，在 很多地方，相邻的轨道会发生分离，这种分离导致它们后面的轨道在一定时间以后变得 完全没有关系。 吸引子作为一个整体有内外两种方向，一切在吸引子之外的流都趋向它，形成所谓 稳定的效应，而一切在吸引子之内的流，则互相排斥，形成不稳定的效应。因此，奇怪 吸引予的维数必须大于零，其内部的流才有相互排斥的余地。典型的奇怪吸引子的产生 过程是：流在收缩体积元时，沿某些方向压缩，而沿其他一些方向延伸。由于保持在一 个有界区域内，因此，体积元在伸缩的同时进行折叠，折叠的结果是吸引子具有奇怪的 分形结构。同时，这种伸缩和折叠过程使轨道在奇怪吸引子上产生混沌运动。 奇怪吸引子是混沌现象中的主要角色，因为混沌现象就是指具有整体稳定性的耗散 系统中的内部的不稳定性。而混沌轨道则是在奇怪吸引子上盘旋运动的解的流，因此， 有奇怪吸引子可以被看作为混沌现象的代名词。 ，(r 1叫爿 海交通人学坝 学位论文 2 4 混沌系统主要参数 2 4 1 信号频谱 系统输出的频谱分郁决定了系统行为是否为周期性的。有限的一些尖峰对应于周期 行为。这也就是蜕没有可辨认的尖峰就表明了系统行为是非周期的。一般使用傅立叶变 换来观察系统频谱。系统频谱的有效计算通过f f 丁算法实现。 给定一个数据序列扛 = x o , _ ，一。 ，通过f f t 得到变换序列 x = 抵，爿。 。对应关系为： x = z j e “讲 ( 2 7 ) 计算功率谱时将f f t 计算的复数结果取模平方只= j x ，。 2 4 2 分形和分形维数 图2 4l o r e n z 系统输出信号频谱 分形是一个流的不稳定点。从概念上讲它是动态行为的改变点，也就是说当一个稳 定点变为两个稳定点时或者从一个宿点变为一个鞍点时。这些改变并不是由于时间的演 变导致的，而是由于系统参数的改变导致。对分形的理解有助于确定系统是否发生混沌。 分形有很多种，比如h o p f 分形，p i t c h f o r k 分形，e x p l o s i v e 分形等等。 海交通入学坝。i 学位论文 分形系统的维数也有很多种，比如拓扑维数，e u c l i d e a n 维数和分形维数。我们简单 的介绍一下分形维数的传统计算方法： 记数法计算分形维数，或称h a u s d o r f f - b e s i c o v i t c h 方法。这利叻法是用不同大小的 n 维立方体来将点集覆盖。首先用长度为上的超立方体将所有的点集覆盖，然后将l 变 为l = l 2 。n ( o 是包含点的超立方体个数。使用i , , = l 2 “并得出结采： d ：! ! g 丛g ! ! ( 2 8 ) 一* l o g ( 1 , ，) 另一个获得分形维数的方法是使用l y a p u n o v 系数： 肚+ 钶 这里被定义为满足下列条件 ，+ 】 po 并且 0 ) 或者收缩( 2 i 0 ) 的平均指数 速率。耗散系统的l y a p u n o v 指数之和是小于零的，对于混沌系统而言，至少有一个 l y a p u n o v 指数是大于零的，这正指明了系统对初值的敏感性。 考虑一个n 维连续时间动力学系统： i d z = f ( z ，f ) ( 2 1 1 ) 其中z 和f 属于n 向量域。要决定对应于初始条件z ( o ) 的n 个l y a p u n o v 指数，我 们需要找到在经过z ( o ) 轨道的无穷小空间的演变轴。也就是考虑由( 2 1 2 ) 决定的切线方 程： l ：海交通人学硕j 学位论文 d o 。z ：，韶( 2 1 2 ) 砒 这罩j 是hx ”的j a c o b i a n 矩阵，它山下式定义： 屯= 詈 这样，( 2 1 2 ) 的解就可以被得m 为 韶( r ) = m ( z o ) ，f ) 泌( o ) ( 2 13 ) ( 2 1 4 ) 这阜m ( z ( f ) ，t ) 是切线图，它的演变方程为： 丝：j m ( 2 1 5 ) a t 下面给出t h 定义计算系统n 维l y a p u n o v 指数的步骤 ，丑，屯为系统的1 1 维l y a p u n o v 指数并定义它们的顺序递减：兄。如，乃。计 算步骤如下： 首先选择n 个标准正交的向量作为( 2 1 2 ) 的初始条件。标准的选择方法为 色( 0 ) = ( 1 , 0 0 一) ；e 2 ( o ) = ( 0 ，1 0 ) 。 用数值积分方法将方程( ) 求解到时间f ，这样就得到n 个向量v ，( f ) ，v ：( r ) ，v 。( f ) 。 用g r a i n s c h m i d t 正交化方法得到n 个正交的单位向量： 讯咖赫， ，：善尘尊鹦， ( 2 1 6 ) 吃一耵i 忑碉 u 式( 2 1 1 ) 中每个等式的分母就是该方向向量的长度，用，( 1 ) ，：( 1 ) ，。( 1 ) 来表示。 在计算过程中将它们记录下来。用，( f ) 作为初始条件来解式( 2 1 6 ) ，同样用g r a m s c h m i d t 4 l 二海交通大学坝| 学位论文 正交化得到a ，( 2 0 和长度n ，( 2 ) ，n 。( 2 ) ，n ，( 2 ) 。这样进行足够次数到达时间t = r f 。 l y a p u n o v 指数的计算用下式来得到 l o g n ，( ”2 ) 1 i m 2 ( 217 ) 山予g r a m s c h m i d lj 下交化过程并不改变第一个向量的方向，这一个方向就指明在 随着时间的演变过程中增长最迅速的方向并且它的长度是以e ”为比率增长的( 当时i 剞 足够大时) 。对于其他的向量，也是按照同样的比率变化的。 下面我们用三阶l o r e n z 系统作为计算示例。l o r e n z 混沌系统的系统方程为 a z o = 口 d t 以 一= z 斑 1 d z ， 础 1 ( 2 1 8 ) l o r e n z 方程是一个三阶常微分方程，系统的状态可以用四阶r u n g e - k u t t a 法来加以 求解。我们在求解l y a p u n o v 指数时使用定步长四阶r u n g e k u t t a 法求解系统状态微分方 程和下面的切线微分方程： f 鲁叫睁引 鲁= 鹏，也咆吗也 ld , n s z ? 一= & l z 2 + c 7 z 2 z 。- $ & 3 ( 2 1 9 ) 我们注意到在求解切线方程时仍然需要状态方程的求解结果，事实上当我们需要对 3 个f 交的切线初始条件求解演变方程时一共需要3 + 3 2 = 1 2 个微分方程联立求解。第一 组3 个方程求解l o r e n z 方程的状态变量，后3 组方程每一组方程求解一个初始条件下 的切线方程。 我们使用o 0 1 秒作为r u n g e k u t t a 法的计算步长，f 取为1 秒。( 初值： z z 女 ， ， 准 睁 矿 河交通人学坝1 学位论立 z 。= 0 0 ，z 2 = 1 ，0 ，：3 = 0 0 ；系统参数：仃= 1 0 0 ，p = 2 80 ，= 8 3 ) 在1 0 0 0 0 秒区问内讨 算结果如下： l y a p u n o v 指数：0 9 0 4 0 2 2 9 0 0 0 0 3 6 2 3 3 5 01 4 5 7 0 9 5 计算结果和其他文献8 1 中基本一致。 下面我们再用四阶r o e s s l e r 系统作为计算示例。r o e s s l e r 混沌系统的系统方程为 出1 加 出 加 出3 m 2 z 】+ a z 2 + z 4 鲁一。砌， ( 2 2 0 ) 我们在求解r o e s s l e r 方程l y a p u n o v 指数时使用定步长四阶r u n g e k u t t a 法求解系统 状态微分方程和下面的切线微分方程： f 鲁= _ ( 叫蚴 j 鲁咆m ：峨 l 鲁瑚断”v 屯 。等瑙。啦， 初值：z 】= 一2 0 0 ，z 2 = 0 0 ，z 3 = 0 0 ，z 4 = 1 5 0 系统参数：n = o 2 5 ，b = 3 0 ，c = 0 0 5 ，d = o 5 ( 2 2 1 ) 得出结果l y a p u n o v 指数为：0 1 1 1 5 5 6 0 0 2 1 3 8 0 10 0 0 0 1 0 2 5 5 2 3 1 1 2 7 6 6 ，计算结果正确。 2 5 典型混沌系统 混沌理论产生后，从八十年代初期开始人们就开始寻找混沌的应用领域。混沌的类 6 海交通人学埘上学位论文 噪声特性已经被用来产生随机数。用混沌电路就可以产生比世界上最强大的计算机更快 地产生随机数i 们。这样的设备对于保密通信而苦将是很有前景的用来数据加密的随机数 产生器。混沌电路还是用来测试信号接收器的噪声源。这种t 噪声发生器在测试系统抗干 扰性能时也是一种有用的工具。混沌还被用来增加激光的功率，在化学反应中控制振荡 以及稳定不健康动物心脏的节拍。混沌用来压缩图象的研究也受到很多注意。 最典型直观的混沌现象是一股上升烟雾中的絮乱、调和各种颜色时的混合过程以及 轮船和飞机机翼后面的旋涡。在工程领域混沌系统包括： 流体问题 化学反应 弯曲弹性结构的振动 有缝隙或者间隙的机械结构 有滑动摩擦的系统 非线性声学系统 有二极管或者p n 晶体管元件的受激电路 受谐波激励的带有非线性电容或者电感元件的电路 反馈控制设备 非线性光学系统的激光 失同步的通信系统也会表现出混沌现象。神经网络在特定的情况下也会发生混沌。 在冰霜形成时的随机现象以及心跳间的间隔变动也被发现是混沌的。 对于电路混沌系统而言，e n d o ，c h u a 和l e z e k i e l 使用了一个缩相回路( p l l ) ； n e w c o m b 用带r c 反馈的o p ，a m p s 都实现了混沌。在众多的系统中，l o g i s t i c 映射以及 蔡氏电路被研究的最多。下面就讨论这两个混沌系统。本文主要考虑的细胞神经网络混 沌系统将在下一章介绍。 2 5 1 l o g i s t i c 映射 作为最简单的混沌动力学系统，l o g i s t i c 映射是利，群成长模型的一个特殊情况。 海交通人学坝j 学位论文 l o g i s t i c 映射由l o g i s t i c 等式定义 ( 2 2 2 ) 这哩旯是一个正的参数。，( x ) 为从区间 0 ，1 映射到 0 ，1 的函数 ， 0 ，1 寸【0 ，1 ( 2 2 3 ) l o g i s t i c 映射是一个迭代的l o g i s t i c 等式： ( 2 2 4 ) 系统n 次迭代表示为厂”。初值x 0 经过n 次迭代变为x n = ”0 。) 从而决定了系统 的发展。在这里我们显然可以限定l o g i s t i c 映射的耿值范围在【o ，1 内。参数丑决定了 l o g i s t i c 映射的稳定点、周期规律和混沌行为。显然稳定点托必须满足= b e ) 。p 点 集托1 ，。8 2 ，x e 3 ，。印组成周期为p 的轨道必须满足工印2 厂p g 印) 。实际上稳定点就 是周期为1 的轨道。稳定和不稳定取决于当初始条件接近稳定点或者周期点时映射将它 们趋近或者分离。对于l o g i s t i c 映射而言，系统行为为稳定点、p 周期或者混沌的一种。 这耿决于丑的取值。 在丑 3 时l o g i s t i c 映射将趋近于稳定点。在3 口 - 厂( 工) = ox z ( 0 1 2 e s e 其中届、屈为常数，届 岛 可以得出 z ( n ) = z ( 0 ) ( 1 一屈) ( 1 一：) ” m l o g 】一且0 5 ( 4 2 1 ) f 4 2 2 ) 海交通人学硕1 j 学位论文 丌始时z 值大，可能接受较差的恶化解，随着z 值的减小，只能接受较好的恶化解， 最后在z 值趋于零时，就不再接受任何恶化解了。因此，在z ，大于z i ( 0 ) 2 时，我们采 用相对比较小的指数衰减，充分利用混沌的动态特性进行搜索，使算法可以从局部最优 的“陷井”t 跳出，更有可能求得组合优化问题的整体最优解。为了克服其带来的速度问 题，在收敛阶段采用比较大的指数衰减，减小收敛时m 。状态演变图4 9 可以看出。为 了验证各种退火策略的性能，下节我们仍然通过1 0 城市的t s p 问题进行模拟。 图4 7 分段指数退火函数和单细胞t c n n 状态演变 f i g 4 7t h ee v o l v eo f s i n g l e c e l lt c n ns t a t e sw i t hs u b s e c t i o ne x p o n e n t a n n e a l i n g 4 3 3 各种退火策略的仿真比较 我们用1 0 座城市的t s p 作模拟仿真，归一化坐标如下表格 j ：海交通大学坝i 学位论义 表4 3 城市归一化坐标 xyxyxy 0 o o l 2 5 l 0 5 6 3 5 8 5 0 3 5 0 2 9 10 8 9 5 9 6 2o 7 1 0 5 0 1o 5 1 3 5 3 5 0 1 9 3 3 0 40 8 0 8 7 4 00 8 2 2 8 4 00 7 4 6 6 0 50 3 0 3 9 9 5o 0 1 4 9 8 5 0 5 8 5 0 0 90 4 7 9 8 7 3o 1 7 4 1 0 80 8 5 8 9 4 30 0 9 1 t 0 30 3 6 4 4 5 2 0 j 4 7 3 1 3 o 1 6 5 8 9 9 分别用线性退火，指数退火以及分段退火，采用相同的初始值，进行1 0 0 0 次计算 表4 4l o 城市t s p 计算结果 t a b4 4t h er e s u l t so f t s pw i t h1 0c i t i e s 退火策略最优值个数 循环步数 b = 0 o j 5】0 0 01 2 9 指数退火 b = 0 0 39 4 08 l z = z - 0 0 0 0 59 8 71 7 9 线性退火 z = z - 0 0 0 19 0 49 6 屈= 0 0 0 0 1 5 分段退火1 0 0 08 5 屈5 0 0 0 0 5 从表中可以看出，和前面的分析一致，指数退火函数性能优于线性退火函数，在分 段退火函数中分别取反= o 0 0 5 ，：= o 0 0 1 5 ，因此在搜索阶段具有比较慢的衰减速度，而 在收敛阶段具有相对快的衰减速度，从表4 4 中可以看出，分段指数退火函数具有比指 数退火函数更好的准确性和更快的速度，可以平均提高1 0