Evolutionary Divide and Conquer for the Set-Covering Problem

Genetic Algorithms provide a weak search method that scales rather badly when used in their traditional form. On the other hand, the set covering problem, when used to solve real-world problems, presents an enormous search space for genetic algorithms. A method is presented, by which genetic material is maintained for a long time within the population to allow a greater portion of the search space to be covered in the hope of producing greater quality solutions. The problem is broken down into smaller subproblems for which a population of solutions is evolved. The quality of those solutions is then assessed depending on how well they fit in with solutions to other subproblems. We find that the method has merit and potential, and we discuss its sensitivity to various parameters. 1 Introduction 1.1 Retaining Variety The success of a genetic algorithm in finding at least a near optimal solution depends on the amount of genetic material the population is capable of maintaining throughout..