Genetic Algorithms
Genetic Algorithms create agents who compete to find the best solution to a problem using evolution.
Agents are initially created either using the best chromosomes from a previous run or a random mixture of chromosomes. After each round we evaluate each agent to see how well he has done. We then mix up the genes by switching among our best agents and or adding in some mutations. We repeat this for a set number of rounds or until some goal is reached.
If only gene switching is done and no mutations are entered into the population the agents will often only find local maximums not global maximums. If the number of agents is too small a solution may not be found.
Simple Genetic Program – you have predators, prey and food for the prey. When either a predator or prey reaches reproduction energy 2 of 3 genes are passed directly to the child, one is random.
GeneticLife.java
See Also:
Bioinformatics Blog: Genetic Algorithms: A Quick Tutorial
Racing with Evolutionary Algorithms
15 Responses to 'Genetic Algorithms'
Leave a Reply
You must be logged in to post a comment.
Hi!
Thank you for the link to my blog!
I hope you had enjoyed the post upon the walking robots.
See Ya!
Marcelo
Nosophorus
13 Jun 07 at 6:17 am
Hi! I am currently writing a (free and open) e-book called “Global Optimization – Theory and Application”. It is about genetic algorithms, evolutionary algorithms, evolution strategy, leaning classifier systems, simulated annealing, and so on. I hope that I can make this topic more interesting for students and fellow researchers and help people to get started with it. Of course, my book is still very incomplete and probably has also errors, but I try to improve it very much. You can find it at http://www.it-weise.de/projects/book.pdf, I will update it regularly. Constructive criticism is always welcom, as well as new suggestions on what to include in the book.
Kind regards,
Thomas.
Anonymous
28 Jun 07 at 7:24 am
Thank you for letting me know. I’m sure there will be people here interested in your book.
Good luck with it.
herself
28 Jun 07 at 1:51 pm
Thanks for the code sample. Can you suggest some ways that a GA or AI in general might be used in information security? I have a deep interest in both fields.
wlerner
5 Oct 08 at 8:40 pm
You’re welcome.
I’ve been thinking about that myself since one of my websites got hacked back in April.
I’ve collected log files and cleaned the data, even stuffed into a mysql db to make it easier and faster to parse.
It shouldn’t be too hard to evolve something that can recognize the good guys from the bad guys in the log files.
What I haven’t yet figured out is how to create an entity that keeps learning after that with out user input. Threats are constantly changing, new legit browsers hit the net all the time.
So I’ve been stuck on that.
While I could keep tweaking a security program flagging mislabeled bad from good, I’d like to develop one that doesn’t need input since the average webmaster won’t take the time to do that.
Love to hear your thoughts on the subject.
ljmacphee
5 Oct 08 at 11:17 pm
I would imagine that you could continue to learn by keep a database with known attack signatures and having a GA work the problem. The chromosomes could be the individual signatures. I am sure a fitness function could be devised that would allow for mutations that might show new attack methodologies. It seems to me that most attack methodologies do not vary so much that a little applied heuristics could not provide a tremendous advantage.
Do you have any insight in to fitness functions? I would love to see some examples of what you or others have used in their code.
I am relatively new to the study of AI, but I am fascinated by the subject. I have read a number of books on the subject, including GA’s, data mining, game theory and such. A large portion of my PhD course work consists of AI and HCI.
Thanks for taking the time out to talk with me. Hopefully we can stay in touch and bounce thoughts and ideas off of each other.
wlerner
8 Oct 08 at 12:53 am
But could you do that with out input from the webmaster?
Did you see the more recent post on the Santa Fe Ant Trail? that is another genetic algorithm and a bit more sophisticated than this program, and might give you a better example of a fitness function.
I’ve been working on learning ObjC/Cocoa the last couple of months so I can take some AI stuff to the iPhone. ( hence the lack of posts on this site ) But hope to dig back into the AI in a month or so.
ljmacphee
8 Oct 08 at 12:39 pm
I am sure it could be done without input form the webmaster once the developed software was running.
I looked at the Santa Fe Ant Trail post and it was very informative. I was able to identify a number of different fitness functions. It would be nice if there were a book that identified fitness functions, showed some sample code for them in different languages ( C & Java preferred
) and then explained where they would be useful.
Grats on the iPhone. I exclusively use Macs at home, and mostly *nix variants at work. Let me know how you progress with the iPhone apps, it sounds cool.
wlerner
9 Oct 08 at 7:44 pm
I have been using Genetic Programming: On the Programming of Computers by Means of Natural Selection (Complex Adaptive Systems)
( looks like Amazon has some used copies available too ). I got about 1/3 through it before I set it aside to work on the iPhone and security stuff. You’d probably find it useful.
He uses Lisp, but algorithms are algorithms and I had no trouble using C/Java to follow his algorithms.
We use Mac and *nix here too. No time to do battle with the computer.
ljmacphee
9 Oct 08 at 10:29 pm
Thanks for the tip on the book. I ordered one used after reading the review. It looks like it will be helpful.
Have you ever heard of the GeneXproTools? They are located at http://www.gepsoft.com. Check it out if you get a chance and let me know what you think. I especially like the feature of providing me with code in multiple languages once a solution has been found.
Enjoy your Friday!
wlerner
10 Oct 08 at 10:56 pm
I think you’ll like the book, it’s the best on on GP I’ve found so far. I’m a big fan of used texts. We go through so many of them here, I expect you do also.
I hadn’t seen gepsoft I bookmarked and will try to look at it this weekend.
Allergies are killing me and I’m trying to stuff more ObjC and Sqlite3 into my head today. That’s the main plan for the weekend is to get the basics of tables and db on the iPhone down.
ljmacphee
10 Oct 08 at 11:55 pm
I picked up a license today for the GeneXproTools. I will install it sometime this week and let you know how it goes. I hope your allergies have lightened up. Still waiting on the book.
wlerner
13 Oct 08 at 7:09 pm
Yes, Thanks, today wasn’t too bad.
I have the GepSoft stuff bookmarked but am still playing catchup on everything this week. It’s going to be a couple of more days before I can play with it.
I find it usually takes about a week to get the used books from Amazon.com
I’ll be interested to hear how you like the GeneXpro Tools.
ljmacphee
13 Oct 08 at 11:01 pm
I got the book. I have not had a chance to do more than flip through it, but it appears to be everything you said it would. Thanks! I will let you know how it goes as I read through it.
wlerner
10 Nov 08 at 11:57 pm
I think you’ll really like it. Mine’s sitting on the shelf half finished till I finish a couple of more iPhone programs. Then I hope to dig back in.
ljmacphee
11 Nov 08 at 5:12 pm