Решение задач комбинаторной оптимизации рекуррентными сетями

Решение задачи коммивояжера сетью Хопфилда

Рассмотрим задачу коммивояжера для $$n$$ городов. Известны расстояния $$d_{XY}$$ между каждой парой городов $$X,Y$$ ; коммивояжер, выходя из одного города, должен посетить $$n-1$$ других городов, заходя по одному разу в каждый, и вернуться в исходный. Требуется определить порядок обхода городов, при котором общее пройденное расстояние минимально.

Пусть сеть Хопфилда состоит из $$N=n^2$$ нейронов, а состояние нейронов описывается двойными индексами $$v_{Xi}$$, где индекс $$X$$ связан с именем города, $$i$$ - с позицией города в маршруте коммивояжера. Запишем функцию вычислительной энергии для сети, предназначенной решать задачу коммивояжера. В ней состояние с наименьшей энергией должно соответствовать самому короткому маршруту. Функция энергии должна удовлетворять следующим требованиям:

1) должна поддерживать устойчивое состояние в форме матрицы

$$\begin{equation} V=\{v_{Xi}\}, \end{equation}$$

в которой строки соответствуют городам, столбцы - их номерам в маршруте; в каждой строке и каждом столбце только одна единица, остальные нули;

2) из всех решений вида (1) функция энергии должна поддерживать те, которые соответствуют коротким маршрутам.

Таким требованиям удовлетворяет функция энергии в виде:

$$\begin{equation} E=(A/2) \sum_X \sum_{i}\sum_{j\ne i} v_{Xi}v_{Xj} +(B/2)\sum_i \sum_{X}\sum_{Y\ne X} v_{Xi}v_{Xj}+\\ +(C/2)(\sum_X \sum_{i} v_{Xi}{-}n)^2 {+} (D/2) \sum_X \sum_{X \neq Y} \sum_{i} d_{XY} v_{Xi}(v_{Y,i+1}+v_{Y,i-1}), \end{equation}$$

где первые три члена поддерживают первое требование, четвертый член — второе. Первый член равен нулю, если каждая строка $$X$$ содержит не более одной единицы. Второй равен нулю, если каждый столбец $$i$$ содержит не более одной единицы. Третий равен нулю, если в матрице всего $$n$$ единиц. Короткие маршруты поддерживает четвертый член. В нем индексы $$i$$ берутся по модулю $$n$$ для того, чтобы показать, что $$n$$ -й город соседствует в маршруте с $$(n-1)-\mbox м$$, т.е. $$v_{Y,n+j}=v_{Y,j}$$. Четвертый член численно равен длине маршрута. Каноническое выражение для функции вычислительной энергии имеет вид

$$\begin{equation} E = - (1/2)\sum_{X} \sum_i \sum_{Y} \sum_j W_{Xi,Yj} v_{Xi}v_{Xj} - \sum_{x i}I_{Xi} v_{Xi} \end{equation}$$

Из (2) и (3) получаем веса сети Хопфилда:

$$\begin{align*} W_{Xi,Yj} = - A \delta_{XY}(1 - \delta_{ij}) - B \delta_{ij}(1 - \delta_{XY}) - C - Dd_{XY}(\delta_{j,i+1}+\delta_{j,i-1}),\\ I_{Xi}=Cn. \end{align*} $$

Здесь $$\delta$$ - символ Кронекера.

Моделирование работы сети Хопфилда показало, что лучшее по качеству решение дает сеть, нейроны которой имеют сигмовидную характеристику, а сеть, в которой нейроны имеют ступенчатые переходы, приходила к финальным состояниям, соответствующим маршрутам немного лучшим, чем случайные. Многочисленные исследования показывают, что качество решения задачи минимизации функции энергии (2) существенно зависит от выбора производной сигмовидной униполярной функции активации нейрона в окрестности нуля. При малой величине производной минимумы энергии оказываются в центре гиперкуба решений (некорректное решение), при большой величине производной сеть Хопфилда попадает в вершину гиперкуба, соответствующую локальному минимуму функции энергии. Кроме того, на качество решения существенное влияние оказывает выбор коэффициентов $$A, B, C, D$$. Поиск методов оптимального выбора этих коэффициентов является в настоящее время предметом интенсивных исследований.

Машина Больцмана

Математической основой для решения комбинаторных оптимизационных задач на машине Больцмана является алгоритм, моделирующий затвердевание жидкостей или расплавов (алгоритм имитации отжига). Он базируется на идеях из двух различных областей: статистической физики и комбинаторной оптимизации. Машина Больцмана (МБ) способна реализовать этот алгоритм параллельно и асинхронно. МБ задается четверкой $$B = (N,E,W,V_0), N$$ - число нейронов, $$E=\{(i,j)\}$$ - множество связей между нейронами, при этом все автосвязи принадлежат этому множеству, т.е. $$(i,i)\in E$$. Каждый нейрон может иметь состояние 0 или 1. Состояние $$V_k$$ МБ определяется состояниями нейронов $$V_k=(v_1^k, \ldots, v_N^k), V_0$$ - начальное состояние. Каждая связь $$(i,j)$$ имеет вес $$w_{ij}$$ - вещественное число, множество связей - $$W$$. Связь $$(i,j)$$ называется активной в состоянии $$V_k$$, если $$v_i^kv_j^k=1$$. Вес связи $$(i,j)$$ интерпретируется как количественная мера желательности, чтобы эта связь была активной. При $$w_{ij} \gg 0$$ - активность очень желательна, при $$w_{ij} \ll 0$$ - активность очень нежелательна. Как и в модели Хопфилда, связи в МБ симметричны, т.е. $$w_{ij} = w_{ji}$$.

Функция консенсуса

Для состояния $$V_k$$ МБ вводится понятие консенсуса

$$\begin{align*} C_k= \sum_{i,j} w_{ij} v_i^k v_j^k . \end{align*} $$

Каждая связь в этой сумме учитывается один раз. Консенсус $$C_k$$ интерпретируется как количественная мера желательности, чтобы все связи $$(i,j)$$ в состоянии $$V_k$$ были активны. Для состояния $$V_k$$ определяется множество соседей $$V^{(k)}$$. Соседнее состояние $$V_{k(i)} \in V^{(k)}$$ получается из $$V_k$$ при изменении состояния нейрона $$i$$,

$$\begin{align*} V_{j}^{k(i)} = \left\{ \begin{array}{rl} v_j^k \mbox{ если } j \neq i\\ 1 - v_j^k \mbox{ если } j = i\\ \end{array} \right. \end{align*} $$

Разница консенсусов соседних состояний $$V_k$$ и $$V_{k(i)}$$ равна

$$\begin{align*} \Delta C_{kk(i)} = C_{k(i)} - C_k = (1-2v_i^k)(\sum_{(i,j) \in E(i)} w_{ij}v_i^k + w_{ii}), \end{align*} $$

где $$E(i)$$ - множество связей нейрона $$i$$. Видно, что $$\Delta C_{kk(i)}$$ для всех $$V_{k(i)}\in V^{(k)}$$ могут вычисляться параллельно.

Максимизация консенсуса

Переход МБ из одного состояния в другое с максимизацией консенсуса происходит путем выполнения пошаговой процедуры. На каждом ее шаге выполняется испытание, состоящее из двух частей:

для данного состояния $$V_k$$ генерируется соседнее $$V_{k(i)}$$,

оценивается, может ли быть принято состояние $$V_{k(i)}$$, если может, то результат испытания - $$V_{k(i)}$$, иначе $$V_k$$.

Состояние $$V_{k(i)}$$ принимается с вероятностью

$$\begin{equation} P_{kk(i)}(t)=1/[1+\exp(\Delta C_{kk(i)}/t)], \end{equation}$$

где $$t \ge 0$$ - управляющий параметр ("температура").

Процесс максимизации консенсуса начинается с высокого значения $$t_0$$ параметра $$t$$ и случайно выбранного начального состояния $$V_0$$. В течение процесса параметр $$t$$ уменьшается от $$t_0$$ до 0. По мере того как $$t$$ приближается к нулю, нейроны все реже изменяют свои состояния, и наконец, МБ стабилизируется в финальном состоянии. Практически, МБ стабилизируется в состоянии, соответствующем локальному максимуму консенсуса, который близок (или равен) глобальному. Сходимостью МБ управляют следующие параметры:

1. Начальное значение параметра $$t$$ для каждого нейрона $$i$$

$$\begin{align*} t_0^{(i)} = \sum_{(i,j)\in E(i)} |w_{ij}| + |w_{ii}|. \end{align*} $$

2. Правило понижения $$t$$

$$\begin{align*} t_{j+1}^{(i)} = \alpha t_j^{(i)}, \end{align*} $$

где $$\alpha$$ - положительное число, меньшее единицы, но близкое к ней.

3. Число $$L$$ испытаний, которые проводятся без изменения $$t$$ ( $$L$$ — функция от $$N$$ ).

4. Число $$M$$ последовательных испытаний, не приводящих к изменению состояния машин ( $$M$$ - функция от $$N$$ ), как критерий завершения процесса.

Синхронное и асинхронное функционирование машины Больцмана

Для выполнения синхронного процесса все множество нейронов разбивается на непересекающиеся подмножества $$\{M_1, \ldots, M_m\}$$, такие, что нейроны, попавшие в одно подмножество, не связаны друг с другом. Тогда на каждом такте синхронизации элементы случайно выбранного подмножества $$M_i$$ могут одновременно изменять свои состояния в соответствии с заданной вероятностью.

В асинхронном параллельном процессе все нейроны могут изменять свои состояния только в зависимости от величины вероятности. Практически асинхронный параллелизм может быть выполнен следующим образом. Случайно выбирается подмножество $$M$$, содержащее $$q=2N/3$$ нейронов. Для каждого нейрона из этого подмножества устанавливается состояние в соответствии с $$P_{kk(i)}(t)$$. Получившееся в результате состояние есть результат одного асинхронного шага.

Решение задачи коммивояжера машиной Больцмана

Общий подход к программированию комбинаторных оптимизационных задач состоит в следующем:

каждое решение представляется набором $$\{x_1, \ldots, x_N\},x_i \in\{0,1\}$$, $$N$$ — число нейронов в сети, $$x_i$$ - состояние нейрона. Структура связей и веса выбираются так, что:

$$R1$$. Все локальные максимумы функции консенсуса соответствуют приемлемым решениям задачи;

$$R2$$. Чем лучше приемлемое решение, тем больше консенсус соответствующего состояния машины Больцмана.

Перефразируем для МБ задачу коммивояжера.

$$R1$$. Состояние МБ соответствует локальному максимуму функции консенсуса, если и только если это состояние соответствует приемлемому маршруту.

$$R2$$. Чем короче маршрут, тем выше консенсус соответствующего состояния МБ.

Каждый нейрон соответствует элементу матрицы $$n\times n$$, состояния нейронов обозначаются $$v_{Xi}$$ ( $$n$$ - число городов). Функция консенсуса

$$\begin{align*} C_k = \sum_{(Xi,Yj)} w_{Xi,Yj} v_{Xi}^k v_{Yj}^k . \end{align*} $$

Множество связей в сети определяется как объединение трех непересекающихся подмножеств:

$$E_d$$ - множество связей, несущих информацию о расстояниях между городами,

$$\begin{align*} E_d = \{(Xi,Yj)|(X \neq Y)\wedge (i=(j+1)mod n)\}; \end{align*} $$

$$E_i$$ - множество ингибиторных (запретительных) связей,

$$\begin{align*} E_i = \{(Xi,Yj)|(i \neq j)\wedge (X=Y)\vee (i=j)\wedge (X \neq Y)\}; \end{align*} $$

$$E_b$$ - множество связей смещений,

$$\begin{align*} E_b = \{(Xi,Yj)|(X=Y)\wedge(i=j)\}. \end{align*} $$

Здесь $$X,Y,i,j=1, \ldots, n$$. Общее число связей равно $$2n^3 - n^2$$.

Ингибиторные связи гарантируют, что, в конце концов, ни в одной строке и ни в одном столбце не будет более одной единицы. Связи смещений гарантируют, что хотя бы по одной единице есть в каждом столбце и в каждой строке. Таким образом, связи $$E_i$$ и $$E_b$$ гарантируют выполнение ограничений в задаче и веса их дают одинаковые вклады в консенсусы для всех приемлемых маршрутов.

Связь $$(Xi,Yj)\in E_d$$ активна только в том случае, когда в маршруте есть прямой путь из города $$X$$ в город $$Y$$. Вес связи $$(Xi,Yj)\in E_d$$ равен расстоянию между городами $$X$$ и $$Y$$ с отрицательным знаком. Следовательно, для данного маршрута отрицательный вклад связи из $$E_d$$ в консенсус пропорционален длине пути, поэтому максимизация функции консенсуса соответствует минимизации длины маршрута.

Доказано, что для консенсуса $$C_k$$ выполняются требования $$R1$$ и $$R2$$, если и только если веса связей выбраны следующим образом:

$$\forall (Xi,Yj) \in E_d:w_{Xi,Yj} = - d_{XY},\\$$ $$\forall (Xi,Yj) \in E_i:w_{Xi,Yj} < - \min(\mu_X, \mu_Y),\\$$ $$\forall (Xi,Yj) \in E_b:w_{Xi,Yj} > \mu_X,$$

где

$$\begin{align*} \mu_X = \max \{d_{XP}+d_{XQ}|P,Q=1, \ldots, n \wedge(P \neq Q)\}. \end{align*} $$

При $$d=0,95, L=10, M=100$$ было проведено 100 испытаний для $$n=10$$ и 25 испытаний для $$n=30$$ при различных начальных состояний МБ. Для $$n=10$$ получено оптимальное решение, для $$n=30$$ получено решение на $$14\%$$ хуже оптимума. Вероятностный механизм функционирования МБ дает возможность получать на ней несколько лучшие результаты, чем на модели Хопфилда.