Further Exploration With GA

In order to become more comfortable with Genetic Algorithm implementation, we had been tasked to use GA to find the solution of a quite abstract card game with the following rules:

“Each one of you is given 10 cards, numbered 1–10. You’re asked to divide the cards in two groups where the sum of the numbers on the cards in the first group is as close to 36 and the product of the numbers in the second group is as close as possible to 360.”

This was definitely quite the challenge to effectively implement since each group of cards could be any possible size in any order without having duplicates present in the combination of both groups. I started by creating my chromosome class that comprised of 2 arrays of ints, each representing one group of cards. This way I could easily return the sum of the first group and the product of the second group using custom in-class functions.

Next was determining how the fitness function would work. First we determine how close the first group’s sum is to 36 and then how close the second group’s product is to 360. We then return the absolute value of the sum of these two numbers as our fitness which would return 0 once we reach our optimal combination of cards but initially return values ranging up to 10,000 for non optimal combinations.

For mutation I had one card from each group be swapped over and kept this new chromosome if it gave a lower fitness. If it’s fitness was higher however, it would revert back to it’s original configuration.

After finishing the implementation, I noticed my chromosomes reaching incredibly close fitness values in the single digit range but never seemed to find an optimal solution that would produce 36 sum and 360 prod. This brings me to the conclusion that such a combination is not possible.