So I got it BASICALLY working...

It's a simulator. You can see small bugs on the screen, and a few scripted monster bugs eating the smaller ones. There's food and water lying around for the little bugs to eat. The bugs have a set number of actions they can perform, and only their behaviour in which situations to use them are evolved. They have the ability to move around, blink with different colors, bite, put scent traces and so forth. It doesn't take them very long to figure out it's a better idea to move around than to sit still. If you sit still the monsters catch you very soon and you die. After evolving for a while, they figure out it's a better idea to move away from the monsters rather than towards them. But there it stops. For them to evolve further there's some sort of gap to leap over. They don't even learn that it's a good idea to eat food. I'll explain why in a moment. I hope somebody here could give me pointers on how to break this barrier which my bugs are facing?? I want to get it to work, so even though I put a bunch of work into this I'm prepared to scrap my approach and go about it in another way.

Now that I got the main issue explained, let me get into details.

My approach is based on a huge finite state machine. Each bug is equipped with senses which can detect a couple of different states each. When all possible states of all available senses are multiplied, I get an finite state machine with a few ten-thousand different states. What action to do in that state is determined by mutation and Darwinian evolution. Now, they DO evolve, but they don't get very far. Very stupid smartness is all I get.

I'm quite sure the problem is as follows:

The simple state "food ahead" never occurs! (and similiar simple states) Instead, the state which DOES occurs when there's food ahead is more like "food ahead + enemy to the right + water to the left + I'm low on energy + I'm loaded with water" If the bug evolves the action "bite" for this state, it still won't always eat food. Next time it encounters a piece of food, all the circumstances are the same - except now there's no water to the left. Now that's a completely different state, and the bug doesn't have a clue what to do. It doesn't see any resemblance between the last situation and the new one. It's an easy step to learn that in ANY state it seems to be better to move than to sit still. Monsters are hunting and immobile bugs quickly become eaten by Charles Darwin. It doesn't really matter where you go, as long as you don't sit still. Thus, the whole thing begins with the bugs learning that it's better to move around. All the time. Now, after this it's quite hard for them to make progress. Simply because they can't recognice similiar states!

Some possible solutions:

I'm considering several ideas: - Place the ten-thousand possible states in a quad-tree structure, allowing the bugs to see similiarities in situations by looking along the tree. - When mutations occur, they don't just mutate the behaviour of one state at a time. Instead the mutations find tons of roughly similiar states and mutate them to the exact same behaviour. - Add a "scoring-system" to the genes. Where a bug performed something good, I'll reward the gene which did that by copying that gene into lots of similiar states. - Scrap everything and try to do it with neural nets instead.

Can anyone offer more possible solutions?

Thanks!

I have two ideas.

1. Increase the incentive for eating. It sounds as though there is no real reason to eat (as far as your 'bugs' are concerned).

i.e. Instead of having your creatures just die of stravation right away, have them move slower, and slower, and slower..... and then die. :)


2. Don't be afraid to manipulate the evolution of your bugs. During early generations (when your bugs are at their weakest), make sure that each bug is standing right beside some source of food. This way, bugs that have the 'eat' code will survive and those that dont may not.



I hope this helps.. My $0.02.

Will

I agree with RP, but I would add that the size of the FSM (you mentioned 10s of thousands of states) is going to slow your progress. If you make small mutations to such an FSM, you're very unlikely to see any results from that mutation. Conversely, if you make large mutations, you'll see random results that aren't conserved. Either way, you have a slow process.

Given what you've described, it sounds like you might be able to separate the various senses/actions into different FSMs. Perhaps a food seeking FSM, and a danger avoiding FSM that are independent. It would be akin to independent genes within their chromosomes.

Let us know the results regardless of how you solve the problem.

-Kirk

Thanks for the replies!

Kirk:
Yeah, sounds like it would evolve abit better. The sheer amount of available states really makes my evolving difficult, which I didn't realise when I planned it out.
I could seperate the senses so that only one or a few is active at any given time. Good idea.

RP
1. Very clever. Moving slower and slower. I'll use that!
2. Ah yes, I think in the end I'll have manipulated the evolution so much it's not really scientific anymore! =)
If evolution don't wanna come out and play then I'm gonna drag it out kicking and screaming, goddammit! ;D


edit: It doesn't feel like I have the golden solution yet (although a good start), so if anyone else can offer further ideas I'd appreciate it!

[Edited by - NQ on October 20, 2005 2:38:37 PM]

One thing you might want to do is change the way you train the bugs. First, put them in an environment with enemies and let them learn evasion. Then, put a new batch of bugs in an environment with only food and let them learn to eat. If you have even more states, maybe make an environement targetted at learning each related (in your opinion) subset of state->action pairs.

After you have some bugs trained in many specialized ways, you can make a 'real world' environment that combines everything, put all the best specialized bugs in there and let them 'breed' so maybe one bug can become generalized. You might even want to mix up the bugs every once in a while like move good eaters to the evasion environment so you get a different kind of crossover in the breeding.

It might be interesting to have several displays up, one for each environment. This way you could watch bugs learn to eat, evade, drink, etc and also see how they do overall.

Alternately, you might want to start with one state (learn to eat) and then move all those bugs to another 'learn to evade' environment so the bugs kind of go throuh a 'training course' in each subject before they are tested in the 'real world'. The thing about this method is that the order of the courses can be very important since they will probably tend to forget older courses in favor of new behaviors.

You could try to evolve rules instead of state->action mappings. Each rule could consist of the values of the state for which it applies and the action to perform. A rule might ignore any number of the senses. The rules could also be applied in a certain order, so the first rule to apply is the one that is used.

Ahh.. all of which are clever replies.
I'm getting good input, and lots to think about.
Thanks!

Doesn't this require a lot of memory per bug? Not a big deal these days, I suppose. Personally I would want to reduce those states so that they're not so detailed. I'd want 'food near' and 'monster near' rather than encoding directions, for example.

I would agree that the food needs to have some significant benefit - a bonus to survival over those that don't eat. Maybe well-fed creatures have a 50% chance of surviving a monster attack, for example. Or they move further. Or poorly fed creatures have a chance of dropping dead.

Another idea might be to have a generalisation step - pick a pair of states, if they're similar enough, copy the response for one into the other. Repeat for as many state pairs as you like.

Or you could somehow encode that by having wildcard states, so that similar states end up explicitly merging into one. That may be difficult to represent, however.

Or reduce the number of steps by abstracting away the detail: instead of 'enemy to the right' you could store 'enemy near' and the response could be 'move away from enemy', where the exact detail isn't resolved until the action is executed. Instead of up/down/left/right you'd store 'towards/away from/perpendicular left/perpendicular right', and that has allowed you to generalise to all 4 directions from one rule.

Yes, yes, you're quite right!!

And my bugs currently occupy 35k memory per individual. It's abit much when there's alot of them, but I'm thrilled about the size since my original (even stupider) design was about 300k per individual!
(needless to say, my poor computer coughs and sputters when I run the simulator)

I know it's still heavily overweight, and I'm aiming for something closer to 5k per individual.

Coincidentally, just a minute before I saw your post I thought about the exact same things! You gave me good input though!
First of all, I'm scetching away on a system which doesn't include directions. Secondly, I'm also going to seperate the entire sensory system into several 'modes'.

Basically I'm allowing the bug to 'focus' on certain things. While looking for water, it doesn't care much if there's food nearby, for instance.

Both of these should decrease the number of sensory states (perhaps even below 5k?) and make it easier for bugs to evolve something useful.

You seem to be approaching evolution from the perspective of the modern world. All of what you see around you would be like your program times 10000000000000000, running for 10000000000000000000000000000000000000000 years. (Okay, maybe I'm exagerating). Still, it is unreasonable for you to expect your own program to have anything in common with the world. It just wont.


Acting as a 'guide' for your programs doesn't detract from what you are doing. Evolution has come out to play, but it's not doing what you want. :) To make it do what you want you will need to encourage it. You didn't seem to have any problem adding cross-over, even though cross-over is something that took eons to evolve, and in reality is not a very common attribute when comparing to all of the biomass on the planet.


With regards to your state table sizes: smaller is better. I once 'evolved' a noise filter-- it took only three hours, to get a perfect solution, when I started it off with 20 states. When I had it cranked to 1000 states I didn't even reach 70% solved in 24 hours.

You can easily make the state table sizes 'evolvable'. In your mutation code allow insertion and deletion of states. To make it have consequence, have each state cost a food unit everytime the 'bug' moves. (like 0.001 units / meter).

Hope this helps, and please keep us posted. :)