Повышение эффективности работы генетического алгоритма в процессе решения задачи покрытия множеств
Аннотация
Введение. Практические задачи (размещение пунктов обслуживания, создание микросхем, составление расписаний и пр.) зачастую требуют точного или приближенного к точному решения при большой размерности. Достижение приемлемого результата в данном случае требует решения задачи покрытия множеств — фундаментальной для комбинаторики и теории множеств. Точное решение можно получить с помощью переборных методов, однако в этом случае при повышении размерности задачи во много раз возрастает время работы точного алгоритма. По этой причине следует увеличивать точность приближенных методов: они дают решение, лишь приближенное к точному, однако затрачивают на поиск ответа намного меньше времени при большой размерности.
Материалы и методы. Описывается один из способов решения задачи покрытия — генетический алгоритм. Авторы используют модификацию модели Голдберга и пытаются повысить ее эффективность с помощью различных видов оператора мутации и скрещивания. Речь идет о генной мутации, двухточечной мутации, мутации добавления и удаления, мутации вставки и удаления, сальтации, мутациях на основе инверсии. Отмечены следующие виды оператора скрещивания: одноточечный, двухточечный, трехточечный и их версии с ограничениями, равномерный, триадный. Исследуется влияние условия останова и значений вероятностей генетических операторов на точность получаемых решений. Показано, каким образом увеличение числа особей в поколении влияет на эффективность решения.
Результаты исследования. Итоги экспериментов позволяют сделать три вывода. 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 с.
Для цитирования:
Коновалов И.С., Фатхи В.А., Кобак В.Г. Повышение эффективности работы генетического алгоритма в процессе решения задачи покрытия множеств. Вестник Донского государственного технического университета . 2019;19(4):389-397. https://doi.org/10.23947/1992-5980-2019-19-4-389-397
For citation:
Konovalov I.S., Fatkhi V.A., Kobak V.G. Genetic algorithm efficiency improvement in the course of set cover problem solution. Vestnik of Don State Technical University . 2019;19(4):389-397. https://doi.org/10.23947/1992-5980-2019-19-4-389-397