混沌边缘在组合优化中的应用外文翻译资料

英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

混沌边缘在组合优化中的应用lowast;

科学、工程以及现实生活中的许多问题都与组合优化有关。然而，许多组合优化问题属于NP-hard问题，其全局最优解通常难以求解。因此，寻找组合优化问题的全局最优解或近似最优解的算法受到了广泛的关注。作为一个典型的组合优化问题，旅行商问题(TSP)经常被作为新方法的试金石。人们已经发现自然系统中存在该现象，特别是大脑神经系统，在有序和无序之间的关键区域工作，即混沌的边缘。本文提出了一种基于混沌边缘神经网络(ECNN)的组合优化算法。然后将该算法应用于10个城市、21个城市、48个城市和70个城市的tsp。结果表明，ECNN算法具有较强使网络远离局部极小值的能力。与瞬态混沌神经网络(TCNN)算法、随机混沌神经网络(SCNN)算法和其他优化算法相比，ECNN算法获得的全局最优解和近最优解率相比较而言要高得多。该算法为求解组合优化问题提供了一种有效的方法。

关键词:混沌边缘，混沌神经网络，组合优化，旅行商问题

1. 介绍

任何科学、工程和现实生活中的问题，如旅行商问题(TSP)、大规模集成电路设计、蛋白质结构预测、双金属纳米粒子的结构优化、混沌系统的参数估计等，都与组合优化有关。因此，设计一种快速有效的算法来求解组合优化问题的全局最优解或近似最优解已成为人们关注的焦点。提出了多种方法，如切割平面法、分支定界法和基于Bellman最优原则的动态规划。然而，组合优化问题通常是NP-hard问题，具有不确定性多项式形式的时间复杂度。随着问题规模的增加，精确算法变得越来越无能为力。研究集中在近似算法或启发式算法，以寻求问题在有限的计算时间内的近似最优解。因此提出了许多算法，如随机模拟退化(SSA)算法、一些基于生物现象的算法和人工神经网络算法，并在不同尺度的问题上取得了一定的成果。1982年，Hopfield神经网络被提出，并成功地应用于TSP。Hopfield神经网络可以快速收敛到一个稳定的状态，但通常不是全局最优解。得到的解与初始值和参数有很大关系。研究发现，即使在10个城市的问题中，网络也常常收敛到局部最优解，而对于更大规模的问题，网络变得无能为力。另一方面，基于生物电生理实验的混沌神经网络已被证明具有遍历性，在巡航过程中可以达到全局最优解，但其混沌运动使网络在全局最优解中不稳定。因此无法得到解决办法。研究人在混沌神经网络(CNN)和模拟退火算法的基础上提出了暂态混沌神经网络(TCNN)算法，并将其应用于TSP。通过控制反馈项的衰减，使网络由混沌状态过渡到稳定状态，从而达到最优解。与SSA算法相比，TCNN算法使用混沌动力学而不是蒙特卡罗随机进行退火，这使得TCNN算法的计算时间更少，且获得全局最优的概率更高。利用TCNN可以得到中等规模TSP问题的全局最优解。然而，研究人员发现48个城市95%的TSP解都落在了局部最优解上，算法缺乏跳出这些局部最优区域的能力。

为了改进TCNN算法，在TCNN算法中加入了噪声，增强了搜索的随机性(随机混沌神经网络，SCNN)，并通过该算法改进了10个城市和21个城市的全局最优解的概率对于规模较大的问题(52个城市和70个城市)，SCNN算法的有效解的概率大于TCNN算法。然而，这两个tsp的全局最优解的概率并没有在他们的工作中给出。此外，还提出了几种基于神经网络的改进算法，如高斯小波自反馈混沌神经网络、变频正弦混沌神经网络(FCSCNN)和带滞后噪声的FCSCNN (HNFCSCNN)。这些算法在一定程度上提高了不超过30个城市的tsp的全局最优概率。然而，没有大规模问题的全局最优解的报道。研究表明，基于混沌神经网络的算法比其他算法具有更高的搜索效率。在优化初始阶段，混沌神经网络处于混沌状态。随着时间的推移，混沌神经网络逐渐退化到稳定状态，进而达到优化。然而，混沌运动的退化存在一个缺点。当混沌神经网络退化到稳定状态时，系统可能会远离全局最优解，从而导致退化的神经网络陷入局部最优状态。这样就不能得到全局最优解或近似最优解。在工作控制混乱的混沌神经网络,他等人发现,控制网络可以聚集在一个稳定的模式与初始模式,当网络运作混乱和non-chaos之间的临界区,并认为混乱的边缘(EC)在记忆过程中起着非常重要的作用。事实上，许多自然系统在有序和无序之间的临界状态下运行，如基因表达、形态发生、最佳细胞生长、细菌群落和鸟类群落。特别是神经科学中的大量理论模型和实验表明，大脑运行在有序与无序之间的临界状态，即混沌的边缘。因此，它具有较好的信息传输、信息处理、信息存储和学习能力，且相对稳定。此外，研究表明，人工神经网络在混沌边缘运行时显示出更好的计算能力。近年来，深度学习神经网络的关键特性引起了人们的广泛关注。计算机科学家发现，为了实现更快的学习和训练，减少学习过程中的信息丢失，机器只能在混乱的边缘运行。可能的原因是神经网络在临界区表现出更强的互信息，包含更多的亚稳态，神经元表现出更强的相关性。以上研究表明，神经网络在混沌边缘具有较好的操作能力和信息处理能力。到目前为止，混沌边缘神经网络在组合优化领域的应用还没有报道。TSP问题是典型的组合优化问题之一，经常被用来作为新算法的试金石。本文提出了一种基于混沌边缘的混沌神经网络的组合优化算法，并将该算法应用于10个城市到70个城市的tsp问题

2. 模型

为了改进已有的基于混沌神经网络的TSP算法，提出了一种利用混沌边缘神经网络(neural network on edge of chaos, ECNN)求解TSP的方法。在采用该算法的优化过程中，首先采用了暂态混沌神经网络。当混沌神经网络退化到稳定的神经网络,神经网络的参数调制,使神经网络陷入混乱状态接近临界区之间的混乱和非混沌又开始新一轮的退化从瞬态混沌状态到稳定状态。该开关根据需要解决的问题经过几轮退化过程后结束。这样，网络就处于混沌和非混沌之间的临界状态，即处于混沌的边缘，此时网络的搜索能力最强。因此，网络获得全局最优或接近最优解的能力得到增强。在生物电生理实验的基础上，建立了艾海拉混沌神经网络。它的混沌动力学类似于生物系统。因此，选择混沌神经网络来解决组合优化问题。混沌神经网络在混沌边缘的第i个神经元可以用以下公式来描述。

x_i是第i个神经元的输出,内部状态的第i个神经元,k是神经膜的阻尼因子,alpha;的积极的尺度参数输入,ε的陡度参数输出函数,（2）是第i个神经元的输入偏置,钱数是正的常数,z(t)为随时间变化的自反馈连接重量或耐火强度。Z₁为网络再次混沌时的自反馈系数的初值。beta;为z的阻尼因子，在每个退火过程中随机选取，增强网络的随机性，即beta; = rand (beta;_min， beta;_max)。beta;0为第一次退火过程的阻尼因子。W_{i j}是第i个神经元到第j个神经元的连接权值，满足

其中E为问题的能量函数，TSP的能量函数定义在式(7)中，sigma;E为能量函数在最近的10次迭代中的方差。方差大表示神经网络处于混沌状态，反之则表示网络处于稳定状态。sigma;E的定义如下:

其中，是最接近10次迭代的平均能量函数。在这里，我们用式(3)代替TCNN算法中的反馈项z(t 1) = z(t)(1minus;beta;)。这样，当网络变得稳定时，反馈参数z的突然变化会使系统再次混沌，从而使系统有机会逃离局部最小区域。参数z₁选择在网络运行的混沌状态和稳定状态之间的临界区域附近，即混沌边缘，此时网络具有最佳的搜索能力。TSP是一个典型的组合优化问题。它寻求一个旅行推销员访问一定数量的城市，然后返回起点的最短路径，约束条件是每个城市只访问一次。对于n个城市的TSP，构成一个ntimes;n格网结构。其神经输出X_{i j}表示访问顺序为j的城市i。满足所有约束条件的TSP的最小游览长度可以用神经网络的能量函数表示为:

其中，x_i0 = x_in, x_in 1 = x_i1, d_{i j}为i市到j市的距离，W1、W2分别为约束条件对应的耦合参数和行程长度的成本函数。方程的前两项表示约束条件(每个城市只能访问一次)，最后一项表示旅程的总长度。当能量函数取最小值时，得到满足约束条件的最短有效路径。

结合方程式，(2)、(4)、(7)可以发现，基于ECNN，一定数量城市的TSP动态可以用如下方程描述:

初始的y_{i j}是随机生成的，其值介于minus;1.0和1.0之间。一旦给定初始值，就可以通过神经网络的进化得到问题的最优解

1. ECNN在TSP中的应用

我们使用以下规格在计算机上执行模拟:Dell PowerEdge R730服务器。其CPU为E5- 2650 V4@2.20 GHz，内存为64G。程序用C语言编写，采用单线程方式，即在每次迭代中依次更新神经元的输出信号。首先，将ECNN算法应用于10个城市的TSP。城际距离的坐标数据来自Ref，问题的全局最优解如图1所示。网络参数设为k = 0.9， alpha; = 0.015, z(0) = 0.10, z1 = 0.035, I0 = 0.75， ε = 1/250, W1 = W2 = 1， beta;0 = 0.5， beta; = 0.003.

Fig. 1. 10个城市的TSP的最佳游览，游览中的每个数字代表一个城市。

Fig. 2. (a) 10城市TSP混沌神经网络中一个神经元(x11)的输出分布随参数z的变化。(b)最大Lyapunov指数。(c)参数z的演化。(d)一个神经元的输出演化(x11)。(e)能量函数的演化.

由于网络中神经元的行为相似，我们以网络中单个神经元(x11)的行为动力学为例进行分析。图2(a)显示了10个城市TSP在不同自反馈参数z下混沌神经网络中一个神经元(x11)的输出分布。图2(b)给出了根据Ref.[34]定义计算出的系统的最大Lyapunov指数。图2(a)和图2(b)分为两部分。在右侧，自反馈参数小于0.029时，系统的最大李雅普诺夫指数为负，神经元的输出信号具有一定的离散值，说明网络处于稳定状态。左边的自反馈参数大于0.029,系统的最大李雅普诺夫指数是积极的和神经元的输出信号是随机值的范围从0到1见图2 (a)的黑暗区域,这意味着网络混乱。根据图2(a)和图2(b)，可以选择参数z使系统运行在混沌边缘。图2(c) -2 (e)分别为ECNN算法中参数z的演化，对应一个神经元(x11)的输出演化以及对应的能量函数e的演化。随着反馈参数z的减小，神经元的输出逐渐收敛到一个稳定点，系统的能量逐渐收敛到一个局部最小值，网络在第一次退火过程结束时趋于稳定。对于TCNN算法和SCNN算法，仿真到此结束，得到最优解。然而，系统可能离全局最优解很远，退化的神经网络实际上陷入了一个局部最小值。对于ECNN算法，将自反馈参数调整为0.035(z1)，略大于其临界值0.029。因此，神经元的输出信号和系统的能量再次变得随机，这意味着系统在混沌和非混沌之间的临界区域附近进入混沌状态，开始新一轮的退火过程。这样，系统就成功地从先前的局部最小状态脱离出来。然后随着z的减小，系统逐渐收敛到另一种稳定状态。按照给定的终止规则，经过几轮退化过程后，切换结束。这样，网络就处于混沌和非混沌之间的临界区域，即网络处于混沌的边缘。从以上结果可以得出结论，通过调节自反馈参数z，可以控制混沌神经网络在混沌边缘运行。我们对10个城市的TSP进行了5000次模拟，初始条件为yi j，在区域[minus;1.0,1.0]内随机生成。每次模拟都经过三轮退火处理，得到最优解。结果表明，优化效率与阻尼参数beta;的大小有关。当beta;le;0.003时，所有仿真的全局最优解率可以比较，10个城市的TSP采用TCNN算法[20]和SCNN算法[21]。在SCNN仿真中，噪声幅值A[n(0)] = 0.002，噪声的阻尼因子beta;2 = 0.00005.[21]其他参数与10个城市TSP的ECNN算法相同。TCNN和SCNN算法分别进行了5000次仿真，仿真结果如表1所示。从表1可以看出，与其他算法相比，ECNN算法在优化耗时和获得全局最优解的概率方面具有优势。

然后,我们解决途径TSP,城际的坐标数据距离是来自Ref。参数设置为z1 = 0.035, = 0.5, W1 = 1.0, W2 = 1.0/980,beta;= 0.0001,beta;=兰德(0.00001,0.0003),和其他参数相同10-city TSP中我们使用。每次模拟结束前进行12轮退火处理，得到的全局最优遍历长度为2707。全局最优路径图如图3所示.

Fig. 3. 21城TSP的最佳旅游线路，旅游长度为2707。括号中的每个数字代表一个城市，其他数字代表两个城市之间的距离

对于48个城市的TSP，城际距离数据也来源于参考文献[35]。为了节省计算时间，我们对ECNN算法进行了改进。式(2)中的反馈项只添加到随机选择的m times; m (10 amp;lt;m amp; lt;35)神经元，即所选神经元的动力学由式(8)确定，其余神经元的动力学由Hopfield模型描述，该模型可由下式描述:

48个城市TSP模拟参数z1 = rand (0.027, 0.028)， I = 0.75, W1 = 1.0, W2 = 1.0/3160， beta; = 0.00005， beta; = rand(0.000005, 0.00005)。其他参数与10个城市的TSP中使用的参数相同。在模拟中，参数z1在每个退火过程中都是在0.027到0.028之间随机化的，这使得网络的随机性增加。如果超过30个退火已经完成，并且在最近的20个连续退火过程中没有改进，模拟结束。在我们的仿真中，得

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[589489]，资料为PDF文档或Word文档，PDF文档可免费转换为Word