🔒 Locked

Genetic Algorithm

Started by sharpnova Sep 12, 2006 at 7:42 AM 25 replies 4.9k views

Original Post

Sep 12, 2006 at 7:42 AM

I'm interested in writing a genetic algorithm. I'm sure my idea for it is nothing new or breathtaking, but I'd like to imlement it as follows: There is a world grid of arbitrary size. Food is present distributed more or less randomly. The creatures are placed randomly at the start. They wander around eating food and their fitness will be how many foodstuffs they ate. At the end I'll create a new population of the same size by iterating over the population n times and allowing them to reproduce with a likelihood in proportion to their fitness. I'll have some mutation and crossover. Simple and elementary. Now for my problem.. and I'm sure this is probably the hardest part to figure out for any GA. How will the genetic information work for individuals. More details: The creature can make one of four choices, to move up, down, left, or right. Moving onto a food eats it and causes another food to spawn in a random location (not ontop of a creature or another food) and two creatures can't occupy the same spot, though a creature could elect that his move will be onto a square that another creature occupies. Assuming that the second creature moves away for his move, then the first creature will be able to move there, otherwies he will sit still. The creatures have their genetic code AND are able to see everything in a 5 by 5 grid centered around themself. The world wraps top to bottom and left to right and if they are at an edge, their field of vision is still 5x5 and just wraps around the world to the other side. The problem at last: How do I make some genetic code that can operate on this 5x5 bit of data to yield a result in which direction to choose? I thought at first of having four 5x5 matrices and just multiplying the vision state matrix with each of thoes fuor (one for each direction) and having the creature choose a direction based on which product was largest or smallest or closest to some value. But I realize that with the world being random and there being nothing special about up, down, left, or right from one world to the next, this would not accomplish anything. What I want is for there to be some genetic information that the creature can use to help it decide a direction to take based on it's current 5x5 vision matrix. I'm hoping to see little patterns evolve.. like here are some examples i envision: -creature sees 2 foods to it's lower right, but another creature is in between it and th food. it sees 1 food to it's upper left... and it goes for the food in the upper left.. because evolution wise, those that went for that.. would be more likely to get to get any food at all.. but if there were no creature present.. it would go for the 2 foodstuffs instead of the 1.. or maybe.. if there were 3 or 4 foodstuffs, with another creature in between, and 1 in the upper left, it would go for the 3 or 4, knowing that even though it won't get there first, it would still be more likely to get at least 1 or maybe 2 than if it went for the lone foodstuff well that basically encapsulated the majority of my hopes for the creatures. i realize that this type of behavior is very complex and would probably involve making the genetic code very very long and require hundreds or thousands or millions of generations to evolve.. but i don't care about that. i just want to know how to code some dna that could somehow operate on the 5x5 vision matrix to produce behavior relevant to the current vision state. just this moment i've had a slight idea.. that is probably trash. but maybe.. a vector for each of the 24 non-center squares in the 5x5 vision matrix.. weighted by what it is pointing to.. a foodstuff, an empty square, or an enemy, and by the contents of the few squares near what it's pointing to.. then summing all the vectors up to get a resultant direction.. maybe that's not such a trashy idea after all.. in fact maybe that's a perverse and gross and grossly oversimplified analogue to the way real brains make decisions.. i don't know.. if anyone has a better idea.. or has knowledge of this type of thing and can point me in the right direction, i would appreciate it. thanks. edit: now that i think about it.. my comment about what i figured is probably the hardest part for any GA was probably wrong. i bet it's the fitness function, but since that's so simple in this problem.. i'm just refering to what's the most difficult for this problem.

sharpnova

Sep 12, 2006 at 8:05 AM

I've given it more thought since the post and have developed that vector idea a little further.

The creature sums up all the 24 vectors. (actually i think i could do it with 5 since there are 5 independant vectors... the others are just symetric to those 5... so i could have 5 distinct vectors.. and use them repeatedly to get 24 vectors (all 24 of which could be distinct.. just the.. template.. the formula for the vectors would draw from 5.. aka.. adjacent diagonal, diagonal by 2, adjacent 2 away, and 2 away and up one)) it sums up all these 24 vectors to decide it's direction.

each of these vectors has a direction (simply the line connecting the creature to that square) and a magnitude which could be determined by having each vector weighted for the three possible values (empty, food, creature) but then i figured this wouldn't allow very complex behavior. so how about.. each vector is in turn weighted by sub-vectors specific to it... to all the squares once again.. and i could even take it to a tier 2, 3, etc.

does this seem like a good way to go about it? are there significantly better ways?

i intend on trying to introduce the concept of "remembering past vision states" later on.. but i'm not worried about that yte.

Asbestos

Sep 12, 2006 at 10:20 AM

This isn't so easy. You're trying to evolve a decision making process, one that has rules for "given this state, do this". The problem is that, with 5x5 vision, you have a huge number of possible states.

So you could go for a brute-force method if you wanted, and list every possible state in a look-up table, and then try to evolve the actions. Your dna string wouldn't need to include the state representations, as they will be in order, just the actions. Still, this string would be, what, 3^25 digits long, if every space represents food, creature and empty.

Also, you can try for some kind of chunking of data -- dividing the 5x5 area into four areas, forward, back, left and right. This wouldn't lead to behaviours as complex as above, since the information isn't as fine-grained, would would probably be several orders of magnitude easier to evolve.

I'm not certain I understand the vectors method you propose. I assume what you would be evolving would be the weights that the three categories of space should be? So a vector towards food would be weighted highly and a vector towards a creature might be negative? That could possibly work, but they wouldn't provide any decisions in balanced scenarios, if I understand right. What happens when all squares in the 5x5 area are empty? The creature would have an equal pull in all directions. What happens if the creature is situated exactly between two items of food?

There's quite possibly a good idea there, but you'll have to be sure to work it through.

Of course the standard way of doing this is to use a neural network. Evolutionary neural networks are very easy to create, and require no knowledge of backprop or anything. You simply have 24 input neurons, one for each square, x hidden neurons, say 5, and then perhaps four output neurons to represent a vector in each direction. The resulting direction is the sum of the vectors. The dna string is then all of the weights in order.

ANNs may sound hard when you first begin, but actually this is the most common way of solving this problem, as they are quite easy to program.

As for the fitness, that shouldn't be any problem. Any function that reflects the amount of food eaten will do that. You can either run each generation for a set period of time, and have fitness be directly proportional to the amount eaten. Alternatively you could have creatures die if they haven't eaten for x epochs, and then collect the survivors. Any method will produce a result.

kirkd

Sep 12, 2006 at 10:48 AM

I don't think I fully understand your "24 vectors" idea, so I'll hesitate to comment on that just yet.

One thought that I had was to introduce a true function that rated each square available to move into. For example, let's say your creature can only move in the 4 cardinal directions per tick - N, S, E, W. Each of these squares could be evaluated by a neural network and you move in the direction with the highest evaluated value.

The network's inputs could consist of the states of the 24 non-central squares. It sounds like each square can be empty, contain another creature, or contain food. Each square could easily be represented by a single input to the network with 3 possible values - -1=creature, 0=empty, 1=food. Then you'll have some hidden layer (or not), and the output. You could make it have 4 outputs, one for each cardinal direction, and take the direction with the highest value.

This is just one idea - you could come up with dozens of possibilities.

-Kirk

edit: Asbestos! You posted just before I did! Nice to see we converged on the same option. 8^)

Alrecenk

Sep 12, 2006 at 4:39 PM

If I were doing this I would create a system of weights from 3 input arrays to the 4 outputs. 24x2x4 = 192 variables per AI(maybe go short or byte on that one). Loop through the areas and add a 1 or 0 times each weight to determine how good it is to move in each direction.

for each space{up += (food on space * weight for food on that space)+(unit on space * weight for unit on that space)down+=...right+=...left+=...}

This is fairly similar to what a neural net does, but notice I used 2 arrays of weights instead of one. This should allow for more behaviors if other units are not interpretted as negative food. If they are then of course your AI will run away because it's doing the opposite of what it would do if there was food there, and if you already know what you want it to do then why would you be evolving it in the first place?

sharpnova

Sep 12, 2006 at 4:41 PM

yep I was considering neural networks.. i'll elaborate on my vectors method when I finish my long drive to houston.

and yeah.. already said i'd probably just use the amount of food they ate as a fitness, but like you said, anything proportional to that amount would work too.

actually just having a value for each of the 3^25 state configurations seems like a fun way (moving it down to 3x3 probably of course.. or lines of site like you said) and i might implement that. but I think I will try with these vectors or with a neural network first.

would I need four neural networks, one for each direction? or just one neural network with four outputs and take the largest output?

neural networks seem so primitive.. could a neural network really evolve to have the kind of complex behavior i described?

the way my vectors work is it weights each square with respect to it's environment, then weights the creature with respect to all those weights.. so really we have an analysis of all the spatial relationships of everything.. that could evolve some complexity..

kirkd

Sep 12, 2006 at 5:29 PM

A neural network would definitely be able to capture what you want. The beauty of a neural network is that it would be able to capture more complex behaviors as well. The solution described by Alrecenk is a simple summation of weights times states. This is equivalent to a neural network with no hidden layers, and I would bet that most likely its behavior would be to move toward the largest concentration of food with the lowest concentration of creatures. More or less downhill. The neural network, however, would potentially be able to capture more complex behaviors. Suppose you make the system a little more complex and put in some predators that eat the creatures you're evolving. The creature will then have to balance feeding and avoiding being eaten. Another similar example would be PacMan - he has to eat the dots, avoid being eaten by a ghost, eat the power pellets, and eat ghosts when their blue. A rather complex set of actions.

-Kirk

Asbestos

Sep 13, 2006 at 8:43 AM

Quote:
Original post by sharpnova
would I need four neural networks, one for each direction? or just one neural network with four outputs and take the largest output?

Absolutely not -- just one network with some number of outputs.

Then there are any number of ways that you can go from outputs to direction. You can take the largest of the four directions and head towards there, if you want, although this movement might look rather static, like they were moving around city blocks. Personally, I prefer the idea of looking at the output values as the length of the individual vectors, and summing them to get the final direction. This way each output gets a "vote" as to the overall direction: If one neuron really wants to head to the East, because food is over there, and one neuron really wants to head North, because there is another creature to the South, the creature will head North-East. Note that with this method you could even have just three neurons, each being a vector 120 degrees from the other. Or you could even have two neurons, if you allow them negative values.

fup

Sep 13, 2006 at 3:57 PM

Quote:
Original post by kirkd
Another similar example would be PacMan - he has to eat the dots, avoid being eaten by a ghost, eat the power pellets, and eat ghosts when their blue. A rather complex set of actions.

-Kirk

:o)

kirkd

Sep 13, 2006 at 7:35 PM

Hey! Quit skulking around, fup!! 8^)

BTW, PacMan lives. I have it running currently with the animation working and only need to link up the controls. Once I have that done, I'll start putting NEAT to work. I PROMISE!! My goal is the end of the year (preferably the next month or two - we'll see how much time I have). You still have exclusive license.

Sorry for the aside...

-Kirk

WeirdoFu

Sep 14, 2006 at 9:16 PM

Actually, it doesn't even have to be a very complex mapping. Here's a simple method.

Instead of thinking binary coded GAs, if you think real coded GA, then it would be more feasible. There are a few ways to approach this once it's real coded. The most straight forward way would be to encode probability values for the 4 directions it can move in. So, you might have N:35%, S:15%, E:45%, and W:5%. That's the simplistic way. Then you expand on that. Since you have a 5x5 grid of visibility, you can then create 4 slightly overlapping sectors that represent each direction. Based on the number of food and other animals in the sector, you multiple those two values by weights. To determine the probability of going in a direction, you simply add the weights and divide the weight of a sector by the total. So, for example, if there's nothing in any given sector, you start out with a base weight of 100. Now if we see that there's 1 food in the N, and the weight for food in the north is 2, then the weight for going north become 102. If there's a food in the south and another animal, and the weight for food and animal are 3 and -5, then the weight for the south becomes 98. So, there will be a total of 8 weights to evolve for the GA, a set of 2 for each direction. Then its just how you want to cap these values to create interesting behavior.

Just a quick idea.

haemonculus

Sep 16, 2006 at 9:57 AM

I would do a NN with the input neurons as the visibility grid (5x5 or even more). but you should have 1 input for 1 characteristic meaning 1 input for (food there/not there) and 1 for (other creature there/not there). perhaps adding predaters is simply adding another input neuron (per grid field). you could add some static obstacles too...
so you'll have 5x5x2 input neurons (in case of predators added 5x5x3). then you can choose a number of hidden layer neurons which are connected to the every input neuron. and then you have the 4 output neurons which are connected to every hidden layer neuron.
that's your basic NN setup. with the GA you would use the weights on every neuron2neuron connection as the genetic information. you could encode to binary or even let the GA operate on floats (yeah thats possible ;) ).

when you're calculating which instances of creatures(/genetic information) you should use for the next generations, you let the creatures handle with their individual genetic information filled in the NN that's driving their behaviour. simply counting how much food was eaten by each creature after N cycles and then sort by that amount and you get the X first creatures (and their information) for mutation etc...

and if you like somewhat more realistic behaviour, I would add a sort of timestamps to your NN. meaning you could add some input neurons that show the last N states, the creature was in or what the creature did the last time (moved in x direction/didn't move)

let's assume you have a visibility field of 5x5, on the grid tiles there can be (nothing, another creature, food, predator, wall) you would need 4 neurons per field (for example 0100 -> creature; 0000 -> nothing; i think you get the idea), making 5x5x4 input neurons. adding 4 neurons for the last action (nothing(0000), moved north(1000), south(0100),..) you'll have 5x5x4+4=104 neurons in the input layer. then choosing a number for your hidden layer neurons, say 10 (I don't have an idea what number is good, you have to try ;) ). making 104*10 connections from input to hidden layer, plus 10*4 connections from hidden layer to output. you have 1080 connections (floats!) to store in your genetic information per each creature. thats an incredible amount but I think these creatures will behave very good after enough epochs of GA.

ok perhaps this is all overkill *g* but you get the idea... simply choose the characteristics you need and play a little bit, till you get "intelligent" results

sharpnova

Sep 17, 2006 at 12:38 AM

quick question.

why isn't it just 5x5 inputs? if i'm using floats couldn't the input just be 0 for nothing, 1 for creature 2 for food, 3 for wall, etc.?

actually i already realized the answer to that while typing this... i was going ot have one input per square and use 0 for nothing 1 for creature etc. then in the connection, the weight was going to depend on whether it was 0,1,2,3... in other words.. same amount of overhead as just using 4 input neurons..

and yes i was planning on having predators, walls, (i am going to have the predators evolving as well) and the previous states, i think i mentioned alrady in this thread. i'm going to have all the input neurons necessary to input all the information for the past states (but not past actions.. i'm going to disregard those.. as i think forward planning is behavior.. but basing it on past actions is pointless since a new situation may have a new optimal behavioral response)

i'll be working on this for awhile :p

IMPORTANT QUESTION:

i've read evolution is far slower than back propogation.. but since i have no idea what my target output or target behavior is here.. there is no way for error calculations.. or back propogation.. am i correct in this or not understanding back propogation?

kirkd

Sep 17, 2006 at 8:41 AM

The main reason not to have a single input neuron with 0,1,2,3 for empty, food, wall, creature is that in this situation the various states of a cell have a relative weight with respect to each other. I originally suggested -1,0,1 for creature, empty, and food based on the idea that a creature being present is a bad thing, empty is arbitrary, and food is a good thing. This relative weighting makes sense in this context, but when you add in walls, it doesn't work very well. The neural net will have an extremely hard time trying to decide how to assign weights and may never converge.

The idea propsed by haemonculus sounds like a good one, however, you will end up with a huge number of weights that need to be adjusted and this will take a very long time. The best idea is to simplify the inputs as much as possible without losing information.

You're right about backpropagation. You have to know what your target output is to be able to use it. In this case, all you know is good or bad results. This is an example of reinforcement learning.

-Kirk

Asbestos

Sep 18, 2006 at 8:20 AM

Quote:
Original post by sharpnova
i've read evolution is far slower than back propogation.. but since i have no idea what my target output or target behavior is here.. there is no way for error calculations.. or back propogation.. am i correct in this or not understanding back propogation?

That's right -- this is the exact situation where you should be evolving. If there's no way of creating stimulus-response pairs, you can't really use backprop.

Of course, that's not quite true, as people have tried to find some ways of doing this. You can take a look at a thread I started, http://www.gamedev.net/community/forums/topic.asp?topic_id=411372 which, while it doesn't contain any concrete answers, at least has some good ideas for search terms to do some research on this.

However, that's for a slightly different situation. This is classic A-Life, and thus using a GA is apropriate.

sharpnova

Sep 18, 2006 at 9:07 AM

Quote:
Original post by kirkd
The main reason not to have a single input neuron with 0,1,2,3 for empty, food, wall, creature is that in this situation the various states of a cell have a relative weight with respect to each other.

which is solved by having a different weight for each possible state.. or 4 neurons.

main reason i like 4 neurons is so i can stick to bit operations.. which are probably way faster than floats.

kirkd

Sep 18, 2006 at 10:28 AM

Quote:
Original post by sharpnova
Quote:
Original post by kirkd
The main reason not to have a single input neuron with 0,1,2,3 for empty, food, wall, creature is that in this situation the various states of a cell have a relative weight with respect to each other.

which is solved by having a different weight for each possible state.. or 4 neurons.

Yes, that was my point. The only down side is the very large number of weights that this method leads to.

Quote:

main reason i like 4 neurons is so i can stick to bit operations.. which are probably way faster than floats.

I'm not sure I'm clear on this one. Even if you have bits as your inputs, you're weights are FP adjustable parameters.

-kirk

sharpnova

Sep 18, 2006 at 10:57 AM

well i just meant for the very bottom level, the inputs. or should i just use floats for everything?

Alrecenk

Sep 18, 2006 at 11:12 AM

Bits will save memory if that's an issue, but if they are being multiplied by floats than they will probably be changed to floats and then multiplied and that isn't any faster. If you were to do something like: if(input[a].out())node+=weight[a] ;
it might be a little faster than:
node+=input[a].out()*wieght[a] ;
However, I'd still suggest using all floats so the code is more portable. I have a set of neural net and other AI classes I use for lots of things. So if I were doing this I would use all floats just because I already have the code written. My point is: if you plan on doing much with neural nets it's a good idea to make code that is general purpose.

sharpnova

Sep 18, 2006 at 11:31 PM

if(input[a].out())node+=weight[a] ;

i am doing it exactly like this. but i think you convinced me with your portability argument. it will be a lot easier to add N amount of layers when everything is handled in a standard manner.

thanks.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.