views:

936

answers:

6

I found this very cool C++ sample , literally the "Hello World!" of genetic algorithms.

I so decided to re-code the whole thing in C# and this is the result.

Now I am asking myself: is there any practical application along the lines of generating a target string starting from a population of random strings?

EDIT: my buddy on twitter just tweeted that "is useful for transcription type things such as translation. Does not have to be Monkey's". I wish I had a clue.

+11  A: 

Is there any practical application along the lines of generating a target string starting from a population of random strings?

Sure. Imagine any scenario in which you know how to evaluate the fitness of a particular string, and in which the choices are discrete and constrained in some way:

  • Picking pronounceable names ("Xhjkxc" has low fitness; "Artekzo" has high fitness)
  • Trying out a series of chess moves
  • Guessing the combination to a safe, assuming you can tell how close you are to unlocking each tumbler
  • Picking phone numbers that evaluate to words (e.g. "843-2378" has high fitness because it spells "THE-BEST")
John Feminella
I am not sure I get the "pronounceable" example
JohnIdol
Say you want to find a pronounceable name starting from some random strings, and you have some way to evaluate how pronounceable each name is. Can you see how randomly permuting the strings until you reach something with high "pronounceability" (fitness) would be done with a GA?
John Feminella
Yep, I get that - It all comes down to knowing the right fitness function. So in case of pronounceability it's gotta be related to consonants and vocals pairing or smt like that.
JohnIdol
That's about right. Often the hardest part of writing a GA is picking an appropriate fitness function.
John Feminella
What about the translation thing in the edit - any clue what's that about? I guess something along the same lines of what you're saying here
JohnIdol
If you had a fitness function that told you how much something looks like a real English sentence, you could permute different translations of, say, a French sentence until you got one that looked close to what a native speaker would say. (Often there are many possible translations.)
John Feminella
Isn't that kind of a long shot?
JohnIdol
You'd be surprised. After all, life is a pretty long shot, and here we are. ;)
John Feminella
I guess you could find a fitness fucntion for "english sentences" feeding a large number of english sentences to a neural network so that it can tell english from other languages and then use it as "fitenss evaluator" ...any resources you'd advice about the subject of fine tuning fitness functions?
JohnIdol
GA's are a black art, but not nearly as black as Neural Nets. ;-)
RBerteig
Neural Nets are alchemy!
JohnIdol
+2  A: 

No. Each time you run the GA, you are giving it the eventual answer. This is great for showing how a GA works and to show how powerful it can be, but it does not have any purpose beyond that.

Kevin Crowell
I don't agree with this at all; you don't need to know what "the answer" is to run a GA. In fact, sometimes there is no answer -- as in my "pick a pronounceable name" example. GAs are especially good at this sort of thing.
John Feminella
You do need to know how good a particular answer is (that's what the fitness function is for). But other than that, it's gravy.
John Feminella
Yes, you do not always need to know the answer to run a GA. However, you do for this particular implementation. His question is not about a GA in general, it is about this specific implementation.
Kevin Crowell
Right, I agree with Kevin. I've seen these kinds of GA examples. They're great for examples, but that's all, because **you already know the answer.** Where GA's make sense is where you don't know the answer, or where there is not "one answer" but rather improving degrees of utility.
Charlie Flowers
(In a sense I agree with John too ... what's he's saying - I believe - is that GA's can be remarkably valuable, and the applications that get value out of GA's follow the same principles as this example).
Charlie Flowers
I think both answers are valid - Kevin is interpreting my question literally so in this he's right. John is saying that the exactly same algorithm you can use without knowing the target but only maximizing the fitness - which is right as well and is somehow more kind of what I was looking for.
JohnIdol
A: 

I have used GA in 2 real life research problems.

One was a power optimization problem (maximize number of appliances turned on, meeting the available power constraint and service guarantee for each appliance)

Another was for radio network optimization, maximizing the coverage area given a fixed equipment budget

Midhat
+1  A: 

You could write an EA that writes code in a dynamic language like IronPython with the goal of creating code that a) executes without crashing and b) analyzes the stock market and intelligently buys and sells stock.

That's a very simplistic take on what would be necessary, but it's possible. You would need a host that provides a lot of methods for the IronPython code (technical indicators, etc) and a database of ticks.

It would also be smart to not just generate any old random code, lest you format your own hard-drive. You need a sandbox, and you need to limit the namespaces that are accessable, and you would need to provide a time limit to avoid infinite loops. You could also provide symantic guidelines that allow it to choose appropriate approved keywords instead of just stringing random letters together -- this would greatly speed up evolution.

So, I was involved with a project that did everything but the EA. We had a satellite dish that got real-time stock ticks from the NASDAQ, a service for trading that had an API, and a primitive decision making "brain" that made decisions as the ticks came in.

Sadly, one of the partners flipped out, quit his job, forked the project (got his own dish, etc), and started trading with logic that wasn't ready. He lost a bunch of money. It turns out that for some people this type of project is only a step away from common gambling. But anyway, the project kind of fizzled out after that. Evolving the logic part is the missing link though. And I know there are people out there doing this type of thing.

Brian MacKay
thanks for your contribution on this - definitely interesting and very powerful as a possible application, also nice anecdote :) - any interesting related resources?
JohnIdol
Here's something interesting: http://stackoverflow.com/questions/131165/evolutionary-algorithms-optimal-repopulation-breakdowns
Brian MacKay
That's just some help with EA's. Most of the articles out there on EA's are really pretentious (read: academic) considering how easy it really is to get started with them.
Brian MacKay
A: 

GA has one main disadvantage, it usually works with genetic speed so using it in some serious time-dependant projects is quite risky.

beermann
A: 

One could use that to find maximum and minimum values for C's datatypes such as long double. :P

kummahiih