Решение задач оптимизации генетическими алгоритмами на примере задачи коммивояжера - Курсовая работа

Данная работа посвящена исследованию возможности решать дискретные оптимизационные задачи с помощью генетических алгоритмов.Коммивояжер - странствующий торговец должен объехать N городов. Коммивояжер должен объехать все города один раз.На вход получаем матрицу затрат C = (c[i][j]), i = 1..N, j = 1..N, c[i][j] - затраты на переезд из i-го города в j-ый, c[i][j] неотрицательно, ограниченно; при желании запретить переезд из i-го города в j-ый следует сделать c[i][j] максимально большим. В качестве переменных выбираем элементы матрицы переездов X = (x[i][j]), i = 1..N, j = 1..N, x[i][j] = {0,1}; x[i][j] = 1, если переезд из i-го города в j-ый включается в маршрут и x[i][j] = 0, если переезд из i-го города в j-ый не включается в маршрут.Генетический алгоритм - это эвристический алгоритм поиска, используемый для решения оптимизационных задач путем случайного подбора, комбинирования и вариации исходных параметров.Задача формализуется таким образом, чтобы ее решение могло быть закодировано в виде вектора («генотипа ») генов, где каждый ген может быть битом , числом или неким другим объектом.Создать начальную совокупность структур (популяцию) Оценить каждую структуру остановка := FALSE ПОВТОРИТЬ (F(размер популяции)) РАЗ НАЧАЛО Выбрать две структуры (родители) из множества предыдущей итерации Применить оператор кроссовера к выбранным структурам и получить две новые структуры (потомки)Создание начальной популяции: Перед первым шагом нужно случайным образом создать начальную популяцию; даже если она окажется совершенно неконкурентоспособной, вероятно, что генетический алгоритм все равно достаточно быстро переведет ее в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции, и на них можно было подсчитать функцию приспособленности.Заключается в полном переборе всевозможных маршрутов коммивояжера и выборе самого оптимального из них. Данный алгоритм позволяет получить точное решение задачи, использует O(N^2) памяти (память нужна для матрицы С и одного вектора Х). Однако данный алгоритм является очень трудоемким по времени работы, поскольку всего существует N! различных маршрутов, и использовать его имеет смысл только при N <15. В данной работе он использовался для тестирования результатов других алгоритмов при маленьких N. //solution_t - структура для хранения решений solution_t base_solve::solve ()В основе алгоритма лежит идея сравнения различных вариантов допустимых решений задачи (по значению целевой функции) не в конце построения множества всех возможных вариантов, а на каждом шаге построения возможных вариантов (подзадаче). Для «задачи коммивояжера» удобно выбрать следующие подзадачи и пересчет (способ перехода от одной подзадачи к другой): Подзадачи: для подмножества городов S из {1..N}, и j ? S, обозначим через D[S,j] длину кратчайшего пути, проходящего через все города S и заканчивающегося в j. Данный алгоритм позволяет получить точное решение задачи, использует O(N*2^N) памяти (память нужна для матриц C и D, а вариантов множества S - 2^N) и работает за O(N*2^N), так как должны заполниться все ячейки матрицы D. Таким образом, с помощью динамический алгоритм решения «задачи коммивояжера» можно использовать при N <25. //Bj - матрица, в которой хранятся индексы последних городов на соответствующих маршрутах в D solution_t *dinamic_solve::solve ()// zip_links_1/2 - вектора с индексами, указывающими на элементы zip_prnt в порядке, // отвечающему исходным маршрутам counter = 0; {zip_links_2[counter] = zip_numbers[links_to_vertices1[prnt2->result[i - 1]]]; {zip_res_links_1[i] = zip_res_links_2[i] = zip_links_1[i ]; {zip_res_links_1[i] = zip_res_links_2[i] = zip_links_1[i ]; while (zip_res_links_2[i] == zip_res_links_1[i]) {i-;} pnt1 = zip_res_links_2[i] = zip_links_1[i]; i2 = i - 1;Таблица 4.13 Генетический алгоритм с кроссовером «по частям», «цикличекой» мутацией для двух городов и 1 итерацией 4 Генетический алгоритм с кроссовером «по частям», «цикличекой» мутацией для двух городов и 2 итерациями 6 Генетический алгоритм с одноточечным кроссовером, «цикличекой» мутацией для одного города и вторым критерием сходимости 10 Генетический алгоритм с одноточечным кроссовером, «смешенной» мутацией для двух городов и вторым критерием сходимости 15 Генетический алгоритм с двухточечным кроссовером, «смешенной» мутацией для двух городов и вторым критерием сходимостиДанный тест представляют собой «несимметричные незамкнутые задачи коммивояжера» при количестве городов не больше 10, даются программе на вход в виде матрицы затрат. Использовался этот тест для уверенности в правильности работы точных алгоритмов перебора и динамического программирования, а также для исследования работы генетического алгоритма на задачах малой размерности.Данный тест представляют собой «несимметричные незамкнутые задачи коммивояжера» при количестве городов порядка 15-19, даются программе на вход в виде матрицы за

Оглавление

Введение

1. Постановка задачи

1.1 Общее описание задачи

1.2 Формальная постановка

2. Общее описание генетического алгоритма

2.1 Формализация задачи для решения генетическим алгоритмом

2.2 Общая схема алгоритма

2.3 Подробный разбор некоторых элементов алгоритма

3. Описание алгоритмов решения задачи

3.1 Алгоритм полного перебора

3.2 Алгоритм динамического программирования

3.3 Генетический алгоритм

4. Описание исследований и их результатов

4.1 Перечень тестировавшихся алгоритмов

4.2 Тест на задачах малой размерности

4.3 Тест на задачах средней размерности

4.4 Тест на задачах высокой размерности

4.5 Тест для исследования «алгоритма повторных применений» генетического алгоритма

Выводы

Литература

Данная работа посвящена исследованию возможности решать дискретные оптимизационные задачи с помощью генетических алгоритмов. Исследования проводились на примере решения «несимметричной незамкнутой задачи коммивояжера» - известной комбинаторной NP-трудной задачи, для которой наилучший известный на данный момент точный алгоритм работает с асимптотикой O(2^n). В ходе исследований результаты работы генетического алгоритма сравнивались с результатами работы с решением «несимметричной незамкнутой задачи коммивояжера» динамическим программированием по таким параметрам, как время работы, точность результата и объем используемой памяти на различных входных данных.

1.