Основы теории нейронных сетей



         

Задача коммивояжера - часть 2


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

городПорядок следования
1234
A0100
B0001
C1000
D0010

Продемонстрируем теперь, как сконструировать сеть для решения этой NP-полной проблемы. Каждый нейрон снабжен двумя индексами, которые соответствуют городу и порядковому номеру его посещения в маршруте. Например,

OUT_{xj} = 1
показывает, что город
x
был
j
-м по порядку городом маршрута.

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

Первое требование удовлетворяется введением следующей, состоящей из трех сумм, функции энергии:

E=\frac A2\sum_{x}\sum_i\sum_{j\ne i} OUT_{xi}OUT_{xj}+ \frac{B}{2}\sum_i\sum_x\sum_{y\ne x}OUT_{xi}OUT_{yi}+\\
+ \frac{C}{2}\left[\left(\sum_x\sum_iOUT_{xi}\right)-n\right]^2,

где

A
,
B
и
C
— некоторые константы. Этим достигается выполнение следующих условий:

  1. Первая тройная сумма равна нулю в том и только в том случае, если каждая строка (город) содержит не более одной единицы.
  2. Вторая тройная сумма равна нулю в том и только в том случае, если каждый столбец (порядковый номер посещения) содержит не более одной единицы.
  3. Третья сумма равна нулю в том и только в том случае, если матрица содержит ровно

    n
    единиц. Второе требование — предпочтение коротких маршрутов — удовлетворяется с помощью добавления следующего члена к функции энергии:

     E=\frac{D}{2}\sum_x\sum_{y\ne x}\sum_i d_{xy} OUT_{xi}(OUT_{y,i+1}+OUT_{y,i-1}),

Заметим, что этот член представляет собой длину любого допустимого маршрута. Для удобства индексы определяются по модулю

n
, т. е.
OUT_{n+j} = OUT_j
, a
D
— некоторая константа.

При достаточно больших значениях

A
,
B
и
C

низкоэнергетические состояния будут представлять допустимые маршруты, а большие значения

D
гарантируют, что будет найден короткий маршрут.

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

Получаем

w_{xi,yi}=-A\delta_{xy}(1-\delta_{ii})
(не допускает более одной единицы в строке)

-B\delta_{ij}(1-\delta_{xy})
(не допускает более одной единицы в столбце)

-C
(глобальное ограничение)




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