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 Solution
+
Yellow Solution
=
Composite Solution

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.

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).

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

``````

paufler.net@gmail.com