GENETIC ALGORITHMS FOR PARTITIONING SETS
William A. Greene · International Journal of Artificial Intelligence Tools · 2001
We first revisit a problem from the literature, that of partitioning a given set of numbers into subsets such that their sums are as nearly equal as possible. We devise a new genetic algorithm, Eager Breeder, for this problem. The algorithm is distinctive in its novel and aggressive way of extracting parental genetic material when forming a child partition, and its results are a substantial improvement upon prior results from the literature. Then we extend our algorithm to the more general setting, of partitioning a set in the case that the environment provides us a measure of the fitness of individual subsets in the partition. We apply the extension to two artificial problems, one with a targeted partition whose subsets are of very diverse sizes, and one whose subsets are the same size. Finally, we apply our approach to several map coloring problems, and obtain good results there as well. In our different stages of work, we exploit different heuristics, which are attuned to the particular partitioning problem under attack.