Vestnik of Don State Technical UniversityVestnik of Don State Technical UniversityВестник Донского государственного технического университета1992-59801224110.12737/20225Машиностроение и машиноведениеMACHINE BUILDING AND MACHINE SCIENCEМашиностроение и машиноведениеApplication of genetic algorithm for the set-covering problem solution Применение генетического алгоритма для решения задачи покрытия множествФатхиВладимир Ахатович FatkhiVladimir Akhatovich fatkhi@mail.ruКоновалов Игорь СергеевичKonovalov Igor СергеевичКобакВалерий ГригорьевичKobakValeriy Григорьевичvalera33305@mail.ruДонской государственный технический университетРоссияDon State Technical UniversityRussian Federation2106201621062016163125132https://zh-szf.ru/en/nauka/article/12241/view
Рассматриваются взвешенная и невзвешенная задачи нахождения минимального покрытия множеств, а также ее применимость для решения важнейших оптимизационных практических задач, таких как размещение пунктов обслуживания, назначение экипажей на транспорте, проектирование интегральных схем и конвейерных линий. Цель статьи — описание методов повышения эффективности решения данной задачи. Сформулирован принцип работы генетического алгоритма и возможность использования его модификации в качестве метода решения задачи покрытия множеств. Рассматривается жадная стратегия Хватала для решения задачи покрытия. Для решения задач небольшого размера разработан алгоритм полного перебора в качестве точного алгоритма. Описан модифицированный генетический алгоритм, разработанный Нгуеном М. Х. Создано программное средство для сравнения производительности этих алгоритмов. Сделаны выводы о том, что решение задачи покрытия множеств разработанной модификацией генетического алгоритма более эффективно, чем генетическим алгоритмом Нгуена М. Х. и жадной стратегией, причем в задачах небольшого размера полученные результаты отличаются небольшой погрешностью.
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 meth-ods 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 algo-rithm for the solution of small-size tasks is developed. The modi-fied 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.H.greedy strategy of Chvatalexhaustive enumeration.
Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому также является NP-сложной). К задаче о покрытии можно свести многие задачи дискретной оптимизации: стандартизации, упаковки и разбиения множества, построения расписаний. Известна также и обратная сводимость задачи о покрытии к этим задачам. На практике задачи о покрытии возникают при размещении пунктов обслуживания, в системах информационного поиска, при назначении экипажей на транспорте, проектировании интегральных схем и конвейерных линий и т. д.
Коновалов, И. С. Сравнительный анализ работы жадного алгоритма Хватала и модифицированной модели Голдберга при решении взвешенной задачи нахождения минимального покрытия множеств / И. С. Коновалов, В. А. Фатхи, В. Г. Кобак // Труды СКФ МТУСИ. - 2015. - Ч. I. - С. 366-370.Konovalov, I.S., Fatkhi, V.A., Kobak, V.G. Sravnitel´nyy analiz raboty zhadnogo algoritma Khvatala i modifitsi-rovannoy 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, ek-sperimental´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 ex-treme 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. [Appli-cation of genetic algorithm to the problem of finding cover sets.] Dinamika neodnorodnykh system, 2008, vol. 33, iss. 12, pp. 206-219 (in Russian).