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


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


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

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

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

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

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

  • Выбирается случайный город
    с
    .
  • Определяется номер образа города в выходном слое -
    i_c
    .
  • Векторы связей
    w^i
    , соединяющих нейрон
    i_c
    , и всех его
    2r
    близлежащих соседей справа и слева:
    j=i_c-r
    ,
    i_c-r+l, \ldots ,i_c, \ldots ,i_c+r-l, i_c+r
    модифицируются следующим образом:
    w^j(t+1)=\frac{w^j(t)+c^i\alpha(t)}{\|w^j(t)+c^i\alpha(t)\|}
    , где
    \|x\|
    - Евклидова норма вектора
    x
    .


    Начало  Назад  Вперед