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

Скачать в pdf «Нейрокомпьютинг и его применения в экономике и бизнесе»


В классической постановке, коммивояжер должен объехать N городов по замкнутому маршруту, посетив каждый из них лишь однажды, таким образом, чтобы полная длина его маршрута была минимальной. Если решать задачу коммивояжера “в лоб” — перебором всех замкнутых путей, связывающих N городов, то придется проверить все (N — l) !/2 возможных маршрутов. Будучи NP -полной, задача коммивояжера не имеет практически реализуемого точного решения. На примере этой задачи мы ниже и рассмотрим различные методы ее приближенного решения с помощью нейросетей.



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


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


Рассмотрим сеть, состоящую из N х N бинарных нейронов, состояния которых мы обозначим via е{0, l} (7 =    , где индекс i кодирует город, а индекс а — номер


города в маршруте (см. Рисунок 1). Если обозначить через dy расстояние между / -м и j -м городами, решение задачи коммивояжера сводится к минимизации целевой функции

при дополнительных условиях


IX =1 (v«) и IX=i (v*)


/    a


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


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

Скачать в pdf «Нейрокомпьютинг и его применения в экономике и бизнесе»