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

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

Радиус взаимодействия постепенно уменьшается согласно некоторому правилу (например, вначале можно положить

$r=0.1N$

, затем за первые 10% циклов снизить его до значения 1, которое далее поддерживается постоянным).

Параметр усиления

$\alpha$

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

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

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

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

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

сеть Хопфилдасеть Кохонена

Длина маршрута	<7	<5.73
Средняя длина маршрута	>6	4.77
Наименьшая длина маршрута	5.07	4.26

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

$N^2$

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

Содержание Назад Вперед