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


              

длина маршрута может быть достаточно


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

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


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


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

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

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

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


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

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