Two decks problem

In the two decks problem there’s a deck of N cards, numbered from 1 to N, and they have to be divided in two decks in such a way that the cards in one pile sum as close as possible to I and the cards in the other multiply as close as possible to J.

We can use a ListGenotype with a binary alphabet, so a length of N represents N cards ranging from 1 to N, and each gene value (i.e. 0 or 1) maps that card to one deck (i.e. 1 or 2 respectively).

Customizing the phenotype

We’re gonna introduce a new concept. A ListGenotype is enough, yes, but it will be nice to vary it’s genotype. We dont care about the internal representation; we only want the actual individual, that is, the two decks.

It requires two things; first, overriding the phenotype method (obviously), and second, telling to the initializer that the class of the ListGenotype instances is not the standard, but is the new one created by us. So let’s get to it.

First, our ListGenotype subclass:

class CardsGenotype(ListGenotype):
    def phenotype(self):
        """The phenotype will be a tuple of two decks containing a list
        of the cards included on that decks."""
        # Those positions marked as 0 will belong to the deck 1 (sum)
        deck1 = [i for (i, g) in enumerate(self, start=1) if g == 0]
        # Those positions marked as 1 will belong to the deck 2 (productS)
        deck2 = [i for (i, g) in enumerate(self, start=1) if g == 1]

        return deck1, deck2

Once we have our class (and it’s a ListGenotype subclass), we just need to create the initializer advising it to use our custom class instead of the default ListGenotype.

initializer = AlphabetInitializer(
        size=N, alphabet=alphabet.BINARY, cls=CardsGenotype
    )

We can now continue with the fitness implementation.

Fitness

The idea is to reach two targets. In the example are specified as two variables, TARGET_I and TARGET_J:

TARGET_I = 36   # Sum target
TARGET_J = 360  # Product target

In our fitness, we will compute the error to each target (using the proportional difference) and then add it. Maybe there is a better solution, but this one does the trick.

def fitness(phenotype):
    deck1, deck2 = phenotype

    error1 = abs((sum(deck1) - TARGET_I) / TARGET_I)
    error2 = abs((reduce(operator.mul, deck2, 1) - TARGET_J) / TARGET_J)

    error = error1 + error2

    # Return the fitness according to that error
    return 1 / (1 + error)

Check the first line of the function. Do you see how the custom phenotype is being used? Nice, now we’re prepared to configure and run the algorithm as usual.

Algorithm configuration

Let’s configure out algorithm. As we did before, it is enough to use the default operators, but this time telling to the AlphabetInitializer that the ListGenotype class to use is out implementation.

ga = GeneticAlgorithm(
    # ... Stuff ...
    initializer=AlphabetInitializer(
        size=N, alphabet=alphabet.BINARY, cls=CardsGenotype
    ),
    # ... More stuff ...
)