Introduction

Genetic algorithms... What is it used for? Well, for one interested in game development, it might help in creating better A.I. It can help you tweak your choice settings in a real-time strategy game so that a computer-controlled opponent might evolve, choose it's actions better, learn and so on. This is my first article ever, so if you feel that something is missing or unclear, please contact me (TheCell61 at hotmail dot com) so I can update it and hopefully make it better. This article is intended for people who have little or no knowledge about genetic algorithms and genetic programming. So what is a genetic algorithm exactly? Well, it's simply doing things the mother nature's way: Only the fittest may survive. So, how can we translate this into computer language? Well, it's better if we take a look at how mother earth does it in the first time. And the best way is to tell you a little story.

Once upon a time, there was a little land called Esras. In this land, there was two kind of creatures, plants and herbivores. Herbivores were wandering around, eating food as they found it. But someday, plant supply started to run low, and so, they had to travel further. Those who didn't travel died of starvation, and so, only those who travelled survived and had a chance to reproduce. But since they travelled a lot more than their relative, they developed leg muscles. But soon, they also were running low on food, and thus, they travelled again. But some were more speedy than the other, and they gained an advantage over the other. They were the first to get to new plants, and so they were able to eat more than the others, and thus survive much longer. Those who were too slow to get to food eventually died. And so on...

So, Mother Nature's way is simply a way to get the best out of us, allowing us to survive and eventually mate. But how does this apply to computer? Well, it's (relatively) simple. When a human baby is born, he/she inherits the parent's chromosomes, 23 from the mother, 23 from the father. The chromosomes are a set of gene which defines hair color, eye color, etc... and a gene is an array of data. So, a chromosome is an array of genes, and a gene is an array of data. So, a gene looks like:

    (11100010)

and a chromosome looks like (in binary data):

      Gene1     Gene2      Gene3     Gene4
    (11000010, 00001110, 001111010, 10100011)

Each gene represents some data (Eye color, hair color, sight, etc.). So, when a baby is born, it's a simple exchange of information, from both the mother and father. And sometimes, mutation occurs. A mutation is simply a reversed bit in a gene. This way, we ensure a diversity in the gene pool. Let me give you a concrete example in a computer perspective. You have a pool of creatures that you want to evolve. You have a gene value for sight, speed and TotalEnergy. Once the chromosomes are decoded, each gene is read as follows:

1stChromosone |  2ndChromosone
Sight Speed   |  TotalEnergy
(0110 0110)   |  (1100)

So now, we have a creature with defined attributes in the form of chromosomes. But how do you make it evolve to become better? Well, that's the trickiest part. You need rules to define what makes an animal the fittest. Usually, in artificial life, it's simple if it's still alive, but sometimes, it can be very complex. A very simple rule in real-time strategy game might be that if a computer takes you more time to beat than another, that opponent has a better chance to mate, and thus, to produce a better opponent. But let's keep it simple, and let it just do it for the survival. If a life-form survives, it must be fit. But if we only destroy the weak, and don't reproduce; we'll only destroy our artificial life. Hence the need to reproduce. As in the little story mentioned above, we must do some exchange to ensure that we evolve, and get the best of each artificial life. And to this, we must exchange information about each gene. To do so, we must make a cross-over in the chromosomes.

             Cross-Over:
                  v
    1stChromosone | 2nd Chromosone
    (Sight Speed) | (TotalEnergy)
    (0110 0110)   | (1100)

So, when two artificial life mate, we exchange information.

First Parent's 2 Chromosomes:

    1stChromo | 2ndChromo
    (01100110) | (1100)

second Parent's 2 Chromosomes:

    1stChromo | 2ndChromo
    (00101111) | (0110)

When those two mate together, we create 2 children with a mixed set of chromosomes:

Baby1's 2 Chromosomes:

    1stParent  | 2ndParent
    1stChromo  | 2ndChromo
    (01100110) | (0110)

Baby2's 2 Chromosomes:

    2ndParent | 1stParent
    1stChromo | 2ndChromo
    (00101111) | (1100)

Mutation appears as a gene being slightly modified. So, Baby1 could get no mutation, but baby2 could get a mutation. So, Baby2's set of Chromosomes may look like this after mutation:

Baby2's 2 Chromosomes

1stChromo | 2ndChromo
(00101111) | (1101)
                 ^
                 |

This mutation ensure a diversity in the gene pool, and permits some new twist when the genes looks too much alike.

What we've done here is simply take the first Chromosome of each parent, and mix it with the second Chromosome. Notice that the first Chromosome is composed of 2 genes, and the second chromosome is composed of only one gene.

Now we put all of this together, and apply it to artificial life. We have a pool of artificial life-form creatures (called AL from now on). We put them in an environment which we then define the rule as follows. Each creature needs food to survive. Eyesight permits it to see food farther. Speed permits it to get to food faster. MaximumEnergy is the maximum energy a creature can get. Then we define that if a creature's current energy ever gets to 0, the creature die. If 2 creatures meet, and their CurrentEnergy is over 50%, they mate and create 2 children. We assign a gene for each characteristic (Eyesight, speed, and MaximumEnergy). In addition, we group the first two gene together to form a chromosome, and the last gene consists of a chromosome in itself. What will happen is that, at first, many AL will mate. Then, many will die due to lack of food. But those who will stay alive are the strongest (or luckiest) of all AL, because they can store more energy, or they get to food faster, or see them, first. Hence, they get a better chance to mate, and produce better creatures, and so on. Sometimes, what happens is that a creature might survive due to luck. Genetic algorithm is meant for optimization, but it's hard to get an exact maximum.

Well, that's the end of this article. I hope it helped you to better understand Genetic Algorithms in general, as it is simply a basic article. Feel free to contact me if you have any questions or feel that something is missing or unclear.

TheCell (TheCell61 at hotmail dot com)