Author
|
Topic: Genetic Algorithms (Read 1035 times) |
|
Bass
Initiate
Posts: 196
Reputation: 5.74
Rate Bass
I'm a llama!
|
 |
Genetic Algorithms
« on: 2006-06-21 22:50:33 » |
 |
Hi, new here!
Anyone care to discuss Genetic & Evolutionary Algorithms? I've recently began studying the topic and would like to learn more. It is a very fascinating topic, if you havn't read anything on it, I highly recommend it. I'm still learning myself, but I've read one paper from the Computer Science Dept of Stanford. I have gotten my hands on a few books that I'm going to read ASAP on the subject and Algorithms in general. Any info you can share on the subject? I have an essay coming up and need some ideas!
Cheers.
|
|
|
|
|
Fox
Adept
Gender: 
Posts: 122
Reputation: 7.35
Rate Fox
Never underestimate the odds.
|
|
Re:Genetic Algorithms
« Reply #1 on: 2006-06-23 17:31:00 » |
|
Cool subject. Ok, I'll bite.
As you may already know, Genetic Algorithm (GA) transforms a population (set) of individual objects, each with an associated fitness value, into a new generation of the population using the Darwinian principle of reproduction and "survival of the fittest" (although initially coined by Alfred Wallace) and analogs of naturally occuring genetic operations such as crossover (sexual recombination) and mutation.Each individual in the population represents a possible solution to a given problem.
One of my favorite classes of problems to solve with genetic algorithms is finding strategies for simple games. The “evolving genomes” don’t “know” anything about tick tac-toe other than to make a move each time it’s allowed, and when the “environment” tells it it has won, lost, or tied. The two “genomes” evolve toward the goal of winning, or, if unable to win, not losing.
M[UMPS] code allows two “genomes”, initialized to completely random play strategies, to “evolve” the ability to play ordinary 3x3 tic-tac-toe.
Here’s a sample of an output, which, being randomly driven, varies:
Coad:
000 1
020
001
000 2
002
110
...
111 391
122
212
W
000000010
000001200
001001200
001001202
001001212
001021212
002121112
011221212
111122212
111 392
122
212
In this example, the two genomes “stabilize” after 390 plays of the game. Interestingly, the two genomes aren’t “good” at tick-tac-toe in general, only in playing with each other. To evolve genomes that are good at it in general requires a more complicated “ecology” than just two “organisms.”
To explain, the thing that AI folks like about Lisp is that the language is built to generate code on the fly and execute it. *Everything* in Lisp is a "list" including the code. So all you have to do to do this "evolutionary" stuff is keep the algorithms around (kinda like gene sequences in deoxyribonucleic acid) and then randomly change them or choose to "express" them by picking the list and doing a:
Coad: (eval 'list)
many other languages have "eval" functions (vb, javascript, etc), but the fact that lists are the both the basic datastructure and how you write code makes it *extremely* straight forward in Lisp. Very cool.
Here's one of my favorite sites on the topic: http://www.generation5.org/ although there are lots of them out there. Google "neural networks" as well as "genetic programming": they use almost identical techniques.
Learning Algorithmically,
Fox
|
I've never expected a miracle. I will get things done myself. - Gatsu
|
|
|
|
Logged
