Genetic algorithm efficiency improvement in the course of set cover problem solution

Abstract

Introduction. Practical tasks (location of service points, creation of microcircuits, scheduling, etc.) often require an exact or approximate to exact solution at a large dimension. In this case, achieving an acceptable result requires solving a set cover problem, fundamental for combinatorics and the set theory. An exact solution can be obtained using exhaustive methods; but in this case, when the dimension of the problem is increased, the time taken by an exact algorithm rises exponentially. For this reason, the precision of approximate methods should be increased: they give a solution that is only approximate to the exact one, but they take much less time to search for an answer at a large dimension.Materials and Methods. One of the ways to solve the covering problem is described, it is a genetic algorithm. The authors use a modification of the Goldberg model and try to increase its efficiency through various types of mutation and crossover operators. We are talking about gene mutations, two-point mutations, addition and deletion mutations, insertion and deletion mutations, saltation, mutations based on inversion. The following types of crossover operator are noted: single-point, two-point, three-point and their versions with restrictions, uniform, triad. The effect of the stopping condition and the probability values of genetic operators on the accuracy of the solutions is investigated. It is shown how an increase in the number of individuals in a generation affects the efficiency of a solution. Research Results. The experiment results allow us to draw three conclusions. 1) It is recommended to use a combination of gene mutation and single-point crossing. 2) With an increase in the number of individuals, the accuracy of the result and the time to obtain it increases. The average deviation from the exact result at a task size of 25 × 25 was 0%, at 50 × 50 – 0%, at 75 × 75 – 0.013%, at 100 × 100 – 0%, at 110 × 110 – 0% (the number of individuals was 500).3) It is advisable to use the probabilities of the mutation and crossover operator 100% and 100%, respectively. Discussion and Conclusions. Recommendations are given to improve the efficiency of covering problem solution. To this end, a preferred combination of the genetic algorithm parameters, of types of crossover and mutation operators is indicated.

Keywords

• генетический алгоритм
• задача покрытия множеств
• модель голдберга
• условие останова
• скрещивание
• мутация