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

This is basically the concept of ''niching'' in genetic programming.

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

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

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.

Hey, Thanks for the help!

I''ll be checking those places out!

Dwiel

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

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

Niching methods are particularly suited for tasks for which multiple unique solutions may exist, such as multimodal problems, classification tasks, multiobjective opimization, etc. Here''s an excellent reference. Long and very academic, but perhaps one of the best overall references I''ve seen.

-Kirk

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.