📄Работа №35444
Тема: Анализ генетического алгоритма для приближенного решения задачи коммивояжера
Тип работы
Дипломные работы, ВКР
Предмет
Информатика и вычислительная техника
Объем:
76 листов
Год:
2019
Просмотров:
778
6500
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 4
1 Теоретическая часть 5
1.1 Задача коммивояжера 5
1.2 Генетические алгоритмы 7
1.3 Операции генетического алгоритма 9
1.3.1 Инициализация 9
1.3.2 Отбор 9
1.3.3 Кроссовер 9
1.3.4 Мутации 10
1.3.5 Проверка условия остановки 10
1.4. Генетический алгоритм для решения задачи коммивояжера 10
1.4.1 Операции и модели для решаемой задачи 10
1.4.2 Модель маршрута и популяции 11
1.4.3 Формирование начальной популяции 12
1.4.4 Скрещивание 12
1.4.5 Мутация 13
1.4.6 Отбор в следующее поколение 14
1. Реализация генетического алгоритма для задачи коммивояжера 14
1.1 Входные данные 14
1.1.1 XML-файл 15
1.1.2 Список 16
1.2 Выходные данные 17
1.3 Решение задачи в Windows Form 19
1.4 Классы приложения 21
1.5 Интерфейс приложения 23
2. Эксперименты и анализ результатов 25
2.1 Дополнительные вычисления 26
2.1.1 Реализация метода полного перебора 26
2.1.2 Реализация алгоритма неравенства треугольника 28
2.2 Эксперименты 29
2.2.1 Анализ сложности генетического алгоритма 29
2.2.2 Анализ времени генетического алгоритма 31
2.2.3 Сравнение точности генетического алгоритма 32
2.2.4 Зависимость решения от параметров 33
Заключение 41
Список литературы 42
Список терминов 43
Приложение
1 Теоретическая часть 5
1.1 Задача коммивояжера 5
1.2 Генетические алгоритмы 7
1.3 Операции генетического алгоритма 9
1.3.1 Инициализация 9
1.3.2 Отбор 9
1.3.3 Кроссовер 9
1.3.4 Мутации 10
1.3.5 Проверка условия остановки 10
1.4. Генетический алгоритм для решения задачи коммивояжера 10
1.4.1 Операции и модели для решаемой задачи 10
1.4.2 Модель маршрута и популяции 11
1.4.3 Формирование начальной популяции 12
1.4.4 Скрещивание 12
1.4.5 Мутация 13
1.4.6 Отбор в следующее поколение 14
1. Реализация генетического алгоритма для задачи коммивояжера 14
1.1 Входные данные 14
1.1.1 XML-файл 15
1.1.2 Список 16
1.2 Выходные данные 17
1.3 Решение задачи в Windows Form 19
1.4 Классы приложения 21
1.5 Интерфейс приложения 23
2. Эксперименты и анализ результатов 25
2.1 Дополнительные вычисления 26
2.1.1 Реализация метода полного перебора 26
2.1.2 Реализация алгоритма неравенства треугольника 28
2.2 Эксперименты 29
2.2.1 Анализ сложности генетического алгоритма 29
2.2.2 Анализ времени генетического алгоритма 31
2.2.3 Сравнение точности генетического алгоритма 32
2.2.4 Зависимость решения от параметров 33
Заключение 41
Список литературы 42
Список терминов 43
Приложение
📖 Введение
В настоящий момент одна из основных проблем теоретической информатики остается до сих пор открытой: равенство классов P и NP. Пока доказательство не найдено, NP-полные задачи остаются трудноразрешимыми с вычислительной точки зрения. На основе желания составить и реализовать в виде компьютерной программы алгоритм, который будет решать сложные задачи, были предложены генетические алгоритмы конце шестидесятых - начале семидесятых годов XX века. Они являются эвристическими алгоритмами поиска, базирующиеся на теории естественной эволюции Чарльза Дарвина и возникшие в результате наблюдения и попыток копировать естественные процессы, происходящие в мире живых организмов, такие, как скрещивание и мутация для отбора популяции живых существ.
Данная работа посвящена изучению генетического алгоритма для решения одной из самых известных NP-полных задач - задачи коммивояжера, суть которой отражается в поиске минимального пути, содержащего все вершины, начиная со стартовой и возвращающийся в исходную вершину. Эта задача встречается в различных областях деятельности (экономика, физика, технические науки и т.п.). Созданы различные алгоритмы для решения задачи коммивояжера, включающие приближенные и точные.
Целью работы является рассмотрение работы генетического алгоритма на примере задачи коммивояжера и произведение сравнительного анализа с некоторыми другими алгоритмами по оценке времени и сложности, а также точности решения. Следует выяснить, от чего зависит получения хорошего решения генетического алгоритма, и какие проблемы остаются неразрешенными.
Основным инструментом для практического исследования была выбрана среда разработки Visual Studio, поскольку она имеет множество
встроенных функций и панелей инструментов для решения задач генетического программирования и их визуального представления.
Данная работа посвящена изучению генетического алгоритма для решения одной из самых известных NP-полных задач - задачи коммивояжера, суть которой отражается в поиске минимального пути, содержащего все вершины, начиная со стартовой и возвращающийся в исходную вершину. Эта задача встречается в различных областях деятельности (экономика, физика, технические науки и т.п.). Созданы различные алгоритмы для решения задачи коммивояжера, включающие приближенные и точные.
Целью работы является рассмотрение работы генетического алгоритма на примере задачи коммивояжера и произведение сравнительного анализа с некоторыми другими алгоритмами по оценке времени и сложности, а также точности решения. Следует выяснить, от чего зависит получения хорошего решения генетического алгоритма, и какие проблемы остаются неразрешенными.
Основным инструментом для практического исследования была выбрана среда разработки Visual Studio, поскольку она имеет множество
встроенных функций и панелей инструментов для решения задач генетического программирования и их визуального представления.
✅ Заключение
В ходы выполнения работы была разработана пользовательская программа в программе Visual Studio на языке C++ для решения задачи коммивояжера. Конечная программа находит наименьшее решение с помощью генетического алгоритма и строит минимальный маршрут. Также были реализованы алгоритмы полного перебора и неравенства треугольника для решения задачи коммивояжера. По результатам трех алгоритмов были сделаны эксперименты для оценки генетического алгоритма.
Генетические алгоритмы при небольшом количестве вершин в графе могут давать точное решение за небольшое время с помощью регулирования параметра количества поколений. Данный параметр единственный сохранял закономерность в процессе всех экспериментов. С увеличением количества вершин достижение точности решения усложняется, однако эксперименты показали, что погрешность вычислений не более, чем в два раза, что является большим преимуществом над другими алгоритмами.
Обобщая все эксперименты, можно сделать вывод, что генетический алгоритм дает огромное преимущество во времени решения задачи коммивояжера, и при большом количестве городов, увеличение количество поколений является единственной закономерностью для минимизации маршрута. Вероятность получения точного решения невелика при больших данных, но мое исследование еще продолжается, поскольку в моей работе были рассмотрены далеко не все зависимости и комбинации параметров.
Генетические алгоритмы при небольшом количестве вершин в графе могут давать точное решение за небольшое время с помощью регулирования параметра количества поколений. Данный параметр единственный сохранял закономерность в процессе всех экспериментов. С увеличением количества вершин достижение точности решения усложняется, однако эксперименты показали, что погрешность вычислений не более, чем в два раза, что является большим преимуществом над другими алгоритмами.
Обобщая все эксперименты, можно сделать вывод, что генетический алгоритм дает огромное преимущество во времени решения задачи коммивояжера, и при большом количестве городов, увеличение количество поколений является единственной закономерностью для минимизации маршрута. Вероятность получения точного решения невелика при больших данных, но мое исследование еще продолжается, поскольку в моей работе были рассмотрены далеко не все зависимости и комбинации параметров.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.