Глава 45. Задача коммивояжёра

Переборные задачи, нацеленные на поиск оптимального варианта, называют задачами комбинаторной оптимизации.

Дадим формальную постановку задачи оптимизации. Дано конечное (обычно очень большое) множество $X$ и числовая функция $U\left(x\right)$ на этом множестве. Эту функцию называют целевой. Требуется найти такой $x_{*}\in X$, что $U\left(x_{*}\right)$ будет наименьшим, то есть $U\left(x_{*}\right)⩽U\left(x\right)$ для всех $x\in X$. Вариант постановки задачи, когда требуется найти точки максимума целевой функции, легко сводится к поиску точек минимума функции $-U$.

Задача коммивояжёра может быть поставлена как задача оптимизации. В качестве множества $X$ достаточно взять $S_n$ (множество перестановок $n$-элементного множества), а в качестве целевой функции $U\left(x\right)$ — длину замкнутой ломаной, проходящей через $n$ заданных точек в порядке, заданной перестановкой $x\in X$.

Для решения задачи поиска точки минимума функции придумано множество методов. Например, для дифференцируемых функций $U$, определённых на числовом множестве $X$, как известно, точки минимума (если они есть) следует искать среди критических точек $U$, то есть таких $x$, что $U^{\prime }\left(x\right)=0$. Однако о дифференцируемости функции, определённой на конечном множестве, к тому же не обязательно числовом, говорить не приходится, поэтому метод, основанный на критических точках, не годится. Полный перебор всех $x$ мы тоже отвергаем по причинам, которые обсуждались выше.

Для множеств $X$, для которых определено отношение близости, годятся и другие методы. Среди них — метод градиентного спуска.

Отношение близости — это способ определить для двух элементов множества, являются ли они близкими (в каком-нибудь смысле). Для числовых множеств, для множеств точек на плоскости или в пространстве близкими можно считать два числа (две точки), расстояние между которыми не превосходит некоторого маленького числа $\epsilon$. Для множества $S_n$ близкими удобно считать две перестановки, отличающиеся на одну транспозицию, то есть получающиеся друг из друга «рокировкой» двух элементов множества. Например, перестановки $\left(2,4,1,3\right)$ и $\left(2,3,1,4\right)$ являются близкими в этом смысле, так как отличаются перестановкой элементов с номерами $2$ и $4$. Можно определить и более строгое отношение близости, при котором близкие перестановки отличаются на соседнюю транспозицию, когда рокировка затрагивает элементы множества с соседними номерами. Тогда указанные выше перестановки близкими уже не будут, но близкими окажутся $\left(2,4,1,3\right)$ и $\left(2,4,3,1\right)$.

Суть метода градиентного спуска отражена в его названии и заключается в следующем. Строится последовательность $\left\{x_0,x_1,x_2,x_3,\dots \right\}\subset X$, в которой начальный элемент $x_0$ выбирается произвольно (возможно, случайным образом), а каждый последующий является одним из соседей предыдущего, причём именно тем из соседей, для которого значение функции $U$ будет наименьшим. Построение последовательности завершается тогда, когда последовательность значений целевой функции $\left\{U\left(x_0\right),U\left(x_1\right),U\left(x_2\right),U\left(x_3\right),\dots \right\}$ перестанет быть монотонно убывающей.

Последний элемент построенной последовательности называют точкой локального минимума. Это такая точка, в которых значение $U$ строго меньше, чем во всех соседних с ней. В слове «локальный» заключён главный недостаток описанного метода. Локальных минимумов у функции $U$ может быть много, и каждому из них отвечает, как правило, своё локально минимальное значение целевой функции. Нас же интересует абсолютный минимум функции и тот элемент множества $X$, в котором он достигается. Если бы было легко найти все точки локального минимума, перебором среди них мы нашли бы точку абсолютного минимума. Но метод градиентного спуска не даёт рецепта поиска всех точек локального минимума, он позволяет найти лишь какую-нибудь.

Имеется вероятностная версия метода градиентного спуска. На каждом шаге для элемента множества $X$ выбирается случайный сосед. Если значение целевой функции в случайной соседней точке уменьшилось, она добавляется в последовательность, и мы переходим к следующему шагу. Если же нет, то снова выбирается случайный сосед. Алгоритм останавливается, если достаточно долго не пополняется последовательность (не происходит переход к следующему шагу): вероятно, алгоритм в этом случае привёл в точку локального минимума.

Один из приближённых методов решения таких задач оптимизации — метод имитации отжига. Отжиг — уже упоминавшийся процесс постепенного остывания вещества, при котором молекулы на фоне всё замедляющегося теплового движения собираются в наиболее энергетически выгодные конфигурации. Термин «отжиг» пришёл из металлургии. Дело в том, что металл в более энергетически выгодном состоянии одновременно твёрже и прочней: требуется большее внешнее воздействие, большая механическая работа над куском металла, чтобы нарушить выгодную конфигурацию молекул, «приподнять» эту конфигурацию над самым дном энергетической ямы.

Метод имитации отжига является модификацией вероятностного метода градиентного спуска. Отличие заключается в поведении алгоритма, когда $U\left(x\right)⩽U\left(\tilde{x}\right)$, где $x$ — очередной элемент последовательности, а $\tilde{x}$ — его сосед, выбранный наугад. Вероятностный метод градиентного спуска отвергал такого соседа безусловно, а метод имитации отжига допускает добавление такого «плохого» соседа в последовательность, правда, с некоторой вероятностью $p$, зависящей от того, насколько плохой сосед ухудшил целевую функцию. Возьмём разность $∆U=U\left(\tilde{x}\right)-U\left(x\right)$ (она неотрицательна, если сосед «плохой») и положим $$p=e^{-\frac{∆U}{\Theta }}\text{.}$$ Здесь $e$ — некоторое число, большее единицы (какое именно, не принципиально, но обычно берут $e\approx \mathrm{2,718281828459045\dots }$ — основание натуральных логарифмов), а $\Theta$ — некоторое положительное число, называемое температурой.

На рисунке 45.1. «Вероятность мутации для метода имитации отжига» показаны зависимости вероятности мутации от величины $∆U$ при различных значениях температуры $\Theta$. Высоким температурам соответствуют графики, чей цвет ближе к красному, низким — к синему. Как и положено, значение вероятности заключено в отрезке $\left[0;1\right]$. При отрицательных $∆U$ вероятность равна $1$, что соответствует случаю «хорошей» мутации.

Рисунок 45.1. Вероятность мутации для метода имитации отжига

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

Рисунок 45.2. Решение задачи коммивояжёра методом имитации отжига