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

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

Задача покрытия множества, генетический алгоритм, модель Голдберга, алгоритм полного перебора, метод ветвей и границ, алгоритм Алексеева, set covering problem, genetic algorithm, Goldberg model, exhaustive algorithm, branch-and-bound method, Alekseev algorithm

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

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

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

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

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

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. - 121 с.

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

10. Алексеев, О. Г. Некоторые алгоритмы решения задачи о покрытии и их экспериментальное исследование на ЭВМ / О. Г. Алексеев, В. Ф. Григорьев // Журнал вычислительной математики и математической физики. - 1984. - Т. 24, №10. - С. 1565-1570.