×

A hybrid neural approach to combinatorial optimization. (English) Zbl 0847.90119

Summary: Both the Hopfield neural network and Kohonen’s principles of self-organization have been used to solve difficult optimization problems, with varying degrees of success. In this paper, a hybrid neural network is presented which combines, for the third time, a new self-organizing approach to optimization with a Hopfield network. It is demonstrated that many of the traditional problems associated with each of these approaches can be resolved when they are combined into a hybrid model. After presenting the broad class of 0-1 optimization problems for which this hybrid neural approach is suited, details of the algorithm are presented and convergence properties are discussed. This hybrid neural approach is applied to solve a practical sequencing problem from the car manufacturing industry. Performance results are compared with classical as well as other neural techniques, and conclusions are drawn.

MSC:

90C27 Combinatorial optimization
90B35 Deterministic scheduling theory in operations research
90C09 Boolean programming
92B20 Neural networks for/in biological studies, artificial life and related topics

Software:

GAMS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hopfield, J. J.; Tank, D. W., “Neural” computation of decisions in optimization problems, Biological Cybernet., 52, 141-152 (1985) · Zbl 0572.68041
[2] Tank, D. W.; Hopfield, J. J., Simple neural optimization networks: an A/D converter, signal decision circuit and a linear programming circuit, IEEE Trans. Circuit Syst., 5, 533-541 (1986)
[3] Tagliarini, G.; Page, E., Solving Constraint Satisfaction Problems with neural networks, (Proc. Int. Conf. Neural Networks III. Proc. Int. Conf. Neural Networks III, San Diego (1987)), 741-747
[4] Reklaitis, G. V.; Tsirukis, A. G.; Tenorio, M. F., Generalised Hopfield Networks and nonlinear optimization, (Touretzky, D. S., Advances in Neural Information Processing Systems 2 (1990), Morgan Kaufmann), 355-362
[5] Wilson, G. V.; Pawley, G. S., On the stability of the TSP algorithm of Hopfield and Tank, Biological Cybernet., 58, 63-70 (1988) · Zbl 0637.65062
[6] Hedge, S.; Sweet, J.; Levy, W., Determination of parameters in a Hopfield/Tank computational network, (Proc. Int. Conf. Neural Networks II (1988), IEEE Press: IEEE Press San Diego), 291-298
[7] Kamgar-Parsi, B.; Kamgar-Parsi, B., Dynamical stability and parameter selection in neural optimization, (Proc. Int. Joint Conf. Neural Networks IV (1992), IEEE Press: IEEE Press Maryland), 566-571 · Zbl 0687.68031
[8] Lai, W. K.; Coghill, G. G., Genetic breeding of control parameters for the Hopfield.Tank neural net, (Proc. Int. Joint Conf. Neural Networks IV (1992), IEEE Press: IEEE Press Maryland), 618-623
[9] Brandt, R. D.; Wang, Y.; Laub, A. J.; Mitra, S. K., Alternative networks for solving the Travelling Salesman Problem and the List-Matching Problem, (Proc. Int. Conf. Neural Networks II (1988), IEEE Press: IEEE Press San Diego), 333-340
[10] Van den Bout, D. E.; Miller, T. K., A Travelling Salesman objective function that works, (Proc. Int. Conf. Neural Networks II (1988), IEEE Press: IEEE Press San Diego), 299-303
[11] Gee, A. H.; Prager, R. W., Limitations of neural networks for solving Traveling Salesman Problems, IEEE Trans. Neural Networks, 6, 280-282 (1995)
[12] Kohonen, T., Self-organized formation of topologically correct feature maps, Biological Cybernet., 43, 59-69 (1982) · Zbl 0466.92002
[13] Fang, L.; Li, T., Design of competition-based neural networks for combinatorial optimization, Int. J. Neural Syst., 1, 221-235 (1990)
[14] Angéniol, B.; De La Croix, G.; Le Texier, J-Y., Self organizing feature maps and the Travelling Salesman Problem, Neural Networks, 1, 289-293 (1988)
[15] Favata, F.; Walker, R., A study of the application of Kohonen-type neural networks to the Travelling Salesman Problem, Biological Cybernet., 64, 463-468 (1991) · Zbl 0722.92002
[16] Fort, J. C., Solving a combinatorial problem via self-organizing process: an application of the Kohonen algorithm to the Traveling Salesman Problem, Biological Cybernet., 59, 33-40 (1988) · Zbl 0641.92020
[17] Durbin, R.; Willshaw, D., An analogue approach to the travelling salesman problem using an elastic net method, Nature, 326, 689-691 (1987)
[18] Kohonen, T., Self-organization and Associative Memory (1984), Springer: Springer Berlin · Zbl 0528.68062
[19] Ritter, H.; Schulten, K., Convergence properties of Kohonen’s topology conserving maps: fluctuations, stability, and dimension selection, Biological Cybernet., 60, 59-71 (1988) · Zbl 0653.92026
[20] Cottrell, M.; Fort, J. C., A stochastic model of retinotopy: a self-organizing process, Biological Cybernet., 53, 166-170 (1986) · Zbl 0605.92001
[21] Hopfield, J. J., Neurons with graded response have collective computational properties like those of two-state neurons, (Proc. Natl Acad Sci. U.S.A., 81 (1984)), 3088-3092 · Zbl 1371.92015
[22] Parretto, B. D.; Kabat, W.; Wos, L., Jobshop scheduling using automated reasoning: a case study of the car sequencing problem, J. Automated Reasoning, 2, 1-42 (1986)
[23] Hackman, S. T.; Magazine, M.; Wee, T., Fast effective algorithms for simple assembly line balancing problems, Ops Res., 37, 916-924 (1989) · Zbl 0689.90047
[24] McCormick, S. T.; Pinedo, M.; Shenker, S.; Wolf, B., Sequencing in an assembly line with blocking to minimize cycle time, Ops Res., 37, 925-935 (1989) · Zbl 0689.90048
[25] Brooke, A.; Kendrick, D.; Meeraus, A., GAMS—A User’s Guide (1990), Scientific Press: Scientific Press California
[26] Gee, A. H., Problem solving with optimization networks, (Ph.D. thesis (1993), Queen’s College: Queen’s College Cambridge, U.K)
[27] Smith, K.; Krishnamoorthy, M.; Palaniswami, M., Traditional heuristic versus Hopfield network approaches to a Car Sequencing Problem, CSIRO DMS Technical Report: DMS-C94/64 (1994) · Zbl 0912.90165
[28] Botros, N.; Abdul-Aziz, M., Hardware implementation of an artificial neural network using field programmable gate arrays (FPGA’s), IEEE Trans. Ind. Electron., 41, 6, 665-667 (1994)
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.