новая папка 1 / 294549
.pdfВведем понятие операции композиции двух хромосом. Хромосома R называется композицией двух хромосом М и Q тогда и только тогда, когда существует элемент Pi , такой, что Pi M и является последним в М, и
Pi Q и является первым в Q.
Отношение – связь между любыми объектами в природе. Отношение между популяциями – это пара, причем упорядоченная, первая компонента которой является новой популяцией, а вторая – областью задания отношения. В отличие от понятия множества понятие отношения является определенным понятием.
Выше рассматривались четкие множества. В них можно однозначно сказать, является ли рассматриваемый объект элементом этого множества. Следовательно, эти множества имеют четкие границы, определяющие принадлежность или непринадлежность элемента множеству. В генетических алгоритмах не всегда можно провести четкую грань между принадлежностью и непринадлежностью элементов множеству.
5. Практическое применение генетического алгоритма
Рассмотрим применение генетических алгоритмов, например при решении задачи коммивояжёра. Эта одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
Стоить отметить, что задача коммивояжёра относится к числу трудновычислимых задач: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.
Для ускорения процесса вычислений может быть использован генетический алгоритм; он не всегда дает точное значение, чаще всего приближенное, но при большом количестве вершин способен сильно сэкономить время вычисления.
Программа, помимо генетического алгоритма, использует алгоритм перестановок, который дает точное решение. Его можно сравнить с результатом, который был получен в процессе работы генетического алгоритма.
Рассмотрим в качестве примера граф, который хранится в текстовом файле. Первое число указывает количество вершин в графе. Далее идет матрица смежности, в которой указаны связи между городами с указанием расстояния. В нашем примере для наглядности используется граф с 10 вершинами (табл. 6).
11
|
|
Пример графа в задаче коммивояжера |
|
Таблица 6 |
||||||
|
|
|
|
|
||||||
0 |
2 |
4 |
2 |
5 |
6 |
4 |
1 |
2 |
|
3 |
4 |
0 |
5 |
3 |
4 |
2 |
3 |
4 |
2 |
|
4 |
9 |
7 |
0 |
5 |
7 |
5 |
7 |
8 |
4 |
|
8 |
4 |
3 |
6 |
0 |
2 |
5 |
4 |
6 |
7 |
|
3 |
2 |
4 |
6 |
3 |
0 |
6 |
2 |
6 |
4 |
|
6 |
3 |
4 |
5 |
6 |
7 |
0 |
8 |
3 |
4 |
|
5 |
1 |
2 |
3 |
4 |
1 |
3 |
0 |
2 |
2 |
|
3 |
2 |
4 |
5 |
7 |
9 |
6 |
7 |
0 |
5 |
|
7 |
4 |
6 |
3 |
6 |
4 |
6 |
5 |
5 |
0 |
|
7 |
2 |
2 |
4 |
2 |
1 |
2 |
1 |
2 |
1 |
|
0 |
Программа считывает данную информацию и записывает ее в динамический массив, после чего происходит его обработка. Сначала формируется начальная популяция с использыванием метода «жадного» алгоритма. Это самая первая популяция имеет следующий вид:
Фрагмент работы программы
Популяции: |
|
-1- |
|
1 10 9 8 7 6 5 4 3 2 |
46 |
4 10 9 5 7 6 8 3 2 1 |
34 |
3 10 9 8 7 6 5 4 2 1 |
45 |
2 10 9 8 6 5 4 3 7 1 |
42 |
5 10 9 8 7 6 4 3 2 1 |
50 |
4 10 9 5 7 6 8 3 2 1 |
34 |
2 10 9 8 7 6 4 3 5 1 |
43 |
3 10 9 8 7 5 4 6 2 1 |
42 |
9 10 8 7 6 5 4 3 2 1 |
48 |
-2- |
|
4 10 2 5 7 6 8 3 9 1 |
32 |
4 10 9 5 7 6 8 3 2 1 |
34 |
9 10 2 5 7 6 8 3 4 1 |
37 |
2 10 9 8 6 5 4 3 7 1 |
42 |
3 10 9 8 1 5 4 6 2 7 |
39 |
… |
|
Далее за конечное число шагов последовательно выполняются мутация, скрещивание и отбор. По окончании происходит поиск наименьшего пути.
В нашем примере цикл генетического алгоритма отработал 10 раз и дал результат – путь 2 10 4 5 7 8 9 3 6 1 с расстоянием 30. Это гораздо лучше, чем результат, полученный на первом этапе при формировании началь-
12
ной популяции; там кратчайший путь равнялся 34. На это ушло 52 миллисекунды.
Фрагмент работы программы
… |
|
-9- |
|
4 10 2 5 7 8 9 3 6 1 |
31 |
4 10 2 5 7 8 3 9 6 1 |
33 |
4 10 2 5 7 6 8 3 9 1 |
32 |
4 10 2 5 7 8 9 3 6 1 |
31 |
4 10 2 5 7 8 9 3 6 1 |
31 |
4 10 2 5 7 8 9 3 6 1 |
31 |
4 10 2 5 7 8 9 3 6 1 |
31 |
-10- |
|
2 10 4 5 7 8 9 3 6 1 |
30 |
4 10 2 5 7 8 3 9 6 1 |
33 |
4 10 2 5 7 6 8 3 9 1 |
32 |
4 10 2 5 7 8 9 3 6 1 |
31 |
4 10 2 5 7 8 9 3 6 1 |
31 |
4 10 2 5 7 8 9 3 6 1 |
31 |
4 10 2 5 7 8 9 3 6 1 |
31 |
4 10 2 5 7 8 9 3 6 1 |
31 |
Кратчайший путь = 30
Маршрут коммивояжера: 2-10-4-5-7-8-9-3-6-1
Время работы алгоритма = 52 ms.
Теперь для проверки корректности решения программа делает полный перебор всевозможных решений, используя алгоритм перестановок; как и говорилось ранее, данный алгоритм применим лишь при малом количестве вершин. Для 10 вершин алгоритм отработал очень быстро (17 миллисекунд) и дал точное решение – путь 1 8 2 6 9 3 4 10 7 5 с расстоянием 28.
Фрагмент работы программы Алгоритм перестановок в задаче коммивояжера
Перестановка: |
|
1 2 3 4 5 6 7 8 10 9 |
44 |
1 2 3 4 5 6 7 9 10 8 |
43 |
1 2 3 4 5 6 7 10 9 8 |
41 |
1 2 3 4 5 6 8 7 10 9 |
40 |
1 2 3 4 5 6 8 9 10 7 |
39 |
1 2 3 4 5 6 9 7 10 8 |
38 |
1 2 3 4 5 6 10 7 9 8 |
37 |
1 2 3 4 5 7 6 8 10 9 |
36 |
1 2 3 4 5 7 6 10 9 8 |
34 |
13
1 2 4 5 7 3 6 10 9 8 |
32 |
1 2 4 5 7 9 3 6 10 8 |
30 |
1 2 6 8 9 3 4 10 7 5 |
29 |
1 8 2 6 9 3 4 10 7 5 |
28 |
Кратчайший путь = 28
Маршрут коммивояжера: 1-8-2-6-9-3-4-10-7-5.
Время работы алгоритма = 17 ms.
…
Теперь сравним результаты: точный 28, а приближенный 30. Погрешность вычислений оказалась незначительной, и длина пути возросла менее чем на 7 %. Можно сделать вывод, что генетический алгоритм работает и дает хорошее приближенное значение. При большем количестве вершин, например 66, генетический алгоритм обгонит по времени метод перестановок в миллиарды раз.
Генетический алгоритм дает преимущества при решении практических задач. Одно из них – это адаптация к изменяющейся окружающей среде. В реальной жизни проблема, которая была поставлена для решения изначально, может претерпеть огромные изменения в процессе своего решения. При использовании традиционных методов все вычисления приходится начинать заново, что приводит к большим затратам машинного времени. При эволюционном подходе популяцию можно анализировать, дополнять и видоизменять применительно к изменяющимся условиям, для этого не требуется полный перебор. Другое преимущество генетических алгоритмов для решения задач состоит в способности быстрой генерации достаточно хороших решений.
Эффективность генетического алгоритма – степень реализации запланированных действий алгоритма и достижение требуемых значений функции приспособленности. Эффективность во многом определяется структурой и составом начальной популяции.
14
Литература
1.Гладков Л.А. Генетические алгоритмы / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик. – М. : ФИЗМАТЛИТ, 2006. – 320 с.
2.Растригин Л.А. Адаптация сложных систем / Л.А. Растригин. – Ри-
га : Зинатне, 1981. – 375 с.
3.Панченко Т.В. Генетические алгоритмы : учебно-методическое пособие / Т.В. Панченко ; под ред. Ю.Ю. Тарасевича. – Астрахань : Издательский дом «Астраханский университет», 2007. – 87 с.
4.Букатова И.Л. Эвоинформатика : Теория и практика эволюционного моделирования / И.Л. Букатова, Ю.И. Михасев, А.М. Шаров. – М. : Нау-
ка, 1991. – 206 с.
15
Учебное издание
ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ: БАЗОВЫЕ ПОНЯТИЯ
Учебно-методическое пособие для вузов
Составители: Артемов Михаил Анатольевич, Стародубцев Игорь Юрьевич,
Стародубцева Наталья Александровна
Корректор В.П. Бахметьев Компьютерная верстка О.В. Шкуратько
Подписано в печать 24.06.2014. Формат 60×84/16. Усл. печ. л. 1. Тираж 25 экз. Заказ 464.
Издательский дом ВГУ 394000, г. Воронеж, пл. Ленина, 10
Отпечатано в типографии Издательского дома ВГУ 394000, г. Воронеж, ул. Пушкинская, 3
16