Lightning Talk

Building a Solution Set Recipe
with
Genetic Programming

For when the generalized form of a solution is known.
But the path to an optimum (or acceptable) solution is not.

Genetics is a Metaphor

Red Genes, Yellow Genes, combine to form Mixed Gene Sequence

Red Solution
+
Yellow Solution
=
Composite Solution

Cookie Graphic

Building a Recipe

Possible parameters for a Chocolate Chip Cookie recipe.

Ingredient	Low	High
Flour (cups)	1	10
Eggs (each)	1	10
Sugar (cups)	1	10
Chocolate Chips (bags)	1	25
Walnuts (cups)	0	10

Simplistic (Random)

The simplest procedure would be to simply plug and chug away, taking random guesses as to what might work.


from random import randint, choice

def random_recipe():
    '''Returns a random recipe formula in the form of a list six integers long.
        Ex: [1, 2, 7, 13, 8]'''
    flour = randint(1, 10)
    eggs = randint(1, 10)
    sugar = randint(1, 10)
    chips = randint(1, 25)
    walnuts = randint(0, 10)
    recipe = [flour, eggs, sugar, chips, walnuts]
    return recipe

Scoring

But is the recipe any good?

Trying every combination could be costly.
Trying a recipe at random could be unappetizing.
Best pre-qualify as much as possible.


def score_recipe(recipe):
    '''Simplistic scoring for a chocolate chip recipe.
    Takes an integer recipe list, returns a signle integer value.
        Ex: recipe=[10, 9, 7, 12, 0], returns: 101'''
    flour, eggs, sugar, chips, walnuts = recipe
    lots_o_chips = chips * chips
    low_nuts = (chips - walnuts) * 10
    things_are_expensive = - sugar * eggs
    carbs_suck = - pow(flour, 2)
    score = lots_o_chips + low_nuts + things_are_expensive + carbs_suck
    return score

Meaningful scoring IS the limiting factor in Genetic Programming.

Creating a Seed

Genetic Programming is an iterative approach, so a seed recipe is required. But there is no reason to only use one recipe as the seed.


def seed_recipes(keepers):
    '''Returns a num long sorted list of (score, recipe) tuples.
        Ex: [(428, [4, 7, 1, 19, 10]), (347, [4, 4, 3, 15, 0])...''' 
    seed = [random_recipe() for _ in range(keepers)]
    seed = [(score_recipe(s), s) for s in seed]
    seed = sorted(seed, reverse=True)
    return seed

The seed could be an empty value: [(0, [0, 0, 0, 0, 0])] * keepers.
But for this to achieve meaningful results, the rest of the example code would also have to change, as well.

Cookie Graphic

Fixed Length Iterator

Using a fixed length loop, the search period for the ideal Chocolate Chip Cookie is decided in advance.


def recipe_mutator(seed, keepers):
    '''Genetic Algorithm applied to a recipe seed.
        1) New random recipes are added to seed
        2) All combinations of recipes are woven together
        3) Only the best are returned
        Takes a sorted scored recipe list (the seed) and returns same.
        Keepers is length and controls extent of manipulations.
        Score of best returned recipe is always >= that of passed seed.'''
    seed = list(seed)      #Needed for recipe_iterator() below
    print 'Passed Seed:', seed[:2]
    for n in range(keepers):
        print 'Recipe Mutator: Loop %d of %d' % (n + 1, keepers)
        seed += seed_recipes(keepers)
        mutations = []   
        for sR1 in seed:        #'Weaving' occurs in this loop
            for sR2 in [s for s in seed if s != sR1]:
                mutations.append([choice(pair) for pair in zip(sR1, sR2)])
        seed += mutations
        seed = sorted(seed, reverse=True)
        seed = seed[:keepers]
        print seed[:2]
    return seed

#Sample Output
#Passed Seed: [(584, [5, 10, 8, 23, 7]), (208, [6, 3, 4, 14, 8])]
#Recipe Mutator: Loop 1 of 5
#[(621, [10, 5, 7, 24, 6]), (618, [4, 5, 6, 22, 4])]
#Recipe Mutator: Loop 2 of 5
#[(621, [10, 5, 7, 24, 6]), (618, [4, 5, 6, 22, 4])]
#Recipe Mutator: Loop 3 of 5
#[(672, [4, 6, 8, 24, 8]), (643, [7, 1, 2, 22, 1])]
#Recipe Mutator: Loop 4 of 5
#[(672, [4, 6, 8, 24, 8]), (643, [7, 1, 2, 22, 1])]
#Recipe Mutator: Loop 5 of 5
#[(769, [2, 9, 8, 25, 3]), (672, [4, 6, 8, 24, 8])]

In the dual nested sR1 & sR2 loops, the values for the two recipes are woven together (i.e. a new recipe is created taking for each values the value from either sR1 or sR2 for each ingredient).

Cookie Graphic

Recursive Iterator

Rather than a fixed number of loops or manipulations, the search will continue in the code below until the maximum recursion depth is reached (typically 1000) or a target score is beat.


def recipe_iterator(seed, keepers, target, i):
    '''Returns a scored recipe list whose best recipe exceeds target score,
    or throws an exception trying.
        No provision is made to limit recursion depth or
            insure score is mathematically obtainable.'''
    if seed[0][0] <= target:
        i += 1
        seed = recipe_mutator(seed, keepers)
        return recipe_iterator(seed, keepers, target, i)
    else:
        print 'Recipe Iterator Loops: %d' % i
        return seed

If name == 'main':

If __name__ == '__main__': know it, love it, use it.

Code won't fire unless module is run as main, so code can be imported cleanly without running any functions, but can still be used as a one off.


if __name__ == '__main__':
    #Eyeballing Scoring Criteria
    print 'Reasonable Recipe Score: %d' % (25 * 25 + 250 - 1 - 1)
    #Random Number, higher runs longer, gives better results
    keepers = 5
    #Test run of function
    recipe = random_recipe()
    print 'recipe: ', recipe
    #Test run of function
    score = score_recipe(recipe)
    print 'score: ', score
    #Genetic Programming Demo Run
    seed = seed_recipes(keepers)
    rm_recipe = recipe_mutator(seed, keepers)[0]
    ri_recipe = recipe_iterator(seed, keepers, target=850, i=0)[0]
    print
    print rm_recipe
    print ri_recipe

#Output
#Reasonable Recipe Score: 873
#recipe:  [2, 2, 5, 20, 2]
#score:  566
#Passed Seed: [(584, [5, 10, 8, 23, 7]), (208, [6, 3, 4, 14, 8])]
#Recipe Mutator: Loop 1 of 5
#[(621, [10, 5, 7, 24, 6]), (618, [4, 5, 6, 22, 4])]
#... (lots of lines of skipped output
#Recipe Mutator: Loop 4 of 5
#[(860, [3, 3, 2, 25, 0]), (850, [1, 1, 4, 25, 2])]
#Recipe Mutator: Loop 5 of 5
#[(860, [3, 3, 2, 25, 0]), (850, [1, 1, 4, 25, 2])]
#Recipe Iterator Loops: 82

#(769, [2, 9, 8, 25, 3]) #print rm_recipe
#(860, [3, 3, 2, 25, 0]) #print ri_recipe

Red Genes, Yellow Genes, combine to form Mixed Gene Sequence with additional mutations