Нейрокомпьютинг и его применения в экономике и бизнесе


Оптимизация и сеть Хопфилда


В 1985г. Хопфилд и Танк предложили использовать минимизирующие энергию нейронные сети для решения задач оптимизации (Hopfield & Tank, 1985). В качестве примера они, естественно, рассмотрели задачу коммивояжера.

Для решения этой задачи с помощью нейронной сети Хопфилда нужно закодировать маршрут активностью нейронов и так подобрать связи между ними, чтобы энергия сети оказалась связанной с полной длиной маршрута. Хопфилд и Танк предложили для этого следующий способ.

Рассмотрим сеть, состоящую из

N\times N
бинарных нейронов, состояния которых мы обозначим
\nu_{i\alpha}\in \{0,1\}
 (i=1,\ldots ,N; \alpha=1, \ldots ,N)
, где индекс
i
кодирует город, а индекс
\alpha
- номер города в маршруте (см. рисунок 6.1). Если обозначить через
d_{ij}
расстояние между
i
-м и
j
-м городами, решение задачи коммивояжера сводится к минимизации целевой функции
L(\nu)=\frac{1}{2}\sum_{i,j,\alpha}^{i\neq j}d_{ij}\nu_{i\alpha}\left(\nu_{j \alpha-1}+\nu_{j \alpha+1}\right)
при дополнительных условиях
\sum_i \nu_{i\alpha}=1 (\forall\alpha),

и

\sum_\alpha \nu_{i\alpha}=1 (\forall i)

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

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

E(\nu)=\frac{1}{2}\sum^{i\neq j}_{i,j,\alpha}d_{ij}\nu_{i\alpha}\left(\nu_{j \alpha-1}+\nu_{j\alpha+1}\right)+\frac{\gamma}{2}\left[\sum_{\alpha}\left(\sum_{i}\nu_{i\alpha}-1\right)^2+\sum_{i}\left(\sum_{\alpha}\nu_{i\alpha}-1\right)^2\right],

где т.н. множитель Лагранжа

\gamma
регулирует строгость соблюдения дополнительных условий в конечном решении.

Слева - один из возможных маршрутов коммивояжера в случае задачи с 5 городами. Справа - кодировка этого маршрута состояниями 25 бинарных нейронов

Рис. 6.1.  Слева - один из возможных маршрутов коммивояжера в случае задачи с 5 городами. Справа - кодировка этого маршрута состояниями 25 бинарных нейронов

Осмысленному решению будет соответствовать стационарное состояние сети, в котором лишь

N
нейронов сети будут активными (
\nu_{i\alpha}
) и в каждом столбце и в каждой строке матрицы
\|\nu_i\alpha\|
будет находиться один и только один единичный элемент.

Величина множителя Лагранжа

\gamma
регулирует "торг" между поиском маршрута минимальной протяженности и осмысленностью вида самого маршрута. Частное решение, соответствующее локальному минимуму функционала
E
, может быть осмысленным (второе слагаемое обращаются на нем в ноль), но первое слагаемое (длина маршрута) для него, возможно будет слишком велико.


Начало  Назад  Вперед



Книжный магазин