傅立叶混沌神经网络模型中的模拟退火策略

傅立叶混沌神经网络模型中的模拟退火策略 徐耀群，秦峰 哈尔滨商业大学系统工程研究所 哈尔滨 150028 哈尔滨商业大学计算机与信息工程学院,黑龙江哈尔滨 150028 (E-mail: ) 摘要：本文分析了傅立叶混沌神经网络模型的动力学特性对自反馈连接权值的敏感性,研究了退火函数对优化过程中的准确性和 计算速度的影响。并利用暂态混沌神经网络退火过程分段的思想对傅立叶混沌神经网络模型进行改进, 提出了一种具有随机性和确定 性并存的优化算法，在保证优化算法准确性的基础上,加快收敛速度,并利用对经典旅行商( TSP) 的研究,表明算法具有很强的克服陷 入局部极小能力,较大程度提高了优化、时间和对初值的鲁棒性能, 验证了这种优化策略的有效性，同时给出了模型参数对性能影响 的一些结论. 关键词： 傅立叶混沌神经网络；模拟退火；TSP Fourier chaotic neural network model of simulated annealing strategy Yaoqun Xu, Feng Qin Institute of System Engineering, Harbin University of Commerce, Harbin, 150028 School of computer and Information Engineering, Harbin University of Commerce, Harbin, 150028 (E-mail: ) Abstract: Fourier analysis of the chaotic neural network model of the dynamics of the feedback since the value of the sensitivity of the right to connect to study the function of the annealing process of optimizing the accuracy and speed of impact. And using transient chaotic neural network of sub-annealing process of thinking of the Fourier chaotic neural network model to improve, a co-exist with uncertainty and randomness of the optimization algorithm, to ensure accuracy of optimization algorithm, on the basis of speeding up Convergence rate, and using the classic traveling salesman (TSP) study showed that the algorithm is very strong capacity to overcome a local minimum, the greater the increase optimization, time and the initial value of robust performance, the certification of this optimization The effectiveness of strategies, given the model parameters on the performance of some of the conclusions. Keywords：Fourier chaotic neural network；Simulated Annealing ；TSP 0 引 言 在过去几年里，Hopfield 神经网络已经被证明是解决组合优化问题的有效工具，但是由于其利用梯度下降的 动 力学,因此这种网络在求解许多实际优化问题时所遇到的最大困难是极易陷入局部极小点 1。为了解决这一问题, 人们将混沌动力学的全局搜索特性引入神经网络之中,提出了多种混沌神经网络模型,其中大多数是通过在Hopfield 网络中引入自反馈而使自身表现出暂态的混沌动力学行为以避免陷入组合优化问题的局部极小点，因此网络的动 态特性很敏感地依赖于自反馈连接权值 ， 类似于随机模拟退火中的温度 , 其一般按指数退火函数动态)t(izti 变化 ,对网络的优化性能和收敛速度有很大的影响。有许多学者针对这一问题，提出了改进方法。例如：修等 2通 过指数递减的自反馈提出了激励函数由Sigmoid和Gauss函数组合的线性自反馈混沌神经网络，费等 3通过指数递减 的自反馈提出了内外方法结合的线性混沌神经网络，Zhou等 4通过控制非线性函数中的参数提出了具有非线性自 反馈的混沌神经网络。 本文通过引入徐耀群,孙明等提出的一种傅立叶混沌神经元模型，该混沌神经元模型的激励函数由Sigmoid函数 和三角函数加和组成，并利用一种改进的变指数退火函数 ,提出对自反馈权值 的一种新优化策略 ,既充分利)t(iz 2 用混沌的动态特性进行搜索 ,又克服其带来的速度问题 ,减少收敛时间。仿真分析与验证表明，本模型能够有效减 少网络运算的迭代步数，提高了网络的搜索效率，显示出更为优良的性能。 1 傅立叶暂态混沌神经网络 通过把以往的单调递增的Sigmoid激励函数转换成非单调的激励函数，利用自反馈项引入混沌特性，提出了一 种傅立叶混沌神经元模型，基于该模型构造如下傅立叶暂态混沌神经网络： (1)t()t(iiyfx (2)t()t()t(1t( 01 IxzIxwky iii nijjii (3)）tti zz (4)(S)(21uuf (5)/exp/S0 (6)sin(cos212 式中 ， 和 为第 i个神经元的输出 ,内部状态和输入偏置， ; （ 0）为自反馈)t(ixtiyiI n,32,1i)t(izti 连接项； (0 1 ) 为时变参量 zi ( t) 的衰减因子； 为从神经元 到神经元 的连接权值； 、 和jiwj 01 是激励函数的陡度参数； （ ）为神经隔膜的阻尼因子； 为不应度参数； 为一正参数； 、2k00I 是三角函数前的系数。随着时间变化 ,当自反馈连接权 以指数方式 (即 : )趋 )t(iztii eztz( 于零时 , 此网络逐渐退化为一个Hopfield神经网络。故此网络用来求解非线性优化问题的过程可分为两个阶段 ： 混 沌搜索阶段和梯度收敛阶段。在第一个阶段 ,由自反馈项来产生一个混沌过程以避免陷入网络的局部最小问题。第 一阶段结束后 ,可以为第二阶段提供一个全局最优解附近的初始值。可见如何控制第一阶段产生的混沌搜索过程 , 是利用混沌神经网络解决非线性优化问题的关键。所以 的演变策略对优化的性能和时间有很大的影响。)t(iz 2 模拟退火策略的优化算法 为了更好的理解上述网络模型的运行机理 , 以单个神经元为例来检验该网络的动力学行为： (7)t()t(yfx (8)1t( 0Ixzky (9)1 (10)(S)2uuf (11)/ep)(S01 (12)sin(cos(212 下面分析该模型的混沌特性： 选取适当的参数，能使神经元表现出暂态混沌行为。下面通过神经元的倒分岔图和最大 Lyapunov 指数时间演 化图来分析该模型的动力学特性。 取 =0.02， =2， =2， =1/3， =1/3， =0.283， =0.4， =1， =0.65，则 =0.002 的倒分01212)(y)(zk0I 岔图和最大 Lyapunov 指数时间演化图如图 14 所示。 3 0 200 400 600 800 10000 0.5 1 1.5 图 1： 取 0.002 的倒分叉图 0 200 400 600-1 -0.5 0 0.5 图 2 ： 取 0.002 的最大 Lyapunov 指数谱图 下面通过改变网络参数而保持其余参数不变来研究其对网络混沌动态行为的影响。图3和图4是网络参数 取 0. 004时的网络输出 x ( t) ,自反馈连接权 z ( t) 的时间演化图。 0 200 400 600 800 10000 0.5 1 1.5 图 3： 取 0.004 的倒分叉图 4 0 100 200 300-0.6 -0.4 -0.2 0 0.2 0.4 图 4 ： 取 0.004 的最大 Lyapunov 指数谱图 从图3和图4可以看出 ,随着参数的增大 ,网络输出 x ( t) 的混沌动态消失得更快 ;而且因为自反馈连接权 以指数方式 (即 : 衰减 ,所以其趋于0的收敛速度也随着参数的增大而加快了。)t(iztii eztz)( 由上面倒分叉图和最大Lyapunov指数谱图分析可知：网络的混沌动态特性很敏感地依赖于自反馈连接权值 , 的下降速度直接影响到判断优化算法的两个重要指标 :准确性和速度。在该傅立叶暂态混沌神经网)t(iti 络模型中，随着自反馈连接项 的减小， 对网络的影响越来越小，网络逐渐趋于稳定的平衡点，这个过渡过程iziz 表现在网络的单神经元就是一个倒分岔的过程。在前半段表现出混沌现象，当 下降到某一程度时，混沌消失，iz 转为收敛阶段。当 下降速度很快时，将通过短暂的搜索阶段直接进入收敛过程，因此算法的速度很快，但因为iz 没有充分利用混沌的丰富动态特征，容易陷入局部最小值，准确性大大降低；相反地 , 如果 变化小 ,可以提)t(iz 高准确性而牺牲了优化速度。 通过研究大量利用混沌神经网络进行函数优化的文献 3、 4,发现其虽然都能得到全局最优解 , 但收敛速 度太慢。究其原因主要有两个 : 1) 在整个优化过程中只采用单一的参数 ,使得 的动态特性变化过于单一 ,)t(iz 造成网络退火策略无法同时满足准确性和速度两方面的要求 ; 2) 当网络的输出趋于稳态后 ,即得到了一个全局最 优解附近的值 ,其自反馈项 还是存在较小的数值 ,每次叠代对网络第二阶段的梯度收敛过程有扰)t(0Ixz 动 , 使得网络不得不用较长的时间来收敛到全局最优解。下面针对以上情况提出一个对自反馈项的优化策略 : 文献 5针对 的动态特性变化过于单一的问题 ,采用分段指数退火函数 (13) 来代替原网络模型中的式 (3) :)t(i (13) 2/)0()(),()1( ),()(12)1( iiii ztztzotherstzitz 式中1 ,2 为常数 ,1 2。 开始时 的值较大 ,而参数值较小可以充分利用混沌的丰富动态特征 ,使得网络输出值能在大范围内进行遍)t(iz 历搜索 ,使算法可以从局部最优值中跳出 , 而得到全局最优解 ;随着 值的减小 ,网络输出逐渐收敛于分岔点 , )t(iz 所以可以采用比较大的指数衰减 ,减小收敛时间。通过以上分析，如果在傅立叶混沌神经网络模型中加入分段指数 退火函数，在 时，采用相对比较小的指数衰减，充分利用混沌的动态特性进行搜10)0(33其 中iiz 索，使网络可以跳出局部最优的陷阱，将更有可能求得组合优化问题的整体最优解；在收敛阶段采用比较大的指 数衰减，克服小指数衰减带来的速度问题，减小收敛时间 11。所以基于此提出了基于分段指数退火的傅立叶暂态 混沌混沌神经网络。 3 分段指数退火傅立叶混沌神经网络 基于以上分析在此提出了基于分段指数退火的傅立叶暂态混沌混沌神经网络模型： 5 (14)t()t(iiyfx (15)t()t()t(1t( 01 IxzIwkyiii nijjii (16)其 他)( 1)t(2 33tzz (17)(S21uuf (18)/expS01 (19)sin()cos()( 212 在上述网络模型中 、 是分段模拟退火参数，且 ； 是分段参数， ，其余参数与上面12 2313 相同。混沌神经网络模型的动态特性很敏感的依赖于 、 和 的取值。 为网络记忆保留或遗忘内部状态的ktizk 能力；自反馈连接项 是动态减小的，类似于随机模拟退火中的温度，退火速度依赖于 、 和 的大小。)t(iz 123 当 =0 时，退火速度依赖于 ，当 =1 时，退火速度依赖于 ，在这两种情况下网络相当于仅有一个退火参3132 数。只有当 时，网络才是分段网络，其退火速度才依赖于 、 ， 最终使网络收敛到一个平衡03 12)t(iz 点； 也具有很重要的作用，它代表着能量函数对动态特性的影响；在解决组合优化问题的时，它们的搭配必须 适合，如果 太大，则能量函数的影响太强，以至于无法得到暂态混沌现象；如果 太小，能量函数的影响太弱， 将无法收敛到最优解。 通过其神经元模型分析其动力学特性： 取 =0.02， =2， =2， =1/3， =1/3， =0.283， =0.4， =1， =0.65， =0.002， =0.004 和01212)1(y)(zk0I12 =0.6 的倒分岔图和最大 Lyapunov 指数时间演化图如图 56 所示。3 0 200 400 600 800 10000 0.5 1 1.5 图 5 取 0.002 的倒分叉图1 6 0 100 200 300 400 500-1 -0.5 0 0.5 图 6 取 0.004 的最大 Lyapunov 指数谱图2 由于 =0.0020.004，所以图 5 与图 3、图 6 与图 4 相比较，分段傅立叶混沌神经元因为比傅立叶混沌神经1 元晚进入了收敛阶段；由于 =0.0040.002，所以图 5 与图 1、图 6 与图 2 相比较，分段傅立叶混沌神经元因为2 比傅立叶混沌神经元早进入了收敛阶段。所以分段傅立叶混沌神经网络的混沌搜索能力是介于傅立叶混沌神经网 络分别在 = 和 = 时的混沌搜素能力之间的。1 4 仿真实验结果与分析 为验证基于分段退火策略的改进傅立叶混沌神经网络模型在优化问题求解上的稳定性和普适性，针对不同的参数 取值情况下，使用该网络模型对TSP问题进行了仿真研究，同时通过与傅立叶网络模型的仿真实验结果观 察，对模型特征和性能进行了分析和对比。 在旅行商( TSP)问题中的应用 旅行商( TSP)问题是一个经典的组合优化问题，是一个 NP-困难问题，可描述为“寻找一条遍历 N 个城 市的最短路径，每个城市必须而且只能访问一次，且最后回到起始点” 对于 N 个城市的对称 TSP 问题的可能 路径有( N-1)!/2 条。 本文将分段傅立叶混沌神经网络应用于 10 城市旅行商问题。达到最短路径并满足所有限制条件的一个能量函 数可以描述如式(22) 13。在（22）中： 为神经元输出，代表第 x 个城市在第 i 次序上被访问， 为城市 x、yxiV xyd 之间的距离。由于行列式的对称性，系数 A=B，一个全局最小的 值代表一条最短的有效路径。此时，分段傅立E 叶混沌神经网络模型(15)可以描述为(23)式。 本文采用以下经典归一化后的 10 城市坐标： (0.4, 0.4439); ( 0.2439, 0.1463); ( 0.1707, 0.2293); ( 0.2293, 0.716); ( 0.5171,0.9414); ( 0.8732, 0.6536); ( 0.6878, 0.5219); ( 0.8488, 0.3609); ( 0.6683, 0.2536); ( 0.6195, 0.2634). 该 10 城市最短路径为 2.6776，见图 7。 (20)4221641211 3/.), xxxxf 5i (21)1.0).()5.0(.)07 2122 (22) nx ni nxyi iyxxiixi VdDVBVAE1 1 1,22()( (23)t()()tt( 01,11 IzVdky iinyinyinjxjii 7 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.90.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 x y 图 7 10 城市 TSP 问题的最优 本文研究同一 下，不同的参数 和 的分段指数退火思想对求解 10 城市 TSP 的影响。 越接近 1，分段123 3 傅立叶混沌神经网络的退火速度越依赖于 ，当 =1 时，退火速度仅依赖于 ； 越接近 0，分段傅立叶混沌23 神经网络的退火速度越依赖于 ，当 =0 时，退火速度仅依赖于 。1 1 取 =0.01， =0.01， =20， =20， =1/30， =1， =0.6， =0.1， =0.2，A=1.5，t=0.04， 1220k)(z0I D=2， =0.0008。 下表是在不同参数 和 时 2000 次随机分配初始值的仿真试验数据。3 2 合法 路径 最优 路径 合法 比 最优比 平均迭 代次数 0 2000 1998 100% 99.9% 1441 0.001 2000 1996 100% 99.8% 1432 0.003 2000 1998 100% 99.9% 13630.4 0.005 2000 1998 100% 99.9% 1339 0.001 2000 1998 100% 99.9% 1401 0.003 2000 1997 100% 99.85% 12320.5 0.005 2000 1996 100% 99.8% 1185 0.001 2000 1998 100% 99.9% 1356 0.003 2000 1999 100% 99.95% 11010.6 0.005 2000 1997 100% 99.85% 1030 0.001 2000 1999 100% 99.95% 1314 0.003 2000 1998 100% 99.9% 954.250.7 0.005 2000 2000 100% 100% 865.12 0.001 2000 1998 100% 99.9% 1269 0.003 2000 1998 100% 99.9% 798.380.8 0.005 2000 1998 100% 99.9% 689.39 0.001 2000 2000 100% 100% 1220 0.003 2000 1998 100% 99.9% 633.160.9 0.005 2000 1998 100% 99.9% 507.97 不同参数 和 下仿真结果23 通过上表仿真数据分析： 1）当 =0 时，该分段傅立叶混沌神经网络只有一个模拟退火参数 ，此时只是一个普通的傅立叶混沌神经3 1 网络。因此可通过该行与其他行的比较来分析分段指数退火的傅立叶混沌神经网络的优越性。 2）通过上表中第一行与其余各行的平均迭代次数进行比较分析，可以看出基于分段指数退火的傅立叶混沌神 8 经网络的平均迭代次数比普通傅立叶混沌神经网络的平均迭代次数都有着不同程度的减小，这说明了分段指数退 火思想对网络的收敛速度确实有所提高。 3）下面详细分析了参数所起的重要作用：通过上表可以看出其收敛速度的提高程度依据参数 和 的不同23 而有所差异。例如：当 =0.4 时，平均迭代次数减少的就很有限。所以要想使分段指数退火的傅立叶混沌神经网3 络达到高的收敛速度，则 就不能取得太小；只有当 0.5 时，才会达到较好的收敛效果。 越大，此时分段3 3 傅立叶混沌神经网络的收敛速度越依赖于 ，因为 ，所以此时，网络的收敛速度越快。221 通过对比参数分析：当 =0.4， =0.005 时，分段指数退火的傅立叶混沌神经网络的收敛速度与普通傅立叶3 混沌神经网络的收敛速度几乎没有多少提高。当 =0.8， =0.005 时，分段指数退火傅立叶混沌神经网络的收敛3 速度比普通傅立叶混沌神经网络的收敛速度提高一倍以上。 4）总的来说，当 和 在一定的范围内差距比较大的时候，同时 既不是很大又不是很小的时候，网络在12 3 收敛速度方面的提高比较明显，同时网络的求解精度几乎没有受到影响；这也说明了参数的适当选取对于实际应 用问题起着重要的作用。 5 结论 本文重点研究了傅立叶混沌神经网络中的模拟退火参数对求解 10 城市旅行商问题的影响，并将分段指数退火 函数的思想引入到傅立叶混沌神经网络，提出了一种有效的分段指数退火傅立叶暂态混沌神经网络模型，并将其 应用于解决 TSP 问题，与原傅立叶混沌神经网络相比寻优能力较好，网络收敛速度有了较大的提高，并且具有较 高的非线性度。结果显示，分段指数退火的傅立叶混沌神经网络能够充分利用混沌动态特性进行搜索，能够跳出 局部最优的陷阱，又能够加快收敛速度，减少收敛时间。纵观全文，本文提出的基于分段指数退火函数的傅立叶 混沌神经网络模型是一种很有潜力的傅立叶混沌神经网络模型。因此，分段傅立叶混沌神经网络有待进一步深入 研究，其应用领域有待拓展，以充分发挥模型优势解决实际问题。 1 CHEN L , A IHARA K. Chaotic simulated annealing by a neural network model with transient chaos J . Neura