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

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.

1. Коновалов, И. С. Применение генетического алгоритма для решения задачи покрытия множеств / И. С. Коновалов, В. А. Фатхи, В. Г. Кобак // Вестник Донского гос. техн. ун-та. — 2016. — № 3. — С. 125–132.

2. Коновалов, И. С. Сравнительный анализ работы жадного алгоритма Хватала и модифицированной модели Голдберга при решении взвешенной задачи нахождения минимального покрытия множеств / И. С. Коновалов, В. А. Фатхи, В. Г. Кобак // Тр. СКФ МТУСИ. Часть I. — Ростов-на-Дону : СКФ МТУСИ, 2015. — С. 366–371

3. Еремеев, А. В. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования / А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов // Дискретный анализ и исследование операций. — 2000. — Т. 7, № 2. — С. 22–46.

4. Есипов, Б. А. Исследование алгоритмов решения обобщенной задачи о минимальном покрытии / Б. А. Есипов, В. В. Муравьев // Изв. Самар. науч. центра РАН. — 2014. — № 4 (2). — С. 308–312.

5. Кононов, А. В. Приближенные алгоритмы для NP-трудных задач / А. В. Кононов, П. А. Кононова ; Новосиб. гос. ун-т. — Новосибирск : РИЦ НГУ, 2014. — 117 с.

6. Chvatal, V. A greedy heuristic for the set-covering problem / V. Chvatal // Mathematics of Operations Research. — 1979. — Vol. 4, № 3. — P. 233–235.

7. Лебедев, О. Б. Покрытие методом муравьиной колонии / О. Б. Лебедев // КИИ-2010. Двенадцатая национальная конференция по искусственному интеллекту с международным участием : тр. Т. 2. — Москва : Физматлит, 2010. — С. 423–431.

8. Лебедев, Б. К. Покрытие на основе метода роя частиц / Б. К. Лебедев, В. Б. Лебедев // Нейроинформатика-2011 : сб. науч. тр. XIII Всерос. науч.-техн. конф. Ч. 2. — Москва : Физматлит, 2011. — C. 93–103.

9. Holland, J. H. Adaptation in Natural and Artificial Systems / J. H. Holland. — Ann Arbor : University of Michigan Press, 1975. — P. 245.

10. Становов, В. В. Исследование эффективности различных методов самонастройки генетического алгоритма / В. В. Становов, Е. С. Семенкин // Актуальные проблемы авиации и космонавтики. — 2012. — № 8. — С. 319–320.

11. Коромыслова, А. А. Исследование свойства масштабируемости генетического алгоритма / А. А. Коромыслова, Е. С. Семенкин // Актуальные проблемы авиации и космонавтики. — 2012. — № 8. — С. 305–306.

12. Еремеев, А. В. Генетический алгоритм для задачи о покрытии / А. В. Еремеев // Дискретный анализ и исследование операций. — 2000. — Т. 7, № 1. — С. 47–60.

13. Нгуен Минь Ханг. Применение генетического алгоритма для задачи нахождения покрытия множества / Нгуен Минь Ханг // Динамика неоднородных систем. — Москва : ЛКИ, 2008. — T. 33, вып. 12. — С. 206–219.

14. Goldberg D. E. Genetic algorithms in search, optimization and machine learning / D. E. Goldberg. — Reading : Addison-Wesley, 1989. — P. 432.

15. Коновалов, И. С. Стратегия элитизма модифицированной модели Голдберга генетического алгоритма при решении задачи покрытия множеств / И. С. Коновалов, В. А. Фатхи, В. Г. Кобак // Вестник компьютерных и информационных технологий. — 2016. — № 4. — С. 50–56.

16. Панченко, Т. В. Генетические алгоритмы / Т. В. Панченко // Астрахань : Астраханский университет, 2007. — 88 с.

17. Батищев, Д. И. Генетические алгоритмы решения экстремальных задач / Д. И. Батищев. — Воронеж : ВГТУ, 1995. — 69 с.