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).
