ЗАВИСИМОСТЬ ТОЧНОСТИ САМООРГАНИЗУЮЩЕЙСЯ КАРТЫ КОХОНЕНА ПРИ РЕШЕНИИ ЗАДАЧИ КОММИВОЯЖЁРА ОТ РАЗМЕРНОСТИ ЗАДАЧИ

DEPENDENCE OF KOHONEN SELF-ORGANIZING MAP ACCURACY OF SOLVING TRAVELLING SALESMAN PROBLEM ON PROBLEM DIMENSIONALITY

Ihar Niakhai

student, faculty of computer systems and networks, Belarusian State University of Informatics and Radioelectronics,

Belarus, Minsk

АННОТАЦИЯ

В статье исследуется влияние размерности исходной задачи на точность самоорганизующейся сети Кохонена при решении задачи коммивояжёра и даются оценки относительной точности для задач различных размерностей.

ABSTRACT

This article describes dependence of Kohonen SOM results of solving travelling salesman problem on problem dimensionality. Estimated accurasy of SOM for different TSP is provided.

Ключевые слова: задача коммивояжёра; сети Кохонена, самоорганизую-щиеся карты Кохонена.

Keywords: TSP; Kohonen; SOM.

Задача коммивояжёра заключается в поиске оптимального маршрута между заранее заданным числом городов, при котором каждый город посещается строго один раз. Эта задача является NP-полной, поэтому для получения точного решения требуются большие вычислительные мощности и временные затраты. Из-за этого для решения обычно используются приближённые алгоритмы, дающие менее точные результаты, при этом работающие очень быстро. Одним из таких подходов решения задачи является использование сети Кохонена.

Задача коммивояжёра используется в различных отраслях, таких как планирование, логистика и производство интегральных схем. Как правило, в этих отраслях решаются задачи коммивояжёра относительно большой размерности (от нескольких тысяч до миллионов городов). Использование самоорганизующихся сетей Кохонена для решения задачи коммивояжёра подобных размерностей слабо изучено, потому что как правило исследования проводятся для задач небольшой размерности (не более 50-100 городов). Ввиду этого есть необходимость оценки относительной точности нейросети Кохонена при решении задач больших размерностей, с целью определения того, может ли данная сеть использоваться для решения прикладных задач.

Непосредственно для решения задачи используется одномерная самоорганизующаяся карта Кохонена, работа которой подчиняется алгоритму, описанному в 2007 году в работе [1, c. 2]. Для оценки зависимости точности сети Кохонена, работающей по указанному алгоритму, от размерности было выбрано 6 задач из бенчмарка TSPLIB. Для данных задач было проведено тестирование сети с оптимальными параметрами конфигурации. Результаты изображены на таблице 1.

Таблица 1.

Зависимость ошибки от размерности задачи

На основании полученных данных построен график зависимости ошибки от числа городов. График изображён на рисунке 1.

Рисунок 1. Зависимость ошибки от числа городов

На основании полученных результатов, а именно графика зависимости ошибки от числа городов исходной задачи, напоминающего график логарифма, сделан вывод, что точность самоорганизующейся карты Кохонена падает с ростом размерности задачи. Даже с учётом возможности улучшения полученного результата при помощи других алгоритмов, таких как n-opt, полученной точности недостаточно для решения прикладных задач больших размерностей c большой точностью. Тем не менее, в случае решения задач небольших размерностей, самоорганизующаяся карта Кохонена позволяет получить результаты, лишь незначительно отличающиеся от оптимальных, а при необходимости получения неоптимального (до 50%) значения решения задачи большой размерности, её использование также является обоснованным.

Список литературы:

1. Danijel Koržinek, Kohonen Self-Organizing Map for the Traveling Salesperson Problem: Polish-Japanese Academy of Information Technology, 2007. – 8 c.