A self-organising model for the travelling salesman problem
- PDF / 258,122 Bytes
- 10 Pages / 595 x 842 pts (A4) Page_size
- 14 Downloads / 173 Views
#1997 Operational Research Society Ltd. All rights reserved. 0160-5682/97 $12.00
A self-organising model for the travelling salesman problem S Somhom, A Modares and T Enkawa Tokyo Institute of Technology, Japan This work describes a new algorithm, based on a self-organising neural network approach, to solve the Travelling Salesman Problem (TSP). Firstly, various features of the available adaptive neural network algorithms for TSP are reviewed and a new algorithm is proposed. In order to investigate the performance of the algorithms, a comprehensive empirical study has been provided. The simulations, which are conducted on a series of standard data, evaluate the overall performance of this approach by comparing the results with the best known or the optimal solutions of the problems. The proposed algorithm shows signi®cant advances in both the quality of the solution and computational effort for most of the experimental data. The deviation from the optimal solution of this algorithm was, in the worst case, around 2%. This fact indicates that the self-organising neural network may be regarded as a promising heuristic approach for optimisation problems. Keywords: neural networks; optimisation; self-organising; travelling salesman
Introduction In neural networks,1 there are two general learning paradigms: supervised and unsupervised learning. As opposed to supervised learning, where the network has its output compared with known correct answers, the unsupervised learning must discover interesting categories or correlations in the input data by itself. Therefore, it is said to be selforganising neural network. The self-organising neural network is inspired by the functioning of human brain in the group which does not require explicit tutoring by inputoutput correlations and which spontaneously self-organises upon internal presentation of input patterns. Using neural networks for optimisation problems arose from the work of Hop®eld and Tank.2 They introduced an associative neural network model and utilised the notion of energy function to show convergence of the network to a steady state. To apply this model to optimisation problems, the cost function as well as a penalised form of restrictions should be embodied in the energy function. The inherent feature of the network which assures diminution of the energy function during the simulation is the sole mechanism for providing the feasibility of the solution and simultaneously providing for the minimisation of the cost function. Inability to guarantee feasible solutions and complexity of the model may be noted as two major weaknesses of this approach.3,4 Despite its ¯exibility in extension for different combinatorial problems, these shortcomings take it out of Correspondence: S Somhom, Department of Industrial Engineering & Management, Tokyo Institute of Technology, 2-12-1, Ookayama, Meguroku, Tokyo 152, Japan. E-mail: [email protected]
the competition as compared with other sophisticated optimisation algorithms. Recently, the adaptive neural network models, which are
Data Loading...
