Введение
ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ ВВЕДЕНИЕ 5
1. КОМБИНАТОРНАЯ ОПТИМИЗАЦИЯ 7
1.1 Общее описание задач оптимизации 7
1.2 Точные методы решения оптимизационных задач 9
1.3 Методы локального поиска для решения оптимизационных задач 13
2. НЕЙРОСЕТЕВЫЕ АЛГОРИТМЫ И МАТЕМАТИЧЕСКАЯ
ПОСТАНОВКА ЗАДАЧ ОПТИМИЗАЦИИ 17
2.1 Нейронная сеть Хопфилда 19
2.1.1 Сеть Хопфилда с дискретными состояниями и дискретным временем 22
2.1.2 Сеть Хопфилда с непрерывными состояниями и дискретным временем 24
2.1.3 Сеть Хопфилда с непрерывными состоянием и непрерывным временем 25
2.2 Постановка задачи о назначении 26
2.3 Постановка задачи Коммивояжера 27
2.4 Алгоритм решения задач 29
3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ 31
3.1 Выбор языка программирования и программного обеспечения 31
3.2 Описание классов используемых в программе 32
3.3 Описание работы программы, её тестирование и анализ полученных данных.... 36
ЗАКЛЮЧЕНИЕ 42
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 43
ПРИЛОЖЕНИЕ А
Купить

Задачи комбинаторной оптимизации широко распространены и встречаются практически во всех сферах человеческой деятельности. Решение этих задач связано с рядом трудностей. Например, полный перебор возможных решений, как правило, невозможен из -за большого объема вычислений. Из-за дискретности пространства решений неприменимы многие приемы, разработанные в математическом программировании. Однако для большинства прикладных задач достаточно получить хорошее приближенное решение. За счет отказа от поиска точного решения часто удается построить простые алгоритмы для сложных задач. Поэтому на практике часто используются приближенные методы как альтернатива полному перебору.
Решения подобных задач становится наиболее лучшим и быстрым, если в работе использовать нейронные сети. Нейронная сеть представляется как система «нейронов», взаимодействующих между собой подобно настоящим нейронным сетям мозга.
В рамках данной работы, будут рассматриваться решение двух задач - задача о назначениях и задача Коммивояжера, с помощью нейронной сети Хопфилда. Так же для более точного анализа используем один из точных методов решения задач оптимизации - метод ветвей и границ.
Цель работы заключается в исследовании возможности применения рекуррентных нейронных сетей для решения задач комбинаторной оптимизации (на примере задачи о назначениях и задачи Коммивояжера).
Рассмотрим следующие задачи, которые приведут к достижению цели:
• Разработка алгоритма решения классической задачи о назначениях и задачи Коммивояжера с помощью нейронной сети Хопфилда;
• Подбор оптимальных значений коэффициентов нейронной сети Хопфилда для задачи Коммивояжера и классической задачи о назначениях;
• Программная реализация разработанных алгоритмов;
• Анализ и сравнение результатов решений задач с помощью сети Хопфилда с решениями, которые были получены методом ветвей и границ.
Купить