Rachel Shadoan Muses

Great Idea: Genetic Algorithms for Recipes

To be fair, the braised and confused newt on a bed of crushed Doritos turned out to be delicious.

I actually think a genetic algorithm for recipes is BRILLIANT, and I think I have figured out how to implement it, relatively simply (read: ghetto-rig it).

Now, I don’t think you could use it to come up with really detailed recipes, but I think you can use this approach to come up with ideas, or high level recipes.

Basically, a “recipe” object is made up of ingredients and maybe a couple of cooking methods.

In order for this to make complete sense to everyone, I’ll have to give you folks a rundown on genetic algorithms, but that’s going to have to wait until after the Easter holiday starts. (Wait with bated breath, folks, genetic algorithms are sexy, sexy magic.) But the short story of genetic algorithms is that they are a simulation of evolution. You have a population of items, whatever they may be (in this case, they would be recipes). The best, or most fit, items get to reproduce, just like it’s supposed to work in the real world.

The problem with a genetic algorithm for recipes is that it’s hard to evaluate what is “best” or “most fit” without actually making the food and having someone rate it manually. This would take forever, and result in meals much like those in the xkcd strip. So, I have come up with a way to ghetto-rig it.

You rate the recipes by searching for the ingredients in Google and then adding the number of results. I’ll do a short example to make this more clear.

Let’s say we have a recipe: “Cod, kale, stir-fry”.

First we Google “cod kale recipe”, which gives us 1,100,000 results.

Then we Google “kale stir fry recipe”, which gives us 1,660,000 results.

Then we Google “cod stir fry recipe”, which gives us 107,000 results.

Then we Google “cod kale stir fry recipe,” which gives us 532,000 results.

That gives us a grand total of 2,312,700, which is our recipe’s fitness.

Compare this to a recipe of “grapefruit bacon salad”

“grapefruit bacon recipe” gives us 200,000 results.

“bacon salad recipe” gives us 1,380,000 results.

“grapefruit salad recipe” gives us 168,000 results.

and “grapefruit bacon salad recipe” gives us 252,000 results.

That gives us a grand total of 2,000,000. So, our first recipe would have a higher fitness than our second recipe, and would probably be better.

I can’t wait to implement this. I actually think it might work very well. Particularly if, instead of doing it by straight addition, you use a linear combination. That way you can tweak the kind of recipes you want it to produce. If you want to reward highly innovative recipes, you multiply the number it comes up with when you search for all of the ingredients and the method together (that’s the last line in both of the above examples) by a negative number, so that it detracts from the overall score. As a result, “pecan cream cheese cake recipe”, which returns 821,000 results, would score lower than ” ‘green tea’ ‘dark chocolate’ ‘ice cream’ recipe”, which only returns 61,200 results and is therefore more innovative.

I am doing a terrible job explaining this. Sorry–it’s 1:21 am and I am both very excited about the prospect and very tired. It will make more sense when I can lay out some vocabulary and a teeeeny bit of math so that we’re all on the same page.

I think the moral of the story is that the culinary world should be afraid. Very, very afraid. Can you imagine a cookbook full of recipes invented by an algorithm? I CANNOT WAIT. I will call it “Cooking with Robots”.

Advertisements

7 comments on “Great Idea: Genetic Algorithms for Recipes

  1. Ryan
    March 31, 2010

    Nice fitness idea. I’ve been thinking the GA Chef over as well.

    • rachelshadoan
      April 1, 2010

      Thank you! I’m not sure if the fitness idea will work, in practice. It definitely needs to be a linear combination instead of just straight up adding the results of the sets in the power set of ingredients, otherwise I think you would eventually end up with recipes that were really common. So I’ll have to tinker with it a bit, I’m sure, to get the right balance of innovation and … not innovation. Because not everyone likes sardines in their ice cream. πŸ™‚

  2. Rahul Gupta
    April 6, 2010

    Wow! being a foodie and having basic working knowledge of GA, I can’t wait to know results of you experiment πŸ™‚ I found your idea of fitness function for food really creative πŸ™‚

    >> “made up of ingredients and maybe a couple of cooking methods.”
    Don’t forget to include spices in your ingredients list. πŸ˜‰ They carry a lot of potential in creating a range of recipes from the same raw material.

  3. Guilherme Tondello
    April 14, 2010

    Hi! Congrats for the idea!
    Being an engineer and always enthusiastic about artificial inteligence, and genetic algorithms, I`m very curious to see how your idea is going to work…
    Would you mind posting a heads-up on my Flickr whenever you post some result here?

    By the way, not sure how the ingredients and cooking procedures are going to be put together, imagine for instance the computer says you have to stir an apple… or fry a chocolate… But of course, because of the GA, most of the procedures should naturally match the ingredients.. But I`m sure there`s going to be some funny ones… plus, it may be a good start for someone (human, that means) to check the recipees as ideas and refine them into new and creative recipees.

    • Rachel Shadoan
      June 19, 2010

      Hi Guilherme!

      Sorry it’s taken me so long to get back with you. Been a pretty crazy semester. I will be happy to post a heads-up on your flickr when it’s done! But realistically that will be in the fall after I’ve finished the Master’s course I’m currently working on, which doesn’t leave me much time for coding. 😦 This is further complicated by the fact that the beautiful, beautiful generic GA that I wrote a couple of years ago was written for a school project and I was working up so close to the deadline that I didn’t get it commented.

      From my perspective, you can both stir an apple (like making apple sauce, or even cutting it up and stir-frying it) and fry chocolate (Texas, I believe has pioneered deep-fried candy bars).

      I’m actually really excited about the funny ones. I once made a savory tart with sweet potatoes, orange, vanilla, parmesan cheese, garlic, red chile flakes, paprika, cinnamon, cloves, and nutmeg…. It was the most confusing tart I have ever made. It smelled like I was trying to cook an entire meal, dessert included, in one dish. I suppose that any beginning cook is a genetic algorithm for recipe generation! This is just a fun way to formalize it.

  4. barton
    December 7, 2010

    I’m a little sceptical about your rating system… liver and onions recipe may get a lot of hits, cherry and gram cracker cake might get a lot of hits, but I defy you to combine those…

    Finding the right fitness function is going to be the hardest part of this exercise. I was thinking about creating a GA that would work on human ratings of mixes of spices cooked into a neutral base… I think that I could be confident of the quality of the fitness function, but it would be dog slow

    when it comes right down to it I think that cooks doing fusion cooking are actually doing what we’re looking for.

    • Rachel Shadoan
      December 7, 2010

      Liver and onions would get a lot of hits, as would cherry and graham crackers, but liver and graham crackers would not, nor would onions and graham crackers. (I don’t know about cherries and onions–that would probably get a moderate number). The idea is that all of the ingredients have to go well with all of the other ingredients, hence the inclusion of each member of the power set of the recipe components in the fitness function. (Also, I can’t remember if I’ve updated this post, but you have to normalize the totals for the number of ingredients, lest you skew towards longer recipes)

      So, if you have two recipes, one including liver, onions, and lima beans, and one including liver, onions, cherries, and graham crackers, you would expect the former to have a higher fitness since liver goes well with onions and with lima beans, and onions go well with lima beans.

      On the other hand, I haven’t managed to implement this yet, so I don’t know! Maybe I will get a chance over the winter holidays.

      Okay, so now that I gave you that example I actually ran the math on it, and it turns out that liver, onions, cherries, and graham crackers have a slightly higher fitness than liver, onions, and lima beans. Granted, I didn’t include cooking methods or the single-item members of the power set (I know, I’m lazy), but still… And I just ran the example again, including “cake” in the second recipe as per your suggestion, and it still beats out liver, onions, and lima beans (if only slightly). See the lazy version of the math here: Liver Examples

      Well, fine. If I were going to cook liver, onions, cherries, and graham crackers together… I would crush the graham crackers up, coat the liver with them, fry the liver, then top the fried liver with a caramelized onion and cherry sauce.

      Hmm. So you have definitely uncovered a flaw in the fitness function, though I think the core is still sound. All of the individual ingredients and cooking methods of a recipe should go together, in any combination. That part works. What doesn’t work is that there are apparently a lot of spam sites that artificially inflate the hit rate. This site for instance, counts as a hit for “liver cherry recipe”, but doesn’t actually provide a recipe using both liver or cherries. So, I need to figure out a way to search more intelligently, so that I get primarily good hits (ie, real recipes of blogs discussing recipes or food ideas.)

      In the end, this little algorithm should mostly be providing inspiration and fun anyway. Also, I’m totally going to try to combine liver, onions, cherry, and graham cracker now.

Comments are closed.

Information

This entry was posted on March 31, 2010 by in Uncategorized and tagged , , , .
%d bloggers like this: