|
DOI: 10.14489/vkit.2016.04.pp.003-010
Дроговоз П. А., Садовская Т. Г., Шиболденков В. А.
РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА ПОСРЕДСТВОМ ОДНОМЕРНОЙ САМООРГАНИЗУЮЩЕЙСЯ КАРТЫ КОХОНЕНА
(c. 3-10)
Аннотация. Рассмотрены возможность применения одномерной самоорганизующейся карты Кохонена для решения проблемы коммивояжера, ее механизм функционирования и практические аспекты применения особенных свойств. Показаны традиционные, часто употребляемые методы решения задачи, их особенности и отличия от способа нейрокартирования. Проведен анализ свойств «хороших» решений для составления механизма выбора подмножества оптимальных решений и даны оценка влияния топологических особенностей карты, ее размера и структуры соседства на результат. Проведено сравнение нейросетевого подхода с другими алгоритмами для решения задачи коммивояжера и представлены результаты статистического анализа исходов. Рассмотренны процесс работы с нитевидной и кольцевой архитектурами карты, а также временная и программная сложность алгоритма. Приведено описание концепции упругой сетки и использования коэффициентов упругости.
Ключевые слова: самоорганизующаяся карта Кохонена; искусственная нейронная сеть; интеллектуальный анализ данных; задача коммивояжера.
Drogovoz P. A., Sadovskaya T. G., Shiboldenkov V. A.
THE SOLUTION OF THE TRAVELLIHG SALESMAN PROBLEM THROUGH ONE-DIMENSIONAL KOHONEN SELF-ORGANIZING MAP
(pp. 3-10)
Abstract. In this paper examines the possibility of using one-dimensional Kohonen self-organizing map to solve the travelling salesman problem. Considers the traditional, most frequently used methods of solving the tasks, their characteristics and differences from the method of neuromapping. Analyzes the properties of «good» solutions, for drawing up the mechanism of selecting a subset of optimal solutions. Examines the mechanism of functioning of a Kohonen self-organizing map when solving the traveling salesman problem and the practical aspects of the use of its special properties. Elaborated the influence of topological features of the card, its size and structure, neighbourhood on the result. Discusses the process of working with filamentous and ring architecture of the card. Describes the concept of elastic mesh and use the coefficients of elasticity. Elaborated a comparison of neural network approach with other algorithms for solving the travelling salesman problem, and presents the results of the statistical analysis of outcomes. Considered temporary and software the complexity of the algorithm.
Keywords: Self-organizing map of Kohonen; Artificial neural network; Data mining; Travelling salesman problem.
П. А. Дроговоз, Т. Г. Садовская, В. А. Шиболденков (Московский государственный технический университет им. Н. Э. Баумана) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
P. A. Drogovoz, T. G. Sadovskaya, V. A. Shiboldenkov (Bauman Moscow State Technical University) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
1. Мудров В. И. Задача о коммивояжере. М.: Либроком, 2013. 64 с.
2. Моргунов И. Б. Разработка математической модели выбора оптимального маршрута // Вестник УГАТУ. 2008. T. 11, № 1(28). C. 194 – 199.
3. Хаггарти Р. Дискретная математика для программистов / пер. с англ. 2-е изд. М.: Техносфера, 2005. 400 с.
4. Макаркин С. Б., Мельников Б. Ф. Адекватность математических моделей на примере задачи коммивояжера [Электронный ресурс] // Философские проблемы информационных технологий и киберпространства: электрон. журн. 2013. № 2. С. 4 – 17. URL: http:// cyberspace. pglu.ru/issues/detail.php?ELEMENT_ID=1328 (дата обращения: 18.10.2015).
5. Борознов В. О. Исследование решения задачи коммивояжера // Вестник Астраханского гос. техн. ун-та. Сер. Управление, вычислительная техника и информатика. 2009. № 2. С. 147 – 151.
6. Щербина О. А. Метаэвристические алгоритмы для задач комбинаторной оптимизации (обзор) // Таврический вестник математики и информатики. 2014. № 1(24). С. 56 – 72.
7. Малыхина М. П., Частикова В. А., Власов К. А. Исследование эффективности работы модифицированного генетического алгоритма в задачах комбинаторики // Современные проблемы науки и образования. 2013. № 3. С. 32.
8. Частикова В. А., Власов К. А. Разработка и сравнительный анализ эвристических алгоритмов для поиска наименьшего гамильтонова цикла в полном графе // Фундаментальные исследования. 2013. № 10. С. 63 – 67.
9. Басараб М. А., Вельц С. В. Иерархическое представление компьютерной сети на основе нейронной сети Хопфилда // Наука и образование: электрон. науч.-техн. изд. 2013. № 9. С. 335 – 348. URL: http://cyberleninka.ru/article/n/ierarhicheskoe-predstavlenie-kompyuternoy-seti-na-osnove-neyronnoy-seti-hopfilda (дата обращения: 18.10.2015).
10. Савченко О. В., Куреннов Д. В. Система управления роботом на основе конечного автомата и нейронной сети // Вестник УГАТУ. 2014. № 5. С. 192 – 196.
11. Колесников К. В., Карапетян А. Р., Курков А. С. Нейросетевые модели оптимизации маршрутов доставки данных в динамических сетях // Международный научный журнал. 2015. № 6. С. 1 – 9.
12. Зиновьев А. Ю. Визуализация многомерных данных. Красноярск: Изд-во КГТУ, 2000. 180 c.
13. Хайкин С. Нейронные сети: полный курс. 2-е издание. М.: Вильямс, 2006. 1104 с.
14. Разработка нейросетевых инструментов интеллектуального анализа экономических показателей / П. А. Дроговоз и др. // Аудит и финансовый анализ. 2015. № 3. С. 431 – 440.
15. Ревотюк М. П., Кот О. В. Реоптимизация решения задач коммивояжера методом эластичных сетей / Материалы Междунар. науч. конф. Минск, Беларусь, 26 октября 2011 г. Минск: БГУИР, 2011. C. 246 – 247.
16. Гавенко С. С., Светличная В. А. Оптимизация обслуживающих работ на основе метаэвристических технологий / Информационные управляющие системы и компьютерный мониторинг: материалы III Всеукраинской конф. г. Донецк, Украина, 16 – 18 апреля 2012 г. Донецк: ДонНТУ, 2012. Т. 1. С. 275 – 279.
17. Покидышева Л. И., Веретнова К. Ю. Главные многообразия для анализа и визуализации финансовых данных // Международный научно-исследовательский журнал. 2013. № 8 – 2 (15). С. 51 – 56.
1. Mudrov V. I. (2013). The problem of the traveling salesman. Moscow: Librokom.
2. Morgunov I. B. (2008). Development of a mathematical model of selecting an optimal route. Vestnik UGATU, Vol. 11, 28(1), pp. 194-199.
3. Haggarty R. (2005). Discrete mathematics for computing. 2nd (Ed.). Moscow: Tekhnosfera.
4. Makarkin S. B., Mel'nikov B. F. (2013). The adequacy of mathematical models on example of the traveling salesman problem. Filosofskie problemy informatsionnykh tekhnologii i kiberprostranstva, (2), pp. 4 – 17. Available at: http://cyberspace.pglu.ru/issues/detail.php?ELEMENT_ID=1328 (Accessed: 18.10.2015).
5. Boroznov V. O. (2009). Studying the problem of the traveling salesman. Vestnik Astrakhanskogo gosudarstvennogo tekhnicheskogo universiteta. Seriia: Upravlenie, vychislitel'naia tekhnika i informatika, (2), pp. 147-151.
6. Shcherbina O. A. (2014). Metaheuristic algorithms for combinatorial optimization problems (review). Tavricheskii vestnik matematiki i informatiki, 24(1), pp. 56-72.
7. Malykhina M. P., Chastikova V. A., Vlasov K. A. (2013). Study the effectiveness of the modified genetic algorithms in combinatorial problems. Sovremennye problemy nauki i obrazovaniia, (3), p. 32.
8. Chastikova V. A., Vlasov K. A. (2013). Development and comparative analysis of heuristic algorithms for finding the smallest Hamiltonian cycle in a complete graph. Fundamental'nye issledovaniia, (10), pp. 63-67.
9. Basarab M. A., Vel'ts S. V. (2013). Hierarchical view of a computer network based on the Hopfield neural network. Nauka i obrazovanie, (9), pp. 335-348. Available at: http://cyberleninka.ru/article/n/ierarhicheskoe-predstav-lenie-kompyuternoy-seti-na-osnove-neyronnoy-seti-hopfilda (Accessed: 18.10.2015).
10. Savchenko O. V., Kurennov D. V. (2014). Robot control system based on finite automate and neural network. Vestnik UGATU, (5), pp. 192-196.
11. Kolesnikov K. V., Karapetian A. R., Kurkov A. S. (2015). Neural network models for optimizing delivery routes of data in dynamic networks. Mezhdunarodnyi nauchnyi zhurnal, (6), pp. 1-9.
12. Zinov'ev A. Iu. (2000). Visualization of multivariate data. Krasnoiarsk: Izdatel'stvo KGTU.
13. Khaikin S. (2006). Neural networks: complete course. 2nd (Ed.). Moscow: Williams.
14. Drogovoz P. A. et al. (2015). Development of neural network tools of intellectual analysis of economic indicators. Audit i finansovyi analiz, (3), pp. 431-440.
15. Revotiuk M. P., Kot O. V. (2011). Optimization of solving the traveling salesman problems using elastic networks method. Proceedings of the International scientific conference. 26 October 2011. Minsk, Belarus, (pp. 246-247). Minsk: BGUIR.
16. Gavenko S. S., Svetlichnaia V. A. (2012). Optimization of maintenance work on the basis of meta heuristic methods. Information control systems and computer monitoring: proceedings of the III All-Ukranian conference, 16-18 April 2012. Donetsk. Ukraine, Vol. 1, (pp. 275-279), Donetsk: DonNTU.
17. Pokidysheva L. I., Veretnova K. Iu. (2013). The main varieties for the analysis and visualization of financial data. Mezhdunarodnyi nauchno-issledovatel'skii zhurnal, 15(8-2), pp. 51-56.
Статью можно приобрести в электронном виде (PDF формат).
Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.
После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.
Для заказа статьи заполните форму:
{jform=1,doi=10.14489/vkit.2016.04.pp.003-010}
.
This article is available in electronic format (PDF).
The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.
After depositing your payment on our bank account we send you file of the article by e-mail.
To order articles please fill out the form below:
{jform=2,doi=10.14489/vkit.2016.04.pp.003-010}
.
.
|
Архив номеров
Разработка концепции и создание сайта - ООО «Издательский дом «СПЕКТР»