Решение задачи коммивояжера нейросетевыми методами

Хопфилда является не единственным ее достоинством, которое используется на практике.

Другим важным свойством этой архитектуры является уменьшение ее целевой функции в форме энергии, что можно рассматривать как алгоритм оптимизации этой функции.

широк: в него попадают все билинейные и квадратичные формы с

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

Применение сети Хопфилда к задачам комбинаторной оптимизации

сформировали новую научную дисциплину - нейроматематику.

Применение сети Хопфилда к

задачам комбинаторной оптимизации

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

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

САПР и иные, при внешней кажущейся простоте постановки имеют решения,

которые можно получить только полным перебором вариантов.

Применения сети Хопфилда к задачам комбинаторной оптимизации

в задаче (например, как N!), и поиск точного решения для

практически полезных значений N становится заведомо неприемлимо дорогим.
Такие задачи называют неполиномиально сложными или NP-полными. Если удается сформулировать такую задачу в терминах оптимизации функции энергии (информации, Ляпунова), то нейронная сеть дает весьма мощный инструмент поиска приближенного решения.

Применения сети Хопфилда к задачам комбинаторной оптимизации

D...). Произвольный маршрут может быть представлен в виде таблицы, в

которой единица в строке, отвечающей данному городу, определяет его номер в маршруте. Сопоставим теперь клетке
таблицы на пересечении
строки X и столбца i
нейрон Sxi из {0,1}.
Возбужденное состояние
данного нейрона
сигнализирует
о том, что город X в
маршруте
следует посещать
в i-тую очередь.

для нейросети, и динамика полученной системы будет приводить к уменьшению

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

Решение задачи коммивояжера

Нейронной сети удавалось находить близкие к оптимальным решения за приемлемые

времена даже для задач с несколькими десятками городов.

Решение задачи коммивояжера