Применение генетического алгоритма для решения задачи покрытия множеств
Автор: Коновалов Игорь Сергеевич, Фатхи Владимир Ахатович, Кобак Валерий Григорьевич
Журнал: Вестник Донского государственного технического университета @vestnik-donstu
Рубрика: Информатика, вычислительная техника и управление
Статья в выпуске: 3 (86) т.16, 2016 года.
Бесплатный доступ
Рассматриваются взвешенная и невзвешенная задачи нахождения минимального покрытия множеств, а также ее применимость для решения важнейших оптимизационных практических задач, таких как размещение пунктов обслуживания, назначение экипажей на транспорте, проектирование интегральных схем и конвейерных линий. Цель статьи - описание методов повышения эффективности решения данной задачи. Сформулирован принцип работы генетического алгоритма и возможность использования его модификации в качестве метода решения задачи покрытия множеств. Рассматривается жадная стратегия Хватала для решения задачи покрытия. Для решения задач небольшого размера разработан алгоритм полного перебора в качестве точного алгоритма. Описан модифицированный генетический алгоритм, разработанный Нгуеном М. Х. Создано программное средство для сравнения производительности этих алгоритмов. Сделаны выводы о том, что решение задачи покрытия множеств разработанной модификацией генетического алгоритма более эффективно, чем генетическим алгоритмом Нгуена М. Х. и жадной стратегией, причем в задачах небольшого размера полученные результаты отличаются небольшой погрешностью.
Генетический алгоритм, задача покрытия множеств, модель голдберга, алгоритм нгуена м. х, жадная стратегия хватала, полный перебор
Короткий адрес: https://sciup.org/14250219
IDR: 14250219 | DOI: 10.12737/20225
Список литературы Применение генетического алгоритма для решения задачи покрытия множеств
- Коновалов, И. С. Сравнительный анализ работы жадного алгоритма Хватала и модифицированной модели Голдберга при решении взвешенной задачи нахождения минимального покрытия множеств/И. С. Коновалов, В. А. Фатхи, В. Г. Кобак//Труды СКФ МТУСИ. -2015. -Ч. I. -С. 366-370.
- Еремеев, А. В. Генетический алгоритм для задачи о покрытии/А. В. Еремеев//Дискретный анализ и исследование операций. -2000. -Т. 7, № 1. -С. 47-60.
- Еремеев, А. В. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования/А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов//Дискретный анализ и исследование операций. -2000. -Т. 7., № 2. -С. 22-46.
- Кононов, А. В. Приближенные алгоритмы для NP-трудных задач/А. В. Кононов, П. А. Кононова. -Новосибирск: Новосиб. гос. ун-т., 2014. -117 с.
- Chvatal, V. A greedy heuristic for the set-covering problem//Mathematics of Oper. Res. -1979. -V. 4, № 3. -P. 233-235.
- Holland, J. H. Adaptation in Natural and Artificial Systems. The University of Michigan Press, 1975. -P. 245.
- Goldberg, D. E. Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley, 1989. -P. 432.
- Батищев, Д. И. Генетические алгоритмы решения экстремальных задач/Д. И. Батищев. -Н. Новгород: Нижегородский гос. ун-т., 1995. -69 с.
- Гладков, Л. А. Генетические алгоритмы/Л. А. Гладков, В. В. Курейчик, В. М. Курейчик. -Москва: Физматлит, 2010. -368 с.
- Нгуен, М. Х. Применение генетического алгоритма для задачи нахождения покрытия множества//Динамика неоднородных систем. -2008. -T. 33., Вып. 12. -С. 206-219.
