Quote:Original post by Timkin
Crossover makes no such promises and is therefore not constrained to producing only hill climbing search of the objective space.

This is simply un-true. The change you are making to the alogorithm is essentially 'random', and you do not know what the outcome will be before hand. The population is either moving towards the solution, or it's not... Just because the sequence of data happened to exist somewhere else within the population is of little consequence.

Quote:
As with most search algorithms, premature convergence is a problem. The assumption that a single run of a search algorithm will give you a globally optimal solution for an objective function with unknown topology is naive.

I dont recall seeing anyone say it wasn't.

Quote:
The point of GAs is that one can 'balance' the application of the canonical operators to minimise the likelihood of premature convergence, so that when the population becomes flooded with (near-) identical solutions, they are all within tight bounds of the optimal solution.

It doesn't take much to flood a population. I guess this is the crux of what I'm saying. As soon as the odds swing in one particular direction then they are likely to stay that way.

Quote:
No one is suggesting structural crossover. Think of crossover from its genetic counterpoint.

Since you bring it up.. Crossover in the real world is nothing like the cross-over being attempted here. Real cross-over is very specific as to what gets crossed, by whom, and where it happens. Cross-over is an evolved operation, not something that happens willy-nilly. Willy-nilly is how GA/EP applies it. And that is why I question it's place as a problem solving tool.

Quote:
No search algorithm (other than brute force) can unequivocally know this, unless you know the objective function topology... and in which case, why did you need to search in the first place?

I agree with that statement.

Quote:
So pulling _identical_ pieces during cross-over is not crossover.
I ask because this is exactly the case in a mature population. Members will be 99.9999% identical. I hate to use biology as an example, but, look at people.

Quote:
This is the cloning that I was talking about. Crossover produces clones in nearly-converged populations. Unfortunately, it also produces clones in initial populations. Clones do not harm the population, only the convergence speed of the algorithm. They are a wasted opportunity.

Why wasted? Why can't pure duplication be just as advantageous? As you mentioned earlier we cannot know the outcome until we try it.



OWL:

Quote:Original post by Owl
Teh wat? I take "sexual reproduction" as the combination of chromosomes from two individuals to form a third.

So far I know, most in/vertebrates/insects (even plants) reproduce themselves that way.

What do you mean by saying "is very rare in biology" ??

Yes, it is very rare. Of all of the cells in your body, Owl, none of them reproduce sexually. YOU do not reproduce yourself sexually. You may faciliate sexual reproduction, but never do it yourself. Think how RARE it is for the sexual process to occure, compared to the number of times asexual reproduction occures. How many times did you asexually create new sperm before sexually reproducing?

I know it's nice to think of yourself as ONE, but, you are a vast collection of single celled organisms. We are giant robotic biospheres.

Even if you don't buy that, there are _WAY_ more species that reproduce asexually than there are ones that reproduce sexually. Don't forget that we're really really big-- we cannot see th

So, yeah, it's quite rare.

I have to ask this: what are we tring to do? Simulate humans, or simulate DNA?

Quote:Original post by RPGeezus
Even if you don't buy that, there are _WAY_ more species that reproduce asexually than there are ones that reproduce sexually.
So, yeah, it's quite rare.

When you say species I guess you're including simple organisms (as sperm, virus, bacteria). If not, then I got to disagree. I belive most (complex) animal life (which is what most people refer to when saying "species") reproduce sexually (crossing over DNA).

Quote:Original post by RPGeezus
I have to ask this: what are we tring to do? Simulate humans, or simulate DNA?

These people are trying to immitate the reproduction of complex organisms with the hope of generating complex algorithms to solve problems, based on the premise that if nature can solve problems that way, it should be possible to replicate it computationally.

I belive the problem with GA is the "random" element, which I don't think it really occurs in nature.

OP: you're right about the water bit. :) I still hold that most life forms are asexual. Complex lifeforms are a different matter....

Quote:
The cool thing about crossover is that you can select the good attributes from an already successful member. The data didn't "happen to exist" (except for the first generation), it has been slowly changing and storing up the good genes while filtering out the bad ones.

You can chose only the good sequences in their entirety, sure. Anything is possible. But you likely wont.

The term 'gene' is deceptive as it implies discreet blocks of self-contained function. It says nothing about 'gene' dependancy, etc... I think in the case of an algorithm, code, or lego structure, we do not have knowledge of dependancy. If we did then we would probably have designed it in to the operators being used.

i.e.

j = 1k = 10for i = j to k   a = a + 1;   b = b * 2   if a > 5      c = b / a;next j

How would you know which parts of the above code are required to keep the others working?

DNA isn't random, and neither is biological cross-over. Both are complex structures.

Maybe Kylotan has an answer. :)

Quote:Original post by Timkin
I think you're missing the point of what I'm saying. Of course the outcome of mutation and crossover are both random, because they are stochastic operators, however they are both selected from a countably finite set of possibilities.
The possibile outcomes of mutation are found within a small hypershpere of the
state space, centered on the current chromosome.

I agree with you.

Quote:Original post by Timkin
The radius of this sphere is a function of the encoding scheme. Mutation can only generate local perturbations to the solution hypothesis represent by the chromosome. The outcomes of crossover are not so constrained, since solutions will lie within a hypersphere that encompasses both parents.

Two things:
There is no law that states that the actual solution space will encompass the area between both points. It may be that each solution is so drastically different, or sufficiently complex, that combining the two can only result in no solution. I realize this is an extreme, but saying that the combination of the two covers such a broad area is also extreme. I am not arguing that it is possible, because I believe it is, rather that it's the exception and not the rule.

That said, you don't have to restrict mutation to only one change per run. This way you have method by which the spheres radius is variable.

Quote:Original post by Timkin
If these parents are distant within the state space, then the set of possible offspring spans more of the objective function than those of mutation alone. The possibility of finding new optima of the objective function within this offspring set is far higher than for the outcome set of mutation.

It's hard to argue with words like 'possible'. :) While it is possible you will get a perfect solution, by chance, it's is unlikely. I also find it unlikely that taking a chunk of 'code' from one member and pasting it in to another is likeley to have much of an advantagous affect.

If I took half of kernerl32.dll and mixed it with half of netapi32.dll, I'd get a crashing computer. :)

Quote:Original post by Timkin

Quote:Just because the sequence of data happened to exist somewhere else within the population is of little consequence.

I'm not sure what you're trying to say here...could you explain it please.

If I get a=b from random mutation, or randomly extract it from the 'code' of another member is of little consequence. It got there randomly. a=b, via crossover, could just have easily been a=c from a different member, or a=d from mutation.

I think I'm repeating myself here, but, just because a pattern works well in one member, it is no gaurantee that the same pattern will work well in a different member. In most cases (sorry I cant be more specific) 'crossover' will have the highest chance of working when crossing two nearly identical members. If this is the case then it's really not much different than mutation. The spheres that you talk about start taking on a much different shape..

i.e. Mixing a human with a bananna gives us mush. Mixing a human with a human gives us (usually) a human, though slightly different from either parent.

Quote:Original post by Timkin

Quote:
It doesn't take much to flood a population. I guess this is the crux of what I'm saying. As soon as the odds swing in one particular direction then they are likely to stay that way.

To a certain extent that is true, however I can say (based on research analysis and experience) that this is very much problem and encoding dependent.

Can you think of a way where you could get the same (or similar) results using only mutation?

I have no problems with seeing early convergence (I kind of encourage it), and have no problem with a temporarily stagnant population. I have methods which keep things moving.

Quote:Original post by Timkin

Quote:Why wasted? Why can't pure duplication be just as advantageous? As you mentioned earlier we cannot know the outcome until we try it.

Clones are a waste of an algorithmic iteration. The solutions already existed in the population so producing the clone offspring did nothing to change the state of the population. Hence, that iteration of reproduction was a waste for the search of the state space.

I do not agree.

i.e.

Member A:   i++;i--;crossed with itself:i++;i++;

Something new made from something old.. Maybe +2 is better than +0, maybe not.

When you say 'solution' I get the impression that you feel each 'chunk' of data in a member is 'solution'. I dont feel that way. Each 'chunk' may be part of a solution, but on it's own may be (and likely is) nothing.

Quote:Original post by Kylotan
Quote:Cross-over is an evolved operation, not something that happens willy-nilly. Willy-nilly is how GA/EP applies it.

No it's not...

How do you enforce cross-over so that it always makes sense? I assume this must be very specific to a certain applications.

Quote:Original post by Kylotan
Because then you may as well just have a population size of 1. The principal value of genetic algorithms over other similar techniques is that the population shares information among itself. If you have no crossover, this information is not getting shared on any significant level. And if you have duplicate solutions, then there is no information to share anyway.

Without cross-over you can still have variety, and the shareing of information. Cloning with mutation ensures sharing.

I can have 50 members, each 1 or two operations away from each other. 99% identical. If I prefer 'new over old', and I get in to a flat spot, it is conceivable that I could have 50 members, all derived from the same ancestor, but 50 operations apart. By operation I mean a mutation (or cross-over). We can also increase the rate of mutation and modify the selection process if stagnation becomes a factor; this elminates the need to reset the system.

Quote:Original post by Kylotan
If both solutions are on the global maximum then any combination of their traits will be.

Maybe I misunderstand you.. Are you saying 'if two hands of poker are equally strong, any combination of the cards contained in those hands must be as strong'? I could have two flushes, but with different suits. Two full-houses with different cards, etc..

Tim, some of what you've been saying doesn't match up with some of what Kylotan has been saying. I understand neither of you agree about my final view with regards to crossover, but you seem to be disagreeing for exlusivley different reasons.

Will

This is a good discussion. :)

Quote:Original post by Kylotan
99% of GA applications will encode the solutions as homogeneous lists of values. Crossover will exchange values in one with the corresponding value in the other, which are appropriately constrained by definition

Quote:Original post by Timkin
In a good encoding scheme (for a GA) your attributes should be as orthogonal as possible. This has implications on how effectively you can search the objective function surface and how effective your operators are in the GA.

Would you both agree with this statement:
"The effectiveness of cross-over is directly related to how statistically unrelated the discreet components, that make up the solution, are."

or...

"The effectiveness of cross-over is directly related to how flexible the operators, that make up the solution, are with regards to order and placement within said solution".


Maybe this is an ideal to strive towards but is it realistic? Growing lego, or growing code, both unfortunately have the requirement of fitting in to the 'context' of the solution.

I agree with what you both have said (except for the 99% part Kylotan), and am forced to change my tune. 'Cross-over is not effective for many problems, but is effective in a very limited set of cases'.

You have each moved me closer to your way of thinking, but I'm not a convert just yet. ;)

Quote:Original post by Timkin

Quote:While it is possible you will get a perfect solution, by chance, it's is unlikely. I also find it unlikely that taking a chunk of 'code' from one member and pasting it in to another is likeley to have much of an advantagous affect.

And yet it does! ;)

And so does mutation. :D

Quote:Original post by Timkin

Quote:If I took half of kernerl32.dll and mixed it with half of netapi32.dll, I'd get a crashing computer. :)

Thats not a valid example. If I took 10 dlls each of the same code length and broke them up into n segments of code, then jumbled those segments to make m 'randomised' dlls, I could still recover my original 10 dlls using crossover alone. I could do it faster if I permitted selection and mutation as well.

I think it's a valid example: Two members of a population at opposite ends of an extreme; granted, you would try to prevent this from actually occuring.

Part of the requirement for Cross-over is diversity, yet diversity _can_ be the very thing that keeps it from working. The 'orthagonal' parts of the encoding scheme is just one way to restricting diversity.

If you don't like the word restrict, then we could say that 'the orthangonal encoding limits the area of solution space along an axis'. Do you agree with that statement?

Quote:Original post by Timkin

Quote:just because a pattern works well in one member, it is no gaurantee that the same pattern will work well in a different member.

True. But then that is what selection is for. Even in nature there is no guarantee that an offspring is fit for its environment. Selection pressure ensures that, on average, the strong survive. If no weaklings survived to produce offspring, then the population would loose its genetic diversity and would fail if the optimal solution were changed. In a GA, we don't typically change the optimal solution, so we can afford to be more brutal with regards to culling off weaklings via strong selection pressure.

I agree. I dont think there was ever a disagreement in this regard. Your last sentence speaks the truth. :D

Quote:Original post by Timkin

Quote:Can you think of a way where you could get the same (or similar) results using only mutation?

Indeed. Mutation rates are typically so low in a GA (about 5% of total genes) that it has been shown unequivocally that mutation alone cannot move you out of an optima once your population resides within it. Selection pressure will obliterate any favourable mutation before it can take hold in the population.

I wanted to know how you would achieve the same solution using mutation alone. Could you elaborate?

It seems you are suggesting that the system will get unavoidably stuck with just mutation, which is not true.

In the same way cross-over has 'hidden' requirements so that it will work, I suppose there are requirements for mutation as well. The implementation must provided ways in which stagnation and plateaus can be worked through (without a reset). Allowing mutations to be cumulative over generations is one such way, and having a dynamic fitness measurement is another. There are probably hundreds of methods that would work.

Of course, saying this does not make it impossible for cross-over to get stuck.

Quote:Original post by Kylotan
1 solution, cloned and mutated, just carries information from 1 previous solution plus some random value. Whereas 1 solution based on crossover carries information from 2 previous solutions.

I agree cross-over gives you information from two immediate parents. That fact has never come in to question. :)

I question the _utility_ of this. There are certain requirements that must be met for this to work properly, or even at all-- it would also seem (to me) that there is a relationship between the distance in solution space of the two parents, and the probablitity of a cross-over contributing to the solution. Mutation does not have this limitation.

If all of the operatives of the solution are 'orthagonal' then the soltuion space will be much more confined-- and so the distance between any two members 'laterally' will be smaller... Not all problems facilitate this.

There are definate constraints placed on cross-over... and therefore definate limitations. I'm saying mutation alone can achieve all of the same goals, with less contraints, in less cycles, and in more situations (is more flexible).

Quote:Original post by Timkin

Quote:
Something new made from something old.. Maybe +2 is better than +0, maybe not.

In a diploid coding scheme, you would never cross one chromosome with the other. GAs are not asexual.

Who said anything about diploid? :) What if your GA's are of variable size? Do you restrict cross-over only to members of the same length? What if length is a variable for my members? If my environment is complex enough I'm sure to have a few operands that require 'context'.

Quote:Original post by Kylotan
No, because 'the' global maximum implies the same position, which isn't actually possible with 1 set of playing cards. The situation you refer to [poker] would be two equally beneficial local maxima.

Kylotan, poker-hands are fine example. Uniform size, limited operands, many local minima, and easily defined global maximums.

Come now, if a problem only had ONE best solution you probably wouldn't be using something like GA's to find it...

Within a population there will be competition for who gets to represent the solution, and not just for the solution itself.. This is built in to evolution.

Quote:Original post by Timkin

Quote:Tim, some of what you've been saying doesn't match up with some of what Kylotan has been saying.

I didn't realise I was supposed to agree with Kylotan! ;)

Quote:Original post by Kylotan
My 2 paragraphs above are analogous to where Timkin said

Is seems that there are some areas where you both see things differently. You may agree on the same ideas in the end, but for different reasons.

I was hoping the two of you might fire a few words at each other-- my posts are getting rather long. ;)

Will