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

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

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

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

Содержание слайда: Применение сети Хопфилда к задачам комбинаторной оптимизации Исследования возможности использования нейронных сетей для решения таких задач сегодня сформировали новую научную дисциплину - нейроматематику.

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

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

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

Содержание слайда: Рассмотрим классический пример NP-полной проблемы - так называемую задачу коммивояжера: На плоскости расположены N городов, определяемые парами их географических координат: (xi,yi), i=1..N. Некто должен, начиная с произвольного города, посетить все эти города, при этом в каждом побывать ровно один раз. Проблема заключается в выборе маршрута путешествия с минимально возможной общей длиной пути. Полное число возможных маршрутов равно , и задача поиска кратчайшего из них методом перебора весьма трудоемка. Приемлемое приближенное решение может быть найдено с помощью нейронной сети, для чего требуется переформулировать задачу на языке оптимизации функции энергии (Ляпунова)

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

Содержание слайда: Решение задачи коммивояжера Составим теперь целевую функцию E(S) задачи поиска оптимального маршрута. Она будет включать 4 слагаемых: Первые три слагаемых отвечают за допустимость маршрута: каждый город должен быть посещен не более чем один раз (в каждой строке матрицы имеется не более одной единицы), под каждым номером должно посещаться не более одного города (в каждом столбце - не более одной единицы) и, кроме того, общее число посещений равно числу городов N (в матрице всего имеется ровно N единиц):

Содержание слайда: Решение задачи коммивояжера Видно, что каждое из этих трех слагаемых обращается в нуль на допустимых маршрутах, и принимает значения больше нуля на недопустимых. Последнее, четвертое слагаемое минимизирует длину маршрута:

Содержание слайда: Решение задачи коммивояжера За dXY обозначено расстояние между городами X и Y. Отрезок пути X-Y включается в сумму только тогда, когда город Y является относительно города X либо предыдущим, либо последующим. Множители  , ,  и  имеют смысл относительных весов слагаемых. Общий вид функции энергии (Ляпунова) сети Хопфилда дается выражением:

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

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

Содержание слайда: Решение задачи коммивояжера Хопфилдом и Тэнком изложенная модель была опробована в вычислительном эксперименте. Нейронной сети удавалось находить близкие к оптимальным решения за приемлемые времена даже для задач с несколькими десятками городов.