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

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

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

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

AY, = «Е {X-Yj) + /R- [Yj,, - 2Yj + Yj ,),

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

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

и параметра R. Эти коэффициенты нормированы

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

= ф(х, - , i?)/E, ф(х, - у, , r) ,

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

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

ЮОЛ элементарных операций изменения маршрута). Поиск продолжается до тех пор, пока

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

£ = -« i?X log Е Ф(1 X, - I, i?) + I Yy.i - р ,

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

Дурбин и Уиллшоу показали, что для задачис 30 городами, рассмотренной Хопфилдом и

Танком, метод эластичной сети генерируетнаикратчайший маршрут примерно за 1000

итераций. Для 100 городов найденный этимметодом маршрут лишь на 1% превосходил оптимальный.

Оптимизация с помощью сети Кохонена.

Успех применения метода эластичной сети для решении задачи коммивояжера был оценен Фаватой и Уолкером, понявшими, что в нем, по сути, используется отображение двумерного распределения городов на одномерный кольцевого маршрута (Favata & Walker, 1991). Поскольку в наиболее общем виде такой подход был сформулирован Кохоненом, то использование его самоорганизующихся карт для оптимизации оказалось вполне естественным. Сеть Кохонена позволяет обеспечить выполнение условия, которому должен удовлетворять хороший маршрут в задаче коммивояжера: близкие города на плоскости должны быть отображены на близкие в одномерном маршруте.

Алгоритм решения задачи следует из оригинальной схемы Кохонена, в которую вносятся лишь небольшие изменения. Используется сеть, состоящая из двух одномерных слоев нейронов (т.е. содержащая лишь один слой синаптических весов). Входной слой состоит из трех нейронов, а выходной - из Л (по числу городов). Каждый нейрон входного слоя связан с каждым выходным нейроном. Все связи вначале инициируются случайными значениями. Для каждого города входной 3-мерный вектор формируется из двух его координат на плоскости, а третья компонента вектора представляет из себя нормирующий параметр, вычисляемый так, чтобы все входные вектора имели одинаковую Евклидову длину и никакие два вектора не были бы коллинеарны. Это эквивалентно рассмотрению двумерных координат городов, как проекций трехмерных

векторов, лежащих на сфере. Обозначим через w"* 3-мерный вектор синаптических связей,

связывающих у-й выходной нейрон с входными нейронами. Если с - трехмерный входной

вектор, определяющий / -й город, то активация j-го выходного нейрона при подаче с на вход

определяется скалярным произведением (с, w ). Выходной нейрон, для которого это произведение максимально, называется образом города.

Алгоритм формирования маршрута формулируется следующим образом. Выбираются значения для параметра усиления а и радиуса взаимодействия г. Следующий цикл выполняется вплоть до выполнения условия а <0.

1)Выбирается случайный город с.

2)Определяется номер образа города в выходном слое - .

3)Векторы связей w , соединяющих нейрон , и всех его 2г близлежащих соседей справа и слева: j = i - г, i - г +1, i, + г - 1, + г модифицируются следующим образом:

W(/ + l) =

w(0 + ca(0

w(0 + c«(Oir

где х - Евклидова норма вектора х. Для устранения концевых эффектов слой выходных нейронов считается кольцевым, так что Л-й нейрон примыкает к первому.

4)Радиус взаимодействия постепенно уменьшается согласно некоторому правилу (например, вначале можно положить г = 0.1N , затем за первые 10% циклов снизить его до значения 1, которое далее поддерживается постоянным).

5)Параметр усиления а постепенно снижается на небольшую величину ( например, в экспериментах Фавата и Уолкера он линейно уменьшался до нуля).

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

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

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

Таблица 1. Сравнение результатов решения задачи коммивояжера с 30 городами

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

вычислительных затрат, растущих не медленне, чем Л. Ниже мы опишем нейросетевой подход, в котором они растут линейно с размерностьюзадачи.