350 руб
Журнал «Нейрокомпьютеры: разработка, применение» №4 за 2011 г.
Статья в номере:
Понижение разрядности элементов матрицы для ускорения алгоритма дискретной оптимизации
Ключевые слова: бинарная минимизация квадратичный функционал модель Хопфилда нейронные сети дискретизация
Авторы:
М. Ю. Мальсагов - аспирант, Научно-исследовательский институт системных исследований РАН (НИИСИ РАН). E-mail: Magomed.Malsagov@gmail.com
Аннотация:
Исследована задача минимизации многоэкстремального квадратичного функционала, построенного в пространстве состояний с бинарными переменными. Для ускорения вычислений локального поля предлагается дискретизировать матрицу, на которой построен функционал, заменяя ее элементы целыми числами. Процедура ориентирована на решение задач в конфигурационном пространстве высокой размерности, поскольку дискретизация матрицы уменьшает необходимый объем оперативной памяти и вычислительную сложность алгоритма. В работе рассматривались матрицы с равномерным и нормальным распределением элементов. Теоретический анализ подкреплен многочисленными экспериментами.
Страницы: 22-32
Список источников
  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.