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

OPTIMAL PARAMETERS OF KOHONEN SELF-ORGANIZING MAP FOR SOLVING TRAVELLING SALESMAN PROBLEM

Ihar Niakhai

Student, Belarusian State University of Informatics and Radioelectronics, Belarus, Minsk

Natalya Egorova

Scientific director, Cand. tech. sciences, associate professor, Belarusian State University Informatics and Electronics, Republic of Belarus, Minsk

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

Abstract. This article describes influence of Kohonen SOM configuration on results of solving travelling salesman problem. Optimal parameters ranges were found in order to allow Kohonen SOM to achieve optimal results.

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

Keywords: TSP; Kohonen; SOM.

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

Непосредственно для решения задачи используется 1D Kohonen SOM, работа которого подчиняется алгоритму, описанному в [1, c. 2]. Алгоритм выполняется заданное число итераций и выглядит для каждой итерации следующим образом:

1) Выбирается случайный город из списка.

2) Перебираются все нейроны и находится нейрон-победитель, который ближе всех находится к городу (используется евклидово расстояние).

3) Вычисляются нейроны-соседи победителя (в зависимости от текущего значения коэффициента соседства η).

4) Обновляются веса нейронов-соседей (в зависимости от текущего коэффициента обучения λ).

5) Уменьшаются коэффициенты обучения λ и соседства η на заданные величины Δλ и Δη.

Таким образом, для решения задачи коммивояжёра необходимо задать следующие 4 параметра: начальные коэффициенты обучения λ и соседства η, а также шаги их изменения Δλ и Δη соотвественно. Все данные параметры изменяются на интервале (0, 1). Кроме этого, используется дополнительный параметр M, который является множителем для количества нейронов в сети. В работе [1, c. 4] данный параметр принимался равным 1, в то время как в последующей работе [2, c. 2] использовалось значение, равное 8. В общем случае данный коэффициент может принимать любые значения на интервале [1, +∞);

Для различных параметров сети было проведено тестирование полученной сети Кохонена на различных задачах из бенчмарка TSPLIB, предоставляемых университетом Ватерлоо в Канаде. По результатам тестирования были сделаны следующие выводы:

1. На задачах с небольшим числом городов (менее 75) для достижения большей точности результата нужно выполнять больше запусков SOM, так как результаты на небольших картах будут сильнее отличаться в зависимости от случайной инициализации сети и процедуры выбора случайного нейрона.

2. Оптимальное значение коэффициента M на задачах до 1000 городов составляет 2. На задачах больших размерностей возможно повышение коэффициента до 8, дальнейшее повышение негативно влияет на точность сети.

3. Изменение коэффициента η в сторону снижения положительно влияет на результат. Наилучшие результаты, как правило, показывает η около 0.5 – 0.8. Сильное снижение (ниже 0.5) или увеличение (более 0.8) заметно снижают точность полученного результата.

4. Относительный размер ошибки сети растёт с увеличением числа городов в задаче, вне зависимости от её конфигурации.

5. Оптимальные начения шагов изменения коэффициентов Δλ и Δη находятся в диапазоне 0.99 – 0.9999.

На основании полученных результатов сделан вывод о том, что самоорганизующиеся карты Кохонена отлично подходят для решения задач с числом городов менее 1000, при условии задания коэффициентов в вышеуказанных диапазонах. Для решения задач с большим числом городов сети Кохонена подходят слабо, ввиду того, что заметно растёт размер относительной ошибки.