Solution of The Set Covering Problem with Genetic Algorithm


Oluçoğlu M., Berberler M. E.

DEU International Symposium Series on Graduate Researches 2022, İzmir, Turkey, 17 - 18 November 2022, pp.177-186

  • Publication Type: Conference Paper / Full Text
  • City: İzmir
  • Country: Turkey
  • Page Numbers: pp.177-186
  • Dokuz Eylül University Affiliated: Yes

Abstract

This project involves solution of covering problem of set cover by genetic algorithm, which is one of the artificial intelligence
methods. Set cover problem is a classical problem combinatorics, computer science, operations research and complexity theory. Set cover
is one of the problems of NP-hard complexity class. Set cover aims to cover all the elements in the problem with minimum set by using various
parameters of the genetic algorithm. The roulette wheel algorithm for gene selection and the uniform crossing for the crossing of genes were
found appropriate. Apart from these, the most appropriate population size and iteration number were found to be variable according to the
number of set and element. The population size was selected according to the size of the set number, n, 2 * n, 4 * n, 8 * n (n: number of sets).
Genetic algorithm and problem generation coded in C language. Problems solved with the solvents in GAMS and compared with our genetic algorithm
based on the results and solution times. It has been observed that the genetic algorithm reaches the optimum results in a shorter time period
than GAMS.