智能算法求解TSP问题的比较

目前TSP问题的求解方法不仅种类繁多,而且模型迥异。集中讨论求解TSP问题的智能算法,将其分为进化算法、Hopfield神经网络和自组织映射3类,对每类方法进行了原理研究、性能分析和优缺点比较。最后通过不同规模的实验进行验证,发现进化算法与局部搜索的组合求解TSP性能最好。今后的研究将集中在如何寻找更优的局部搜索。     

Hopfield网络求解TSP的算法改进

本文在对Hopfield神经网络求解旅行商(TSP)问题的算法进行研究的基础上结合实例针对典型改进算法的优缺点作了进一步探讨。     

利用Hopfield神经网络求解旅行商问题研究

本文主要研究利用连续的Hopfield网络求解TSP问题,从连续的Hopfield神经网络原理出发,结合TSP问题的要求,在给定参数要求下求得问题的最优解。并分析了实际算法的弱点,给出分析改进算法,加快了算法的收敛速度,改善有效解并提高最优解的比例。     

基于精确罚函数的神经网络优化方法求解TSP问题

利用精确罚函数方法结合神经网络来求解最优化问题,重点求解的是组合优化问题的TSP经典问题,重点讲述的是Hopfield神经网络基于精确罚函数求解组合优化问题TSP,在用Hopfield神经网络求解TSP问题时,人工神经网络的初始态对应着无约束优化问题的初始解,人工神经网络系统的稳态对应着无约束问题的优化解。在求解TSP问题中是利用能量函数来构造的。当人工神经网络系统达到稳定状态时的一个极小点也就是TSP问题的最优解。     

一种基于聚类技术的Hopfield网络求解TSP方法

Hopfiled神经网络方法已被广泛用于求解旅行商问题（TSP），但对于解中规模和大规模的TSP，存在效果不理想甚至难以求解的问题。为了较好地解决这个问题，该文提出一种K-Means聚类算法与Hopfield网络方法相结合求解TSP的新方法，先应用聚类算法对所给城市进行聚类以获得几组规模较小的城市，然后对每一组城市应用Hopfield网络方法进行求解，最后把求解后的每组城市连接起来。计算机仿真结果表明，该方法可以获得最优有效解，并且解的质量明显提高，对求解中大规模的TSP比较有效。     

求解旅行商问题的几种智能算法

旅行商问题（TSP）是一个典型的组合优化问题,易于描述却难于求解。对于大规模TSP问题,目前仍未有非常有效的方法,如何快速有效的求解TSP问题有着重要的理论价值和实际意义。文章介绍了什么是TSP,论述了目前求解旅行商问题较为有效的六种智能算法（遗传算法、蚁群算法、Hopfield神经网络算法、模拟退火算法、人工免疫算法、混合优化算法）,并简单阐述了其优缺点,给出了未来针对TSP问题的研究重点。     

智能优化算法求解TSP 问题

TSP（旅行商）问题代表组合优化问题，具有很强的工程背景和实际应用价值，但至今尚未找到非常有效的求解方法．为此，讨论了最近研究比较热门的使用各种智能优化算法（蚁群算法、遗传算法、模拟退火算法、禁忌搜索算法、Hopfield神经网络、粒子群优化算法、免疫算法等）求解TSP问题的研究进展，指出了各种方法的优缺点和改进策略．最后总结并提出了智能优化算法求解TSP问题的未来研究方向和建议．     

一种Hopfield神经网络算法复杂性研究的新方法

首先分析了基于Hopfield神经网络的TSP问题求解方法,提出从研究能量函数、状态空间分布和可行解的关系来研究以Hopfield为代表的优化神经网络的计算复杂性的思想;并给出从状态空间到线性表的映射方法,引入状态-程序复杂性。分析结果表明,绝对状态一程序复杂性更为充分地反映能量函数的求解过程;相对状态-程序复杂性提供了一种在多项式时间内对NP问题算法的有效性进行衡量的尺度。     

Hopfield网络应用实例分析

分析离散型Hopfield神经网络在模式识别中应用以及连续型Hopfield网络在求解TSP问题中的应用，并给出仿真实例。总结了Hopfield网络在实际应用中的一般方法。     

基于混沌粒子群算法和Hopfield网络求解TSP问题

针对Hopfield网络求解TSP问题经常出现局部最优解,该文将混沌粒子群算法（PSO）与之结合,提出一种基于混沌粒子群的Hopfield神经网络方法。通过实验将其与文献[5,8]以及“PSO＋HNN”策略比较,验证了该文算法不仅能够以更大概率收敛到全局最优,而且耗时更少。     

A theoretical investigation into the performance of the Hopfieldmodel

An analysis is made of the behavior of the Hopfield model as a content-addressable memory (CAM) and as a method of solving the traveling salesman problem (TSP). The analysis is based on the geometry of the subspace set up by the degenerate eigenvalues of the connection matrix. The dynamic equation is shown to be equivalent to a projection of the input vector onto this subspace. In the case of content-addressable memory, it is shown that spurious fixed points can occur at any corner of the hypercube that is on or near the subspace spanned by the memory vectors. Analysed is why the network can frequently converge to an invalid solution when applied to the traveling salesman problem energy function. With these expressions, the network can be made robust and can reliably solve the traveling salesman problem with tour sizes of 50 cities or more.     

指针网络改进遗传算法求解旅行商问题

虽然遗传算法相较于其他算法能够更好地求解旅行商问题,但这种算法在使用的过程中容易陷入局部最优的问题,进而导致问题求解遭遇困境。文章在简要介绍旅行商问题的基础上,介绍了遗传算法求解旅行商问题的思路和方法,并明确算法应用中存在的不足。在此基础上提出基于指针网络改进遗传算法求解旅行商问题的新思路,为弥补遗传算法的缺陷提供相应的原理支持。     

Scheduling multiprocessor job with resource and timing constraintsusing neural networks

The Hopfield neural network is extensively applied to obtaining an optimal/feasible solution in many different applications such as the traveling salesman problem (TSP), a typical discrete combinatorial problem. Although providing rapid convergence to the solution, TSP frequently converges to a local minimum. Stochastic simulated annealing is a highly effective means of obtaining an optimal solution capable of preventing the local minimum. This important feature is embedded into a Hopfield neural network to derive a new technique, i.e., mean field annealing. This work applies the Hopfield neural network and the normalized mean field annealing technique, respectively, to resolve a multiprocessor problem (known to be a NP-hard problem) with no process migration, constrained times (execution time and deadline) and limited resources. Simulation results demonstrate that the derived energy function works effectively for this class of problems.     

A neural network approach to job-shop scheduling

A novel analog computational network is presented for solving NP-complete constraint satisfaction problems, i.e. job-shop scheduling. In contrast to most neural approaches to combinatorial optimization based on quadratic energy cost function, the authors propose to use linear cost functions. As a result, the network complexity (number of neurons and the number of resistive interconnections) grows only linearly with problem size, and large-scale implementations become possible. The proposed approach is related to the linear programming network described by D.W. Tank and J.J. Hopfield (1985), which also uses a linear cost function for a simple optimization problem. It is shown how to map a difficult constraint-satisfaction problem onto a simple neural net in which the number of neural processors equals the number of subjobs (operations) and the number of interconnections grows linearly with the total number of operations. Simulations show that the authors' approach produces better solutions than existing neural approaches to job-shop scheduling, i.e. the traveling salesman problem-type Hopfield approach and integer linear programming approach of J.P.S. Foo and Y. Takefuji (1988), in terms of the quality of the solution and the network complexity.     

论遗传算法在旅行商问题中的应用

旅行商问题是算法应用中的基本问题,遗传算法具有通用性、智能性、鲁棒性、全局性和并行性的特点,正好适合于该问题的求解。但基本遗传算法在解决旅行商问题时效率不高,并且容易陷于局部最优解。为了解决这一问题,提出了一种改进的遗传算法。文章首先对旅行商问题进行了描述,对遗传算法进行了介绍,对其中的个体选择、交叉算法等重要因素做了一定地改进。最后,用一个简单的实例对基本遗传算法和改进的遗传算法进行了比较,发现改进的遗传算法在解决旅行商问题上的效率问题上有了一定的提高。     

基于混沌粒子群算法和Hopfield网络求解TSP问题

针对Hopfield网络求解TSP问题经常出现局部最优解,该文将混沌粒子群算法(PSO)与之结合,提出一种基于混沌粒子群的Hopfield神经网络方法。通过实验将其与文献[5,8]以及"PSO+HNN"策略比较,验证了该文算法不仅能够以更大概率收敛到全局最优,而且耗时更少。     

A New Relaxation Procedure in the Hopfield Network for Solving Optimization Problems

When solving an optimization problem with a Hopfield network, a solution is obtained after the network is relaxed to an equilibrium state. The relaxation process is an important step in achieving a solution. In this paper, a new procedure for the relaxation process is proposed. In the new procedure, the amplified signal received by a neuron from other neurons is treated as the target value for its activation (output) value. The activation of a neuron is updated directly based on the difference between its current activation and the received target value, without using the updating of the input value as an intermediate step. A relaxation rate is applied to control the updating scale for a smooth relaxation process. The new procedure is evaluated and compared with the original procedure in the Hopfield network through simulations based on 200 randomly generated instances of the 10-city traveling salesman problem. The new procedure reduces the error rate by 34.6% and increases the percentage of valid tours by 194.6% as compared with the original procedure.     

On the relationship between the biconnectivity augmentation and travelling salesman problems

A strategy for solving the traveling salesman problem is adapted to the problem of finding a biconnected subgraph of a weighted graph whose cost function satisfies the triangle inequality. An approximation algorithm similar to Christofides' algorithm [5] for the traveling salesman problem is shown to possess the same worst-case bound of $\text{3}\text{2}$ when applied to the biconnectivity augmentation problem. A tight inequality is derived relating the cost of an optimal traveling salesman tour to the cost of an optimal biconnection.     

A new and efficient ant-based heuristic method for solving the traveling salesman problem

Abstract: In this paper, we present an efficient metaheuristic approach for solving the problem of the traveling salesman. We introduce the multiple ant clans concept from parallel genetic algorithms to search solution space using different islands to avoid local minima in order to obtain a global minimum for solving the traveling salesman problem. Our simulation results indicate that the proposed novel traveling salesman problem method (called the ACOMAC algorithm) performs better than a promising approach named the ant colony system. This investigation is concerned with a real life logistics system design which optimizes the performance of a logistics system subject to a required service level in the vehicle routing problem. In this work, we also concentrate on developing a vehicle routing model by improving the ant colony system and using the multiple ant clans concept. The simulation results reveal that the proposed method is very effective and potentially useful in solving vehicle routing problems.