ПРИБЛИЖЕННОЕ РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА С ПОМОЩЬЮ АЛГОРИТМА ИМИТАЦИИ ОТЖИГА С КЛАСТЕРИЗАЦИЕЙ

ПРИБЛИЖЕННОЕ РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА С ПОМОЩЬЮ АЛГОРИТМА ИМИТАЦИИ ОТЖИГА С КЛАСТЕРИЗАЦИЕЙ

Дауирхан Мухит Берикулы

 магистрант, Университет Туран,

Республика Казахстан, г. Алматы

Ким Екатерина Романовна

канд. техн. наук, доц., Университет Туран,

Республика Казахстан, г. Алматы

Введение.

При решении задач логистики очень часто возникает проблема нахождения оптимальных маршрутов перевозки различного вида товаров в пункты потребления с обязательным условием возвращения в исходный пункт. Такие проблемы можно отнести к одной из самых популярных проблем комбинаторной оптимизации, а именно к задачам коммивояжера (или TSP от англ. Travelling salesman problem), которая состоит в нахождении наиболее выгодного маршрута через указанные города хотя бы один раз с последующим возвращением в исходный город. В критериях задачи приведены аспект рентабельности маршрута (самый дешевый, самый короткий, совокупный критерий и т. д.) И соответствующие массивы расстояний, затрат и тому подобное [1-5].

Если количество городов маленькое, то решение задачи не составит труда. Но с увеличением численности городов возникает сложность в решении задачи и необходимости применения модифицированных методов и алгоритмов решения [6-10].

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

Словесная формулировка задачи.

Обобщённая задача коммивояжёра – это задача комбинаторной оптимизации, которая считается обобщением известной задачи коммивояжёра. Начальными данными для проблемы являются большая численность узлов, разделение этого числа на так называемые кластеры и массивы затрат перехода от одного узла к другому. Задача коммивояжера – найти кратчайший замкнутый путь, который посетил бы вершину в каждом кластере (также есть улучшения, в случае если путь должен посещать хотя бы одну вершину в каждом кластере) [3, 5].

Методы решения задачи.

Для решения данной задачи существует множество различных методов, как точных, так и эвристических. Рассмотрим наиболее популярные из методов [5, 7, 10].

Алгоритм имитации отжига (англ. Simulated annealing) — артельный алгоритмический способ заключения проблемы массовой улучшения, в частности комбинаторной и дискретной оптимизации. Один из примеров способ Монте-Карло.

Методы Монте-Карло (ММК) представляют собой группу численных методов, используемых для исследования случайных процессов. Суть метода состоит из следующих процессов: развитие описывается с помощью математической модели, используя генератор случайных величин, модель вычисляется многократно, из основе полученных данных рассчитываются вероятностные характеристики рассматриваемого процесса. Например, чтобы использовать метод Монте-Карло для определения среднего расстояния между двумя случайными точками в круге, вам необходимо взять координаты большого количества случайных пар точек в данном круге и вычислить расстояние для каждой пары, а затем посчитать для них среднее арифметическое.

Кластеризация: метод k-средних. Метод k-средних представляет собой метод кластерного анализа, цель которого заключается в разделении m наблюдений на k кластеров, каждое наблюдение принадлежит кластеру, центр (центроид) которого находится ближе всего.

Евклидово расстояние используется в качестве меры близости.

Алгоритм решения задачи:

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

На функцию даем суммарную дистанцию коммивояжера. А изменение функции будет реверс случайного маршрута.

Разбор основных функций кода программы:

Посчитать Евклидово расстояние:

double dist(pair<int, int> x, pair<int, int> y);

Реверс случайного пути:

vector<int> GenerateStateCandidate(vector<int> sequence);

Если в текущем решении Коммивояжер обходит в каком-то порядке города, берем случайные города i и j, переворачиваем путь между ними.

Считает суммарную дистанцию маршрута:

double CalculateEnergy(vector<int> sequence);

Случайное первоначальное решение:

vector<int> randperm();

Вероятность проскока на не оптимальное решение в алгоритме имитации отжига, нужно для того чтобы обойти локальные минимумы:

double GetTransitionProbability(double dE, double T){

         return exp(-dE / T);

}

Переводим исполнение вероятности в bool:

bool MakeTransit(double p);

Уменьшение температуры: чем меньше температура, тем менее вероятен проскок на не оптимальное решение.

double DecreaseTemperature(double iTemp, int k);

И сам алгоритм имитации отжига для нахождения решения для задачи Коммивояжера.

void SimulatedAnnealing();

Теперь у нас есть функция, которая возвращает маршрут для одного коммивояжера. Модификация этого алгоритма для обобщенной задачи Коммивояжера решим с помощью кластеризацией k-средних.

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

Также в зависимости от того, сколько у нас путников и сколько городов они должны посетить, жадным образом с начала пути делим города на путников. Получается, для каждого путника определили города, которые они должны посетить. В конце у нас есть несколько обычных коммивояжеров со своими собственными городами, что мы уже умеем решать.

Выводы: В работе было доказано асимптотическая эффективность данного алгоритма.

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

1. Hopfield J. J., Tank D. W. Neural computation of decisions in optimization problems // Biological Cybernetics. 1985. Vol. 52. P. 141–152.
2. Durbin R., Willshaw D. An analogue approach to the traveling salesman problem using an elastic net method // Nature. 1987. Vol. 326. 689 p.
3. Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H., Teller E. J. Equations of state calculations by fast computing machines // J. Chem. Phys. 1953. Vol. 21. P. 1087–1092.
4. Ермаков С. . Метод Монте-Карло и смежные вопросы. М.: Наука, 1975. 472 с.
5. Ермаков С.М., Леора С. Н. Метод Метрополиса в задачах поиска экстремума // Математические модели. Теория и приложения. 2010. Вып. 11. С.-Петербург. C. 72–82.
6. Сердюков А. И. Задача коммивояжера на максимум в конечномерных вещественных пространствах // Дискретный анализ и исследование операций. 1995. Т. 27, № 1. C. 50–56.
7. Гимади Э. Х., Глазков Ю. В., Глебов А. Н. Алгоритмы приближенного решения задачи о двух коммивояжерах в полном графе с весами ребер 1 и 2 // Дискретный анализ и исследование операций. 2007. Сер. 2. Т. 14, № 2. C. 41–61.
8. Винклер Г. Анализ изображений, случайные поля и динамические методы Монте-Карло. Новосибирск. Изд. СО РАН, 2002. 343 с.
9. Beardwood J., Haton J. H., Hammersley J. M. The shortest path through many points // Proc. Cambridge Phil. Soc. (1959). Vol. 55. P. 299–327.
10. Товстик Т. М., Жукова Е. В. Алгоритм приближенного решения задачи коммивояжера / / Вестник СПбГУ. Сер. 1. 2013. Вып. 1.