A study of the application of Kohonen-type neural networks to the travelling salesman problem. (English) Zbl 0722.92002
It is observed that animals often have to resolve difficult tasks of optimization and that this process can be studied by applying the formal framework of neural networks to a simple problem such as the Travelling Salesman Problem. Existing work is reviewed with particular emphasis on recent studies using “self-organization networks”. An algorithm is described in which general principles developed by T. Kohonen [see: Self-organization and associative memory (1988; Zbl 0659.68100)] are applied to the Travelling Salesman Problem.
MSC:
| 92B20 | Neural networks for/in biological studies, artificial life and related topics |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68T05 | Learning and adaptive systems in artificial intelligence |
Citations:
Zbl 0659.68100References:
| [1] | Angenioli B (1988) Self-organizing feature maps and the Travelling Salesman Problem. Neur Net 1:289–293 · doi:10.1016/0893-6080(88)90002-0 |
| [2] | Burn D (1988) An improved elastic net method for the Travelling Salesman Problem, Proc IEEE Int Conf Neur Net I-69–76 |
| [3] | Cuykendall R, Reese R (1989) Scaling the neural TSP algorithm. Biol Cybern 60:365–371 · Zbl 0709.94618 · doi:10.1007/BF00204774 |
| [4] | Durbin R, Willshaw D (1987) An analogue approach to the travelling salesman problem using an elastic net method. Nature 326:689–691 · doi:10.1038/326689a0 |
| [5] | Garey M, Johnson D (1977) Computers and intractability. Freeman, San Francisco · Zbl 0369.90053 |
| [6] | Hopfield JJ, Tank DW (1985) ”Neural” computation of decisions in optimization problems. Biol Cybern 52:141–152 · Zbl 0572.68041 |
| [7] | Hueter G (1988) Solution of The Traveling Salesman Problem with an adaptive ring. Proc IEEE Int Conf Neur Net I-85–92 · doi:10.1109/ICNN.1988.23832 |
| [8] | Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680 · Zbl 1225.90162 · doi:10.1126/science.220.4598.671 |
| [9] | Kohonen T (1982) Self-organized formation of topologically correct feature maps. Biol Cybern 43:59–69 · Zbl 0466.92002 · doi:10.1007/BF00337288 |
| [10] | Kohonen T (1988) Self-organization and associative memory. Springer, Berlin Heidelberg New York · Zbl 0659.68100 |
| [11] | Kohonen T (1989) Speech recognition based on topology-preserving neural maps. In: Aleksander I (eds) Neural computing architectures, North Oxford Academic, London |
| [12] | Lin S, Kernighan BW (1973) An effective heuristic algorithm for the travelling-salesman problem. Oper Res 21:498–516 · Zbl 0256.90038 · doi:10.1287/opre.21.2.498 |
| [13] | Von der Malsburg Ch, Willshaw DJ (1977) How to label nerve cells so that they can interconnect in an ordered fashion. Proc Natl Acad Sci USA 74:5176–5178 · doi:10.1073/pnas.74.11.5176 |
| [14] | Wilson GV, Pawley GS (1988) On the stability of the travelling salesman problem algorithm of Hopfield and Tank. Biol Cybern 58:63–70 · Zbl 0637.65062 · doi:10.1007/BF00363956 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
