Повышение эффективности работы генетического алгоритма в процессе решения задачи покрытия множеств

Автор: Коновалов И.С., Фатхи В.А., Кобак В.Г.

Журнал: Вестник Донского государственного технического университета @vestnik-donstu

Рубрика: Информатика, вычислительная техника и управление

Статья в выпуске: 4 т.19, 2019 года.

Бесплатный доступ

Введение. Практические задачи (размещение пунктов обслуживания, создание микросхем, составление расписаний и пр.) зачастую требуют точного или приближенного к точному решения при большой размерности. Достижение приемлемого результата в данном случае требует решения задачи покрытия множеств - фундаментальной для комбинаторики и теории множеств. Точное решение можно получить с помощью переборных методов, однако в этом случае при повышении размерности задачи во много раз возрастает время работы точного алгоритма. По этой причине следует увеличивать точность приближенных методов: они дают решение, лишь приближенное к точному, однако затрачивают на поиск ответа намного меньше времени при большой размерности. Материалы и методы. Описывается один из способов решения задачи покрытия - генетический алгоритм. Авторы используют модификацию модели Голдберга и пытаются повысить ее эффективность с помощью различных видов оператора мутации и скрещивания. Речь идет о генной мутации, двухточечной мутации, мутации добавления и удаления, мутации вставки и удаления, сальтации, мутациях на основе инверсии...

Еще

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

Короткий адрес: https://sciup.org/142221974

IDR: 142221974 | DOI: 10.23947/1992-5980-2019-19-4-389-397

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

Введение . Многие практические задачи требуют точного или приближенного к точному решения при большой размерности. Среди таких задач: размещение пунктов обслуживания, создание микросхем, составление расписаний. Достижение приемлемого результата в данном случае требует решения задачи покрытия множеств — фундаментальной для комбинаторики и теории множеств. Точное решение можно получить с помощью переборных методов (например, метода ветвей и границ). Естественно, при повышении размерности задачи во много раз возрастает время работы точного алгоритма. По этой причине следует увеличивать точность приближенных методов: они дают решение, лишь приближенное к точному, однако затрачивают на поиск ответа намного меньше времени при большой размерности.

Наглядным примером может служить также следующая практическая задача. Допустим, необходимо собрать команду специалистов для корабля. Члены экипажа должны обладать в совокупности всеми требуемыми навыками, но количество сотрудников должно быть минимальным. Это невзвешенная задача покрытия, то есть «весы» членов группы одинаковы и поэтому не важны. Если же каждому члену команды поставить в соответствие какую-то величину — вес (например, опыт работы), то задача станет взвешенной. Актуальной практической проблемой является решение данной задачи за более короткое время, которое позволяет получить результат, как можно более приближенный к точному.

Материалы и методы

Постановка задачи. Дано множество U из n элементов и совокупность подмножеств U , S = { S 1 ,…, S k }. Каждому подмножеству S i сопоставлена некоторая неотрицательная стоимость c : S → Q + . S' ⊆ S является покрытием, если любой элемент из U принадлежит хотя бы одному элементу из S' [1, 2].

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

Методы решения задачи. Генетический алгоритм. Задачи покрытия решаются с помощью эвристических методов, приближенных алгоритмов с априорной оценкой, точных алгоритмов [3, 4].

Точные алгоритмы (самый известный из них — метод ветвей и границ) дают точное решение, но в задачах большой размерности бесполезны, т. к. затрачивают слишком много времени. Если точностью решения можно до известной степени пренебречь, рекомендуется использовать приближенные алгоритмы [5], которые решают задачу за приемлемое время. Речь идет об алгоритмах с априорной оценкой (например, жадный алгоритм [6]) и вероятностных эвристиках (метод муравьиных колоний [7, 8], нейронные сети, эволюционные вычисления).

В данной статье рассматриваются генетические алгоритмы (ГА) и способы повышения их эффективности. В 1975 году Джон Холланд предложил ГА вероятностного характера, основанные на правилах естественного отбора и наследования. Свойства ГА исследуются в [10, 11]. Подробное описание применимости генетического алгоритма для решения задачи покрытия приводится в [1]. Способы применения ГА для данной задачи описаны в [12, 13].

Авторы представленного исследования применяют модель Голдберга [14], которая модифицирована следующим образом: использованы различные виды оператора мутации и скрещивания, обеспечена защита от появления «неправильных» покрытий в процессе изменения особей.

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

^ CjXj ^ min, j=1

где x k — n -мерный вектор, у которого j -й элемент x kj равен 1, если подмножество Sj является составной частью покрытия, и равен 0 в ином случае; c j — стоимость подмножества S j .

Условие останова алгоритма — количество поколений неизменности решения.

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

В [15] описана модификация данного алгоритма с помощью стратегии формирования элитных особей.

Обзор видов оператора скрещивания. При скрещивании двух особей потомки приобретают часть генов от каждого из родителей, и тем самым расширяется пространство поиска. В классическом варианте ГА используется одноточечный кроссовер. Ученые, занимающиеся генетическими алгоритмами, предлагают свои разновидности данного оператора [16, 17]. Как говорилось ранее, авторы предложили бинарное кодирование особи, а не вещественное, поэтому из всех разновидностей можно использовать только некоторый круг. Скрещивание особей с вещественными генами описывается в [16]. Приведем обзор разновидностей кроссовера, подходящих для использования в данном ГА.

Одноточечный кроссовер (рис . 1). Выбираются две особи для скрещивания.

Родитель 1

1	0	1	1	0	0	1	1	1	0
Родитель 2
0	0	1	0	1	1	0	0	1	0
Точка скрещивания — ген #4 Потомок 1
1	0	1	1	1	1	0	0	1	0
Потомок 2
0	0	1	0	0	0	1	1	1	0

Рис. 1. Одноточечный кроссовер

Случайным образом разыгрывается точка скрещивания. В потомок 1 копируется часть генов родителя 1 до точки скрещивания, а часть генов родителя 2 — после точки скрещивания. Потомок 2 создается аналогичным образом, но наоборот.

Двухточечный кроссовер (рис . 2). Выбираются две особи для скрещивания.

Родитель 1

	1	0	1	1	0	0	1	1	1	0
Родитель 2
	0	0	1	0	1	1	0	0	1	0
Точка скрещивания 1 — ген #3, точка скрещивания 2 — ген #7 Потомок 1
	1	0	1	0	1	1	0	1	1	0
Потомок 2
	0	0	1	1	0	0	1	0	1	0

Рис. 2. Двухточечный кроссовер

Случайным образом разыгрываются две разные точки скрещивания. В потомок 1 копируется часть генов родителя 1 до точки скрещивания 1, часть генов родителя 2 между точками скрещивания и часть генов родителя 1 после точки скрещивания 2. Потомок 2 создается аналогичным образом, но наоборот.

Аналогично работает многоточечный кроссовер и его частный случай — трехточечный. Описанные операторы можно модифицировать, а именно: дополнительно проверить, чтобы точки скрещивания выбирались

Информатика, вычислительная техника и управление

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

Равномерный кроссовер [16] (рис. 3). Случайно генерируется маска — двоичная особь. При этом часть генов потомка переходит от одного родителя, часть — от другого.

Родитель 1

Родитель 2

Маска

Потомок 1

1	0	1	1	1	1	1	0	1	0
Потомок 2
0	0	1	0	0	0	0	1	1	0

Рис. 3. Равномерный кроссовер

Далее маска анализируется. Если в ней «1», то соответствующий ген родителя 1 переходит в соответствующее место потомка 1. Если иначе, то потомок 1 принимает ген родителя 2.

Потомок 2 генерируется обратным путем. Ген заимствуется от родителя 1, если на том же месте в маске располагается «0». Если иначе, то потомок 1 принимает ген родителя 2.

Похожая идея используется в работе триадного кроссовера [16] . Отличие в том, что в качестве маски используется особь из поколения, выбранная случайным образом. Затем 10 % генов маски подвергаются мутации. Далее: если ген родителя 1 совпадает с геном маски, то этот ген переходит потомку 1, иначе ген переходит от родителя 2. У потомка 2 на тех местах, где потомок 1 принял гены родителя 1, находятся гены родителя 2, и наоборот.

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

В классическом ГА используется одноточечный оператор мутации (рис. 4): в особи случайным образом выбирается точка мутации — ген, который далее меняется своим значением с соседним геном.

Родитель

1	0	1	1	0	0	1	1	1	0
Точка мутации = ген #4 Потомок
1	0	1	0	1	0	1	1	1	0

Рис. 4. Одноточечный оператор мутации

Кроме этой мутации рассмотрено еще несколько видов.

Двухточечный оператор мутации (рис. 5) — модификация одноточечного: случайно выбираются два гена, и они обмениваются своими значениями.

Родитель

1	0	1	1	0	0	1	1	1	0
	Точки мутации = ген #4 и #7 Потомок
1	0	1	1	0	0	1	1	1	0

Рис. 5. Двухточечный оператор мутации

Генная мутация (рис. 6) основана на том, что инвертируется значение одного случайно выбранного гена.

Родитель

1	0	1	1	0	0	1	1	1	0
Точка мутации = ген #4 Потомок
1	0	1	0	0	0	1	1	1	0

Рис. 6. Генная мутация

Мутация добавления и удаления [16] (рис. 7) получается в результате совмещения двух операций: добавления случайного гена в конец хромосомы и удаления случайного гена из полученной хромосомы.

Родитель

	1		0		1		1		0		0		1		1		1		0
Добавление гена «0» в конец особи
1		0		1		1		0		0		1		1		1		0		0
Удаление гена #4 Потомок
	1		0		1		0		0		1		1		1		0		0

Рис. 7. Мутация добавления и удаления

Мутация вставки и удаления [16] похожа на мутацию добавления и удаления: случайный ген добавляется в случайную позицию хромосомы и случайный ген удаляется из полученной хромосомы.

Мутация на основе плотности мутации [16] . Каждый ген особи мутирует с определенной вероятностью. Вероятность мутирования гена обычно выбирается так, чтобы изменению подверглись от 1 % до 10 % генов.

Сальтация [17] (рис. 8) — мутация на основе инверсии k генов особи.

Родитель

1 0 1 1 0 0 1 1 1 0 k = 3, мутирование генов #4, #6, #7 Потомок

Рис. 8. Сальтация

Инверсия [17] (рис. 9) — мутация генов между двумя точками разрыва, выбранными случайным образом. Родитель

Точки разрыва — ген #4 и #7 Потомок

Рис. 9. Инверсия

Транслокация [17] (рис. 10) — мутация генов, которые попали в два случайно выбранных участка особи. Родитель

Интервал #1 = [ген #1; ген #3], Интервал #2 = [ген #5; ген #7] Потомок

Рис. 10. Транслокация

Дополнение [17] — мутация, при которой особь потомка формируется путем инвертирования каждого гена особи родителя.

Результаты исследования

Анализ производительности генетического алгоритма с использованием различных сочетаний «мутация + скрещивание» . Какие комбинации видов бинарной мутации и скрещивания более выгодно использовать для увеличения эффективности ГА? Авторы спроектировали программное средство с использовани-

Информатика, вычислительная техника и управление

ем языка C Sharp для сравнения генетических алгоритмов по оптимальности решений и затрат времени. Для экспериментов использовался персональный компьютер с операционной системой Microsoft Windows 10 Pro x64, процессором Intel(R) Core(TM) i5-2500KCPU 3.30GHz, оперативной памятью 6 Гб.

Выполнено по 100 опытов с матрицами размером n х m , где n — число подмножеств множества U , m — число элементов множества U . Матрицы формируются случайным образом. При этом соблюдаются перечисленные ниже условия.

— Коэффициент заполненности матрицы подмножеств единицами p = 0,5.

— Случайным образом генерируются веса подмножеств из интервала от 1 до 200.

— Число подмножеств = 100, мощность множества U = 100.

Для ГА использованы перечисленные ниже параметры.

— Количество поколений = 50.

— Вероятность кроссовера = 1.

— Вероятность мутации = 1.

— Условие останова =100 поколений.

— Оператор кроссовера:

Скр1 — одноточечный;

Скр2 — ограниченный одноточечный;

Скр3 — двухточечный;

Скр4 — ограниченный двухточечный;

Скр5 — трехточечный;

Скр6 — ограниченный трехточечный;

Скр7 — равномерный;

Скр8 — триадный.

— Оператор мутации:

Мут1 — генная;

Мут2 — одноточечная;

Мут3 — двухточечная;

Мут4 — мутация добавления и удаления;

Мут5 — мутация вставки и удаления;

Мут6 — сальтация;

Мут7 — дополнение;

Мут8 — инверсия;

Мут9 — транслокация.

В табл. 1 показаны средние значения результатов сравнения алгоритмов по весам покрытий, а в табл. 2 — по времени работы. Также в табл. 1 и 2 вошли результаты работы генетического алгоритма с 50 особями, предложенного Нгуен Минь Хангом в [13].

Таблица 1

Сравнение эффективности видов оператора скрещивания и мутации по весам покрытий

Алгоритм 100x100 50 особей	Мут1	Мут2	Мут3	Мут4	Мут5	Мут6	Мут7	Мут8	Мут9	ГА Нгуен Минь Ханга
Скр1	41,78	60,35	45,02	60,12	55,07	67,46	67,46	67,46	67,46	46,23
Скр2	42,29	58,23	44,87	59,37	51,83	67,46	67,46	67,46	67,46
Скр3	42,53	58,75	45,38	61,35	55,93	67,41	67,46	67,72	67,46
Скр4	42,91	63,63	45,75	63,38	57,64	67,46	67,46	67,46	67,46
Скр5	42,41	60,58	45,18	63,11	54,92	67,46	68,52	67,46	67,46
Скр6	42,71	65,96	46,37	65,38	58,2	67,46	67,46	67,46	67,32
Скр7	41,74	50,61	45,52	53,75	48,31	67,46	67,46	67,29	67,46
Скр8	43,39	57,84	45,3	60,37	54,07	67,46	67,46	67,46	67,46

Таблица 2

Сравнение эффективности видов оператора скрещивания и мутации по временным затратам (мс)

Алгоритм 100x100 50 особей	Мут1	Мут2	Мут3	Мут4	Мут5	Мут6	Мут7	Мут8	Мут9	ГА Нгуен Минь Ханга
Скр1	2418	1363	2028	1996	1777	1569	2251	1746	1853	1900
Скр2	2365	1399	1974	2175	1817	1571	2257	1756	1855
Скр3	2485	1417	2111	2008	1824	1627	2325	1841	1935
Скр4	2568	1416	2126	2145	1884	1626	2304	1809	1909
Скр5	2537	1406	2131	1862	1825	1631	2338	1834	1927
Скр6	2509	1422	2139	1902	1822	1636	2315	1820	1903
Скр7	2679	1569	1970	2220	2124	1697	2410	1905	2008
Скр8	2484	1443	2084	1950	1910	1654	2353	1866	1942

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

Влияние вероятности мутации и кроссовера на эффективность генетического алгоритма. Для исследования указанной проблемы применено описанное выше программное средство. Рассмотрена комбинация «генная мутация + равномерное скрещивание» как самая эффективная (наравне с «генная мутация + одноточечное скрещивание»). Размерность задачи 100x100, 50 особей. Результаты приведены в табл. 3 и 4.

Таблица 3

Сравнение эффективности вероятностей оператора скрещивания и мутации по весам покрытий

Мутация Скрещивание	0,2	0,4	0,6	0,8	1
0,2	60,31	59,45	59,37	54,65	44,35
0,4	58,2	58,09	57,51	54,71	45,01
0,6	57,98	57,58	54,67	52,67	44,75
0,8	54,03	55,18	55,07	51,11	44,68
1	52,17	50,95	50,28	48,89	44,33

Таблица 4

Сравнение эффективности вероятностей оператора скрещивания и мутации по временным затратам (мс)

Мутация Скрещивание	0,2	0,4	0,6	0,8	1
0,2	992	1038	1121	1293	2047
0,4	1038	1101	1196	1418	2115
0,6	1111	1205	1325	1504	2273
0,8	1237	1314	1420	1656	2338
1	1338	1448	1602	1858	2594

Выявлено наилучшее сочетание: вероятность мутации 100 % и вероятность скрещивания 100 %.

Влияние размерности поколения на эффективность ГА . В табл. 5 и 6 приведены результаты с 50, 100, 200, 500, 1000 особями и размерностью задачи 100x100 (ГА1 — одноточечное скрещивание + генная мутация, ГА2 — равномерное скрещивание + генная мутация, ГА3 — ГА Нгуен Минь Хангом).

Таблица 5

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

Особи	ГА1	ГА2	ГА3
50	43,76	43,68	49,53
100	42,88	42,8	47,12
200	42,7	42,61	46,87
500	42,67	42,61	47,64
1000	42,61	42,61	50,35

Информатика, вычислительная техника и управление

Таблица 6

Влияние размерности поколения на временные затраты, необходимые для реализации генетического алгоритма (мс)

Особи	ГА1	ГА2	ГА3
50	2229	2377	1842
100	4175	4791	2219
200	8185	8722	2611
500	19109	20992	8440
1000	37588	41855	14581

Естественно, с увеличением размера поколения увеличивается время работы ГА, и при этом повышается точность решения задачи.

Влияние условия останова на эффективность решения задачи. В рамках представленной работы в качестве условия останова используется число поколений неизменности лучшего решения. В табл. 7 и 8 показаны результаты сравнительного анализа ГА из прошлого эксперимента с условием останова 100, 200, 300, 500.

Таблица 7

Влияние условия останова на веса покрытий, получаемые генетическим алгоритмом

Условие останова	ГА1	ГА2	ГА3
100	49,96	50,28	56,74
200	49,23	48,79	56,29
300	50,14	48,5	57,2
500	49,82	49,66	57,17

Таблица 8

Влияние условия останова на временные затраты, необходимые для реализации генетического алгоритма (мс)

Условие останова	ГА1	ГА2	ГА3
100	2264	2517	1834
200	3840	4251	3479
300	4994	5955	5001
500	7892	8429	8370

С увеличением условия останова увеличивается время работы алгоритма. Это целесообразно при условии останова 200-250 особей.

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

1) Рекомендуется использовать сочетание генной мутации и одноточечного скрещивания.
2) Если повышается число особей, то растет точность результата и время его получения. Среднее отклонение от точного результата при размерности задачи 25x25 составило 0 %, 50x50 — 0 %, 75x75 — 0,013 %, 100x100 — 0 %, 110x110 — 0 % при 500 особях.
3) Эффективно использование вероятности оператора мутации и скрещивания 100 % и 100 % соответственно.

Список литературы Повышение эффективности работы генетического алгоритма в процессе решения задачи покрытия множеств

Коновалов, И. С. Применение генетического алгоритма для решения задачи покрытия множеств / И. С. Коновалов, В. А. Фатхи, В. Г. Кобак // Вестник Донского гос. техн. ун-та. - 2016. - № 3. - С. 125-132.
Коновалов, И. С. Сравнительный анализ работы жадного алгоритма Хватала и модифицированной модели Голдберга при решении взвешенной задачи нахождения минимального покрытия множеств / И. С. Коновалов, В. А. Фатхи, В. Г. Кобак // Тр. СКФ МТУСИ. Часть I. - Ростов-на-Дону: СКФ МТУСИ, 2015. - С. 366-371
Еремеев, А. В. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования / А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов // Дискретный анализ и исследование операций. - 2000. - Т. 7, № 2. - С. 22-46.
Есипов, Б. А. Исследование алгоритмов решения обобщенной задачи о минимальном покрытии / Б. А. Есипов, В. В. Муравьев // Изв. Самар. науч. центра РАН. - 2014. - № 4 (2). - С. 308-312.
Кононов, А. В. Приближенные алгоритмы для NP-трудных задач / А. В. Кононов, П. А. Кононова; Новосиб. гос. ун-т. - Новосибирск: РИЦ НГУ, 2014. - 117 с.
Chvatal, V. A greedy heuristic for the set-covering problem / V. Chvatal // Mathematics of Operations Research. - 1979. - Vol. 4, № 3. - P. 233-235.
Лебедев, О. Б. Покрытие методом муравьиной колонии / О. Б. Лебедев // КИИ-2010. Двенадцатая национальная конференция по искусственному интеллекту с международным участием: тр. Т. 2. - Москва: Физматлит, 2010. - С. 423-431.
Лебедев, Б. К. Покрытие на основе метода роя частиц / Б. К. Лебедев, В. Б. Лебедев // Нейроинформатика-2011: сб. науч. тр. XIII Всерос. науч.-техн. конф. Ч. 2. - Москва: Физматлит, 2011. - C. 93-103.
Holland, J. H. Adaptation in Natural and Artificial Systems / J. H. Holland. - Ann Arbor: University of Michigan Press, 1975. - P. 245.
Становов, В. В. Исследование эффективности различных методов самонастройки генетического алгоритма / В. В. Становов, Е. С. Семенкин // Актуальные проблемы авиации и космонавтики. - 2012. - № 8. - С. 319-320.
Коромыслова, А. А. Исследование свойства масштабируемости генетического алгоритма / А. А. Коромыслова, Е. С. Семенкин // Актуальные проблемы авиации и космонавтики. - 2012. - № 8. - С. 305-306.
Еремеев, А. В. Генетический алгоритм для задачи о покрытии / А. В. Еремеев // Дискретный анализ и исследование операций. - 2000. - Т. 7, № 1. - С. 47-60.
Нгуен Минь Ханг. Применение генетического алгоритма для задачи нахождения покрытия множества / Нгуен Минь Ханг // Динамика неоднородных систем. - Москва: ЛКИ, 2008. - T. 33, вып. 12. - С. 206-219.
Goldberg D. E. Genetic algorithms in search, optimization and machine learning / D. E. Goldberg. - Reading: Addison-Wesley, 1989. - P. 432.
Коновалов, И. С. Стратегия элитизма модифицированной модели Голдберга генетического алгоритма при решении задачи покрытия множеств / И. С. Коновалов, В. А. Фатхи, В. Г. Кобак // Вестник компьютерных и информационных технологий. - 2016. - № 4. - С. 50-56.
Панченко, Т. В. Генетические алгоритмы / Т. В. Панченко // Астрахань: Астраханский университет, 2007. - 88 с.
Батищев, Д. И. Генетические алгоритмы решения экстремальных задач / Д. И. Батищев. - Воронеж: ВГТУ, 1995. - 69 с.

Еще

Статья научная