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?

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

Not true.

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. Maybe having green eyes and red hair is very successful, but only when there are found together. Maybe it's also important to be tall and heavy, but being just heavy or just tall is a bad thing. Crossover allows you to take chunks of correlated good data and combine them with other chunks of correlated good data.

With crossover you can have an irish weakling and a blond haired brute combine and have a decent chance of producing an irish brute. Mutation would simply keep trying to mutate that irish weakling to become both stronger and heavier, but he's so far away from that solution that it's very unlikely he'll ever get there - especially if there's some sub-optimal weight/heigh combination he's already achieved.

Micro-mutation is good from making something good even better, but crossover is good at taking the best genes from different population pools and finding a third, more dominate member.

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.

Depends on the problem and the algorith you use - the equations I was working on for my graduate thesis would often form several dozen "population pools" that would quite happily sit there until it performed crossover with a member from another 'tribe'. I had to set the maximum mutation low since I wanted to get a very acurate answer, so I relied heavily on crossover and a large initial population to provide my genetic diversity.

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

You've either never implimented a GA or have worked on very different problems than I have. A clone may be advantageous to the *individual*, I suppose, but we're looking for an answer to a problem! You run every individual through some sort of fitness test ... running the same vector through the same test is kind of redundant, don't you think? I'd rather have a random guess than run the same number twice.

Yes, it is very rare. Of all of the cells in your body, Owl, none of them reproduce sexually.

Trick statement. ;) Kind of like saying water is rare compared to the vastness of space where there is no water. Silly. :)

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.

Quote: Original post by RPGeezus
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.

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. 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. 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.

Quote: The population is either moving towards the solution

The population (at least in a GA) is always moving toward a solution.

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.

Quote: I dont recall seeing anyone say it [ premature convergence ] wasn't.

No. But you made the comment about the fatality of adding too many copies of the same chromosome to a population, implying that we were arguing against this point. I was just making it clear that I wasn't.

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. Additionally, there are some very simply techniques that overcome this problem and while they don't prevent premature convergence, they do ensure that the algorithm is optimally efficient in getting there by avoiding cloning and hitchhiking, so you have plenty of time to restart with another random population and try again. On those problems where ensembles of solutions are needed to find the global optima, a GA will work at least as well as other methods I have tried (e.g., simulated annealing, simplex, random walk).

Quote:
Since you bring it up.. Crossover in the real world is nothing like the cross-over being attempted here.

No one ever suggested they were the same. Indeed, I thought I was making it clear that they're not the same. Perhaps I wasn't.

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.

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

Neither. GAs are a blind search algorithm, inspired by genetic operators. They make no claims that they simulate anything. Anyone suggesting otherwise is ill-informed.

Cheers,

Timkin

Quote: Original post by RPGeezus

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.

No, no, no... this is just a side-effect of the way you have implemented your candidate solutions. Don't confuse genetic/evolutionary programming, and in particular your implementation of it, with genetic algorithms, which is a more abstract concept. With a genetic algorithm, crossover is deliberately combining traits from two existing solutions. It's only random if your implementation of such does not enforce sensible constraints.

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...

Quote: And that is why I question it's place as a problem solving tool.

...and that is why we're questioning your questioning.

Quote: Why wasted? Why can't pure duplication be just as advantageous?

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.

Quote: Think how RARE it is for the sexual process to occure, compared to the number of times asexual reproduction occures.

Just so you know, this isn't necessarily relevant to the discussion of genetic algorithms as a search method. They were inspired by biological parallels but, as with neural networks, they are just an analogy and not a simulation. The search method is not so much about genetics and biology as it is about emulating the effects of natural selection.

Quote:

Quote: Original post by Kylotan
Imagine you have 2 solutions on the global maximum: crossover will give you another maximal solution

Do you mean 'Crossover _may_ give you another maximal solution'?

No, I mean will. The idea of crossover - in the typical context of GAs - is to exchange traits of the solutions. If both solutions are on the global maximum then any combination of their traits will be. By extension - and more relevant to the algorithm in general - given a continuous fitness function, the nearer both parent solutions are to the maximum, the nearer the child solution will be. It is guided where mutation is not. Yes, if you implement the solutions and crossover in such a way that there is little coherence before and after crossover, then it will be somewhat random and less effective. But that's down to the implementation, not the algorithm itself.

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

Good discussion guys... something to enjoy over morning coffee! 8)

Quote: Original post by RPGeezus
The term 'gene' is deceptive as it implies discreet blocks of self-contained function. It says nothing about 'gene' dependancy, etc...

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.

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

...and to reiterate, GA crossover is not biological crossover.

Quote:
There is no law that states that the actual solution space will encompass the area between both points.

Correct. This is why the success of any search algorithm rests on whether or not the optimal state lies within a region of the state space accessible via the operators of the algorithm, given the initial guess at the solution. Thus, for a GA, it is important to seed the initial population with a selection of solution guesses that span the state space, just as, when training an ANN, you need a test data set that spans the expected operational set. You're right in that GAs cannot generalise (extrapolate), but they don't need to if you use them as they were intended.

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! ;)

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.

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.

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.

Quote:

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

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.

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! ;)

Cheers,

Timkin

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

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: Without cross-over you can still have variety, and the shareing of information. Cloning with mutation ensures sharing.

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.

Quote:

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..

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 would be two equally beneficial local maxima.

What I am saying however, is that the 'hand of poker' or 'bytecode algorithm' representations have very interdependent values that do not lend themselves very well to crossover. Change one card or one byte and the value changes dramatically. This is not an inherent problem with crossover itself, as you seemed to have been suggesting. In fact, the examples given don't lend themselves amazingly well to mutation or any other similar search operator since the search space is close to being discontinuous. If a small change in state is likely to lead to a large change in fitness, then you're approaching a situation where a random or linear search is just as good, if not better, than a directed search.

If the representations were instead 'x, y, and z coordinates', or 'expenditure on science, luxuries, and warfare', or 'list of (doctor/patient/time) tuples', then the values are interchangable and always meaningful. This is more common with GAs, and implementing a meaningful crossover is trivial.

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

My 2 paragraphs above are analogous to where Timkin said 'In a good encoding scheme (for a GA) your attributes should be as orthogonal as possible.' In fact, I don't see any significant disagreements between what the two of us have said over the last few posts, except in the very different ways in which we describe it.

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

Quote: Original post by RPGeezus

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".

Yes to the first, maybe to the second. The quality of the operator goes hand in hand with the representation of the problem.

Quote: 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'.

I would suggest you read more on how GAs have been used, because 99% may not be the correct figure but the answer is certainly between 90% and 100%. This is simply because that is the representation that best lends itself to being solved in this way. If your problem looks like such a representation, you might use GAs. If it doesn't, you would probably use something else.

Quote: Part of the requirement for Cross-over is diversity, yet diversity _can_ be the very thing that keeps it from working.

Of course. Similarly, allowing mutation to have large effects can either be the situation that allows it to find a better solution which is remote in solution space, or the situation that keeps it looking too far afield instead of performing local optimisation. Both have their place and both work together. Neither can be optimal in all situations, and there are infinitely many examples where one could be optimal and the other not; see the 'No Free Lunch' theorem.

Quote: 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).

Basically, if the domain of changes that mutation can bring is smaller than the size of your local plateau, then you're stuck. You fix this by decreasing the selection pressure, allowing worse solutions to survive in the hope that eventually they will yield better ones. But then you converge more slowly due to having a worse population. Again, no free lunch. :)

Quote: 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.

Of course, there are requirements. That is the way search algorithms work - you determine the requirements and then pick an algorithm that fulfils them. For example, A* is an optimal search algorithm for finding a path between 2 places, providing your paths are of monotonically increasing cost. That's a limitation or requirement, as you put it. Breadth first search does not have this requirement, but it's not better - it just suits a different type of problem. The same applies to crossover and mutation.

But, there is not so much of a difference between crossover and mutation as you seem to be implying. Both require that, in general, solutions that are 'close' to each other have fitness values that are close to each other, in order to be effective.

Quote: 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.

Having the operands be orthogonal maximises the space rather than confines it. I'm not sure what you're trying to say here however. But the last point is valid; each problem requires a different solution. For some, crossover is not so good.

Quote: 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).

Mutation... can achieve all of the same goals? Yes.
... with less contraints? If defined that way, Yes.
... in less cycles? No.
... and in more situations (is more flexible)? Yes.

I say no to the 3rd because crossover - where applicable - makes better use of the information encoded in your population than mutation does. When you get 2 solutions which have evolved to be good, but in different ways, crossover provides the chance of yielding a solution that takes the best from both. Mutation does not do anything to explicitly facilitate that. It is like the difference between binary search and linear search.

Quote:

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.

They're a poor example of what you'd use a GA for, because of the heavily discontinuous search space and impractical representation. Crossover would give you some benefit over random search, but not much. The same goes for mutation here.

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

There's no reason why not. GAs don't care about how many best solutions there are, they care about the shape of the solution space.