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

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

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

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

. Если обозначить через

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

вектор, определяющий положение

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

-го города на плоскости, а

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

-координату

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

-й точки на кольце, то закон изменения последний имеет вид

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

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

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

определяют относительное воздействие на точку

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

описанных выше двух сил. Коэффициенты

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

, определяющие воздействие

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

-го города на

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

-ю точку кольца, являются функцией расстояния

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

и параметра

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

. Эти коэффициенты нормированы так, что полное воздействие каждого из городов оказывается одинаковым:

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

где

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

- положительная, ограниченная и убывающая функция d, приближающаяся к нулю при

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

Если в качестве этой функции выбрать распределение Гаусса

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

, то можно определить функцию Ляпунова

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

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

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

Содержание раздела

Главная сайта