Параллельный алгоритм решения задачи коммивояжера с использованием рекуррентной нейронной сети
Автор: Тарков Михаил Сергеевич, Дугаров Гэсэр Александрович
Журнал: Проблемы информатики @problem-info
Рубрика: Теоретическая информатика
Статья в выпуске: 2 (6), 2010 года.
Бесплатный доступ
Предложен параллельный алгоритм решения задачи коммивояжера, основанный на применении ре- куррентной сети Вана с использованием принципа WTA (winner takes all). Данный алгоритм суще- ственно превосходит метод ветвей и границ по быстродействию и предпочтителен при решении задачи коммивояжера с требуемой точностью в реальном масштабе времени.
Задача коммивояжера, рекуррентная нейронная сеть, метод ветвей и границ, параллельные алгоритмы
Короткий адрес: https://sciup.org/14320024
IDR: 14320024
Список литературы Параллельный алгоритм решения задачи коммивояжера с использованием рекуррентной нейронной сети
- Романовский И. В. Алгоритмы решения экстремальных задач. М.: Наука, 1977. 352 с.
- Little J., Murty K., Sweeney D., Karel C. An algorithm for the traveling salesman problem//Oper. Res. 1963. V. 11. P. 972.
- Посыпкин М. А. Параллельные алгоритмы в задачах дискретной оптимизации: вычислительные модели, библиотека, результаты экспериментов/М. А. Посыпкин, И. Х. Сигал, Н. Н. Галимьянова. М.: ВЦ им. А. А. Дородницына РАН, 2006. 52 с.
- Осовский С. Нейронные сети для обработки информации. М.: Финансы и статистика, 2002. 344 с.
- Хайкин С. Нейронные сети: Полный курс. М.: Вильямс, 2006. 1104 с.
- Тарков М. С. Нейрокомпьютерные системы. М.: Интернет ун-т информ. технологий: Бином: Лаб. знаний, 2006. 142 с.
- Меламед И. И. Нейронные сети и комбинаторная оптимизация//Автоматика и телемеханика. 1994. №4. С. 3-40.
- Smith K. A. Neural networks for combinatorial optimization: a review of more than a decade of research//Informs J. Comput. 1999. V. 11, N 1. P. 15-34.
- Feng G., Douligeris C. The convergence and parameter relationship for discrete-time continuous-state hopfield networks//Proc. of the Intern. joint conf. on neural networks, Washington, USA, July 15-19, 2001. N. Y.: IEEE, 2001. V. 1. P. 376-381.
- Hung D. L., Wang J. Digital hardware realization of a recurrent neural network for solving the assignment problem//Neurocomputing. 2003. N 51. P. 447-461.
- Siqueira P. H., Steiner M. T. A., Scheer S. A new approach to solve the traveling salesman problem//Neurocomputing. 2007. N 70. P. 1013-1021.
- Тарков М. С. О построении гамильтоновых циклов в графах распределенных вычислительных систем рекуррентной нейронной сетью//Тр. 10-й Всерос. науч.-техн. конф. "Нейроинформатика-2008". Москва, 22-25 янв. 2008. М.: Изд-во МИФИ, 2008. Ч. 2. С. 76-85.
- Bianchi L., Knowles J., Bowler J. Local search for the probabilistic traveling salesman problem: Correction to the 2-opt and 1-shift algorithms//Eur. J. Oper. Res. 2005. V. 162, N 1. P. 206-219.
- Reinelt G. TSPLIB -a traveling salesman problem library//ORSA J. Comput. 1991. V. 3, N 4. P. 376-384.
- Нейрокомпьютеры в космической технике/Под ред. В. В. Ефимова. М.: Радиотехника, 2004. Кн. 17. 320 с. (Cер. "Нейрокомпьютеры и их применение").
Статья научная
