Application of genetic algorithm for the set-covering problem solution
https://doi.org/10.12737/20225
Abstract
About the Authors
Igor S. KonovalovRussian Federation
Vladimir A. Fatkhi
Russian Federation
Valery G. Kobak
Russian Federation
References
1. 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).
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, 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).
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 extreme 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. [Application of genetic algorithm to the problem of finding cover sets.] Dinamika neodnorodnykh system, 2008, vol. 33, iss. 12, pp. 206–219 (in Russian).
Review
For citations:
Konovalov I.S., Fatkhi V.A., Kobak V.G. Application of genetic algorithm for the set-covering problem solution. Vestnik of Don State Technical University. 2016;16(3):125-132. (In Russ.) https://doi.org/10.12737/20225