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

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

генетический алгоритм, задача покрытия множеств, модель Голдберга, алгоритм Нгуена М. Х, жадная стратегия Хватала, полный перебор, genetic algorithm, set-covering problem, Goldberg's model, algorithm of Nguyen M.H, greedy strategy of Chvatal, exhaustive enumeration

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

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

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

4. Кононов, А. В. Приближенные алгоритмы для NP-трудных задач / А. В. Кононов, П. А. Кононова. - Новосибирск : Новосиб. гос. ун-т., 2014. - 117 с.

5. Chvatal, V. A greedy heuristic for the set-covering problem // Mathematics of Oper. Res. - 1979. - V. 4, № 3. - P. 233-235.

6. Holland, J. H. Adaptation in Natural and Artificial Systems. The University of Michigan Press, 1975. - P. 245.

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

8. Батищев, Д. И. Генетические алгоритмы решения экстремальных задач / Д. И. Батищев. - Н. Новгород : Нижегородский гос. ун-т., 1995. - 69 с.

9. Гладков, Л. А. Генетические алгоритмы / Л. А. Гладков, В. В. Курейчик, В. М. Курейчик. - Москва : Физматлит, 2010. - 368 с.

10. Нгуен, М. Х. Применение генетического алгоритма для задачи нахождения покрытия множества // Динамика неоднородных систем. - 2008. - T. 33., Вып. 12. - С. 206-219.