Sign in to follow this  
  • entries
    74
  • comments
    187
  • views
    34010

Genetic Algorithms

Sign in to follow this  
NickGeorgia

195 views

"Talk about your genetic deficiencies...." -- Deliverance (1972)

Well, now, we begin on our journey into the crazy world of genetic algorithms. What are they? They are a useful tool in optimization problems. For example, if I gave you the equation, y = sin(x)*cos(z)+ x^2*z^2 and said I want you to find the x and z that minimizes y. You could probably do it with calculus, or you could use a genetic algorithm. The usefulness of genetic algorithms is to find that elusive global maximum or minimum (many algorithms can't find one in very complex equations and get stuck in what is called a local minimum or maximum). While many genetic algorithms out there are very successful at doing this job, there is usually no guarantee you will find a global maximum or minimum... still...the chances are better.



Where would you use a genetic algorithm in a game. Well, I will present a very simple idea later on. We can use it to aid our neural networks (remember--minimizing the error) in finding the weights--but we wouldn't do that cause "it would be boring." The manufacturing scheduling problem is one that definitely uses this. Also, we can use it to impress our friends. We can also use it to write books or in journals. But I digress again... let's get started.

We shall use a traditional genetic algorithm (again just to get you started). What makes a genetic algorithm intelligent, well it's feedback. We start with an initial population of solutions (i.e. think people with possible answers) and we evaluate their answers. We then modify these solutions by mixing up the population's chromosomes (i.e. inbreeding) and come up with some children that hopefully have better genes than their parents to provide better solutions ("this corn is something special" -- Deliverance yet again). The circular process of evaluating a population and then stealing their children is what a GA is... but how do we evaluate and generate new children?



The first step in a GA is typically how should we represent our population. The most common way is to use a series of ones and zeros (bits). Why we do this will become apparrent during the sex stage. For example,

Suppose we were measuring stock market variables such as the temperatures in Peru and number of hot women in Wisconsin (yes there is a correlation between hot women in Wisconsin and the cost of cheese), and we want to use these measurements to tell us when we should buy cheddar cheese (if goat cheese from Peru is doing well, we're in trouble).

We are trying still to find our representation. Suppose we know the maximum temperature in Peru is 128 degrees and 0 is the lowest temeperature and the maximum number of hot women from Wisconsin is 512 and minimum is 0. Hey? This isn't a game... I know.. I'll do that later... first lets get some fundamentals!

Then we can represent temperatures as a string of 7 bits that range from:
Peru Temperature Representation
0 = 0000000
1 = 0000001
2 = 0000010
...
128 = 1111111

We can also do this with the hot women but with 9 bits that range from:
0 = 000000000
1 = 000000001
2 = 000000010
...
512 = 111111111

So we can combine these together into a 16 bit stream.

xxxxxxx|xxxxxxxxx First 7 bits are temperature in Peru and last 9 bits are hot women in Wisconsin.

This will represent our "population" and this is called a chromosome. Each bit is a gene.

============================================================

So now that we know how we are going to represent our population, we now need to know how to evaluate a chromosome (or member of the population). This is the cranky boss stage.
This is where we require some intelligence ourselves... how can we creatively make a evaluation function (also known as fitness function--how fit is a member of the population...) Well, we can think to ourselves and say well we want hot women... hot women are nice... so lets try to maximize that thing. Also, we want Peru goat cheese to be filled with bacteria so we would want high temperatures. But, lets say we did a lot of studying on the subject and found the risk associated with these variables can be measured through (from someone's Ph.D. thesis),

risk = abs((Temp)^2/(Women+1) - (Women^2)/(Temp+1))

Hmm you say, if the number of hot women increases, the effect on the risk from the temperature decreases? What gives? Hey, I didn't write that thesis. Let's just pretend OK. Anyway, that will be our fitness function, and obviously we like low risk so we will be minimizing this guy.

Let's maximize instead and take the recipricol of the above
confidence = 1/abs((Temp)^2/(Women+1) - (Women^2)/(Temp+1))

==============================================

So now we have our population representation and how to evaluate them. Now what? We start with a random population of chromosomes:

Let say we generated these:
0101000_000010000 <-- Jim (who is a nice guy, but kind of dense)
0100011_001000010 <-- Mike (he plays video games a lot while at work)
1000011_100010000 <-- Sam (doesn't like cheetoes, prefers dorritoes)
0001111_110000000 <-- George (plays guitar badly)
0111100_111110000 <-- Boris (disects animals when no one is watching)
0110100_000001100 <-- Mary (scared to death)

===============================================

Now we convert each of these guys/gal to their phenotype which is a fancy way of saying back to base 10 numbers.

Jim = [40, 16]
Mike = [35, 34]
Sam = [67, 272]
George = [15, 384]
Boris = [60, 496]
Mary = [52, 12]

Then we calculate the evaluation function for each (Yes, all these calculations are done in my mind, NOT!)

confidence = 1/abs((Temp^2)/(Women+1) - (Women^2)/(Temp+1))

Jim = 0.0114
Mike = 0.3448
Sam = .00093318
George = .00010851
Boris = 0.0649
Mary = 0.1205

=====================================================
Now we calculate the total "fitness" for this population and then we calculate the selection probability. Think natural selection for selection probability--who's gonna mate? For example:

Total Fitness = 0.0114 + 0.3448 + 0.00093318 + 0.00010851 + 0.0649 + 0.1205 = 0.5426

The selection probability (percentage in this case) for each chromosome is calculated by:

Jim.spmax = 0.0114/0.5426* 100% = 2.1%
Mike.spmax = 0.3448/0.5426 * 100% = 63.5%
Sam.sp = 0.00093318/0.5426 * 100% = 0.1720%
George.sp = 0.00010851/0.5426 * 100% = 0.02%
Boris.sp = 0.0649/0.5426 * 100% = 11.9%
Mary.sp = 0.1205/0.5426 * 100% = 22.2%

(this is turning into a murder of an example...Hehe)
==========================================================
Now we play, "bust a deal, face the wheel" -- Mad Max Beyond Thunderdome. This is the natural selection process. We create a roulette wheel based on the percentages we have calculated. Mike's got the best overall score for his numbers of temperature in Peru and hot women in Wisconsin, so he shouldn't have too much trouble finding a date. Time for another poorly drawn picture.



We are selecting chromosomes (people) now that will be having sex. So we spin the wheel this way:
1. We generate a random number, x, between 0 and 100%.
2. We calculate the cumulative probability:
if x < 2.1% then select Jim;
if (2.1% <= x < 63.8%+2.1% = 65.9%) then select Mike;
if (65.9% <= x < 65.9% + 0.1729% = 66.2%) then select Sam;
if (66.2% <= x < 66.2% + 0.02% = 66.22%) then select George;
if (66.22% <= x < 66.22% + 11.9% = 77.12%) then select Boris;
if (77.12% <= x <= 100%) then select Mary;

I gave Mary a little lee-way since she's the only woman (round off error).

So we spin it about 6 times (usually about the size of the initial population) and say we get these selections:

Jim 0101000_000010000
Mike 0100011_001000010
Mike 0100011_001000010
Mary 0110100_000001100
George 0001111_110000000
Mike 0100011_001000010

Whoa, George got in. The party will be at his place.
====================================================
Now comes the part where we use that bit representation. To generate the children (sex).

The first operation is crossover. This is when we select a bit position by random (1-16) and take all bits left of this position on one chromosome (person) and all bits right of this position from another chromosome (person) and generate a child. The chance for a crossover is set to 25% usually. So we go down our selection list and suppose we stop at Mike and he needs to crossover with someone (sex :0) because he hit the 25% by random number generation. Then we select another chromosome (person) by random and lets say it's Mary. We then randomize a crossover point, lets say it's 5. The we cross over from that point (Mike on left, Mary on right):

Mike's genes to crossover--> 01000
Mary's genes to crossover--> 00_000001100
child = 0100000_000001100

and then replace Mike with the generated child.

The next operation is called mutation. Basically, we go through our whole selected population one bit at a time and generate a random number. If this random number is less than or equal to 0.01 (1% chance) we flip the bit (0 if 1 previously, 1 if 0 previously). Since we have 16*6 bits = 96 bits, we would expect around 1 bit (if ever) to have a mutation. Suppose we are on the fourth bit from the left on Mary when we get the 1% chance from the random number. Then,

Mary 0110100_000001100 becomes 0111100_000001100.
=========================================================
So we may get these children after our crossover and mutation sex operations.

Jim, Jr. 0101000_000010000
Mike, Jr. 0100011_000010000
Mike, Jr. 0100011_001001010
Mary, Jr. 0110100_000001100
George, Jr. 0001111_110001100
Mike,Jr. 0100011_001000010

Can you tell who's doing who? After this we have generated the new children and start the process over until we see our total fitness or evaluation start to settle down.

===========================================================



So we run our genetic algorithm a couple 1000 iterations, and then we take the most fit chromosome and use it as the solution that maximizes the confidence in this case.
So if we found 50 degrees in Peru and 10 hot women to be the best, that's when we should buy cheddar.

Anyway, hope you get the idea.

Reiterating the steps:
1. Find a representation suitable for crossover and mutation (there are other operations out there also) and create an evaluation function (best to make it positive if ya can--and maximize)
2. Generate an initial population of chromosomes.
3. Convert these chromosomes to phenotypes and use the evaluation function to determine the fitness.
4. Calculate the cumulative selection probabilties.
5. Spin the roulette wheel to select the potiential mates.
6. Do crossover and mutation.
7. Goto 3... until solutions seem steady.

There are lots of other genetic algorithms out there. I will come back to a game example later.
Hope I didn't make too many mistakes!

Look at this... some marketing people are using GA's with their webpages. See how GA's get exploited for the purposes of "evil?"

Here is a more elaborate tutorial on GA's I found--click on the chapter numbers.

Here is a link to someone writing about games and genetic algorithms..he uses the word sex also... whaooooooo. He says the encoding of bits is the hardest part which I don't agree with. I say coming up with an evaluation part is the hardest part cause we have to make it intelligently.

Just keep in mind, people do things different ways and you may see a lot of genetic algorithms out there. For example, when I use genetic algorithms, I sometimes keep some of the good people in the population no matter what and don't let them get crossover or mutation. It depends on the problem and a tradeoff between how fast you want the solution and how good the solution will be.

So there you have it, a genetic algorithm. You start off with some people. They get evaluated. They generate new children which are hopefully superior. Then they get evaluated... etc. etc. And we stop when we feel the answers are sufficient.
Sign in to follow this  


14 Comments


Recommended Comments

Awesome entry. I've looked over stuff on GAs before but you've just cleared up a number of things for me, thank you [smile]

Share this comment


Link to comment
*raising his hand* :D

I have a couple of more or less intelligent questions.

Question 1:

"What makes a genetic algorithm intelligent, well it's mostly feedback."

what else ?


Question 2:
if x < 2.1% then select Jim;
...
if (66.2% <= x < 66.2% + 0.02% = 66.22%) then select George;

Does Jim not have a greater change of getting some fun than George ?

Question 3:
if (77.12% <= x < 100%) then select Mary;

Should that not be :

if (77.12% <= x <= 100%) then select Mary;
(<= 100% instead of < 100%)

or

generate a number <100 ?

Otherwise, as I see it, the random number could be 100 and you would "waste" an iteration.

Question 4:
crossover.
"The chance for a crossover is set about 25% usually."
"....because he hit the 25% by random number generation..."

I do not quite get the "25%".
How can you say "...about 25% usually." about a random number ?
(I think I am reading it wrong :)

Question 5:
mutation.
As I understand it mutation is done in order to generate a new slighty changed generation.
How do one decide how much mutation ?

Share this comment


Link to comment
Good questions Mike (you rule bartertown afterall). Let me see if I can answer them.

Question 1:
"What makes a genetic algorithm intelligent, well it's mostly feedback." what else ?
Well, to tell the truth. I don't know what else--I blame this on my writing which I did on the fly. Depends on how you define intelligence. Basically, I said feedback was the intelligence because the people in the population represent some form of knowledge. This knowledge gets modified upon each iteration of the GA and hopefully gets better. The evaluation function provides the feedback. Anyway, sorry if I confused ya. Good you asked though cause someone may be wondering the same thing.



Question 2:
if x < 2.1% then select Jim;
...
if (66.2% <= x < 66.2% + 0.02% = 66.22%) then select George;
Does Jim not have a greater change of getting some fun than George ?
Yes Jim has as better chance because he owns a bigger piece of the wheel. Jim owns 2.1% of the wheel, while George only owns 0.02% of the wheel. (oh i see what you mean, the surprise that Jim got in when George got in the party as well... I changed that, thanks)



Question 3:
if (77.12% <= x < 100%) then select Mary;
Should that not be :
if (77.12% <= x <= 100%) then select Mary;
(<= 100% instead of < 100%)
or
generate a number <100 ?
Otherwise, as I see it, the random number could be 100 and you would "waste" an iteration.
Yes sir, you are correct! I will go change that after this.


Question 4:
crossover.
"The chance for a crossover is set about 25% usually."
"....because he hit the 25% by random number generation..."
I do not quite get the "25%".
How can you say "...about 25% usually." about a random number ?
(I think I am reading it wrong :)
Well you can define how often you want crossover to happen. Say I want a mass orgy of crossover... then I would want crossover to happen 60% of the time. I say 25% because that is what a lot of researchers use to start out... then they usually say to themselves... this GA is trash, it's not finding the solution fast enough.... let's make it have more sex. You can do this with mutation as well (instead of 1%, make it 25%) However, you will find your solutions hopping all over the place.


Question 5:
mutation.
As I understand it mutation is done in order to generate a new slighty changed generation.
How do one decide how much mutation ?
These are questions that are usually problem dependent and involve some trial and error. Suppose I gave you y = -x^2 and wanted you to find the x that produces the maximum y, well you probably wouldn't need too much mutation to find the solution. If I gave you a really bumpy equation (lots of hills and valleys) then you probably would like to have a higher mutation rate so the populations won't stay inside the evil local minimums or maximums. Mutation lets these chromosomes pop out of these local minimum or maximum so the search for a global minimum or maximum is possible. It would be an interesting PhD thesis to find the optimum mutation and crossover rates for certain classes of problems... if it hasn't been done already.

Well hopefully, I answered your questions sufficiently. Thanks again for them. Questions usually test my knowledge as well. Also note Micheal, that I'm not "the expert" on a lot of these things, some views might be a whole lot better. But I can see you are interested and that is great! (also thanks for the hints in what I needed to make changes on...hehe)

Share this comment


Link to comment
I <3 You.

Dude that is so awesome, I've been meaning to learn Genetic algorithims as a means to evolve solutions to complex equations (way to take Numeric Methods to another level aye?) and needed something easy yet good to get my feet wet in. Your article was just what I was looking for. *END CHEESY GAY ADVERT TESTIMONY MODE* Seriously though its awesome.

Your function is not differntiable at Point A, the limits as Δx -> 0 at both directions are different. :P

Here is something for you though, rather than evolve solutions one imagines that equations can also be evolved, you have data and the beginings of a formulation, yet you know that there exists no mind intelligent enought to have the data be a perfect fit to a formulated set of equations. So you cook up a complex genetic algorithim to do the job, which I assume would have to be specific to the problem, I imagine these things are quite sensitive and no generic solver could be created. How do you feel about this? That you could never have gotten there by yourself?

I begin to feel that we near such a time, we near the end of the reach of man's intellect. Perhaps we consider that this is no different than a crane or tractor etc., if we wish to build skyscrapers then we must give up the unjustified pride in the works of our hand or in this case, the mind. Just as there exists a limit to our strength so also does one exist for our mind, it simply took us 8,000 years to reach the latter. So it is not suprising that we are very much unused to the idea of incomprehensible developments, we see it as blasphemy. Nonetheless we must we accept the mental analogue of mental boulders.

Even now with the non commutative geometries and their Poisson and Gerstenhaber algebras at the edge of mathematical developments we see a limit in innovation and also, a narrow lining. I imagine that the next step, the next big one is to combine the mathematics or perhaps more accurately, the concepts and methodologies of hte non linear dynamics, non commutative algebras, the concepts of groups and spaces and shapes into one large super analytic mathematics. Of course no mere mind could understand such. Consider this though, in the days of Euler and Laplace the mathematics much of the calculus could not be done without the inventions of Napier some time earlier, the logarithmic table. The table of logarithims and the slide rule (also by Napier) allowed many complex concepts to be calculated that otherwise could not have been. Thus I argue that the algorithmic concept of genetic algorithims be placed on a rigorous axiomatic system allowing for analysis of these complex problems. And just as in the old days you'd whip out your slide rule or your table of logarithimgs to perform your complex calculations so also do I imagine in the future would you whip out your Learned Computer and perform the neccessary actions.

I see this as the step forward. Is this possible? With GA as I see it nothing is set in stone, much is trial and error as you say. How do you remain on your feet, in position during a massive avalanche? This is a good time to be alive I say. Much excitement abounds.

End musing, perhaps i should put this in my journal as well...someday...

Share this comment


Link to comment
Thanks Daerax, I appreciate your enthusiasm. It took me a couple of readings for it to sink in, but I think I understand what you are saying.

Do I mind being limited mentally and having to resort to using tools to aid me? I don't mind it too badly, just as long as I understand the tool. I remember my excitement when I was learning differential equations and proving for the first time in college. I used to believe that I could solve every differential equation by hand. Then I studied some chaos theory and was enlightened. Was I upset? A little I suppose, but in the end, the solution is what matters and if we can find it (the engineer in me talking). Are our brains limited? Probably to some extent. Usually mathematics and science are developed by observations we make. However, sometimes, rarely, our imaginations open up to things we do not observe. This is where I believe our next step in evolution will be. If we don't go this proposed route, then it's not so bad, it's good to always dream of the possibilities of the world we can "see." There will always be an urgancy for innovations for the problems that present themselves. Our tools will get more sophisticated and way of life change. Such is the nature of things... from fire to the Internet. Not a bad world I think, keeps us moving forward. I wonder what we will do near the end of our fuel supply.

Anyway, your proposal on formalizing GA's in a mathematical framework is being done already I believe. People like to understand the limitation of their tools. I do like the fact that you are coming up with ideas and that you seem to come from a mathematical background (my dad, uncle, and grandpa were all mathematicians--my favorites from history are Gauss (Ligget se), Newton, and Archimedies) I still find myself trying to prove Fermat's last theorem on occasion (even though a solution has already been found). Also, I'm hanging on to an idea I have using chaotic equations and their initial conditions to compress data--even though I've been told a few negative things. If you like it, go for it (Just do it-Nike) Daerax... you never know until you try I would say. Also, don't worry about what others think too much if it's something you believe in. Even poor Ohm got laughed at with his V=IR and it was never truely accepted until after his death. Let them laugh, while we try and change the world. (I think I'm digressing) ... Anyway, exciting times indeed.

Share this comment


Link to comment
Cool! Another Bernoulli family hehe. My family is not as mathematically impressive as yours [grin]. Just a computer engineer(phd) and a chemist uncle. My favorite mathematicians are Monge, Archimiedes,Georg Cantor, Henri Poincare, Emmy Noether (for sexual equality) and ofcourse Gauss. That guy was quite the character. I am quite interested in the history of mathematics and so could actaully list many others: Euler, Lagrange, Laplace, Dirichilet (?), Banach, Paul Erdos, Fourier, Jacobi, Poisson, Sophie Germain. Dont forget the super geniuses Galois and the indian Ramanmujam or... ok ill quit now. I got carried away, history of mathematics and biographies on these people is my light reading. [smile]

But yeah, I was rambling about how you would feel if you found out that without a computer's help you could not possibly have figured out something. I originally felt like it would be cheating but with so many claims of this and that mathematics being too difficult to take any further and this physics being beyond that mathematics floating around I see this as the only logical choice. I got used to the idea. Besides, only Newbies feel using prebuilt APIs or even game engines are cheating when its a game your are trying to make. Anyway, Im glad that these steps are already being taken for GAs, seems like an interesting area to explore...

I feel there is too little emphasis placed on non linear dynamics, few people truly grasp it and are comfortable in it. I know Im not. I plan to read up on the Quantum Chaos sometime this year though. Looks like it will be most interesting. Anyway Im glad I have found someone else with high ambitions who would not consider my similarly lofty goals as "foolishness". Truly the only reason there are not more great creations is because most people takes the advice of others as to what and what is not possible instead of listening to themselves (within reason ofcourse, cranks are not cool).

Btw, why not tackle Goldbach's Conjecture instead :P ? Word is Poincare's Conjecture might be solved as well.

Share this comment


Link to comment
Hehe.. someone who likes to read and read about mathematicians... what is the probability on that? The history of mathematics is so facinating I think especially the characters.

I don't know why I still try and solve that Fermat's last theorem. I speculate that it's because of that note in the margin he left before he died. As for the others, well I might look into them. But trying to find that elusive bugger really gets my juices flowing.

Anyway, got to get to bed. Gotta speak with you more in the future!

Share this comment


Link to comment
hehe, yeah. Ive given up my right to sleep...tis 8AM (UK) here. Must stay up now.

I actually have a copy of Fermat's notes in Bachet's work (a book with a bunch of copies of original stuff including the sand reckoner!) and in it he says "...In the same way I have discovered and proved that there cannot be a triangular number, except for one, which is also a fourth power". Is that it? I am simply curious to know why you feel the offered proof is insufficient? Too modern?

Share this comment


Link to comment
Guest Anonymous Poster

Posted

The full text of Fermat's statement, written in Latin, reads "Cubum autem in duos cubos, aut quadrato-quadratum in duos quadrato-quadratos, et generaliter nullam in infinitum ultra quadratum potestatem in duos eiusdem nominis fas est dividere cuius rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet" (Nagell 1951, p. 252). In translation, "It is impossible for a cube to be the sum of two cubes, a fourth power to be the sum of two fourth powers, or in general for any number that is a power greater than the second to be the sum of two like powers. I have discovered a truly marvelous demonstration of this proposition that this margin is too narrow to contain."

I stole the above from somewhere. It's just a feeling I have that there is a more simple proof than the one given. Probably not, but hey it's just fun.

Share this comment


Link to comment
y = sin(x)*cos(z)+ x^2*z^2

for x = 0
z = 0

= 0 * 1 + 0^1*0^2

= 0

Thats the lowest (non-negitive) it can get.

If you need two different values,
x = 0
z = 1/infinity

Thats pretty much the same.

For negitive, the solution would probably -infinity for both x and z.

If both can't be the same, then -infinity for x, x - 1 for z.


As for ga's, you need to give em a better problem... (how about getting a ga to make an ann, thats about the best thing i've seen em do :-))

Either way, nice tutorial.

Any chance you can do something on simulated annealing. (its a nifty thing to use).

From,
Nice coder

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now