Добавление нового нейрона.

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

определяется ближайший к нему нейрон , локальная ошибка для последнего получает приращение . Большое значение этой ошибки служит указанием на то, что соответствующий нейрон лежит в области, где отношение (число нейронов)/(число городов) невелико. Именно в таких областях следует добавлять новые нейроны, поскольку для получения правильного осмысленного маршрута около каждого города должен находиться свой ближайший нейрон. Маршрут и определяется путем перехода вдоль кольца к нейрону, являющимся ближайшим к некоторому городу. Алгоритм поиска оптимального маршрута, использующий две описанные операции, формулируется следующим образом

1. Инициализация: генерируется кольцевая структура, состоящая из трех нейронов, имеющих случайное положение на плоскости.
2. Осуществляется фиксированное число
   
   шагов распространения. На каждом шаге пересчитывается значение локальной ошибки
   
   .
3. Определяется "наихудшее" звено в кольце, связывающее два нейрона
   
   и
   
   , для которых сумма
   
   максимально. Новый нейрон вставляется в середину звена связывающего нейроны
   
   и
   
   , и его ошибка инициализируется величиной
   
   . В то же время значения ошибок для нейронов
   
   и
   
   уменьшается таким образом, чтобы суммарная ошибка сохранилась:
   
   ,
   
4. Если для любых двух городов ближайшие к ним нейроны различны между собой, то маршрут найден. В противоположном случае возвращаемся к шагу 1.

Очевидно, что решение задачи может быть найдено не ранее того, как число нейронов в кольце достигнет числа городов

. В действительности для его достижения требуется сеть с нейронами. Исходя из этого эмпирического наблюдения, согласно которому число итераций имеет порядок , можно оценить общую сложность алгоритма. На шаге 1 требуется инспекция всех нейронов для поиска ближайшего к данному городу. Она производится раз и, поскольку это число постоянно, полное число инспекций также имеет порядок .
На шаге 2 необходимо проверить каждое звено цепи, чтобы найти то, которому соответствует максимальная суммарная ошибка концевых нейронов. Поскольку число звеньев равно числу нейронов, то число действий опять имеет порядок . На шаге 3 для каждого города необходимо найти ближайший нейрон, что, как минимум, требует действий. Таким образом, так как шаги 1-3 требуют по меньшей мере операций, а цикл повторяется раз, то временная сложность алгоритма как минимум равна . Пространственная сложность алгоритма составляет , так как необходимо резервировать память для городов, нейронов и некоторых локальных переменных.

Для улучшения квадратичной временной сложности описанного алгоритма Фритцке и Вильке модифицировали шаги 1-3. Они учли, что согласно численным экспериментам вначале кольцевая структура нейронов быстро распределяется по всей области размещения городов, и затем с ростом числа нейронов изменения приобретают локальный характер. Такое поведение натолкнуло их на идею заменить глобальный поиск нейрона-победителя на шаге 1 приближенной локальной процедурой. А именно: для каждого города запоминается тот нейрон, который наиболее часто оказывался к нему ближайшим, и если город выбран вновь, то поиск ближайшего к нему нейрона ограничивается этим нейроном и его ближайшими по кольцу соседями вплоть до порядка k. Поскольку k есть константа, то сложность поиска оказывается в этом случае .
Рис. 6.3.  Локальный поиск наилучшего нейрона: -предыдущий нейрон ; ближайшие его соседи вплоть до 2 порядка являются кандидатами в победители на следующем шаге

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

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

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

Описанный эффективный нейросетевой подход (FLEXMAP) был протестирован на разных распределениях городов числом до 200 и неизменно находил маршруты, отличающиеся не более чем на 9% от оптимального.


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

---

---