Введение
ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ ВВЕДЕНИЕ 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
ПРИЛОЖЕНИЕ А
Задачи комбинаторной оптимизации широко распространены и встречаются практически во всех сферах человеческой деятельности. Решение этих задач связано с рядом трудностей. Например, полный перебор возможных решений, как правило, невозможен из -за большого объема вычислений. Из-за дискретности пространства решений неприменимы многие приемы, разработанные в математическом программировании. Однако для большинства прикладных задач достаточно получить хорошее приближенное решение. За счет отказа от поиска точного решения часто удается построить простые алгоритмы для сложных задач. Поэтому на практике часто используются приближенные методы как альтернатива полному перебору.
Решения подобных задач становится наиболее лучшим и быстрым, если в работе использовать нейронные сети. Нейронная сеть представляется как система «нейронов», взаимодействующих между собой подобно настоящим нейронным сетям мозга.
В рамках данной работы, будут рассматриваться решение двух задач - задача о назначениях и задача Коммивояжера, с помощью нейронной сети Хопфилда. Так же для более точного анализа используем один из точных методов решения задач оптимизации - метод ветвей и границ.
Цель работы заключается в исследовании возможности применения рекуррентных нейронных сетей для решения задач комбинаторной оптимизации (на примере задачи о назначениях и задачи Коммивояжера).
Рассмотрим следующие задачи, которые приведут к достижению цели:
• Разработка алгоритма решения классической задачи о назначениях и задачи Коммивояжера с помощью нейронной сети Хопфилда;
• Подбор оптимальных значений коэффициентов нейронной сети Хопфилда для задачи Коммивояжера и классической задачи о назначениях;
• Программная реализация разработанных алгоритмов;
• Анализ и сравнение результатов решений задач с помощью сети Хопфилда с решениями, которые были получены методом ветвей и границ.
В ходе данной работы, было проведено исследование возможности применения нейронных сетей для решения задач комбинаторной оптимизации (на примере задачи о назначениях и задачи Коммивояжера).
В результате проведения работы был разработан алгоритм для решения данных задач. Алгоритм работы программы для обеих задач будут совпадать, однако разница в том, что в задаче о назначениях исходная матрица представлена двумерным массивом с целочисленными элементами, а в задаче Коммивояжера двумерным массивом с вещественными элементами, а также в том, что функция энергии для обеих задач имеет разный вид.
Так же проведено тестирование программы. Тестирование заключалось в подборе наиболее оптимальных коэффициентов (весов синоптических связей) для поиска наилучшего решения задач. Проведя анализ результатов тестирования, можно сделать вывод, что, несмотря на небольшую погрешность в решении задач с помощью сети Хопфилда, её решение будет вычисляться быстрее метода ветвей и границ. За счет отказа от поиска очного решения часто удается построить простые алгоритмы для сложных задач. Поэтому на практике часто используются приближенные методы, как альтернатива полному перебору, а также преимущество скорости является наиболее важной стороной в решении задач с помощью нейронной сети.
Подводя итог, можно сказать о том, что все поставленные задачи были выполнены.
