Нейрокомпьютерные системы

       

Решение задачи коммивояжера машиной Больцмана


Общий подход к программированию комбинаторных оптимизационных задач состоит в следующем:

каждое решение представляется набором

Решение задачи коммивояжера машиной Больцмана
,
Решение задачи коммивояжера машиной Больцмана
— число нейронов в сети,
Решение задачи коммивояжера машиной Больцмана
- состояние нейрона. Структура связей и веса выбираются так, что:

Решение задачи коммивояжера машиной Больцмана
. Все локальные максимумы функции консенсуса соответствуют приемлемым решениям задачи;

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

Перефразируем для МБ задачу коммивояжера.

Решение задачи коммивояжера машиной Больцмана
. Состояние МБ соответствует локальному максимуму функции консенсуса, если и только если это состояние соответствует приемлемому маршруту.

Решение задачи коммивояжера машиной Больцмана
. Чем короче маршрут, тем выше консенсус соответствующего состояния МБ.

Каждый нейрон соответствует элементу матрицы

Решение задачи коммивояжера машиной Больцмана
, состояния нейронов обозначаются
Решение задачи коммивояжера машиной Больцмана
(
Решение задачи коммивояжера машиной Больцмана
- число городов). Функция консенсуса

Решение задачи коммивояжера машиной Больцмана

Множество связей в сети определяется как объединение трех непересекающихся подмножеств:

Решение задачи коммивояжера машиной Больцмана
- множество связей, несущих информацию о расстояниях между городами,

Решение задачи коммивояжера машиной Больцмана

Решение задачи коммивояжера машиной Больцмана
- множество ингибиторных (запретительных) связей,

Решение задачи коммивояжера машиной Больцмана

Решение задачи коммивояжера машиной Больцмана
- множество связей смещений,

Решение задачи коммивояжера машиной Больцмана

Здесь

Решение задачи коммивояжера машиной Больцмана
. Общее число связей равно
Решение задачи коммивояжера машиной Больцмана
.

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

Решение задачи коммивояжера машиной Больцмана
и
Решение задачи коммивояжера машиной Больцмана
гарантируют выполнение ограничений в задаче и веса их дают одинаковые вклады в консенсусы для всех приемлемых маршрутов.

Связь

Решение задачи коммивояжера машиной Больцмана
активна только в том случае, когда в маршруте есть прямой путь из города
Решение задачи коммивояжера машиной Больцмана
в город
Решение задачи коммивояжера машиной Больцмана
. Вес связи
Решение задачи коммивояжера машиной Больцмана
равен расстоянию между городами
Решение задачи коммивояжера машиной Больцмана
и
Решение задачи коммивояжера машиной Больцмана
с отрицательным знаком. Следовательно, для данного маршрута отрицательный вклад связи из
Решение задачи коммивояжера машиной Больцмана
в консенсус пропорционален длине пути, поэтому максимизация функции консенсуса соответствует минимизации длины маршрута.

Доказано, что для консенсуса

Решение задачи коммивояжера машиной Больцмана
выполняются требования
Решение задачи коммивояжера машиной Больцмана
и
Решение задачи коммивояжера машиной Больцмана
, если и только если веса связей выбраны следующим образом:

Решение задачи коммивояжера машиной Больцмана

Решение задачи коммивояжера машиной Больцмана

Решение задачи коммивояжера машиной Больцмана

где

Решение задачи коммивояжера машиной Больцмана

При

Решение задачи коммивояжера машиной Больцмана
было проведено 100 испытаний для
Решение задачи коммивояжера машиной Больцмана
и 25 испытаний для
Решение задачи коммивояжера машиной Больцмана
при различных начальных состояний МБ. Для
Решение задачи коммивояжера машиной Больцмана
получено оптимальное решение, для
Решение задачи коммивояжера машиной Больцмана
получено решение на
Решение задачи коммивояжера машиной Больцмана
хуже оптимума. Вероятностный механизм функционирования МБ дает возможность получать на ней несколько лучшие результаты, чем на модели Хопфилда.



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