Hopfield神经网络优化方法

TSP的几种求解方法及其优缺点一、什么是TSP问题旅行商问题，简称TSP,即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。

其图论描述为：给定图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的边集，设D=（dij ）是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。

旅行商问题可分为如下两类：1）对称旅行商问题（dij=dji , ni j=1 , 2, 3, ?, n）;2）非对称旅行商问题（dij dji, ? i, j=1 , 2, 3, ?, n）。

非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。

若对于城市V={V1, V2, V3, ?, V n}的一个访问顺序为T={t l, t2, t3, ?, t i, ?, t n}，其JT中t& V （i=1 , 2, 3, ?, n）,且记t n+1=t1，则旅行商问题的数学模型为：minL= TSP是一个典型的组合优化问题，并且是一个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准。

因此，快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。

二、主要求解方法基于TSP的问题特性，构造型算法成为最先开发的求解算法，如最近邻点、最近合并、最近插入、最远插入、最近添加、贪婪插入等。

但是，由于构造型算法优化质量较差，迄今为止已开发了许多性能较好的改进型搜索算法，主要有：1）模拟退火算法2）禁忌搜索算法3）Hopfield神经网络优化算法4）蚁群算法5）遗传算法6）混合优化策略2.1模拟退火算法方法1）编码选择：采用描述TSP解的最常用的一种策略一一路径编码。

2）SA状态产生函数的设计：对于基于路径编码的SA状态产生函数操作，可将其设计为：①互换操作（SWAP）;②逆序操作（INV ）;③插入操作（INS）。

v1.0 可编辑可修改TSP的几种求解方法及其优缺点一、什么是TSP问题旅行商问题，简称TSP，即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。

其图论描述为：给定图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的边集，设D=（dij）是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。

旅行商问题可分为如下两类：1）对称旅行商问题（dij=dji，Πi，j=1，2，3，⋯，n）；2）非对称旅行商问题（dij≠dji，ϖi，j=1，2，3，⋯，n）。

非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。

若对于城市V={v1，v2，v3，⋯，v n}的一个访问顺序为T={t1，t2，t3，⋯，t i，⋯，t n}，其中t i∈V（i=1，2，3，⋯，n），且记t n+1=t1，则旅行商问题的数学模型为：minL=。

TSP是一个典型的组合优化问题，并且是一个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准。

因此，快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。

二、主要求解方法基于TSP的问题特性，构造型算法成为最先开发的求解算法，如最近邻点、最近合并、最近插入、最远插入、最近添加、贪婪插入等。

但是，由于构造型算法优化质量较差，迄今为止已开发了许多性能较好的改进型搜索算法，主要有：1）模拟退火算法2）禁忌搜索算法3）Hopfield神经网络优化算法4）蚁群算法5）遗传算法6）混合优化策略模拟退火算法方法1）编码选择：采用描述TSP解的最常用的一种策略——路径编码。

2）SA状态产生函数的设计：对于基于路径编码的SA状态产生函数操作，可将其设计为：①互换操作（SWAP）；②逆序操作（INV）；③插入操作（INS）。

TSP的几种求解方法及其优缺点一、什么是TSP问题旅行商问题，简称TSP，即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。

其图论描述为：给定图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的边集，设D=（dij）是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。

旅行商问题可分为如下两类：1）对称旅行商问题（dij=dji，Πi，j=1，2，3，?，n）；2）非对称旅行商问题（dij≠dji，?i，j=1，2，3，?，n）。

非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。

若对于城市V={v1，v2，v3，?，v n}的一个访问顺序为T={t1，t2，t3，?，t i，?，t n}，其中t i∈V（i=1，2，3，?，n），且记t n+1=t1，则旅行商问题的数学模型为：minL=。

TSP是一个典型的组合优化问题，并且是一个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准。

因此，快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。

二、主要求解方法基于TSP的问题特性，构造型算法成为最先开发的求解算法，如最近邻点、最近合并、最近插入、最远插入、最近添加、贪婪插入等。

但是，由于构造型算法优化质量较差，迄今为止已开发了许多性能较好的改进型搜索算法，主要有：1）模拟退火算法2）禁忌搜索算法3）Hopfield神经网络优化算法4）蚁群算法5）遗传算法6）混合优化策略模拟退火算法方法1）编码选择：采用描述TSP解的最常用的一种策略——路径编码。

2）SA状态产生函数的设计：对于基于路径编码的SA状态产生函数操作，可将其设计为：①互换操作（SWAP）；②逆序操作（INV）；③插入操作（INS）。

3）SA状态接受函数的设计：min{1，exp（-△/t）}>random[0，1]准则是作为接受新状态的条件最常用的方案，其中△为新旧状态的目标值差，t为”温度”。

HopField 神经网络解决旅行商问题实验名称：用Hopfield 神经网络解决旅行商(TSP)问题实验内容：旅行商问题（TravellingSalesman Problem, 简记TSP ，亦称货郎担问题)：设有n 个城市和距离矩阵D=[dij]，其中dij 表示城市i 到城市j 的距离，i ，j=1，2 …n ，则问题是要找出遍访每个城市恰好一次的一条回路并使其路径长度为最短。

TSP 的一个解可表述为一个循环排列，假如有５个城市ABCD Ｅ顺序为如有５个城市顺序为Ｃ→A →Ｅ→Ｂ→Ｄ→Ｃ。

那么路线总长度为：D C BD EB AE CA d d d d d d ++++=TSP 问题综合了一大类组合优化问题的典型特征，属于NP 完全问题，不能在多项式时间内进行检验。

若使用动态规划的方法时间复杂性和空间复杂性都保持为n 的指数函数。

HNN 方法是解TSP 问题的另一种有效的方法，在城市数目比较小的情况下可以在较短的时间得到满意的结果。

算法分析：所用到的基本理论与方法，具体算法。

1.根据文献（1），HNN 解TSP 问题的具体步骤为：0、置t=0,A=1.5,D=1;1、读入N 城市之间的距离),,2,1,(n y x d xy =文件；2、计算神经元之间的权重和输入偏置 权重：n j i y x Dd A A T i j xy ij xy YjXi ,2,1,,,,1,,=---=-其中δδδ输入偏置： I=2A;3、)(t U xi 的初值在0附近随机产生（x,i=1,2,……，N ）;4、计算))/)(tanh(1(21)(0U t U t V xi xi +=， 这里2.00=U 5、利用神经元动态方程，计算∑∑==+=∆n y nj yj yjxi xi I V Tt u 11,)(6利用一阶尤拉法计算 ,5.0)()1()1(=∆∆⨯∆++=+t t t u t U t U xi xi xi ，这里7、如果系统达到平衡状态，那么终止程序，否则返回第4步。

基于Hopfield神经网络的异型螺旋槽管优化设计[摘要] 运用matlab神经网络工具箱中的hopfield网络优化电路, 对工业生产中的一种异型螺旋槽管优化设计模型进行了仿真优化设计, 优化计算结果表明, 基于该hopfeild网络的优化设计切实可行,为其它复杂的优化设计问题提供了新的思路和方法。

[关键词] hopfield神经网络螺旋槽管优化设计0.引言j.hopfield在1982年提出了可用作联想存储器的hopfield神经互联网络。

该网络模型是一种循环神经网络，主要应用原理为将输出网络的输出作为约束网络的输入反馈到该网络的输入端并和它的输入进行叠加来约束网络的输出，保证网络的输出最终达到稳定。

hopfiled网络在输入的激励下，会产生不断的动态变化。

如果采用的hopfield网络模型是一个能收敛的稳定网络，则这个反馈与迭代的计算过程所产生的变化会越来越小,一旦到达了稳定平衡状态,那么hopfield网络就会输出一个稳定的恒值,即所求优化问题的解。

本文中应用该hopfield神经网络对工业换热工艺设备之一的异型螺旋槽管进行了优化设计，建立数学函数模型并模拟计算，结果表明确实达到了实用可行的目的。

使设备工作在最佳状态的方法是提供换热器的效率和紧凑性，关键在于强化传热和减少流动阻力，所以如何使得强化传热技术的同时提高传热效果，而且兼顾在增加压降和泵功方面所要花费的代价，使得传热系统的综合性最优，对于传热强化技术的合力应用，有着十分重要的应用意义。

1.hopfield神经网络优化计算的基本步骤利用hopfiled神经网络进行优化计算的基本步骤为：①选择对应问题的一个合适表达方式, 使神经元的输出与问题的解彼此对应起来。

②构造神经元网络的能量函数, 使其最小值对应于问题的最优解。

③由计算能量函数求得其对应的连接权值及相应的参数；④构造相应的神经网络和电路方程；⑤进行计算机仿真求一定条件下的最优解，即为其运行的稳定状态。

实验八：基于神经网络的优化计算实验一、实验目的掌握连续Hopfield神经网络的结构和运行机制，理解连续Hopfield神经网络用于优化计算的基本原理,掌握连续Hopfield神经网络用于优化计算的一般步骤。

二、实验原理连续Hopfield神经网络的能量函数的极小化过程表示了该神经网络从初始状态到稳定状态的一个演化过程。

如果将约束优化问题的目标函数与连续Hopfield神经网络的能量函数对应起来，并把约束优化问题的解映射到连续Hopfield神经网络的一个稳定状态，那么当连续Hopfield神经网络的能量函数经演化达到最小值时，此时的连续Hopfield神经网络的稳定状态就对应于约束优化问题的最优解。

三、实验条件VC＋＋6.0。

四、实验内容1、参考求解TSP问题的连续Hopfield神经网络源代码，给出15个城市和20个城市的求解结果（包括最短路径和最佳路线），分析连续Hopfield神经网络求解不同规模TSP问题的算法性能。

2、对于同一个TSP问题（例如15个城市的TSP问题），设置不同的网络参数，分析不同参数对算法结果的影响。

3、上交源代码。

五、实验报告1、画出连续Hopfield神经网络求解TSP问题的流程图。

2、根据实验内容，给出相应结果及分析。

(1)15个城市（测试文件TSP15.TXT）tsp15.txt 最短路程 371最佳路线1914861351534712210111→→→→→→→→→→→→→→→(2)20个城市（测试文件TSP20.TXT）tsp20.txt 最短路程349最佳路线→→→→→→→→→→→→→→→→→→→→→1416189713151117351242891916102013、总结连续Hopfield神经网络和遗传算法用于TSP问题求解时的优缺点。

遗传算法易出现早熟收敛和收敛性差的缺点。

Hopfield算法对高速计算特别有效，但网络不稳定。

用Hopfield解TSP问题效果并不理想。

%% 连续Hopfield神经网络的优化—旅行商问题优化计算% function main%% 清空环境变量、定义全局变量clear allclcglobal A D%% 导入城市位置load city_location%% 计算相互城市间距离distance=dist(citys,citys');%% 初始化网络N=size(citys,1);A=200;D=100;U0=0.1;step=0.0001;delta=2*rand(N,N)-1;U=U0*log(N-1)+delta;V=(1+tansig(U/U0))/2;iter_num=10000;E=zeros(1,iter_num);%% 寻优迭代for k=1:iter_num% 动态方程计算dU=diff_u(V,distance);% 输入神经元状态更新U=U+dU*step;% 输出神经元状态更新V=(1+tansig(U/U0))/2;% 能量函数计算e=energy(V,distance);E(k)=e;end%% 判断路径有效性[rows,cols]=size(V);V1=zeros(rows,cols);[V_max,V_ind]=max(V);for j=1:colsV1(V_ind(j),j)=1;endC=sum(V1,1);R=sum(V1,2);flag=isequal(C,ones(1,N)) & isequal(R',ones(1,N));%% 结果显示% 计算初始路径长度sort_rand=randperm(N);citys_rand=citys(sort_rand,:);Length_init=dist(citys_rand(1,:),citys_rand(end,:)');for i=2:size(citys_rand,1)Length_init=Length_init+dist(citys_rand(i-1,:),citys_rand(i,:)');end% 绘制初始路径figure(1)plot([citys_rand(:,1);citys_rand(1,1)],[citys_rand(:,2);citys_rand(1,2)],'o-') for i=1:length(citys)text(citys(i,1),citys(i,2),[' ' num2str(i)])endtext(citys_rand(1,1),citys_rand(1,2),[' 起点' ])text(citys_rand(end,1),citys_rand(end,2),[' 终点' ])title(['优化前路径(长度：' num2str(Length_init) ')'])axis([0 1 0 1])grid onxlabel('城市位置横坐标')ylabel('城市位置纵坐标')% 计算最优路径长度[V1_max,V1_ind]=max(V1);citys_end=citys(V1_ind,:);Length_end=dist(citys_end(1,:),citys_end(end,:)');for i=2:size(citys_end,1)Length_end=Length_end+dist(citys_end(i-1,:),citys_end(i,:)');enddisp('最优路径矩阵');V1% 绘制最优路径figure(2)plot([citys_end(:,1);citys_end(1,1)],...[citys_end(:,2);citys_end(1,2)],'o-')for i=1:length(citys)text(citys(i,1),citys(i,2),[' ' num2str(i)])endtext(citys_end(1,1),citys_end(1,2),[' 起点' ])text(citys_end(end,1),citys_end(end,2),[' 终点' ])title(['优化后路径(长度：' num2str(Length_end) ')'])axis([0 1 0 1])grid onxlabel('城市位置横坐标')ylabel('城市位置纵坐标')% 绘制能量函数变化曲线plot(1:iter_num,E);ylim([0 2000])title(['能量函数变化曲线(最优能量：' num2str(E(end)) ')']);xlabel('迭代次数');ylabel('能量函数');elsedisp('寻优路径无效');end% %===========================================% function du=diff_u(V,d)% global A D% n=size(V,1);% sum_x=repmat(sum(V,2)-1,1,n);% sum_i=repmat(sum(V,1)-1,n,1);% V_temp=V(:,2:n);% V_temp=[V_temp V(:,1)];% sum_d=d*V_temp;% du=-A*sum_x-A*sum_i-D*sum_d;% %==========================================% function E=energy(V,d)% global A D% n=size(V,1);% sum_x=sumsqr(sum(V,2)-1);% sum_i=sumsqr(sum(V,1)-1);% V_temp=V(:,2:n);% V_temp=[V_temp V(:,1)];% sum_d=d*V_temp;% sum_d=sum(sum(V.*sum_d));% E=0.5*(A*sum_x+A*sum_i+D*sum_d);% % % % 计算dufunction du=diff_u(V,d)global A Dn=size(V,1);sum_x=repmat(sum(V,2)-1,1,n);sum_i=repmat(sum(V,1)-1,n,1);V_temp=V(:,2:n);V_temp=[V_temp V(:,1)];sum_d=d*V_temp;du=-A*sum_x-A*sum_i-D*sum_d;% % % % % 计算能量函数function E=energy(V,d)global A Dn=size(V,1);sum_x=sumsqr(sum(V,2)-1);sum_i=sumsqr(sum(V,1)-1);V_temp=V(:,2:n);V_temp=[V_temp V(:,1)];sum_d=d*V_temp;sum_d=sum(sum(V.*sum_d));E=0.5*(A*sum_x+A*sum_i+D*sum_d);。

实验六基于神经网络的优化计算实验一、实验目的掌握连续Hopfield神经网络的结构和运行机制，理解连续Hopfield神经网络用于优化计算的基本原理,掌握连续Hopfield神经网络用于优化计算的一般步骤。

二、实验原理连续Hopfield神经网络的能量函数的极小化过程表示了该神经网络从初始状态到稳定状态的一个演化过程。

如果将约束优化问题的目标函数与连续Hopfield神经网络的能量函数对应起来，并把约束优化问题的解映射到连续Hopfield神经网络的一个稳定状态，那么当连续Hopfield神经网络的能量函数经演化达到最小值时，此时的连续Hopfield神经网络的稳定状态就对应于约束优化问题的最优解。

实验报告1、画出连续Hopfield神经网络求解TSP问题的流程图。

2、根据实验内容，给出相应结果及分析。

(1)、参考求解TSP问题的连续Hopfield神经网络源代码（设置参数A=15,B=15,D=0.015, u0=0.02,h=0.5，r= cityNumber*10），给出15个城市和20个城市的求解结果（包括最短路径和最佳路线），分析连续Hopfield神经网络求解不同规模TSP问题的算法性能。

1）int main(int argc,char *argv[])：修改路径计算的代码2）最后要求输出：TSP4(2)、对于同一个TSP问题（例如15个城市的TSP问题），设置不同的网络参数（A=50,B=50,D=0.01,C=50，u0=0.02, h=0.5，r=cityNumber*100；A=0.5, B=0.5, D=0.5, C=0.2，u0=0.02,h=0.5,r=cityNumber*100；A=500,B=500,D=500,C=200，u0=0.02,h=0.5, r=cityNumber*100;A=5, B=5, D=0.01, C=5，u0=0.02,h=0.5, r=cityNumber*100），分析不同参数对算法结果的影响。