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

Сентябрь 3, 2022

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

Содержание

2. Применение сети Хопфилда к задачам комбинаторной оптимизации Ассоциативность памяти нейронной сети Хопфилда является не единственным ее
3. Класс целевых функций, которые могут быть минимизированы нейронной сетью достаточно широк: в него попадают все билинейные
4. Исследования возможности использования нейронных сетей для решения таких задач сегодня сформировали новую научную дисциплину - нейроматематику.
5. Применения сети Хопфилда к задачам комбинаторной оптимизации Применение нейронных сетей для решения традиционных математических задач выглядит
6. Многие задачи оптимального размещения и планирования ресурсов, выбора маршрутов, задачи САПР и иные, при внешней кажущейся
7. Часто число вариантов быстро возрастает с числом структурных элементов N в задаче (например, как N!), и
9. Решение задачи коммивояжера Обозначим названия городов заглавными буквами (A, B, C, D...). Произвольный маршрут может быть
10. Решение задачи коммивояжера
11. Решение задачи коммивояжера
12. Решение задачи коммивояжера
13. Решение задачи коммивояжера
14. Обучение Хебба можно заменить прямым заданием указанных весов и порогов для нейросети, и динамика полученной системы
16. Скачать презентацию

Слайд 2

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

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

Слайд 3

Класс целевых функций, которые могут быть минимизированы нейронной сетью достаточно широк:

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

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

Слайд 4

Исследования возможности использования нейронных сетей для решения таких задач сегодня сформировали

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

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

Слайд 5

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

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

Слайд 6

Многие задачи оптимального размещения и планирования ресурсов, выбора маршрутов, задачи САПР

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

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

Слайд 7

Часто число вариантов быстро возрастает с числом структурных элементов N в

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

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

Слайд 8

Слайд 9

Решение задачи коммивояжера
Обозначим названия городов заглавными буквами (A, B, C, D...).

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

Слайд 10