一种改进的Hopfield神经网络对TSP问题的求解方法.pdf

《一种改进的Hopfield神经网络对TSP问题的求解方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2014年第3期闽南师范大学学报(自然科学版)No．3．2014年(总第85期)JournalofMinnanNormalUniversity(Nat．Sci．)GeneralNo．85一种改进的Hopfield神经网络对TSP问题的求解方法闫玉莲(闽南师范大学物理与信息工程学院，福建漳州363000)摘要：论文对Hopfield神经网络的能量函数进行重构，使得新能量函数具有参数少、表达式简洁、计算效率高等特点；并引入遗传算法中的变异算子，使得改进后的Hopfield神经网络的具有自适应调整的功能．同时，针对有效解易陷入局部极小值

2、等问题，运用数据转换技术、贪心算法等对有效解进行优化．最后对不同规模的TSP问题仿真．结果表明这些改进方法和技巧是可行的．关键词：Hopfield神经网络；能量函数；TSP问题；变异算子：贪心算法；数据转化中图分类号：TP301．6文献标志码：A文章编号：2095—7122(2014)O3—0037—07ASolvingMethodtoTSPBasedonImprovedHopfieldNeuralNetworksYANYu-lian(SchoolofPhysicsandInformationEngineering，MinnanN

3、ormalUniversity，Zhangzhou，Fujian363000，China)Abstract：Anewtypeneur~networksenergyfunctionofHNN(Hopfieldneuralnetworks)isproposedinthispaper．Theenergyfunctionisthusgiveninasimplerformula,fewerparametersandhighercomputingeficiency．Meanwhile，themutationoperatorofgenetica

4、lgorithmisappliedinthisHNN，whichmaketheHNNcanserf-adjustundersomeconditions．Moreover,greedyalgorithmanddamtransformationtechniquealeintroducedinthiskindHNN，whichcanmakeHNNescapesfromthelocalminimumpointstosomeextent．Finaly，aseriesofTSPproblemsaresimulatedwithdiferentn

5、umberofcities，andtheresultsofthesesimulationscanexplainwellthatthesemeansisefectivetoHNN．Keywords：Hopfieldneuralnetworks；energyfunction；TSP；mutationoperator；greedyalgorithm；datatransformationtechniques1新能量函数的改进及连接权矩阵Hopfield神经网络[】'2]在最优化、模式识别、图像处理及动力系统参数在线估计等领域有着广泛的应用

6、，但是该方法也存在有效解成功率低、计算量较大等问题[3]．另一方面，遗传算法J(GA，geneticalgorithm)是一种研究较多的智能算法，其最终结果的优劣受初始种群的影响较大，包括初始种群的数量以及种群的多样性等．由于这两类方法有各自的优缺点，目前，一些文献考虑把这两种方法结合在一起处理问题]，如应用Hopfield神经网络生成的解来构造遗传算法的初始种群．以保证其种群的多样性．Hopfield神经网络求解TSP问题是一个研究较多的问题，但是该方法存在参数设置繁琐、局部极小值即计算效率低等问题_3]．本文提出一种新思路，即

7、引入遗传算法中的变异算子(mutationoperator)来优化神经网络的解，同时，对原来的能量函数进行改进，使之具有参数少、计算效率高等特点．首先，n个城市的TSP问题(旅行商问题)，Hopfield神经网络的方法是构造一个换位矩阵(vz)nxn其中代表城市序号，i是访问顺序，若Vx／=1意味着第i步访问第个城市，反之若／)x／=0则表示第i步不访问第个城市．只要该矩阵每一行每一列有且仅有一个元素为1，其他元素为0，就可得到一个有效路径．以一个5城市(ABCDE)问题为例，如右图，该矩阵表示的访问顺序为C_EA__+BD_C．

8、收稿日期：2013-09—26作者j笱介：目玉莲(1972-)，女，辽宁省兴城市人．讲师·37·2014点闽南师范大学学报(自然科学版)对于TSP问题的求解，经典的Hopfield神经网络的能量函数为[2]：∑∑∑v十号+[∑一叫+川+Vx,Vy川