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

         

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


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

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

. Если обозначить через
вектор, определяющий положение
-го города на плоскости, а
-координату
-й точки на кольце, то закон изменения последний имеет вид

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

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

где

- положительная, ограниченная и убывающая функция d, приближающаяся к нулю при
Если в качестве этой функции выбрать распределение Гаусса
, то можно определить функцию Ляпунова

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

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



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