donstuAdvanced Engineering Research (Rostov-on-Don)Advanced Engineering Research (Rostov-on-Don)2687-1653Don State Technical University10.12737/20225donstu-106Research ArticleINFORMATION TECHNOLOGY, COMPUTER SCIENCE AND MANAGEMENTИНФОРМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И УПРАВЛЕНИЕApplication of genetic algorithm for the set-covering problem solutionПрименение генетического алгоритма для решения задачи покрытия множествКоноваловИгорь СергеевичKonovalovIgor S.xigorx92@mail.ruФатхиВладимир АхатовичFatkhiVladimir A.fatkhi@mail.ruКобакВалерий ГригорьевичKobakValery G.valera33305@mail.ruДонской государственный технический университетРоссияDon State Technical UniversityRussian Federation201630092016163125132Copyright © Konovalov I.S., Fatkhi V.A., Kobak V.G., 20162016Коновалов И.С., Фатхи В.А., Кобак В.Г.Konovalov I.S., Fatkhi V.A., Kobak V.G.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.vestnik-donstu.ru/jour/article/view/106

The weighed and unweighted minimal set-cover problem, its applicability for the solution of the major optimization practical tasks, such as arrangement of service points, assignment of crews in transport, as well as the integrated-circuit and conveyer lines designing is considered. The paper objective is to describe methods of improving efficiency of this task solution. The principle of operation of the genetic algorithm and the applicability of its modification as a method of the solution to the set-cover problem are defined. Greedy strategy of Chvatal for the set-cover problem solution is considered. An exhaustive algorithm as an exact algorithm for the solution of small-size tasks is developed. The modified genetic algorithm developed by Nguyen M. H. is described. A software tool for comparing the performance of these algorithms is created. It is concluded that the solution of the set-cover problem by our genetic algorithm modification is more effective than by the genetic algorithm of Nguyen M. H. or the greedy strategy. And the results obtained in small-size tasks are noted for insignificant error.

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

генетический алгоритмзадача покрытия множествмодель Голдбергаалгоритм Нгуена М. Хжадная стратегия Хваталаполный переборgenetic algorithmset-covering problemGoldberg's modelalgorithm of Nguyen M.Hgreedy strategy of Chvatalexhaustive enumerationReferencesКоновалов, И. С. Сравнительный анализ работы жадного алгоритма Хватала и модифицированной модели Голдберга при решении взвешенной задачи нахождения минимального покрытия множеств / И. С. Коновалов, В. А. Фатхи, В. Г. Кобак // Труды СКФ МТУСИ. - 2015. - Ч. I. - С. 366-370.Konovalov, I.S., Fatkhi, V.A., Kobak, V.G. Sravnitel'nyy analiz raboty zhadnogo algoritma Khvatala i modifitsirovannoy modeli Goldberga pri reshenii vzveshennoy zadachi nakhozhdeniya minimal'nogo pokrytiya mnozhestv. [Comparative analysis of work greedy algorithm of Chvatal and modified Goldberg models weighted in solving the problem of finding minimal coverings of sets.] Trudy SKF MTUSI, 2015, Part I, pp. 366–370 (in Russian).Еремеев, А. В. Генетический алгоритм для задачи о покрытии / А. В. Еремеев // Дискретный анализ и исследование операций. - 2000. - Т. 7, № 1. - С. 47-60.Eremeev, А.V. Geneticheskiy algoritm dlya zadachi o pokrytii. [Ageneric algorithm for the covering problem.] Discrete Analysis and Operations Research, 2000, vol. 7, ser. 2, no. 1, pp. 47–60 (in Russian).Еремеев, А. В. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования / А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов // Дискретный анализ и исследование операций. - 2000. - Т. 7., № 2. - С. 22-46.Eremeev, А.V., Zaozerskaya, L.A., Kolokolov, A.A. Zadacha o pokrytii mnozhestva: slozhnost', algoritmy, eksperimental'nye issledovaniya. [The set covering problem: complexity, algorithms, and experimental investigations.] Discrete Analysis and Operations Research, 2000, vol. 7, ser. 2, no. 2, pp. 22–46 (in Russian).Кононов, А. В. Приближенные алгоритмы для NP-трудных задач / А. В. Кононов, П. А. Кононова. - Новосибирск : Новосиб. гос. ун-т., 2014. - 117 с.Kononov, А.V., Kononova, P.A. Priblizhennye algoritmy dlya NP-trudnykh zadac.h [Approximate algorithms for NP-hard problems.] Novosibirsk: Novosibirsk State University, 2014, 117 p. (in Russian).Chvatal, V. A greedy heuristic for the set-covering problem // Mathematics of Oper. Res. - 1979. - V. 4, № 3. - P. 233-235.Chvatal, V. A greedy heuristic for the set-covering problem. Mathematics of Oper. Res., 1979, vol. 4, no. 3, pp. 233–235.Holland, J. H. Adaptation in Natural and Artificial Systems. The University of Michigan Press, 1975. - P. 245.Holland, J. H. Adaptation in Natural and Artificial Systems. The University of Michigan Press, 1975, 245 p.Goldberg, D. E. Genetic algorithms in search, optimization and machine learning. Reading, MA : Addison-Wesley, 1989. - P. 432.Goldberg, D. E. Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley, 1989, 432 p.Батищев, Д. И. Генетические алгоритмы решения экстремальных задач / Д. И. Батищев. - Н. Новгород : Нижегородский гос. ун-т., 1995. - 69 с.Batishchev, D.I. Geneticheskie algoritmy resheniya ekstremal'nykh zadach. [Genetic algorithms for solving extreme problems.] N. Novgorod: State University of Nizhni Novgorod, 199, 69 p. (in Russian).Гладков, Л. А. Генетические алгоритмы / Л. А. Гладков, В. В. Курейчик, В. М. Курейчик. - Москва : Физматлит, 2010. - 368 с.Gladkov, L.А., Kureychik, V.V., Kureychik, V.M. Geneticheskie algoritmy. [Genetic algorithms.] Moscow: Fizmatlit, 2010, 368 p. (in Russian).Нгуен, М. Х. Применение генетического алгоритма для задачи нахождения покрытия множества // Динамика неоднородных систем. - 2008. - T. 33., Вып. 12. - С. 206-219.Nguyen, М.H. Primenenie geneticheskogo algoritma dlya zadachi nakhozhdeniya pokrytiya mnozhestva. [Application of genetic algorithm to the problem of finding cover sets.] Dinamika neodnorodnykh system, 2008, vol. 33, iss. 12, pp. 206–219 (in Russian).

The authors declare that there are no conflicts of interest present.