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


Метод эластичной сети


Иной подход к решению задачи коммивояжера использовали в 1987 году Дурбин и Уиллшоу (Durbin & Willshaw, 1987). Хотя они явно и не использовали в своей работе понятия искусственной нейронной сети, но в качестве отправной точки упоминали об аналогии с механизмами установления упорядоченных нейронных связей. Исследователи предложили рассматривать каждый из маршрутов коммивояжера как отображение окружности на плоскость, так что в каждый город на плоскости отображается некоторая точка этой окружности. При этом требуется, чтобы соседние точки на окружности отображались в точки, по возможности ближайшие и на плоскости. Алгоритм стартует с помещения на плоскость небольшой окружности (кольца), которая неравномерно расширяясь проходит практически около всех городов и, в конечном итоге, определяет искомый маршрут. Каждая точка расширяющегося кольца движется под действием двух сил: первая перемещает ее в сторону ближайшего города, а вторая смещает в сторону ее соседей на кольце так, чтобы уменьшить его длину. По мере расширения такой эластичной сети, каждый город оказывается ассоциирован с определенным участком кольца.

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

R
. Если обозначить через
X_i
вектор, определяющий положение
i
-го города на плоскости, а
Y_j
-координату
j
-й точки на кольце, то закон изменения последний имеет вид
\Delta Y_{j}=\alpha\sum_{j}W_{ij}\cdot(X_i-Y_j)+\beta R\cdot(Y_{j+1}-2Y_j+Y_{j-1}),

где параметры

\alpha,\beta
определяют относительное воздействие на точку
Y_j
описанных выше двух сил. Коэффициенты
W_{ij}
, определяющие воздействие
i
-го города на
j
-ю точку кольца, являются функцией расстояния
|X_i-Y_i|
и параметра
R
. Эти коэффициенты нормированы так, что полное воздействие каждого из городов оказывается одинаковым:
W_{ij}=\Phi\left(|X_i-Y_j|,R\right)/\sum_{k}\Phi\left(|X_i-Y_k|,R\right),

где

\Phi(d,R)
- положительная, ограниченная и убывающая функция d, приближающаяся к нулю при
d>R
Если в качестве этой функции выбрать распределение Гаусса
\exp(-d^2/2R^2)
, то можно определить функцию Ляпунова
E=-\alpha R\sum_i \log\sum_j\Phi(|X_i-Y_j|,R)\beta\sum_j |Y_{j+1}-Y_j|^2,

которая минимизируется в ходе динамического изменения параметров кольца.

Дурбин и Уиллшоу показали, что для задачи с 30 городами, рассмотренной Хопфилдом и Танком, метод эластичной сети генерирует наикратчайший маршрут примерно за 1000 итераций. Для 100 городов найденный этим методом маршрут лишь на 1% превосходил оптимальный.




Начало  Назад  Вперед