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

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

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

Результаты исследования. Итоги экспериментов позволяют сделать три вывода. 1) Рекомендуется использовать сочетание генной мутации и одноточечного скрещивания. 2) При повышении количества особей растет точность результата и время его получения. Среднее отклонение от точного результата при размере задачи 25×25 составило 0 %, при 50×50 — 0%, при 75×75 — 0,013 %, при 100×100 — 0 %, при 110×110 — 0 % (количество особей — 500). 3) Целесообразно использовать вероятности оператора мутации и скрещивания 100 % и 100 % соответственно.

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

1. Коновалов, И. С. Применение генетического алгоритма для решения задачи покрытия множеств / И. С. Коновалов, В. А. Фатхи, В. Г. Кобак // Вестник Донского гос. техн. ун-та. — 2016. — № 3. — С. 125–132.

2. Коновалов, И. С. Сравнительный анализ работы жадного алгоритма Хватала и модифицированной модели Голдберга при решении взвешенной задачи нахождения минимального покрытия множеств / И. С. Коновалов, В. А. Фатхи, В. Г. Кобак // Тр. СКФ МТУСИ. Часть I. — Ростов-на-Дону : СКФ МТУСИ, 2015. — С. 366–371

3. Еремеев, А. В. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования / А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов // Дискретный анализ и исследование операций. — 2000. — Т. 7, № 2. — С. 22–46.

4. Есипов, Б. А. Исследование алгоритмов решения обобщенной задачи о минимальном покрытии / Б. А. Есипов, В. В. Муравьев // Изв. Самар. науч. центра РАН. — 2014. — № 4 (2). — С. 308–312.

5. Кононов, А. В. Приближенные алгоритмы для NP-трудных задач / А. В. Кононов, П. А. Кононова ; Новосиб. гос. ун-т. — Новосибирск : РИЦ НГУ, 2014. — 117 с.

6. Chvatal, V. A greedy heuristic for the set-covering problem / V. Chvatal // Mathematics of Operations Research. — 1979. — Vol. 4, № 3. — P. 233–235.

7. Лебедев, О. Б. Покрытие методом муравьиной колонии / О. Б. Лебедев // КИИ-2010. Двенадцатая национальная конференция по искусственному интеллекту с международным участием : тр. Т. 2. — Москва : Физматлит, 2010. — С. 423–431.

8. Лебедев, Б. К. Покрытие на основе метода роя частиц / Б. К. Лебедев, В. Б. Лебедев // Нейроинформатика-2011 : сб. науч. тр. XIII Всерос. науч.-техн. конф. Ч. 2. — Москва : Физматлит, 2011. — C. 93–103.

9. Holland, J. H. Adaptation in Natural and Artificial Systems / J. H. Holland. — Ann Arbor : University of Michigan Press, 1975. — P. 245.

10. Становов, В. В. Исследование эффективности различных методов самонастройки генетического алгоритма / В. В. Становов, Е. С. Семенкин // Актуальные проблемы авиации и космонавтики. — 2012. — № 8. — С. 319–320.

11. Коромыслова, А. А. Исследование свойства масштабируемости генетического алгоритма / А. А. Коромыслова, Е. С. Семенкин // Актуальные проблемы авиации и космонавтики. — 2012. — № 8. — С. 305–306.

12. Еремеев, А. В. Генетический алгоритм для задачи о покрытии / А. В. Еремеев // Дискретный анализ и исследование операций. — 2000. — Т. 7, № 1. — С. 47–60.

13. Нгуен Минь Ханг. Применение генетического алгоритма для задачи нахождения покрытия множества / Нгуен Минь Ханг // Динамика неоднородных систем. — Москва : ЛКИ, 2008. — T. 33, вып. 12. — С. 206–219.

14. Goldberg D. E. Genetic algorithms in search, optimization and machine learning / D. E. Goldberg. — Reading : Addison-Wesley, 1989. — P. 432.

15. Коновалов, И. С. Стратегия элитизма модифицированной модели Голдберга генетического алгоритма при решении задачи покрытия множеств / И. С. Коновалов, В. А. Фатхи, В. Г. Кобак // Вестник компьютерных и информационных технологий. — 2016. — № 4. — С. 50–56.

16. Панченко, Т. В. Генетические алгоритмы / Т. В. Панченко // Астрахань : Астраханский университет, 2007. — 88 с.

17. Батищев, Д. И. Генетические алгоритмы решения экстремальных задач / Д. И. Батищев. — Воронеж : ВГТУ, 1995. — 69 с.