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

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

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

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

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

и

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

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

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

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

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

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

нейронов сети будут активными ( ) и в каждом столбце и в каждой строке матрицы будет находиться один и только один единичный элемент.

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

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

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

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

и значений порогов нейронов . Общее число весов в сети - порядка .

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

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

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

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


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

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

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

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

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


Содержание раздела

---

---