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

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

Санкт-Петербургский Государственный Политехнический Университет

кафедра прикладной математики

Курсовая работа по методам оптимизации:

«Решение задач оптимизации генетическими алгоритмами

на примере задачи коммивояжера»

Студент Кацман Виктор, группа 33601/2

Оглавление

Введение

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.     
Постановка задачи

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

Коммивояжер - странствующий торговец должен объехать N городов. Известны затраты на переезд между i-ым и j-ым городами, которые заданы в виде матрицы C = (c[i][j]), i = 1..N, j = 1..N. Коммивояжер должен объехать все города один раз. Требуется определить, в каком порядке следует объезжать города, чтобы суммарные затраты были минимальны.

Задача коммивояжера называется симметричной, если затраты на переезд между парой городов не зависят от направления переезда, в противном случае задача несимметрична.

Задача коммивояжера называется замкнутой, если коммивояжеру требуется вернуться в стартовый город после посещения всех остальных, в противном случае задача незамкнута.

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

На вход получаем матрицу затрат 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-ый не включается в маршрут. Получаем следующую задачу:

2. В качестве переменных выбираем элементы «вектора номеров городов» X = (x[i]), i = 1..N, x[i] ; ∀j ≠ k: x[j] ≠ x[k]. Получаем следующую задачу:

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

Генетический алгоритм - это эвристический алгоритм поиска, используемый для решения оптимизационных задач путем случайного подбора, комбинирования и вариации исходных параметров.

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

Задача формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора <#"724410.files/image003.gif"> N^2.

Алгоритм поиска N-ой статистики:

partition (arr, l, r)

{= arr[r];= l - 1;(j = l; j < r - 1; j++)

{(arr[j] <= x)

{++; (i != j)

{[j] += arr[i];[i] = arr[j] - arr[i];[j] = arr[j] - arr[i];

}

}

}++;(i != r){ arr[r] += arr[i]; arr[i] = arr[r] - arr[i]; arr[r] = arr[r] - arr[i];}i;

}

_partition (arr, l, r)

{= rand () % (r - l) + l;(i != r){ arr[r] += arr[i]; arr[i] = arr[r] - arr[i]; arr[r] = arr[r] - arr[i];}partition (arr, l, r);

}

_i_min (arr, l, r, i)

{(l == r) return arr[l];= rand_partition (arr, l, r);= q - l + 1;(i == k) return arr[k];if (i < k) return choose_i_min (arr, l, q - 1, i);return choose_i_min (arr, q + 1, r, i - k);

}

Данный оператор отбора можно существенно улучшить, если учитывать не только значения функции приспособленности, но и саму популяцию, а именно, выбирать особи, не схожие друг с другом. Отчасти этот недостаток в текущей модели восполняется мутациями по двум городам.

. Критерий сходимости популяции:

В исследованиях использовалось два критерия сходимости популяции: по прохождении определенного числа итераций и по достижению модулем разности между минимальным значением функции приспособленности и N-ой статистики выборки из функций приспособленности всех особей числа меньшего некоторого ε > 0.

. Код основной части алгоритма:

solution_not_found = 1;

while (solution_not_found)

{(i = 0; i < cur_size; i++) {arr[i] = generation[i]->min;}_min = choose_i_min (arr, 0, cur_size - 1, G.size);

с = 0;(i = 0; i < cur_size; i++)

{(generation[i]->min <= k_min && с <= G.alloc*2)

{= generation[i];[i] = generation[с];[с++] = ext;

}

}_size = с;

//crossover(i = 0; i < cur_size; i++)

{(j = i+1; j < cur_size; j++)

{(!isEqual(generation[i], generation[j]))

{(crossover(generation[i], generation[j], &(generation[с]), &(generation[с + 1])))

с += 2;

}

}

}_size = с;

//mytationsmin_genmin = UINT_MAX;(i = 0; i < cur_size; i++) {(min_genmin > generation[i]->min) {min_genmin = generation[i]->min;}

}(mytations)

{(i = 0; i < cur_size; i++)

{(generation[i]->min == min_genmin) continue;= mytation (generation[i], ext1, ext2);= generation[i];[i] = ext3;= ext;

}

}_genmin = UINT_MAX;(i = 0; i < cur_size; i++) {(min_genmin > generation[i]->min) {min_genmin = generation[i]->min; solution_ind = i;}

}(min_genmin + eps > k_min) solution_not_found = 0;

}

. Оценки алгоритма:

Таким образом, описанная выше реализация генетического алгоритма использует:

·        O(N^3) памяти: O(N) требуется для хранения одной особи, максимально возможный размер популяции (перед отбором) составляет O(N^2).

·        O(N^3) времени на одну итерацию (наибольшее время уходит на кроссовер: требуется O(N^2) операций кроссовера, трудоемкость каждой из которых O(N))

Оценка трудоемкости всего алгоритма зависит от выбранного критерия сходимости популяции: в случае выбора первого критерия - O(N^3 * M), где M - число итераций; в случае второго критерия теоретическая оценка затруднительна в связи с разнообразным набором возможных входных данных, практическая оценка будет приведена ниже.

Также затруднительна теоретическая оценка точности решения, это связано с тем, что задачи могут иметь принципиально разное количество значительно менее затратных путей. Практическая оценка будет приведена ниже.

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

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

Таблица 4.1

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

Данный тест представляют собой «несимметричные незамкнутые задачи коммивояжера» при количестве городов не больше 10, даются программе на вход в виде матрицы затрат. Использовался этот тест для уверенности в правильности работы точных алгоритмов перебора и динамического программирования, а также для исследования работы генетического алгоритма на задачах малой размерности.

Тест включает в себя по 100 задач каждой из размерностей 5, 6, 7, 9, 10, матрица ограничений содержит значения от 0 до 1000.

Результаты тестов (в левом столбце указаны номера алгоритмов, в остальных - результаты для соответствующей размерности входных данных; в ячейке указано время работы в тактах процессора и точность результата в виде частного разности между полученными и точными решениями и 1000 - верхнего ограничения данных):

Таблица 4.2

По результатам данного теста хорошо видна нецелесообразность использования алгоритма полного перебора для решения «задачи коммивояжера». Также можно заметить нецелесообразность использования генетического алгоритма без мутаций (21), потому как и время его работы и ошибка по сравнению с точным результатом растет быстрее, чем, например, у 3-его алгоритма (с одноточечным кроссовером и «циклической» мутацией для одного города и одной итерации).

Кроме того, из проведенных исследований следует, что для решения «задач коммивояжера» малой размерности лучше подходит алгоритм динамического программирования (и по времени и по точности).

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

Данный тест представляют собой «несимметричные незамкнутые задачи коммивояжера» при количестве городов порядка 15-19, даются программе на вход в виде матрицы затрат. Использовался этот тест для исследования времени и точности работы генетического алгоритма на задачах средней размерности.

Тест включает в себя по 100 задач каждой из размерностей 15, 17, 19, матрица ограничений содержит значения от 0 до 1000.

Результаты тестов (в левом столбце указаны номера алгоритмов, в остальных - результаты для соответствующей размерности входных данных; в ячейке указано время работы в тактах процессора и точность результата в виде частного разности между полученными и точными решениями и 1000 - верхнего ограничения данных):

Таблица 4.3

По результатам данного теста хорошо видна нецелесообразность использования динамического программирования для решения «задачи коммивояжера» ввиду больших временных затрат. Трудоемкость работы генетического алгоритма на основе исследований составляет o(N^4), что позволяет надеяться на достаточно быстрое решение задачи высокой размерности. Плохую тенденцию представляет ухудшение точности: средняя разность между полученным и оптимальным значениями растет быстрее, чем линейно относительно N*1000 (1000 - верхняя граница данных). Для решения этой проблемы можно применять алгоритм несколько раз и брать наилучший результат, это может привести к лучшему результату в связи со случайными генерациями мутаций.

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

Данный тест представляют собой «несимметричные незамкнутые задачи коммивояжера» при количестве городов до 100, даются программе на вход в виде матрицы затрат. Использовался этот тест для исследования времени работы генетического алгоритма на задачах высокой размерности. Оценить отклонение полученного решения от точного на данных задачах затруднительно в связи с длительным временем, необходимым для получения точного решения

Тест включает в себя по 100 задач каждой из размерностей 40, 60, 80, 100 матрица ограничений содержит значения от 0 до 1000.

Результаты тестов (в левом столбце указаны номера алгоритмов, в остальных - результаты для соответствующей размерности входных данных; в ячейке указано время работы в тактах процессора):

Таблица 4.4

По результатам проведенных тестов на трудоемкость можно подвести следующие итоги по оценкам скорости работы генетического алгоритма:

·        На процедуры алгоритма выполняющиеся один раз за весь алгоритм независимо от количества итераций тратится примерно треть времени от первой итерации или одноитерационного алгоритма (следует из сравнения времен, затраченных алгоритмами со сходимостью по конечному числу итераций).

·        В среднем, в алгоритме со сходимостью по второму критерию проходит не более log(N)*5 итераций. Это подтверждает общую оценку трудоемкости алгоритма o(N^4).

·        Оператор кроссовера «по частям» работает примерно столько же, сколько одноточечный оператор кроссовера и любой из них работает быстрее двухточечного оператора кроссовера.

·        «Не циклическая» мутация по двум городам работает медленнее, чем «циклическая» мутация по одному городу и дает не лучший результат (исходя из результатов предыдущих тестов), её использование в алгоритме нецелесообразно.

·        В целом, все вариации генетического алгоритма работают примерно одинаковое время, что дает возможность их комбинировать между собой без увеличения трудоемкости алгоритма.

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

«Алгоритм повторных применений» генетического алгоритма представляет собой решение одной и той же задачи несколько раз модификациями генетического алгоритма с последующим выбором наилучшего результата. В данном случае его использование представляется очень уместным, поскольку разные модификации генетического алгоритма для одной задачи могут дать решения сильно различающейся точности (разностью с оптимальным решением).

Задачей исследований является установить точность, которую можно будет ожидать при решении задач высокой размерности. (Время работы «Алгоритм повторных применений» генетического алгоритма можно оценить исходя из времен работы входящих в него модификаций генетического алгоритма)

Для этого исследуется точность, которую можно ожидать от решения задачи средней размерности различными комбинациями модификаций генетического алгоритма.

Тест включает в себя по 5 задач каждой из размерностей 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23 матрица ограничений содержит значения от 0 до 1000.

Результаты тестов (в левом столбце указаны алгоритмы (в виде номеров входящих в них модификаций, отобраны на основе точности, показанной предыдущими тестами), в остальных - результаты для соответствующей размерности входных данных; в ячейке указана точность результата в виде частного разности между полученными и точными решениями и 1000 - верхнего ограничения данных):

Таблица 4.5

По результатам проведенных тестов на точность можно подвести следующие итоги по оценкам точности работы генетического алгоритма:

·        Как и ожидалось, алгоритм, включающий в себя все вариации, оказался наиболее точным (решение, возвращаемое им, ближайшее к оптимальному).

·        Из мутаций наилучшую точность обеспечивают «не циклическая» по двум городам и «смешанная» по двум городам. То, что наиболее точные решения достигаются при мутациях для двух городов говорит о возможности достижения лучших результатов при увеличении числа городов, подвергающихся мутациям.

·        Из кроссоверов наилучшую точность обеспечивают кроссовер «по частям» и двухточечный кроссовер, что, в сочетании с более быстрой работой кроссовера «по частям» дает преимущества в его использовании. Также, это говорит о том, что при увеличении числа городов точность решения при использовании кроссовера «по частям» наверняка будет улучшаться по сравнению с точностью решения при использовании двухточечного кроссовера (в связи с тем, что кроссовер будет влиять на расположение большего числа городов в потомстве).

·        В целом, результаты позволяют ожидать точности примерно 20% от N для наилучших модификаций за достаточно быстрое время. Благодаря этому, появляется возможность оценить значение целевой функции в оптимальной точке. Теоретически, дальше можно применять различные модификации генетического алгоритма до тех пор, пока это значение не будет достигнуто, но оценить количество требуемых применений и модификации, которые следует применять затруднительно.

генетический алгоритм коммивояжер программирование

Выводы

Генетический алгоритм решения «задачи коммивояжера» представляет собой один из самых быстрых алгоритмов решающих «задачу коммивояжера». Таким образом, его использование оправдано для быстрого получения приближенного решения. Модифицирование генетического алгоритма позволяет стабилизировать его ожидаемую точность и на основании этого оценить значение целевой функции в оптимальной точке, но не позволяет получить саму оптимальную точку.

Литература

1. Д.И. Батищев, С.А. Исаев. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов (1997)

2.      Д.И. Батищев, С.А. Исаев, Е.К. Ремер. Эволюционно-генетический подход к решению задач невыпуклой оптимизации (1998)

.        Р. Акоф, М. Сасиени, Основы исследования операций, Издательство «Мир», (1971).

.        Задачи оптимизации и нечеткие переменные (1980)

.        А.И. Орлов. Теория принятия решений (2004)

6.      R. Allenson. Genetic Algorithms with Gender for Multivariate Optimisation. (1992).

.        Blickle, Thiele "A Comparison of Selection Schemes used in Genetic Algorithms" (1993)

.        Darrel Whitley "A Genetic Algorithm Tutorial" (1993).