Решение задачи коммивояжера машиной Больцмана
Общий подход к программированию комбинаторных оптимизационных задач состоит в следующем:
каждое решение представляется набором
,
— число нейронов в сети,
- состояние нейрона. Структура связей и веса выбираются так, что:
. Все локальные максимумы функции консенсуса соответствуют приемлемым решениям задачи;
. Чем лучше приемлемое решение, тем больше консенсус соответствующего состояния машины Больцмана.
Перефразируем для МБ задачу коммивояжера.
. Состояние МБ соответствует локальному максимуму функции консенсуса, если и только если это состояние соответствует приемлемому маршруту.
. Чем короче маршрут, тем выше консенсус соответствующего состояния МБ.
Каждый нейрон соответствует элементу матрицы
, состояния нейронов обозначаются
(
- число городов). Функция консенсуса
Множество связей в сети определяется как объединение трех непересекающихся подмножеств:
- множество связей, несущих информацию о расстояниях между городами,
- множество ингибиторных (запретительных) связей,
- множество связей смещений,
Здесь
. Общее число связей равно
.
Ингибиторные связи гарантируют, что, в конце концов, ни в одной строке и ни в одном столбце не будет более одной единицы. Связи смещений гарантируют, что хотя бы по одной единице есть в каждом столбце и в каждой строке. Таким образом, связи
и
гарантируют выполнение ограничений в задаче и веса их дают одинаковые вклады в консенсусы для всех приемлемых маршрутов.
Связь
активна только в том случае, когда в маршруте есть прямой путь из города
в город
. Вес связи
равен расстоянию между городами
и
с отрицательным знаком. Следовательно, для данного маршрута отрицательный вклад связи из
в консенсус пропорционален длине пути, поэтому максимизация функции консенсуса соответствует минимизации длины маршрута.
Доказано, что для консенсуса
выполняются требования
и
, если и только если веса связей выбраны следующим образом:
где
При
было проведено 100 испытаний для
и 25 испытаний для
при различных начальных состояний МБ. Для
получено оптимальное решение, для
получено решение на
хуже оптимума. Вероятностный механизм функционирования МБ дает возможность получать на ней несколько лучшие результаты, чем на модели Хопфилда.
Содержание раздела
