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


              

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


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

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

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

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

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

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

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