Neural network models for combinatorial optimization : a survey of deterministic, stochastic and chaotic approaches

• Autorzy: Smith K. , Potvin J. , Kwok T.
• Języki publikacji: EN

Abstrakty

EN

This paper serves as a tutorial on the use of neural networks for solving combinatorial optimization problems. It reviews the two main classes of neural network models : the gradient-based neural networks such as the Hopfield network, and the deformable template approaches such as the elastic net method and self organizing maps. In each class, the original model is presented, its limitations discussed, and subsequent developments and extensions are reviewed. Particular emphasis is placed on stochastic and chaotic variations on the neural network models designed to improve the optimization performance. Finally, the performance of these neural network models is compared and discussed relative to other heuristic approaches.

Słowa kluczowe

EN

chaos; combinatorial optimization; deformable templates; Hopfield networks; neural networks; self-organizing map

PL

chaos; odwzorowanie samoporządkujące; optymalizacja kombinatoryczna; sieć Hopfielda; sieć neuronowa

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2002
• Tom: Vol. 31, no. 2
• Strony: 183--216
• Opis fizyczny: Bibliogr. 87 poz.,Rys., wykr.,

Twórcy

autor

Smith K.

• School of Business Systems, Faculty of Information Technology, P.O. Box 63B , Monash University, Victoria 3800, Australia

autor

Potvin J.

• Departement d 'Informatique et de Recherche Operationnelle Universite de Montreal, C.P. 6128, Succ. Centre-Ville, Montreal (Quebec) H3C 3J7, Canada

autor

Kwok T.

• School of Business Systems, Faculty of Information Technology, P.O. Box 63B , Monash University, Victoria 3800, Australia

Bibliografia

• AARTS, E.H.L. and KORST, J. (1989) Simulated Annealing and Boltzmann Machines. John Wiley & Sons, Essex.
• AIHARA, K., TAI
• AIHARA, K. (1994) Chaos in neural response and dynamical neural Network models: towards a new generation of analog computing. In: M. Yamaguti, Towards the Harnessing of Chaos. Elsevier Science Publishers B. V., Amsterdam, 83-98.
• AIYER, S.V.B., NIRANJAN, M. and FALLSIDE, F. (1990) A theoretical investigation into the performance of the Hopfield model. IEEE Transactions on Neural Networks, 1, 204-215.
• ARKYAMA, Y., YAMASHI TA , A., KAJIURA, M. and Arso, H. (1989) Combinatorial Optimization with Gaussian Machines. Proceedings IEEE International Joint Conference on Neural Networks, 1, 533-540.
• AMARTUR, S. C., PIRAINO, D. and TAKEFUJI, Y. (1992) Optimization Neural Networks for the Segmentation of Magnetic Resonance Images. IEEE Transactions on Medical Imaging, 11, 215-220.
• ANGENIOL, B., VAUBOIS, G. and LE TEXIER, J.Y. (1988) Self-Organizing Feature Maps and the Travelling Salesman Prob lem. Neural Networks, 1, 289-293.
• ASAI, H., 0NODERA, K., KAMIO, T. and NINOMIYA, H. (1995) A study of Hopfield neural networks with external noises. Proceedings of the IEEE International Conference on Neural Networks, 4, 1584- 1589.
• BARR, R.S., GOLDEN, B.L., KELLY, J.P., RESENDE, M.G .C. and ST EWART, W.R. (1995) Designing and Reporting on Computat ional Experiments with Heur istic Methods . Journal of Heuristics, 1, 9-32.
• BOERES, M.S.C ., DE CARVALHO, L.A.V. and BARBOSA, V .C. (1992) A Faster Elastic Net Algorithm for the Traveling Salesman Problem. Proceedings of the Int. Joint Conf. on Neural Networks, 2, 215-220 .
• BRANDT, R.D ., WANG, Y., LAUB, A.J. and MITRA, S.K. (1988) Alternative networks for Solving the Travelling Sa lesman Prob lem and the Li st – Matching Problem. Proceedings International Conference on Neural Networks, 2, 333-340.
• BuRKE, L.I. (1994) Adapt ive Neural Networks for the Traveling Salesman Problem: Insights from Operations Research. Neural Networks, 7, 681-690.
• BURKE, L.I. and DAMANY, P. (1992) The Guilty Net for the Traveling Salesman Problem. Computers f3 Operations Research, 19, 255-265 .
• BURKE, L.I. and IGNIZIO, J.P. (1992) Neural Networks and Operations Research: An Overview. Computers f3 Operations Research, 19, 179-189.
• CHEN , L. and AIHARA, K. (1995) Chaotic Simul ated Annealing by a Neura l Network Model with Transient Chaos. Neural Networks, 8, 915-930.
• DESIENO, D. (1988) Adding a Conscience Mechanism to Competitive Learning. Proceedings of the IEEE Int . Conf. on Neural Networks, 1, 117-124.
• DURBIN, R. and WILLSHAW, D.J. (1987) An Analogue Approach to the Traveling Salesman Problem using an Elastic Net Method. Nature, 326, 689-691.
• FAVATA, F. and WALKER, R. (1991) A Study of the Application of Kohonen – type Neural Networks to the Traveling Sa lesman Prob lem. Biological Cybernetics, 64, 463- 468.
• Foo, Y.P.S. and Szu, H. (1989) Solving large-scale optimization problems by divide-and-conquer neural networks. Proceedings IEEE International Joint Conference on Neural Networks, 1, 507- 511.
• GAREY, M.R. and JOHNSON, D.S. (1979) Computers and Intractability. W.H. Freeman, New York.
• GEE, A.H. (1993) Problem Solving with Optimization Networks. Ph.D. dissertation, Queen's College, Cambridge University, U.K.
• GHAZIRI, H. (1991) Solving Routing Problems by a Self-Organizing Map. In: T. Kohonen, K. Makisara, 0. Simula, J. Kangas, eds., Artificial Neural Networks. North -Holland, Amsterdam, 829- 834.
• GHAZIRI, H. (1996) Superv ision in the Self-Organizing Feature Map: Application to the Vehicle Routing Problem. In: I.H. Osman and J.P. Kelly, eds., MetaHeuristics: Theory 8 Applications. Kluwer, Boston, 651- 660 .
• GOLDSTEIN, M. (1990) Se lf-Organizing Feature Maps for the Multiple Traveling Salesmen Problem. Proceedings of the Int ernational Neural Network Conference, 1, 258- 261.
• GUERRERO, F., SMITH , K.A. and LOZANO, S. (1999) Self-organizing neural approach for solving the quadratic assignment problem. Proc. Int. Workshop on Soft Computing in Industry, 13-18.
• GUERRERO, F., LOZANO, S., SMITH, K.A. and EGUIA, I. (2000) Facility Location using Neural Networks. In: Suzuki, Y. Ovaska, T. Furuhashi, R. Roy, and Y. Dote, eds. , Soft Computing in Industrial Applications. Springer-Verlag, London, 171-179.
• GUERRERO, F., LOZANO, S., CANCA, D. and SMITH, K.A. (1998) Machine Grouping in Cellular Manufacturing: A Self-Organizing Neural Network. Proceedings 4th Int. Conf. on Engineering Applications of Neural Networks. Systems Engineering Association, Turku, Finland, 374- 377.
• GUERRERO, F., LOZANO, S., SMITH, K.A. and KwoK, T. (1999) Manufacturing cell formation using a new self-organizing neural network. Proc. Int. Conf. on Computers and Industrial Engineering, l, 668-672.
• HASEGAWA , M. , IKEGU CH I, T. and AIHARA, K. (1997a) Combination of chaotic neurodynamics with the 2-opt algorithm to solve traveling salesman problems. Physical Review Letters, 79, 2344-2347.
• HASEGAWA, M., IKEGUCHI, T. , MATOZAKI , T. and AIHARA , K. (1997b) An analysis on additive effects of nonlin ea r dynamics for combinatorial optimization. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E80-A, 206- 213.
• HASEGAWA, M., lKEGUCHI , T. and AIHARA , K. (1998) Solving quadratic assignment problems by chaotic neurodynamic s. Proceedings of the 1997 International Conference on Ne1tral Information Processing and Intelligent Information Systems, l, 182- 185.
• HAYAKAWA, Y., MARUMOTO, A. and SAWADA, Y. (1995) Effects of the chaotic noise on the performance of neural network model for optimization problems. Physical Review E, 51, R2693- R2696.
• HEGDE, S., SWEET, J. and LEVY , W . (1988) Determination of Parameters in a Hopfield/Tank Computational Network. Proceedings IEEE International Conference on Neuml Networks, 2, 291-298.
• HINTON , G.E. , SEJNOWSKI , T.J. and ACKLEY, D.H. (1984) Boltzmann machines: constraint satisfaction networks that learn. Carnegie Mellon University T ec hnical Report CMU-CS-84- 119.
• HOPFIELD, J.J. (1982) Neural Networks and Physical Systems with Emergent Collective Computational Abilities. Proceedings of the National Acade my of Sciences, 79, 2554-2558.
• HOPFIELD, J.J. (1984) Neurons with Graded Response have Collective Computational Properties like those of Two-State Neurons. Proceedings of the National Academy of Sciences, 81, 3088- 3092.
• HoPFIELD, J.J. and TANK, D.W. (1985) Neural Computation of Decisions In Optimization Problems. Biological Cybernetics, 52, 141 - 152.
• HOOKER, J.N. (1995) Testing Heuristics: We Have it All Wrong. Journal of Heuristics, 1, 33-42.
• JOHNSON, D.S. (1990) Local Optimization and the Traveling Salesman Problem. Volume 443 of Lecture Notes in Computer Science. "Automata, Languages and Programming". Springer-Verlag, Berlin, 446-461.
• KAMGAR - PARSI, B. and KAMGAR-PARSI, B . (1992) Dynamical Stability and Parameter Selection in Neural Optimization. Proceedings IEEE International Conference on Neural Networks, 4, 566-571.
• KIRKPATRICK S., GELATT, C.D . and VECCHI, M.P. (1983) Optimization by Simulated Annealing. Science, 220, 671-680.
• KoHONEN, T. (1982) Self-Organized Formation ofTopologically Correct Feature Maps. Biological Cybernetics, 43, 59-69.
• KOHONEN, T. (1988) Self-Organization and Associative Memory. Springer, Berlin.
• KwoK, T., SMITH, K. and WANG, L. (1998a) Solving combinatorial optimization problems by chaotic neural networks. In: C. Dagli et al., eds., Intelligent Engineering Systems Through Artificial Neural Networks: Neural Networks, Fuzzy Logic, Evolutionary Programming, Data Mining, and Rough Sets, 8, 317-322, New York: ASME Press.
• KwoK, T., SMITH, K. and WANG, L. (1998b) Incorporating chaos into the Hopfield neural network for combinatorial optimization. World Multiconference on Systemics, Cybernetics and Informatics, 1, 659-665.
• KwoK, T. and SMITH, K. (1999a) A unified framework for chaotic neural network approaches to combinatorial optimization. IEEE Transactions on Neural Networks, 10, 978-981.
• KwoK, T. and SMITH, K.A. (2001) A noisy self-organizing neural network with bifurcation dynamics for combinatorial optimization. IEEE Transactions on Neural Networks (submitted) .
• LAI, W.K. and COGHILL, G.G. (1992) Genetic Breeding of Control Parameters for the Hopfield/Tank Neural Net. Proceedings Inter-national Joint Conference on Neural Networks, 4, 618-623.
• LIN, S. and KERNIGHAN, B.W. (1973) An effective heuristic algorithm for the travelling salesman problem. Operations Research, 21, 498-516.
• Lo, J.T-H. (1992) A new approach to global optimization and its applications to neural networks. Proceedings IEEE Inter-national Joint Conference on Neural Networks, 4, 600-605.
• Loor, C.K. (1992) Neural Network Methods in Combinatorial Optimization. Computers f3 Operations Research, 19, 191-208.
• LOZANO, S., GUERRERO, F., EGUIA, I. and SMITH, K.A. (1998) Cell Formation using Two Neura l Networks in Series. In: C. Dagli et al., eds., Intelligent Engineering Systems Through Artificial Neural Networks, 8, ASME Press, 341-346.
• MATSUYAMA, Y. (1991) Self-Organization via Competition, Cooperation and Categorization Applied to Extended Vehicle Routing Problems. Proceedings of the Int. Joint Conf. on Neural Networks, 1, 385-390.
• MCCULLOCH, W.S. and PITTS, W. (1943) A Logical Calculus ofldeas Immanent in Nervous Activity. Bulletin of Mathematical Biophysics, 5, 115- 133.
• MINSKY, M. and PAPERT, S. (1969) Perceptrons, MIT Press, Cambridge, MA.
• NEMHAUSER, G.L. and WOLSEY, L.A. (1988) Integer and Combinatorial Optimization, John Wiley & Sons, Canada.
• NOZAWA, H. (1992) A neural network model as a globally coupled map and applications based on chaos. Chaos, 2, 377- 386.
• PETERSON, C. and SODERBERG, B. (1989) A New Method for Mapping Optimization Problems onto Neural Networks . International Journal of Neural Systems, 1, 3- 22.
• PETERSON, C. and SODERBERG, B. (1993) Artificial Neural Networks. In: C.R. Reeves, ed., Modern Heuristic Techniques for Combinatorial Optimization, Chapter 5, Blackwell Scientific Publishers, Oxford, UK.
• POTVIN, J.Y. (1993) The Traveling Salesman Problem: A Neural Network Perspective. ORSA Journal on Computing, 5, 328-348.
• POTVIN, J.Y. and ROBILLARD, C. (1995) Clustering for Vehicle Routing with a Competitive Neural Network Model. Neurocomputing, 8, 125- 139.
• ROSENBLATT, F. (1958) The perceptron: A Probabilistic Model for Information Storage and Organization in the Brain. Psychological Review, 65, 386-408.
• RUMELHART, D.E. and MCCLELLAND, J.L. (1986) Parallel Distributed Processing: Explorations in the Microstructure of Cognition. MIT Press, Cambridge, MA.
• SIMMEN, M.W. (1991) Parameter Sensitivity of the Elastic Net Approach to the Traveling Salesman Problem. Neural Computation, 3, 363-374.
• SMITH, K.A. (1995) Solving the Generalized Quadratic Assignment Problem using a Self-Organizing Process. Proceedings of the IEEE Int. Conf. On Neural Networks, 4, 1876- 1879.
• SMITH, K.A. (1996) An argument for abandoning the Travelling Salesman Problem as a neural network benchmark. IEEE Trans. on Neural N etworks, 7, 1542-1544.
• SMITH, K.A. (1999) Neural Networks for Combinatorial Optimization: A Review of More than a Decade of Research. INFORMS Journal on Computing, 11, 15-34.
• SMITH, K.A., ABRAMSON, D. and DuKE, D. (1999) Efficient Timetabling Formulations for Hopfield Neural Networks. In: C. Dagli et al., eds. , Smart Engineering System Design: Neural Networks, Fuzzy Logic, Evolutionary Programming, Data Mining, and Complex Systems, 9, ASME Press, 1027-1032.
• SMITH, K.A. and GuPTA, J.N.D. (2001) Continuous function optimisation via gradient descent on a neural network approximation function. Volume 2084 of Lecture Notes in Computer Science. "Connectionist Models of Neurons, Learning Processes, and Artificial Intelligence". Springer-Verlag, Berlin, 741-748.
• SMITH, K.A., PALANISWAMI, M. and KRISHNAMOORTHY, M. (1996) A Hybrid Neural Approach to Combinatorial Optimization. Computers f Operations Research, 23, 597- 610.
• SMITH, K., PALANISWAMI, M. and KRISHNAMOORTHY, M. (1998) Neural Techniques for Combinatorial Optimization with Applications. IEEE Transactions on Neural Networks, 9, 1301- 1318.
• Szu, H. and HARTLEY, R. (1987) Fast Simulated Annealing. Physics Letters A, 122, 157-162.
• Szu , H. (1988) Fast TSP algorithm based on binary neuron output and analog input using zero-diagonal interconnect matrix and necessary and sufficient conditions of the permutation matrix. Proceedings IEEE International Conference on Neural Networks, 2, 259- 266.
• TAKEFUJI, Y. and Szu, H. (1989) Design of parallel distributed Cauchy machines. Proceedings IEEE International Joint Conference on Neural Networks, 1, 529-532.
• TANK, D.W. an d HOPFIELD, J.J. (1986) Simple neural optimization networks: An A/D converter, signal decision circuit and a linear programming circuit. IEEE Transactions on Circuit Systems, 33, 533- 541.
• TOKUDA, I. , NAGASHIMA, T. and AIHARA, K. (1997) Global bifurcation structure of chaotic neural networks and its application to Travelling Salesman Problems. Neural Networks, 10, 1673-1690.
• VAKHUTINSKY, A.I. and GOLDEN, B.L. (1994) Solving Vehicle Routing Problems using Elastic Nets. Proceedings of the IEEE Int. Conf. On Neural Networks, 7, 4535-4540.
• VAKHUTINSKY, A.I. and GOLDEN, B.L. (1995) A Hierarchical Strategy for Solving Travelling Salesman Problems using Elastic Nets. Journal of Heuristics, 1, 67 -76.
• VAN DER Bou T, D.E. and MILLER, T.K. (1988) A Travelling Salesman Objective Function That Works. Proceedings IEEE International Conference on Neural Networks, 2, 299- 303.
• VAN DER BouT, D.E. and MILLER, T.K. (1989) Improving the Performance of the Hopfield- Tank Neural Network through Normalization and Annealing. Biological Cybernetics, 62 , 129- 139.
• VAN DER BOUT, D.E. and MILLER, T.K. (1990) Graph partitioning using annealed neural networks. IEEE Transactions on Neural Networks, 1, 192-203.
• WANG, L. and SMITH, K.A. (1998) On chaotic simulated annealing. IEEE Transactions on Neural Networks, 9, 716- 718.
• WILLSHAW, D.J. and VON DER MALSBURG, C. (1979) A Marker Induction Mechanism for the Establishment of Ordered Neural Mappings: Its Application to the Retinotectal Problem. Philosophical Transactions of the Royal Society, Series B 287, 203- 243.
• WILSON, G.V. and PAWLEY, G.S. (1988) On the stability of the TSP algorithm of Hopfield and Tank. Biological Cybernetics, 58, 63- 70.
• WOLFE, W.J. (1999) A fuzzy Hopfield-Tank traveling salesman problem model. INFORMS Journal on Computing, 11, 329-44.
• YAMADA, T., AIHARA, K. and KOTANI, M. (1993) Chaotic neural networks and the Travelling Salesman Problem. Proceedings of the International Joint Conference on Neural Networks, 2, 1549-1552.
• ZHOU, D., YASUDA, K. and YOKOYAMA, R. (1997) A method to combine chaos and neural network based on the fixed point theory. Transactions of the Institute of Electrical Engineers of Japan, 117-C, 599- 608.