×

A review of Hopfield neural networks for solving mathematical programming problems. (English) Zbl 1176.90617

Summary: The Hopfield neural network (HNN) is one major neural network (NN) for solving optimization or mathematical programming (MP) problems. The major advantage of HNN is in its structure can be realized on an electronic circuit, possibly on a VLSI (very large-scale integration) circuit, for an on-line solver with a parallel-distributed process. The structure of HNN utilizes three common methods, penalty functions, Lagrange multipliers, and primal and dual methods to construct an energy function. When the function reaches a steady state, an approximate solution of the problem is obtained. Under the classes of these methods, we further organize HNNs by three types of MP problems: linear, non-linear, and mixed-integer. The essentials of each method are also discussed in details. Some remarks for utilizing HNN and difficulties are then addressed for the benefit of successive investigations. Finally, conclusions are drawn and directions for future study are provided.

MSC:

90C35 Programming involving graphs or networks

Software:

TSPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abe, S., Global convergence and suppression of spurious states of the Hopfield neural networks, IEEE Transactions on Circuits Systems, 40, 246-257 (1993) · Zbl 0800.94229
[2] Ackley, D. H.; Hinton, G. E.; Sejnowski, T. J., A learning algorithm for Boltzmann machines, Cognitive Science, 9, 147-169 (1985)
[3] Aiyer, S. V.B.; Niranjan, M.; Fallside, F., A theoretical investigation into the performance of the Hopfield model, IEEE Transactions on Neural Networks, 1, 204-215 (1990)
[4] Aourid, M.; Kaminska, B., Minimization of the 0-1 linear programming problem under linear constraints by using neural networks: Synthesis and analysis, IEEE Transactions on Circuits and Systems - I: Fundamental Theory and Applications, 43, 421-425 (1996)
[5] Araújo, F.; Rebeiro, B.; Rodrigues, L., A neural network for shortest path computation, IEEE Transactions on Neural Network, 12, 1067-1073 (2001)
[6] Basheer, I. A.; Hajmeer, M., Artificial neural networks: Fundamentals, computing, design, and application, Journal of Microbiological Methods, 43, 3-31 (2000)
[7] Bazaraa, M. S.; Jarvis, J. J.; Sherali, H. D., Programming and Network Flows (2005), John-Wiley: John-Wiley New York · Zbl 1061.90085
[8] Bazaraa, M. S.; Sherali, H. D.; Shetty, C. M., Nonlinear Programming Theory and Algorithms (2006), John-Wiley: John-Wiley New York · Zbl 1140.90040
[9] Bouzerdoum, A.; Pattison, T. R., Neural network for quadratic optimization with bound constraints, IEEE Transactions on Neural Networks, 4, 293-304 (1993)
[10] Bruck, J.; San, J., A study on neural networks, International Journal of Intelligent Systems, 3, 59-75 (1988) · Zbl 0648.94023
[11] Burke, L. I.; Ignizio, J. P., Neural network and operations research: An overview, Computers and Operations Research, 19, 179-189 (1992) · Zbl 0825.90766
[12] Chen, L.; Aihara, K., Chaotic simulated annealing by a neural network model with transient chaos, Neural Networks, 8, 915-930 (1995)
[13] Chong, E. K.P.; Hui, S.; Żak, S. H., An analysis of a class of neural networks for solving linear programming problems, IEEE Transactions on Automatic Control, 44, 1995-2006 (1999) · Zbl 0957.90087
[14] Cichocki, A.; Unbehauen, R., Neural Networks for Optimization and Signal Processing (1993), John Wiley: John Wiley New York · Zbl 0824.68101
[15] Croes, G. A., A method for solving traveling salesman problems, Operations Research, 6, 791-812 (1958) · Zbl 1414.90303
[16] da Silva, I. N.; Amaral, W. C.; Arruda, L. V.R., Neural approach for solving several types of optimization problems, Journal of Optimization Theory and Applications, 128, 563-580 (2006) · Zbl 1112.90106
[17] Dillon, J. D.; O’Malley, M. J., A Lagrangian augmented Hopfield network for mixed integer non-linear programming problems, Neurocomputing, 42, 323-330 (2002) · Zbl 1015.68147
[18] Du, K. L.; Swamy, M. N.S., Neural Networks in a Softcomputing Framework (2006), Springer: Springer London, UK · Zbl 1101.68757
[19] Durbin, R.; Willshaw, D., An analogue approach to the traveling salesman problem using an elastic net method, Nature, 326, 689-691 (1987)
[20] Effati, S.; Baymain, M., A new nonlinear neural network for solving convex nonlinear programming problems, Applied Mathematics and Computation, 168, 1370-1379 (2005) · Zbl 1081.65054
[21] El-Bouri, A.; Balakrishnan, S.; Popplewell, N., A neural network to enhance local search in the permutation flowshop, Computers and Industrial Engineering, 49, 182-196 (2005)
[22] Gee, A. H.; Prager, R. W., Limitations of neural networks for solving travelings salesman problems, IEEE Transactions on Neural Networks, 6, 280-282 (1995)
[23] Gill, P. E.; Murray, W.; Wright, M. H., Practical Optimization (1981), Academic: Academic London · Zbl 0503.90062
[24] Gong, D.; Gen, M.; Yamazaki, G.; Xu, W., Lagrangian ANN for convex programming with linear constraints, Computers and Industrial Engineering, 32, 429-443 (1997)
[25] Hagan, M. T.; Demuth, H. B.; Beale, M., Neural Network Design (1996), PWS Publishing Co: PWS Publishing Co Massachusetts
[26] Ham, F. M.; Kostanic, I., Principles of Neurocomputing for Science and Engineering (2001), McGraw-Hill: McGraw-Hill New York
[27] Hasam, G.-O.; Nezam, M.-A., An efficient simplified neural network for solving linear and quadratic programming problems, Applied Mathematics and Computation, 175, 452-464 (2006) · Zbl 1093.65061
[28] Haykin, S., Neural Networks: A Comprehensive Foundation (1999), Prentice-Hall: Prentice-Hall New Jersey · Zbl 0934.68076
[29] Hopfield, J. J., Neural networks and physical systems with emergent collective computational abilities, Proceedings of the National Academy of Sciences, 79, 2554-2558 (1982) · Zbl 1369.92007
[30] Hopfield, J. J., Neurons with graded response have collective computational properties like those of two-state neurons, Proceedings of the National Academy of Sciences, 81, 3088-3092 (1984) · Zbl 1371.92015
[31] Hopfield, J. J., Artificial neural networks, IEEE Circuits and Devices Magazine, September, 3-10 (1988)
[32] Hopfield, J. J.; Tank, D. W., Neural computation of decisions in optimization problems, Biological Cybernetics, 52, 141-152 (1985) · Zbl 0572.68041
[33] Kamgar-Parsi, Behzad; Kamgar-Parsi, Behrooz, On problem solving with Hopfield neural networks, Biological Cybernet, 62, 415-423 (1990) · Zbl 0687.68031
[34] Kennedy, M. P.; Chua, L. O., Neural networks for nonlinear programming, IEEE Transportation Circuits System, 35, 554-562 (1988)
[35] Klimasauskas, C. C., Neural networks: A new technology for information processing, Data Base, 20, 21-23 (1989)
[36] Kohonen, T., Self-organized formation of topologically correct feature maps, Biological Cybernetics, 43, 59-69 (1982) · Zbl 0466.92002
[37] Kumar, S., 2005. Neural Networks: A Classroom Approach. International Edition, McGraw-Hill, Singapore.; Kumar, S., 2005. Neural Networks: A Classroom Approach. International Edition, McGraw-Hill, Singapore.
[38] Kurita, N.; Funahashi, K., On the Hopfield neural networks and mean field theory, Neural Networks, 9, 1531-1540 (1996) · Zbl 0869.68080
[39] Lan, K. M.; Wen, U. P.; Shih, H. S.; Lee, E. S., A hybrid neural network approach to bilevel programming, Applied Mathematics Letters, 20, 8, 880-884 (2007) · Zbl 1162.90514
[40] Li, S. Z., Improving convergence and solution quality of Hopfield-type neural networks with augmented Lagrange multipliers, IEEE Transactions on Neural Networks, 7, 1507-1516 (1996)
[41] Lin, C. L.; Lai, C. C.; Huang, T. H., A neural network for linear matrix inequality problems, IEEE Transactions on Neural Networks, 11, 1078-1092 (2000)
[42] Looi, C. K., Neural network methods in combinatorial optimization, Computers and Operations Research, 19, 3/4, 191-208 (1992) · Zbl 0757.90069
[43] Maa, C. Y.; Shanblatt, M. A., Linear and quadratic programming neural network analysis, IEEE Transaction on Neural Networks, 3, 380-394 (1992)
[44] Malek, A.; Tari, A., Primal-dual solution for the linear programming problems using neural networks, Applied Mathematics and Computation, 167, 198-211 (2005) · Zbl 1079.65069
[45] Martı´n-Valdivia, M.; Ruiz-Sepúlveda, A.; Triguero-Ruiz, F., Improving local minima of Hopfield networks with augmented Lagrange multipliers for large scale TSPs, Neural Networks, 13, 283-285 (2000)
[46] Méida-Casermeiro, E.; Galán-Marı´n, G.; Muñoz-Peréz, J., An efficient multivalued Hopfield network for the traveling salesman problem, Neural Processing Letters, 14, 203-216 (2001) · Zbl 0994.90121
[47] Munehisa, T.; Kobayashi, M.; Yamazaki, H., Cooperative updating in the Hopfield model, IEEE Transactions on Neural Networks, 12, 1243-1251 (2001)
[48] Nygard, K. E.; Jueli, P.; Kadaba, N., Neural networks for selecting vehicle routing heuristic, ORSA Journal of Computing, 2, 353-364 (1990) · Zbl 0825.90363
[49] Papageorgiou, G.; Likas, A.; Stafylopatis, A., Improved exploration in Hopfield network state-space through parameter perturbation driven by simulated annealing, European Journal of Operations Research, 108, 283-292 (1998) · Zbl 0957.90019
[50] Pavlik, P., Parallel Hopfield machine, Neurocomputing, 4, 89-91 (1992)
[51] Peng, M. K.; Gupta, N. K.; Armitage, A. F., An investigation into the improvement of local minima of the Hopfield network, Neural Networks, 9, 1241-1253 (1996)
[52] Qu, H.; Yi, Z.; Tang, H., Improving local minima of columnar competitive model for TSPs, IEEE Transactions on Circuit and Systems I, 53, 1353-1362 (2006) · Zbl 1374.90326
[53] Reinelt, G., TSPLIB - A traveling salesman problem library, ORSA Journal on Computing, 3, 376-384 (1991) · Zbl 0775.90293
[54] Ricanek, K., Lebby, G.L., Haywood, K., 1999. Hopfield like networks for pattern recognition with application to face recognition. In: International Joint Conference on Neural Network, vol. 5, pp. 3265-3269.; Ricanek, K., Lebby, G.L., Haywood, K., 1999. Hopfield like networks for pattern recognition with application to face recognition. In: International Joint Conference on Neural Network, vol. 5, pp. 3265-3269.
[55] Rodrı´guez-Vázquez, A.; Domı´nguez-Castro, R.; Rueda, A.; Huertas, J. L.; Sánchez-Sinencio, E., Switched-capacitor neural networks for linear programming, Electronics Letters, 24, 496-498 (1988)
[56] Rodrı´guez-Vázquez, A.; Domı´nguez-Castro, R.; Rueda, A.; Huertas, J. L.; Sánchez-Sinencio, E., Nonlinear switched-capacitor ‘neural networks’ for optimization problems, IEEE Transactions on Circuits Systems, 37, 384-397 (1990)
[57] Sexton, R. S.; Aldaee, B.; Dorsey, R. E.; Johnson, J. D., Global optimization for artificial neural networks: A tabu search application, European Journal of Operational Research, 106, 570-584 (1998) · Zbl 0991.90139
[58] Sexton, R. S.; Dorsey, R. E.; Johnson, J. D., Optimization of neural networks: A comparative analysis of the genetic algorithm and simulated annealing, European Journal of Operational Research, 114, 589-601 (1999) · Zbl 0938.90069
[59] Sharda, R., Neural networks for the MS/OR analyst: An application bibliography, Interfaces, 24, 116-130 (1994)
[60] Shih, H. S.; Wen, U. P.; Lee, E. S.; Lan, K. M.; Hsiao, H. C., A neural network approach to multiobjective and multilevel programming problems, Computers and Mathematics with Applications, 48, 95-108 (2004) · Zbl 1062.90060
[61] Shirazi, B., Yih, S., 1989. Critical analysis of applying Hopfield neural net model to optimization problems. In: IEEE International Conference on Systems, Man and Cybernetics, vol. 1, 14-17 November, pp. 210-215.; Shirazi, B., Yih, S., 1989. Critical analysis of applying Hopfield neural net model to optimization problems. In: IEEE International Conference on Systems, Man and Cybernetics, vol. 1, 14-17 November, pp. 210-215.
[62] Silva, I. N.; Amaral, W. C.; Arruda, L. V., Design and analysis of an efficient neural network model for solving nonlinear optimization problems, International Journal of Systems Science, 36, 833-843 (2005) · Zbl 1126.90406
[63] Sima, J., Orponen, P., 2001. A Computational Taxonomy and Survey of Neural Network Models. Available from: <http://citeseer.ist.psu.edu/sima01computational.html>; Sima, J., Orponen, P., 2001. A Computational Taxonomy and Survey of Neural Network Models. Available from: <http://citeseer.ist.psu.edu/sima01computational.html>
[64] Smith, K. A., Neural networks for combinatorial optimization: A review on more than a decade of research, INFORMS Journal on Computing, 11, 15-34 (1999) · Zbl 1034.90528
[65] Smith, K. A.; Gupta, J. N.D., Neural networks in business: Techniques and applications for the operations research, Computers and Operations Research, 27, 1023-1044 (2000) · Zbl 0961.90016
[66] Smith, K.; Palaniswami, M.; Krishnamoorthy, M., Traditional heuristic versus Hopfield neural network approaches to a car sequencing problem, European Journal of Operational Research, 93, 300-316 (1996) · Zbl 0912.90165
[67] Smith, K.; Palaniswami, M.; Krishnamoorthy, M., Neural techniques for combinatorial optimization with applications, IEEE Transactions on Neural Networks, 9, 1301-1318 (1998)
[68] Takahashi, Y., Mathematical improvement of the Hopfield model for TSP feasible solutions by synapse dynamic systems, IEEE Transactions on Systems, Man, and Cybernetics, Part B, 28, 906-919 (1998)
[69] Takahashi, Y., A neural network theory for constrained optimization, Neurocomputing, 24, 117-161 (1999) · Zbl 0922.68097
[70] Talaván, P. M.; Yáñez, J., Parameter setting of the Hopfield network applied to TSP, Neural Networks, 15, 363-373 (2002)
[71] Tan, K. C.; Tang, H.; Ge, S. S., On parameter settings of Hopfield networks applied to traveling salesman problems, IEEE Transactions on Circuits and Systems - I, 52, 994-1002 (2005) · Zbl 1374.82025
[72] Tank, D. W.; Hopfield, J. J., Simple ‘neural’ optimization networks: An A/D converter, signal decision network and a linear programming circuit, IEEE Transactions on Circuits Systems, 33, 533-541 (1986)
[73] Walsh, M. P.; Flynn, M. E.; O’Malley, M. J., Augmented Hopfield network for mixed integer programming, IEEE Transactions on Neural Networks, 10, 456-458 (1998)
[74] Wang, J., Analogue neural network for solving the assignment problem, Electronics Letters, 28, 1047-1050 (1992) · Zbl 0775.93034
[75] Wang, J., Analysis and design of a recurrent neural network for linear programming, IEEE Transactions on Circuits and Systems - I: Fundamental Theory and Applications, 40, 613-618 (1993) · Zbl 0807.90083
[76] Wang, J., A recurrent neural network for solving the shortest path problem, IEEE Transactions on Circuits and Systems - I: Fundamental Theory and Applications, 43, 482-486 (1996)
[77] Wang, J., Primal and dual assignment networks, IEEE Transactions on Neural Networks, 8, 784-790 (1997)
[78] Wang, J., Primal and dual neural networks for shortest-path routing, IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 28, 864-869 (1998)
[79] Watta, P. B.; Hassoun, M. H., A coupled gradient network approach for static and temporal mixed-integer optimization, IEEE Transactions on Neural Networks, 7, 578-593 (1996)
[80] Widrow, B.; Rumelhart, D. E.; Lehr, M. A., Neural networks: Applications in industry, business and science, Communication of the ACM, 37, 93-105 (1994)
[81] Wilson, G. V.; Pawley, G. S., On the stability of the traveling salesman problem algorithm of Hopfield and Tank, Biological Cybernetics, 58, 63-70 (1988) · Zbl 0637.65062
[82] Wilson, R. L.; Sharda, R., Neural networks, OR/MS Today, 19, 36-42 (1992)
[83] Wong, B. K.; Lai, V. S.; Lam, J., A bibliography of neural networks in business: Techniques and applications research: 1994-1998, Computers and Operations Research, 27, 1045-1076 (2000) · Zbl 0961.90001
[84] Wu, A. I.; Tam, P. K.S., A neural network methodology and strategy of quadratic optimization, Neural Computing and Applications, 8, 283-289 (1999)
[85] Wu, X. Y.; Xia, Y. S.; Li, J.; Chen, W. K., A high-performance neural network for solving linear and quadratic programming problems, IEEE Transactions on Neural Network, 7, 643-651 (1996)
[86] Xia, Y., A new neural network for solving linear programming and its application, IEEE Transactions on Neural Networks, 7, 525-529 (1996)
[87] Xia, Y.; Wang, J., Neural network for solving linear programming problem with bound variables, IEEE Transactions on Neural Networks, 6, 515-519 (1995)
[88] Xia, Y.; Wang, J., A general methodology for designing globally convergent optimization neural networks, IEEE Transactions on Neural Networks, 9, 1331-1334 (1998)
[89] Xia, Y.; Feng, G.; Wang, J., A primal-dual neural network for online resolving constrained kinematic redundancy in robot motion control, IEEE Transactions on Systems Man and Cybernetics Part B - Cybernetics, 35, 54-64 (2005)
[90] Yalcinoz, T.; Short, M. J., Large-scale economic dispatch using an improved Hopfield neural network, IEE Proceedings Generation, Transmission and Distribution, 144, 181-185 (1997)
[91] Zak, S. H.; Upatising, V.; Hui, S., Solving linear programming problems with neural networks: A comparative study, IEEE Transactions on Neural Networks, 6, 94-104 (1995), The MatheWorks: <http://www.mathworks.com/>
[92] Zhang, X. S., Neural Networks in Optimization (2000), Kluwer Academic: Kluwer Academic London · Zbl 1017.90109
[93] Zhang, S.; Constantinides, A. G., Lagrange programming neural networks, IEEE Transactions on Circuits Systems, 39, 441-452 (1992) · Zbl 0758.90067
[94] Zhang, H. C.; Huang, S. H., Applications of neural networks in manufacturing: A state-of-the-art survey, International Journal of Production Research, 33, 705-728 (1995) · Zbl 0915.90143
[95] Zurada, J.M., 1992. Introduction to Artificial Neural Systems. West, New York.; Zurada, J.M., 1992. Introduction to Artificial Neural Systems. West, New York.
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.