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


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


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

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

E(\nu)
к энергии рекуррентной сети:
E(\nu)=\frac{1}{2}\sum^{i\neq j}_{i,j,}\sum_{\alpha,\beta}^{\alpha\neq\beta}w_{i\alpha j\beta}\nu_{i\alpha}\nu_{j\beta}+\sum_{i,\alpha}\vartheta_{i\alpha}\nu_{i\alpha}.

Таким образом находятся значения синаптических связей в сети:

w_{i\alpha j\beta}=-d_{ij}(\delta_{\alpha-1 \beta}+\delta_{\alpha+1 \beta})\gamma\delta_{\alpha\beta}-\gamma\delta_{ij}

и значений порогов нейронов

\vartheta_{i\alpha}
. Общее число весов в сети - порядка
N^3
.

Сети Поттса. Значительного продвижения в эффективности нейросетевой оптимизации можно добиться выбрав более сложный тип нейронов - т.н. Поттсовские нейронны - для более естественного представления условий задачи в терминах нейросети (Gilsen et al., 1989). Поттсовский нейроны принимают одно из N значений, что можно описать N-вектором

(0,\ldots,1,\ldots,0)
, в котором единица помечает принимаемое им значение. Если при решении задачи коммивояжера сопоставить таким нейронам города, а их состояния соотнести с номером города в туре, то условие посещения города лишь однажды будет гарантировано автоматически.

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

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

x_{i\alpha}\in [0,1]

. 1) В качестве тестовых они использовали задачи с 10 и 30 городами. В первом случае сеть в 20 попытках 16 раз эволюционировала к состояниям, описывающим осмысленный маршрут и в 10 случаях давала один из двух возможных оптимальных маршрутов. Поскольку для задачи с

N
городами полное число всевозможных маршрутов равно
N!
(делитель
2N
возникает вследствие инвариантности маршрута относительно циклического сдвига и обращения направления движения), то в задаче с 10 городами оно составляет 181440.


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