here i'd like to give you a little peace of code, which you are able to calculate genetic operations.
What does the code do:
1. It generates an organism, which includes a genome-string (dna) with 4 genomes (simple numbers between 0-3) 2. Then it generate a random modell generation to compare a fitness value later. 3. After initializion the first generation of organisms will created. it compares the genome-string with the modell generation an sign the fittest organism. 4. if in the first run the fittest organism was found it stopps the code and print the best generation. 5. if not, it re-evaluate the next generation with mutation (breaks the genome-string at a random position in two peaces and stitch it with another broken string) and compare again. 6. it prozesses step 5 until the best generation was found.
In the #define section you could play with the settings.
It generate at default 100 organisms and a genome-string of 20 genes. The DoOneRun() routine is a endless loop until it founds the fittest generation, so be carfull if you extend your genome-strings and/or the number of genes. ALLELES is the gene-variations a genome has. Default 4 (Number between 0-3) MUTATION_RATE ist the number which sets, if a new breed get a crossover or a new random generation. Default is 0.001. (1/1000th that a random string will be produced). the bigger the number the more like to become a new random genome. 0.1 = 1/10th.
Yes, it is very simple, but shows how simple genetic algorithms work. You could extend it and use it for AI in your own game, simulator, or whatever you like.
have fun and contribute your extension if you like.
PriNova
P.S.: please rename file-extension from .txt to .c to use it with SED.
thank you for the contribution. I'm a bit into soft computing techniques so this is pretty interesting for me. Here are some remarks concerning your code:
The way you do the selection is a bit special. If I interpreted your code correctly the selection happens in SelectOneOrganism. To be honest I'm quite surpised it really does work the way you realized it. I guess it's because organisms with a higher fitness value are more likely to get over the randomSelectPoint variable. So the selection you implemented works by giving the organisms with a higher fitness value better chances of recombining with other organisms.
In a standard genetic algorithm selection happens differently. You have a base population and by first recombining organisms and then mutating random genes you enlarge the population. Now for the selection you sort these organisms and let only the fittest of them survive. For example if you start with 20 organisms and create 20 new ones you got a new population of 40 members. You now sort them by fittness and let the 20 worst organisms die while the 20 best organisms may continue to live and recombine. In consequence organisms can live and reproduce an arbitrarily long time as long as their fitness value is better than the average. In your approach every organism has a maximum lifespan of one generation. This raises the danger of loosing already pretty good organisms and creating worse ones. You can even see this sometimes when the global fitness value decreases.
I have also a remark about your fitness function. In its current form it is pretty useless. You'd normally use a genetic algorithm whenever you have a problem that you don't have a numeric solution for or which is so hard (in the sense of computational hard) that bruteforce would take too long. This is where the genetic algortihm jumps in and offers improved performance by introducing a heuristic. The condition to be able to do so is, that you have means of measuring how good or bad a solution is, i.e. you need a fitness function. In your case the fitness function renders the algorithm useless as the desired result (i.e. your model organism) is well known from the beginning and the function just compares the current result to the already well known end result. While this is totally ok for a proof of concept the practical use of the algorithm is limited in this form, as finding a good representation of your problem solution as a genome and writing a good fitness function are often the hardest part of a GA.
Finally GAs are not well suited for real time applications as you cannot predict how long they will run until an acceptable solution is found.
EDIT: After reading my whole post again I have to admit it sounds negative. But it's meant to be the complete opposite. You already managed some of the most important parts. It's especially good that you have implemented recombination AND mutation. I've seen many people claiming they had a GA while they only had either recombination OR mutation implemented. Do you mind to tell how you got to GAs? Did you have a specific problem you wanted to solve with this?
Always learn from history, to be sure you make the same mistakes again...
the Selection-Algorithm i choosed in this example is the 'roulette wheel' sampling and is the simplest method. About the lifespan with my organism is true. they live only one generation. And yes this could happen in a loss of best agents. [ironic on] Thats life, every Olympic star will die some day :-) [ironic off]
Yes, the fitness-function compares the goal (here the modell-organism) to test for fitness-level. Usually goals for a serios problem space would be to find the most efficient, fewer task-timing spent or shortest waypath taken agent as a behavior.
Reminded, this should be the first simple example to beginn with AI. Extendable in every way to genetic programming, q-learning, reinforcment learning and all what evolutionary algorithm takes place.
Criticism is good in both ways negativ and/or positiv. This is how we got rewarded and could compare our actions and learn to do it better the next way. Words are enough but sometimes we need pain to learn, that the ofen is hot. hehe
To avoid beeing stuck in a local maxima, its good to have random Jumps in the Mutation rate and selection strenght (How many of the top % survive)
Like 100 generations with a low mutation rate and hight selection competitiveness, and then 10 generations with a very high mutation rate and less competative selection. Kind of like introducing ecological shocks.
So the "convenient" periods are used to optimize to a situation, and the agressive and stressful time offer a potential for novel combinations to jump out of the local maxima, that would otherwise loose against the population residing in the local maxima.
(eg, mammals evolving when dinos got kicked in the but)
