quote: Original post by kirkd
Gotcha. I agree that the standard GA doesn''t perform well without crossover. Not too surprising considering the theory of schema as the foundation.

In another note (sorry to change the direction of the thread but my curiosity is getting the best of me), biological principles have shown that gene duplication, genome expansion/contraction, and chromosomal rearrangement are the cornerstones of adaptation. Have you seen much application of these to modern Evolutionary Computation? Timkin, any thoughts there?

-Kirk

Personally I haven''t done much in Evolutionary Computation in the last 5 years and I''m definitely not a biologist, so I cannot offer much help on whether advanced genetic operators are being used effectively in EC.

I can wade into the crossover discussion though, as I''ve done a fair bit of detailed analysis on it. Unfortunately, a lot of people in the field ''bag'' crossover as an operator through a poor understanding of what it is doing, but moreso through a poor understanding of its side-effects. What a lot of people don''t understand is that cross-over actually supports selection and the propogation of fit schema, particularly in small populations and in populations close to convergence. Unfortunately, in doing so, it also slows the search rate. This is the fundamental paradox of canonical GAs and why many people don''t like them.

Generally speaking though, the use of crossover depends on the problem domain. Take the ANN learning domain that fup works on and consider the chromosomes of two fit ANNs on the domain task. Will crossover necessarily produce a fit offspring? Not likely, unless the encoding scheme is chosen very carefully. Even then I have serious doubts that crossover is going to be beneficial in the short term, if at all (I''m sure fup can give us some more insight as to how he was solved this problem).

On the other hand, crossover is the main driving force for the search. Removing it (and relying solely on mutation) removes the ability to take large steps through the state space of the search domain.

That''s probably enough out of me for now!

Cheers,

Timkin

quote: Generally speaking though, the use of crossover depends on the problem domain. Take the ANN learning domain that fup works on and consider the chromosomes of two fit ANNs on the domain task. Will crossover necessarily produce a fit offspring? Not likely, unless the encoding scheme is chosen very carefully. Even then I have serious doubts that crossover is going to be beneficial in the short term, if at all (I''m sure fup can give us some more insight as to how he was solved this problem).

If I''m just evolving the weights then I only crossover at neuron bounderies. This does not dispose of all the problems but it does seem to be effective to a degree.

If I''m evolving the whole network - topology, weights, activations etc then I use Ken Stanley''s idea of historical gene markers. Each time a new ''innovation'' is created (like adding a link or a node say) that gene is tagged with a number. Each chromosome that contains that gene is tagged similarly. When crossover occurs the genes are lined up and only sections with a similar history are exchanged (multipoint)

Hope that helps

quote: Original post by fup
If I''m just evolving the weights then I only crossover at neuron bounderies. This does not dispose of all the problems but it does seem to be effective to a degree.

This would appear, at least after a short consideration, to be not much better than search based on mutation alone since the only factors dictating which values are considered are the initial values of the population and the mutations created within neuron boundaries. Is this how you see it?

quote: Original post by fup
Each time a new ''innovation'' is created (like adding a link or a node say) that gene is tagged with a number. Each chromosome that contains that gene is tagged similarly.

Could you elaborate on this please. The idea sounds interesting (and not one I recall being familiar with) and I have a different application for it (Using GAs to learn something else that displays the same problems as learning ANNs).

A reference would be great as well... although I should be able to find it myself if you cannot recall one off-hand.

Thanks,

Timkin

The first treats neurons as individual units and retains their functionality. It''s fairly common practice to use this approach even though it doesn''t address the competing conventions problem. It''s not brilliant but it does offer an improvement over just mutation.

You can find more details about the second if you look for the paper: Evolving Neural Networks through Augmenting Topologies by
Kenneth O. Stanley and Risto Miikkulainen. I''m not sure how applicable it will be to other problems though. What are you trying to do?

quote: Original post by fup
The first treats neurons as individual units and retains their functionality. It''s not brilliant but it does offer an improvement over just mutation.

I still don''t see how, since crossover can no longer disrupt a neuron the only other operator for searching the neuron state space is mutation and hence the search depends heavily on how prevalent this operator is and what the initial values of the neurons were. If I''m missing something here, could you please enlighten me.

quote: Original post by fup
I''m not sure how applicable it will be to other problems though. What are you trying to do?

Classifier Systems are a form of Hebbian network and employ a GA to evolve chromosome-encoded rules that define the agent function. In the traditional classifier model rules can chain together, causing each other to fire, thus creating a non-monotonic response function. However, applying a GA to evolving a population of condition-response rules can have the affect of breaking chains that have developed within the population.

I developed a classifier model for a predator-prey problem quite a few years ago and it worked well with just mutation in the GA. Crossover tended to do more harm than good. The method you described above sounded interesting enough to give it a try on my classifier since classifiers and ANNs are very similar; except that classifiers have an obvious internal semantics where ANNs don''t! A trained ANN though is computationally cheaper given the same problem.

Of course, the big thing about classifier systems though is that you can use them to evolve finite state machines... much the same way you (fup) are applying GAs and ANNs to that task!

Cheers,

Timkin

1. Not quite sure what''s confusing you here. The weights within neurons are dependent on the mutation operator. The neuron ordering is affected by the crossover operator. If you have two genomes that represent hidden layers as ABC and XYZ and crossover at the boundaries of the middle neuron then you get AYC and XBZ. These two offspring have completely different functionality. I can probably dig up some references from amongst the pile of papers I have if you want. (do you know a way of searching a load of PDF/PS formatted papers btw? That would be incredibly useful for times like these don''t you think..? I must have hundreds of them)

2. Ah, classifier sytems.. that''s the Holland bucket brigade thingumajig yes? I''ve been meaning to check those out for months but haven''t had the time. I gave them a quick once over a while ago and they sounded interesting (if a bit wieldy). I don''t have any experience working with them though so unfortunately I can''t help you out with this one. I''d like to see what you did with them though.

quote: Original post by fup
1. Not quite sure what's confusing you here.

Hehe... no, I'm not confused. I understand exactly what it is your doing... and you've confirmed what I was thinking... that

quote: The weights within neurons are dependent on the mutation operator.

quote: Original post by fup
2. Ah, classifier sytems.. that's the Holland bucket brigade thingumajig yes?

Yep: Holland's attempt to solve the credit assignment problem!

quote: Original post by fup
I gave them a quick once over a while ago and they sounded interesting (if a bit wieldy).

They are... interesting and wieldy... that is! They're nice in that it's very easy to pull them apart after a number of generations and see exactly what behaviours they have learned. Not something you can do with an ANN. I'm currently looking at game applications for them... in particular for evolving FSMs and for Coupled FSM systems.

quote: Original post by fup
I'd like to see what you did with them though.

Okay. I've found two old mpg movies of my predator in action. It's pretty terse stuff... I did this back in the days before I could program in C... so graphics was pretty basic stuff! The predator is the empty circle, the prey is the black dot. The prey is dumb and just runs in straight lines, bouncing off walls. The predator starts with absolutely no information about how to catch the prey and has to try different actions in the world. Payoff reinforces rules that work and taxation makes all rules have to work hard for survival. Here are the two mpegs... down load them and tell me what you think.

The difference between my system and many other classifiers is that I actually got the bucket brigade to work properly!!!

Cheers,

Timkin

[edited by - Timkin on June 26, 2002 7:27:55 AM]

That''s pretty nice behavior. It almost looks like the preditor is sort of ''taunting''the prey at times rather than just closing the distance each timestep as per basic pursuit. It''ll be interesting to see what game applications you come up with.

quote: Original post by fup
That''s pretty nice behavior.

Thanks! It got me 100% for a subject I did during my honours year!

quote: Original post by fup
It almost looks like the preditor is sort of ''taunting''the prey at times rather than just closing the distance each timestep as per basic pursuit.

I think that''s just a visual side effect of not knowing exactly what to do at that point in time... but of course, if it looks good, that''s just as important!!!

quote: Original post by fup
It''ll be interesting to see what game applications you come up with.

I need to find some time to implement a few of my ideas... which wont happen for a few months yet unfortunately... I need to re-write the old code (which I''ve started doing) and then create a few environments for testing. I''ll keep you and the forum informed of what I come up with.

Cheers,

Timkin