Нейрокомпьютерные системы



              

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


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

каждое решение представляется набором

\{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\%
хуже оптимума. Вероятностный механизм функционирования МБ дает возможность получать на ней несколько лучшие результаты, чем на модели Хопфилда.




Содержание  Назад  Вперед