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


           

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


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

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

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

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

и

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

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

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

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


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

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

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

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

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

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





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий