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

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

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

3-мерный вектор синаптических связей, связывающих -й выходной нейрон с входными нейронами. Если - трехмерный входной вектор, определяющий i -й город, то активация j-го выходного нейрона при подаче на вход определяется скалярным произведением . Выходной нейрон, для которого это произведение максимально, называется образом города.

Алгоритм формирования маршрута формулируется следующим образом. Выбираются значения для параметра усиления

и радиуса взаимодействия r. Следующий цикл выполняется вплоть до выполнения условия .

• Выбирается случайный город
  
  .
• Определяется номер образа города в выходном слое -
  
  .
• Векторы связей
  
  , соединяющих нейрон
  
  , и всех его
  
  близлежащих соседей справа и слева:
  
  ,
  
  модифицируются следующим образом:
  
  , где
  
  - Евклидова норма вектора
  
  .
  
  Содержание  Назад  Вперед
  
  

  ---

  
  
  
  
  
  Forekc.ru
  Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий

  ---