人工神经网络求解TSP问题的改进算法研究.pdf

《人工神经网络求解TSP问题的改进算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第31卷第4期计算机仿真2014年4月文章编号：1006—9348(2014)04—0355—04人工神经网络求解TSP问题的改进算法研究郭中华，金灵，郑彩英(宁夏大学物理电气信息学院，宁夏银川750021)摘要：在算法优化问题的研究中，旅行商问题(TSP)是组合优化领域里的一种描述简单而难以处理的NP完全难题，为解决Hopfield神经网络求解TSP问题时易出现无效解和收敛性能差的问题，提出一种对能量函数“行”、“列”项进行严格约束并在神经元动态方程中使用软限幅函数的改进算法。在参数优化方面进行了分析并选取了最优参数值，与经典Hopfield神

2、经网络TSP求解方法进行比较。对lO个城市仿真研究，实验结果表明：改进算法能使网络函数达到全局搜索从而避免无效解的产生，求得的最优解个数多于原始算法，迭代次数少且易达到有效解。关键词：神经网络；能量函数；仿真中图分类号：TPI83文献标识码：BStudyonImprovedMethodofNeuralNetworktoSolveTSPGUOZhong—hua，JINLing，ZHENGCai—ying(SchoolofPhysicsandElectricalInformationEngineering，NingxiaUniversity，Yinc

3、huanNingxia750021，China)ABSTRACT：Inthestudyofalgorithmsoptimizationproblems，theTravelingSalesmanProblem(TSP)isdescribedasasimpleanddifficulttodealwithNP—-completeprobleminthefieldofcombinatorialoptimization．FortheH0pfieldnetworkinsolvingtheTSPoftengettingan—validandpoorconver

4、genceproblems．weproposedanim—provedalgorithmaboutstrictlyboundtheenergyfunction’S”row”．”column”itemsandusedthesoftlimiterfunctioninneuronaldynamicsequations．Intheparameteroptimizationaspects，weanalyzedandselectedtheoptimalparame—tervalue，comparedwiththeclassicHopfieldneuralne

5、tworktosolvetheTSPproblem．Simulationwascarriedoutwith10citiesandtheexperimentalresultsshowthattheimprovedalgorithmcanachieveglobalsearchingtoavoidgeneratingun—valid，thenumberofoptimalsolutionsismorethantheoriginalalgorithm，andeasytoachieveeffec—tivesolutionwithfeweriterations

6、．KEYWORDS：Neuralnetwork；Tenergyfunction；SimulationTSP的新方法，克服由于梯度下降法所导致的网络能量函数1引言总是下降，使网络陷入局部极小值或不可行解的现象。干能旅行商问题一直是一个难以解决的数学组合优化问题，强等提出一种正的自反馈Hopfield网络，使得解决TSP问因问题的优化尚未完全解决从而被列为NP完全问题⋯。题易获得有效解。齐小刚等分析了神经网络模型在求解近年来，越来越多的优化算法被提出用以解决各种优化问TSP问题过程中参数的选取，通过对输出数据进行归一化处题，如：模拟退火算法、遗传算法

7、、蚁群算法、禁忌搜索算法、理建立网络的评价函数。邱树伟等对连续Hopfield网络人工神经网络算法等。其中Hopfield和Tank_2提出的的数学模型及稳定性进行了分析；针对传统方法参数配置复Hopfield网络具有并行的计算性和容错性而被广泛应用在这杂、收敛速度慢等不足，提出了改进算法。虽然这些改进方一领域。由于该算法存在不稳定性，网络初始状态及其使用法能使得网络函数获得有效解，但未能达到能量函数的全局梯度下降法容易导致结果达不到最优解以及能量函数可能搜索，从而不能有效获得最优解。陷入局部解。费春国等提出一种连续Hoeld网络求解本文根据Ho

8、pfield神经网络能量函数的收敛情况及算法的计算复杂性等缺点提出一种新的改进算法。对能量函数的“行”、“列”项进行严格约束，保证每行每