Введение 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
Приложение
Купить

В настоящий момент одна из основных проблем теоретической информатики остается до сих пор открытой: равенство классов P и NP. Пока доказательство не найдено, NP-полные задачи остаются трудноразрешимыми с вычислительной точки зрения. На основе желания составить и реализовать в виде компьютерной программы алгоритм, который будет решать сложные задачи, были предложены генетические алгоритмы конце шестидесятых - начале семидесятых годов XX века. Они являются эвристическими алгоритмами поиска, базирующиеся на теории естественной эволюции Чарльза Дарвина и возникшие в результате наблюдения и попыток копировать естественные процессы, происходящие в мире живых организмов, такие, как скрещивание и мутация для отбора популяции живых существ.
Данная работа посвящена изучению генетического алгоритма для решения одной из самых известных NP-полных задач - задачи коммивояжера, суть которой отражается в поиске минимального пути, содержащего все вершины, начиная со стартовой и возвращающийся в исходную вершину. Эта задача встречается в различных областях деятельности (экономика, физика, технические науки и т.п.). Созданы различные алгоритмы для решения задачи коммивояжера, включающие приближенные и точные.
Целью работы является рассмотрение работы генетического алгоритма на примере задачи коммивояжера и произведение сравнительного анализа с некоторыми другими алгоритмами по оценке времени и сложности, а также точности решения. Следует выяснить, от чего зависит получения хорошего решения генетического алгоритма, и какие проблемы остаются неразрешенными.
Основным инструментом для практического исследования была выбрана среда разработки Visual Studio, поскольку она имеет множество
встроенных функций и панелей инструментов для решения задач генетического программирования и их визуального представления.

Купить