Solution of The Set Covering Problem with Genetic Algorithm

This project involves solution of covering problem of set cover by genetic algorithm, which is one of the artificial intelligencemethods. Set cover problem is a classical problem combinatorics, computer science, operations research and complexity theory. Set coveris 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 variousparameters of the genetic algorithm. The roulette wheel algorithm for gene selection and the uniform crossing for the crossing of genes werefound appropriate. Apart from these, the most appropriate population size and iteration number were found to be variable according to thenumber 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 algorithmbased on the results and solution times. It has been observed that the genetic algorithm reaches the optimum results in a shorter time periodthan GAMS.