Russian Federation
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 algorithm, set-covering problem, Goldberg´s model, algorithm of Nguyen M.H., greedy strategy of Chvatal, exhaustive enumeration.
Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому также является NP-сложной). К задаче о покрытии можно свести многие задачи дискретной оптимизации: стандартизации, упаковки и разбиения множества, построения расписаний. Известна также и обратная сводимость задачи о покрытии к этим задачам. На практике задачи о покрытии возникают при размещении пунктов обслуживания, в системах информационного поиска, при назначении экипажей на транспорте, проектировании интегральных схем и конвейерных линий и т. д.
1. 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).
2. 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).
3. 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).
4. 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).
5. Chvatal, V. A greedy heuristic for the set-covering problem. Mathematics of Oper. Res., 1979, vol. 4, no. 3, pp. 233–235.
6. Holland, J. H. Adaptation in Natural and Artificial Systems. The University of Michigan Press, 1975, 245 p.
7. Goldberg, D. E. Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley, 1989, 432 p.
8. 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).
9. Gladkov, L.А., Kureychik, V.V., Kureychik, V.M. Geneticheskie algoritmy. [Genetic algorithms.] Moscow: Fizmatlit, 2010, 368 p. (in Russian).
10. 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).
