Open AccessApplication of genetic algorithm for the set-covering problem solution
Author(s) -
I. S. Konovalov,
Vladimir A. Fatkhi,
V. G. Kobak
Publication year - 2016
Publication title -
vestnik donskogo gosudarstvennogo tehničeskogo universiteta
Language(s) - English
Resource type - Journals
eISSN - 1992-6006
pISSN - 1992-5980
DOI - 10.12737/20225
Subject(s) - set cover problem , greedy algorithm , cover (algebra) , genetic algorithm , set (abstract data type) , solution set , mathematical optimization , algorithm , computer science , task (project management) , mathematics , engineering , mechanical engineering , systems engineering , programming language
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.