350 rub
Journal Neurocomputers №4 for 2011 г.
Article in number:
Lowering digit capacity of matrix elements for increasing speed of binary optimization algorithm
Keywords: binary minimization quadratic functional Hopfield model neural networks discretization
Authors:
M. Yu. Malsagov
Abstract:
The goal of the paper is to make a random-search procedure used in binary minimization problems more effective. This sort of problems involves minimization of a quadratic functional built on a particular matrix in a -dimensional configurational space of states with discrete variables , . To solve binary optimization problems, neural net approaches are applied widely and quite successfully. Hopfield model is often used. In this paper, procedure of lowering digit capacity of matrix elements, called discretization, is proposed. In discretization, matrix elements are replaced by integers, which digit capacity lower than source elements; therefore, RAM requirements and algorithm speed are reduced. Zero also replaces elements near zero. Discretization procedure is described in details. Theoretical expressions of probability of local fields - coincidence in random point for matrix with uniform and normal distributions of elements are obtained. Discretization is compared with same methods. Numerous experiments verify theoretical results.
Pages: 22-32
References
  1. Hopfield, J. J., Neural Networks and physical systems with emergent collective computational abilities // Proc. Nat. Acad. Sci. USA. 1982. V. 79. P. 2554-2558.
  2. Hopfield, J. J., Tank, D. W., Neural computation of decisions in optimization problems // Biological Cybernetics. 1985. V. 52. P. 141-152.
  3. Fu, Y., Anderson, P. W., Application of statistical mechanics to NP-complete problems in combinatorial optimization // Journal of Physics A. 1986. Vol. 19. P. 1605-1620.
  4. Poggio, T., Girosi, F., Regularization algorithms for learning that are equivalent to multilayer networks // Science 247. 1990. P. 978-982.
  5. Mulder, S., Wunsch, D., A Million City Traveling Salesman Problem Solution by Divide and Conquer Clustering and Adaptive Resonance Neural Networks // Neural Networks. 2003. V. 16. № 5. P. 827-832.
  6. Kryzhanovsky, B. V., Magomedov, B. M., Mikaelyan, A. L., A Relation Between the Depth of a Local Minimum and the Probabilityof Its Detection in the Generalized Hopfield Model // Doklady Mathematics. 2005. V. 72. № 3. P. 986-990.
  7. Wu, F., Tam, P. K. S., A neural network methodology of quadratic optimization // International Journal of Neural Systems. 1999. V. 9. № 2. P. 87-93.
  8. Pinkas, G., Dechter, R., Improving Connectionist Energy Minimization // Journal of Artificial Inteligence Research. 1995. Vol. 3(195). P. 23-48.
  9. Kryzhanovsky, B., Magomedov, B., Application of domain neural network to optimization tasks // Lecture Notes in Computere Science (ICANN-2005). LNCS 3697. 2005. Part II. P. 397-403.
  10. Kryzhanovsky, B. V., Magomedov, B. M., Fonarev, A. B., On the Probability of Finding Local Minima in Optimization Problems // Proc. of Int. Joint Conf. on Neural Networks (IJCNN-2006). 2006. P. 5888-5892.
  11. Litinskii, L. B., Eigenvalue problem approach to discrete minimization // W.Duch et al. (Eds.): ICANN-2005. LNCS 3697. 2005. P. 405-410.
  12. Hartmann, A. K., Rieger, H., Optimization Algorithms in Physics // Wiley-VCH. Berlin. 2001.
  13. Smith, K. A., Neural Networks for Combinatorial Optimization: A Review of More Than a Decade of Research // INFORMS Journal on Computing. 1999. Vol. 11(1). P. 15-34.
  14. Joya, G., Atencia, M., Sandoval, F., Hopfield Neural Networks for Optimization: Study of the Different Dynamics // Neurocomputing. 2002. Vol. 43(1-4). P. 219-237.
  15. Litinskii, L. B., Magomedov, B. M., Global Minimization of a Quadratic Functional: Neural Networks Approach // Pattern Recognition and Image Analysis. 2005. Vol. 15(1). P. 80-82.
  16. Hartmann, A. K., Rieger, H., New Optimization Algorithms in Physics // Wiley-VCH. Berlin. 2004.
  17. Boettecher, S., Extremal Optimization for Sherrington-Kirkpatrick Spin Glasses // Eur. Phys. Journal B. 2005. № 46. P. 501.
  18. Крыжановский Б. В., Крыжановский В. М. О возможности ускорения процедуры бинарной оптимизации // Известия АН. Теорияисистемыуправления. 2009. №5. С. 62-68.