Archived

This topic is now archived and is closed to further replies.

Species system in GP

This topic is 5147 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I have learning a lot about GP recently and am working on a implementation of it as I speak... I had an idea that I thought I would run by some people here. My idea is to seperate the population into many groups, say species. They would all be randomly generated at first, but then subclassified into species afterwards. By doing this, there would be a much greater chance for programs of similar structure would mix with each other. Along those line, each species would have a set of functions which could be accessed by all of the members of the species. each of these functions would have a chance to mutate each generation. These functions would not only be able to mutate and evolove, they would be allowed to have multipule, slightly varied copies of the same function in each species. There could be 3 functions called funct1, 3 called funct2 and 4 called funct3... then each generation, the functions which were used by programs with the highest fitness would be copied and mutated, replacing the worst. Now adding complexity to GP is not a good thing if you are only doing it to make it more complex. The idea behind the species, is to keep programms with similar structure together. As soon as I have a chance, I will test to see if my hypothosis that programs with more similar structure will result in a less common destructive mutation operator; programms that are more alike will tend to mix into programs that are useful. It makes no sence to try to mix 2 completely different species of animals, and expect a constructive mutation to result. Why should we expect two ''species'' of programs to mix and result in constructive mutation? The idea behind the functions common to the species, is that becaue these functions will be used by most of the species, only species with useful code in these functions will survive. There will be a large advantages to species that contain useful code in these functions. I also have some ideas about how to evolve species into entirely new species, but I havn''t thought it out to much yet so I should probobly wait. Basically, I am just wondering what you guys think about these ideas? Have they been done before? Have they sucseeded? Do you personally think they will work? What do you see that is wrong with my thinking? comments/questions... Thank you! Dwiel

Share this post


Link to post
Share on other sites
Is there any good place I can read about these things? I would like to read a lot of other people''s ideas so that I can learn from their work instead of trying to develop it on my own. I would rather spend my time thinking about things that are new... or atleast, think about which ideas I should implement, as there is definately no set of rules or algorithms that WILL work. It all depneds on the problem.

I have been doing some looking at citseer and also the university in my town has some of the lectures given at that conference... foret the name... something dealing solely with either GA/GP or both... I think just GP... Are there any other places I can find this kind of specific results of people''s work? It seems that to descover some of these algorithms, I have to know about them first... which is kind of circulatory...

Anyway, thanks timkin for the help

Dwiel

Share this post


Link to post
Share on other sites
Off the top of my head I cannot provide specific authors, although there are many... and so a google search that incorporates such terms as ''niching'', ''genetic programming'', ''genetic algorithms'', ''evolutionary strategies'', ''population evolution strategies'', etc, should turn up many results. Indeed, just trying a combination of the first two terms (niching genetic programming) returns several possibly interesting hits.

Other than that, talk to Mike Ducker (MikeD on gamedev). He''s had a fair bit of experience with this sort of thing and could probably provide you with some specific references.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
It sounds to me that ''niching'' would just be a technique used to increase the selection intensity of your GA at the cost of exploration. This is not necessarily a bad thing, so long as you understand the consequences. It will cause your GA to converge quicker, but the risks of getting stuck in local optimums also increases. Without doing too much research in this area, I would be inclined to say that there are easier/less complex ways to increase the selection intensity without having to add the complexity of niching.

Share this post


Link to post
Share on other sites
didn''t see optikal''s post until after the previous post....

I think that niching will do exactly as you say, unless, there are plenty of niches... or groups of organisms. Also, you could make it so that breeding between niches increases in probability as the increase of fitness goes down...

Do you think that these would help?

Thanks for the response!

Dwiel

Share this post


Link to post
Share on other sites
It sounds to me that ''niching'' would just be a technique used to increase the selection intensity of your GA at the cost of exploration. This is not necessarily a bad thing, so long as you understand the consequences. It will cause your GA to converge quicker, but the risks of getting stuck in local optimums also increases. Without doing too much research in this area, I would be inclined to say that there are easier/less complex ways to increase the selection intensity without having to add the complexity of niching.

Speciation will not cause a population to converge quicker or increase the risk of it getting stuck in local minima/maxima. In fact it will do the complete opposite. That''s the whole point. Speciation helps to protect innovation in the genomes.

A good paper to read is Ken Stanley''s NEAT (Neuro Evolution of Augmenting Topologies) paper, which you can find online. That paper also contains many useful references to other work.





My Website: ai-junkie.com | My Book: AI Techniques for Game Programming

Share this post


Link to post
Share on other sites
quote:
Original post by fup
It sounds to me that ''niching'' would just be a technique used to increase the selection intensity of your GA at the cost of exploration. This is not necessarily a bad thing, so long as you understand the consequences. It will cause your GA to converge quicker, but the risks of getting stuck in local optimums also increases. Without doing too much research in this area, I would be inclined to say that there are easier/less complex ways to increase the selection intensity without having to add the complexity of niching.

Speciation will not cause a population to converge quicker or increase the risk of it getting stuck in local minima/maxima. In fact it will do the complete opposite. That''s the whole point. Speciation helps to protect innovation in the genomes.



The reasoning behind my comment was that niching imposes restrictions on which individuals can reproduce with each other. It would seem to me, that removing these restrictions would increase the exploration of the GA (regardless of how well thought out those restrictions are). It will essentially provide an influence over which way the solutions evolve, whereas without these restrictions the way they evolve would be pretty random which would be more exploratory. Please explain further if I have misunderstood, I am interested in this stuff.

Share this post


Link to post
Share on other sites
quote:
Original post by Optikal
quote:
Original post by fup
It sounds to me that ''niching'' would just be a technique used to increase the selection intensity of your GA at the cost of exploration. This is not necessarily a bad thing, so long as you understand the consequences. It will cause your GA to converge quicker, but the risks of getting stuck in local optimums also increases. Without doing too much research in this area, I would be inclined to say that there are easier/less complex ways to increase the selection intensity without having to add the complexity of niching.

Speciation will not cause a population to converge quicker or increase the risk of it getting stuck in local minima/maxima. In fact it will do the complete opposite. That''s the whole point. Speciation helps to protect innovation in the genomes.



The reasoning behind my comment was that niching imposes restrictions on which individuals can reproduce with each other. It would seem to me, that removing these restrictions would increase the exploration of the GA (regardless of how well thought out those restrictions are). It will essentially provide an influence over which way the solutions evolve, whereas without these restrictions the way they evolve would be pretty random which would be more exploratory. Please explain further if I have misunderstood, I am interested in this stuff.


actually, now that you explain it that way... or now that I am awake enough to understand... what you are saying makes very much sence... It seems like having a single population will have a tendancy to find local minimum... due to the fact that they all end up being intermixed... it makes it hard for multipule places in the search space to develop. I am not sure what the effect of this would be, but it seems that maybe I should gather some data say, classifing programms into catagories that would have otherwise been a niche, and see if there is a correlation between closeness of structure, and improvement of the children.

Does this make any sence? If we have multipule populations, we have a smaller chance that the GP will find a relative min/max... If one solution ''gets stuck'', the others can continue improving... I do see your point though...

Good stuff...

Dwiel

Share this post


Link to post
Share on other sites
When using speciation, a population of genomes is divided into species each generation. When a new innovation occurs (through mutation or recombination) that is far enough apart from any existing species a new species is created.

Typically, a species is killed when either its size decreases to zero or its fitness hasn’t increased within a user defined number of generations. This means the individuals that would normally have died out early in the evolution of a population remain active for much longer, protected amongst their species members. (Note, because of the protection afforded by using speciation you can experiment with much higher mutation rates than normal.)


My Website: ai-junkie.com | My Book: AI Techniques for Game Programming

Share this post


Link to post
Share on other sites