论文部分内容阅读
摘 要：文章介绍了运用神经网络线性优化的思想和方法对一类线性优化方面的问题进行了分析，得到了应用神经网络算法求解该类问题的具体步骤和算法方案，并给出了实例进行验证，证明了神经网络线性优化算法是有效的，具有理论意义和实用价值。
关键词：神经网络算法;MTLAB;线性优化
人工神经网络（Artificial Neural Networks， ANN），亦称为神经网络（Neural Networks，NN），是由大量的处理单元（神经元Neurons）广泛互联而成的网络，是对大脑的抽象、简化和模拟，反映人脑的基本特性.人工神经网络的研究是从人脑的生理结构出发来研究人的智能行为，模拟人脑信息处理的功能.它是根植于神经科学、数学、物理学、计算机科学及工程等科学的一种技术。
一、神经网络线性优化方法求解TSP
旅行商问题（Traveling Saleman Problem，简称TSP，亦称货郎担问题）或者邮递员路径问题：有n个城市，其相互间的距离，或者旅行成本为已知，求合理的路线使每个城市都访问一次，且总路径为最短（或者总成本最小）.该问题可表示为
设有N个城市
[C={C1，C2，…，CN}]
给定C中任意两个城市间的距离
[d（Ci，Cj）=dij 1≤i，j≤N]
现在要找出一个城市的排列
[{Cn（1），Cn（2），…，Cn（N）}]
使得闭合路径
[i=1Nd[Cn（i），Cn（i+1）mod N]]
为最小.
从表面看，TSP很简单，其实则不然.对于N个城市的TSP，存在可能的路径数为[（N-1）！/2]条，当N较大时，其数量将是惊人的.计算每一条路径都需要求出N个距离之和，这样各种路径及其距离之和的计算量将正比于[N！/2]，.表3-1给出了用运算速度为1GFLOPS次的CrayⅡ计算机搜索TSP所需的时间.这里还不计算所需的巨大存储空间.从而可见用搜索法求解规模大的TSP是不现实的。
表3-1 TSP的计算量
[城市数N＼&7＼&15＼&20＼&50＼&100＼&200＼&加法量＼&[2.5×103]＼&[6.5×1011]＼&[1.2×1018]＼&[1.5×1064]＼&[5×10157]＼&[10374]＼&搜索时间＼&[2.5×10-5s]＼&[1.8h]＼&[350y]＼&[5×1048y]＼&[10142y]＼&[10358y]＼&]
1985年Hopfield和Tank用神经网络求解[N=30]的TSP，使用900个神经元组成的网络在[0.2s]内找到一个有效解（在[1030]个可能的解中排除[1023]个非最优解），从而开创了神经网络用于优化计算的新途径.其基本思想是：将TSP映射到一个神经网络上，通过网络的动力学方程自动演化到网络的平衡态，自动搜索到局部最优解.
对于TSP，一条访问路径可以用一个换位矩阵表示.以5个城市为例，如表3-2所示换位矩阵表示访问5个城市的路径顺序为[C3→C1→C5→C2→C4→C3]，其路径总长度为
[l=d31+d15+d52+d24+d43]
表3-2用换位矩阵表示访问次序
[＼&1＼&2＼&3＼&4＼&5＼&[C1]＼&0＼&1＼&0＼&0＼&0＼&[C2]＼&0＼&0＼&0＼&1＼&0＼&[C3]＼&1＼&0＼&0＼&0＼&0＼&[C4]＼&0＼&0＼&0＼&0＼&1＼&[C5]＼&0＼&0＼&1＼&0＼&0＼&]
如果下标[x]，[y]表示城市，[i]表示第[i]次访问，则路径长度可以表示为下列一般形式
[l=12xy≠xidxyvxivy，i+1+12xy≠xidxyvxivy，i-1]
[=12xy≠xidxyvxi（vy，i+1+vy，i-1）]
式中，[dxy]表示城市[x]，[y]之间的距离;[vxi]表示换位矩阵中的第[x]行第[i]列的元素，其值为1时表示第[i]步访问城市[x]，其值为0表示第[i]步不访问城市[x].
在表3-2中，各行各列只能有一个元素为1，其余都为0，否则它表示一条无效的路径.每行中只有一个元素为1，表示每个城市必须访问一次，表示为
[xvxi=1 ?i]
每列中只有一个元素为1，表示每个城市只能访问一次，可以表示为
[ivxi=1 ?x]
综合上述讨论，TSP可以表示为如下非线性优化问题：
[min l=12xy≠xidxyvxi（vy，i+1+vy，i-1）]
[st.] [xvxi=1 ?i]
[ivxi=1 ?x]
用罚函数法，将上述约束优化问题表示为下列无约束优化问题：
[J=A2xy≠xidxyvxivy，i+1+B2xy≠xidxyvxivy，i-1+C2（xivxi-n）2+D2xy≠xidxyvxi（vy，i+1+vy，i-1）]
令上式与神经网络的计算能量函数相等，比较同一变量两端的系数，可得第[x]行第[i]列位置上的神经元与第[y]行第[j]列位置上的神经元之间的连接权值为 [Wxi，yj=-Aδxy（1-δij）-Bδij（1-δxy）-C-Ddxy（δj，i+1+δj，i-1）（1-δxy）]
[Ixi=Cn]
式中，[δij=1 i=j0 其他].
Hopfield神经网络的动态方程为
[duxidt=-uxiτ-?E?vxi]
[=-uxiτ-Aj≠ivxj-By≠xvyi-C（xivxi-n）-Dydxy（vy，i+1+vy，i-1）]
[vxi=f（uxi）=12[1+tanh（uxiu0）]]
求解上式，直到收敛，可以得到神经网络的稳态解.在演化过程中，有些神经元的输出[vxi]逐渐增大到1，而有些神经元的输出[vxi]逐渐减少到0，最后收敛到稳定状态，所以，神经元的输出0或者1.
用上述神经网络方法可以解决C-TSP，即中国有31个省直辖市和自治区，我们在其首府之间进行旅行，C-TSP就是在这31个城市中找出一个最短的经过每一个城市各一次并回到起点的路径和距离。
二、结束语
人工神经网络是一类模拟人类神经系统的结构，他揭示数据样本中蕴含的非线性关系，大量处理单元组成非线性自适应动态系统，具有良好的自适应性、自组织及很强的学习、联想、容错和抗干扰能力，在不同程度和层次上可模仿大脑的信息处理机理，可灵活方便的对多成因的复杂未知系数进行高度建模。特别是BP 网络近年来广泛应用于模式识别、预测评估等领域，并取得良好的效果。
参考文献：
[1]高隽.人工神经网络原理及其仿真实例.北京：机械工业出版社，2003.7
[2]党建武.神经网络技术及应用.北京：中国铁路出版社，2007.7
[3]黄平.最优化理论与方法.北京：清华大学出版社，2009.2
[4]周开利.康耀红.神经网络模型及其MATLAB仿真程序设计.北京：清华大学出版社，2005.7
[5]侯媛彬.杜京义.汪梅等.神经网络.西安：西安电子科技大学出版社，2007.8
[6]曾昭.王耀南.神经网络算法在非线性系统中的应用研究[J].湖南师范大学自然科学学报，Vol.30，No.2，2007.7
[7]李振波.人工神经网络算法改进及其在经济分析中的应用.山东大学，2005.4
[8]邢文训.谢金星.现代优化计算方法[M ].北京：清华大学出版社，1999
关键词：神经网络算法;MTLAB;线性优化
人工神经网络（Artificial Neural Networks， ANN），亦称为神经网络（Neural Networks，NN），是由大量的处理单元（神经元Neurons）广泛互联而成的网络，是对大脑的抽象、简化和模拟，反映人脑的基本特性.人工神经网络的研究是从人脑的生理结构出发来研究人的智能行为，模拟人脑信息处理的功能.它是根植于神经科学、数学、物理学、计算机科学及工程等科学的一种技术。
一、神经网络线性优化方法求解TSP
旅行商问题（Traveling Saleman Problem，简称TSP，亦称货郎担问题）或者邮递员路径问题：有n个城市，其相互间的距离，或者旅行成本为已知，求合理的路线使每个城市都访问一次，且总路径为最短（或者总成本最小）.该问题可表示为
设有N个城市
[C={C1，C2，…，CN}]
给定C中任意两个城市间的距离
[d（Ci，Cj）=dij 1≤i，j≤N]
现在要找出一个城市的排列
[{Cn（1），Cn（2），…，Cn（N）}]
使得闭合路径
[i=1Nd[Cn（i），Cn（i+1）mod N]]
为最小.
从表面看，TSP很简单，其实则不然.对于N个城市的TSP，存在可能的路径数为[（N-1）！/2]条，当N较大时，其数量将是惊人的.计算每一条路径都需要求出N个距离之和，这样各种路径及其距离之和的计算量将正比于[N！/2]，.表3-1给出了用运算速度为1GFLOPS次的CrayⅡ计算机搜索TSP所需的时间.这里还不计算所需的巨大存储空间.从而可见用搜索法求解规模大的TSP是不现实的。
表3-1 TSP的计算量
[城市数N＼&7＼&15＼&20＼&50＼&100＼&200＼&加法量＼&[2.5×103]＼&[6.5×1011]＼&[1.2×1018]＼&[1.5×1064]＼&[5×10157]＼&[10374]＼&搜索时间＼&[2.5×10-5s]＼&[1.8h]＼&[350y]＼&[5×1048y]＼&[10142y]＼&[10358y]＼&]
1985年Hopfield和Tank用神经网络求解[N=30]的TSP，使用900个神经元组成的网络在[0.2s]内找到一个有效解（在[1030]个可能的解中排除[1023]个非最优解），从而开创了神经网络用于优化计算的新途径.其基本思想是：将TSP映射到一个神经网络上，通过网络的动力学方程自动演化到网络的平衡态，自动搜索到局部最优解.
对于TSP，一条访问路径可以用一个换位矩阵表示.以5个城市为例，如表3-2所示换位矩阵表示访问5个城市的路径顺序为[C3→C1→C5→C2→C4→C3]，其路径总长度为
[l=d31+d15+d52+d24+d43]
表3-2用换位矩阵表示访问次序
[＼&1＼&2＼&3＼&4＼&5＼&[C1]＼&0＼&1＼&0＼&0＼&0＼&[C2]＼&0＼&0＼&0＼&1＼&0＼&[C3]＼&1＼&0＼&0＼&0＼&0＼&[C4]＼&0＼&0＼&0＼&0＼&1＼&[C5]＼&0＼&0＼&1＼&0＼&0＼&]
如果下标[x]，[y]表示城市，[i]表示第[i]次访问，则路径长度可以表示为下列一般形式
[l=12xy≠xidxyvxivy，i+1+12xy≠xidxyvxivy，i-1]
[=12xy≠xidxyvxi（vy，i+1+vy，i-1）]
式中，[dxy]表示城市[x]，[y]之间的距离;[vxi]表示换位矩阵中的第[x]行第[i]列的元素，其值为1时表示第[i]步访问城市[x]，其值为0表示第[i]步不访问城市[x].
在表3-2中，各行各列只能有一个元素为1，其余都为0，否则它表示一条无效的路径.每行中只有一个元素为1，表示每个城市必须访问一次，表示为
[xvxi=1 ?i]
每列中只有一个元素为1，表示每个城市只能访问一次，可以表示为
[ivxi=1 ?x]
综合上述讨论，TSP可以表示为如下非线性优化问题：
[min l=12xy≠xidxyvxi（vy，i+1+vy，i-1）]
[st.] [xvxi=1 ?i]
[ivxi=1 ?x]
用罚函数法，将上述约束优化问题表示为下列无约束优化问题：
[J=A2xy≠xidxyvxivy，i+1+B2xy≠xidxyvxivy，i-1+C2（xivxi-n）2+D2xy≠xidxyvxi（vy，i+1+vy，i-1）]
令上式与神经网络的计算能量函数相等，比较同一变量两端的系数，可得第[x]行第[i]列位置上的神经元与第[y]行第[j]列位置上的神经元之间的连接权值为 [Wxi，yj=-Aδxy（1-δij）-Bδij（1-δxy）-C-Ddxy（δj，i+1+δj，i-1）（1-δxy）]
[Ixi=Cn]
式中，[δij=1 i=j0 其他].
Hopfield神经网络的动态方程为
[duxidt=-uxiτ-?E?vxi]
[=-uxiτ-Aj≠ivxj-By≠xvyi-C（xivxi-n）-Dydxy（vy，i+1+vy，i-1）]
[vxi=f（uxi）=12[1+tanh（uxiu0）]]
求解上式，直到收敛，可以得到神经网络的稳态解.在演化过程中，有些神经元的输出[vxi]逐渐增大到1，而有些神经元的输出[vxi]逐渐减少到0，最后收敛到稳定状态，所以，神经元的输出0或者1.
用上述神经网络方法可以解决C-TSP，即中国有31个省直辖市和自治区，我们在其首府之间进行旅行，C-TSP就是在这31个城市中找出一个最短的经过每一个城市各一次并回到起点的路径和距离。
二、结束语
人工神经网络是一类模拟人类神经系统的结构，他揭示数据样本中蕴含的非线性关系，大量处理单元组成非线性自适应动态系统，具有良好的自适应性、自组织及很强的学习、联想、容错和抗干扰能力，在不同程度和层次上可模仿大脑的信息处理机理，可灵活方便的对多成因的复杂未知系数进行高度建模。特别是BP 网络近年来广泛应用于模式识别、预测评估等领域，并取得良好的效果。
参考文献：
[1]高隽.人工神经网络原理及其仿真实例.北京：机械工业出版社，2003.7
[2]党建武.神经网络技术及应用.北京：中国铁路出版社，2007.7
[3]黄平.最优化理论与方法.北京：清华大学出版社，2009.2
[4]周开利.康耀红.神经网络模型及其MATLAB仿真程序设计.北京：清华大学出版社，2005.7
[5]侯媛彬.杜京义.汪梅等.神经网络.西安：西安电子科技大学出版社，2007.8
[6]曾昭.王耀南.神经网络算法在非线性系统中的应用研究[J].湖南师范大学自然科学学报，Vol.30，No.2，2007.7
[7]李振波.人工神经网络算法改进及其在经济分析中的应用.山东大学，2005.4
[8]邢文训.谢金星.现代优化计算方法[M ].北京：清华大学出版社，1999