Применение генетического алгоритма для решения задачи покрытия множеств
Аннотация
Рассматриваются взвешенная и невзвешенная задачи нахождения минимального покрытия множеств, а также ее применимость для решения важнейших оптимизационных практических задач, таких как размещение пунктов обслуживания, назначение экипажей на транспорте, проектирование интегральных схем и конвейерных линий. Цель статьи - описание методов повышения эффективности решения данной задачи. Сформулирован принцип работы генетического алгоритма и возможность использования его модификации в качестве метода решения задачи покрытия множеств. Рассматривается жадная стратегия Хватала для решения задачи покрытия. Для решения задач небольшого размера разработан алгоритм полного перебора в качестве точного алгоритма. Описан модифицированный генетический алгоритм, разработанный Нгуеном М. Х. Создано программное средство для сравнения производительности этих алгоритмов. Сделаны выводы о том, что решение задачи покрытия множеств разработанной модификацией генетического алгоритма более эффективно, чем генетическим алгоритмом Нгуена М. Х. и жадной стратегией, причем в задачах небольшого размера полученные результаты отличаются небольшой погрешностью.
Об авторах
Игорь Сергеевич Коновалов
Донской государственный технический университет
Россия
Россия
Владимир Ахатович Фатхи
Донской государственный технический университет
Россия
Россия
Валерий Григорьевич Кобак
Донской государственный технический университет
Россия
Россия
Список литературы
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.
Для цитирования:
Коновалов И.С., Фатхи В.А., Кобак В.Г. Применение генетического алгоритма для решения задачи покрытия множеств. Вестник Донского государственного технического университета . 2016;16(3):125-132. https://doi.org/10.12737/20225
For citation:
Konovalov I.S., Fatkhi V.A., Kobak V.G. Application of genetic algorithm for the set-covering problem solution. Vestnik of Don State Technical University . 2016;16(3):125-132. (In Russ.) https://doi.org/10.12737/20225
Просмотров: 189
Послать статью по эл. почте 