Ассоциативная память[править | править вики-текст]

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

Задачи минимизации[править | править вики-текст]

Обработка визуальных образов (фильтрация и ассоциативная память) — не единственная область применения модели Хопфилда. Динамическая процедура, описанная выше, на каждом шаге понижает значение энергии нейронной сети. Это позволяет решать комбинаторные задачи оптимизации, если они могут быть сформулированы как задачи минимизации энергии. Классической проблемой такого типа является задача коммивояжёра.

Решение задачи о коммивояжёре[править | править вики-текст]

Сеть Хопфилда может использоваться для решения задачи коммивояжера (нужно обойти все n городов и вернуться в исходный так, чтобы длина пройденного маршрута была минимальной). Для этого можно наложить, например, такие требования на сеть:

1. Сеть должна состоять из N=n×n нейронов, которые мы будем рассматривать как квадрат из n строк и n столбцов.

2. Ответ сети должен содержать только один активный нейрон в каждой строке и каждом столбце.

3. Активный нейрон в первом столбце задаёт первый город маршрута, во втором столбце — второй город маршрута, и так далее.

Оказывается, что для решения этой задачи достаточно следующих простых соображений:

• для выполнения условия 2 веса сети должны быть построены таким образом, чтобы каждый нейрон препятствовал активации других нейронов в своей строке и в своём столбце;

• для минимизации длины пути необходимо, чтобы нейрон в i-м столбце тем активнее препятствовал активации нейронов в i+1-м и i−1-м столбцах, чем больше расстояние между ними;

• для того, чтобы сеть Хопфилда вообще работала, необходимо, чтобы веса сети не были все отрицательными.

Всем этим условиям удовлетворяет следующая формула вычисления веса между нейроном, соответствующим городу x на позиции в маршруте i, и нейроном, соответствующим городу y на позиции j:

Wxi,yj=−Aδxy(1−δij)−Bδij(1−δxy)−Cd(x,y)(δi,j+1+δi,j−1)+D

где A, B, C, D — некоторые константы, d(x,y) — расстояние между городами x и y, δxy — символ Кронекера, принимающий значение 1, если x=y и значение 0 в противном случае. Как легко видеть, первый член равен −A для всех связей в той же строке (x=y), кроме связи нейрона с самим собой (при i=j). Второй член равен −B для всех связей в том же столбце (i=j), кроме связи с самим собой (x=y). Третий член пропорционален расстоянию между городами x и y, если эти города соседние в маршруте (i=j−1 или i=j+1).

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

Решение данной задачи интересно не столько своим качеством (существуют алгоритмы, решающие её эффективнее^[3]), сколько самим подходом к задачам оптимизации: если возможно перевести условия некоторой задачи в параметры связей между нейронами, то она может быть относительно неплохо решена сетью без какого-либо дополнительного анализа.