Quote: Original post by Timkin
If you remove crossover from a GA, then you are left merely with random-walk-hillclimbing...certainly an inefficient search method, but one that is easily applied to many domains (and almost any encoding).

Maybe you could explain this in more detail.

Like RunningInt, I too have found cross-over to be much like a large mutation.

Say were on generation 600-- all of the members of a population will be nearly identical. If I move sections from member B in to member A, I'm most likely duplicating code that already exists in member A.

Another way to look at it: Say my cross-over only works 1 instruction at a time (I know this is not how it works, but...) If I take 1 instruction from member B and copy it in to member A, how different is that than randomly adding a new instruction to member A?

I'm open to the very real possibility that my own implementations of this are biased towards mutation. I'd hate to be missing out on some added utility. :)

Thanks Tim.

Will

Quote: Original post by RPGeezus

Quote: Original post by Timkin
If you remove crossover from a GA, then you are left merely with random-walk-hillclimbing...certainly an inefficient search method, but one that is easily applied to many domains (and almost any encoding).

Maybe you could explain this in more detail.

Like RunningInt, I too have found cross-over to be much like a large mutation.

Say were on generation 600-- all of the members of a population will be nearly identical. If I move sections from member B in to member A, I'm most likely duplicating code that already exists in member A.

If all the members are nearly identical, then crossover alone may not do you much good. However, can you say the same about generations 1 to 100?

Quote: Another way to look at it: Say my cross-over only works 1 instruction at a time (I know this is not how it works, but...) If I take 1 instruction from member B and copy it in to member A, how different is that than randomly adding a new instruction to member A?

As you said, that is not how it works, so your example doesn't help. Crossover typically exchanges large amounts of each solution, preserving some qualities of the previous solutions involved, which by their presence in the population and appearance at the selection stage, are assumed to have some degree of merit.

As Timkin has implied, the representation is key here. Crossover works well when your problem contains multiple dimensions which are largely independent. You might have one solution which has a good score in one dimension but has not found a good score in another. And a second solution may have the opposite. Crossover 'beats' mutation here in that crossover is able to combine the knowledge inherent in those two solutions into one improved solution. By comparison mutation loses that information.

Personally I think this might work poorly if you are swapping bytecode instructions in and out at an arbitrary point since there is a large degree of forward and backward referencing in imperative languages. I wouldn't think this was a good representation for GAs to optimise. It might work better as a symbol tree where you're swapping branches at random, as the structure of each solution is largely retained there.

There are two significant inefficiencies with GAs, Hitchhiking and Cloning.

Hitchhiking is the association of a week allele with a strong one through reproduction, whereby the presence of the weak allele is highly correlated with the presence of the strong allele. Because other values of the allele are not so present in the population, only mutation alone can break the correlation, which is difficult to do with low mutation rates seen in most implementations.

Cloning is the effect of crossing two parents and reproducing the same two parents as offspring, simply because of the similarity of subpatters in the parent strings. At full convergence, the probability of producing clones is 1. Indeed, even in initial populations, the probability of cloning is significant. This is the principle result of a thesis I produced back in the mid 90s. I produced a new version of Holland's Schemata Theorem that explains cloning and asymptotic convergence quite naturally. Cloning is the source of the asymptotic convergence of GAs and its cause is crossover.

However, if you remove crossover from your operator set, you are left with only reproduction and mutation. Since mutation will typically only affect a very small percentage of genes in the population in any given generation, then the population as a whole selects only the better members already present. This is hill climbing to a local minima. Any mutations that are not beneficial will usually be rejected by reproduction before they spread into the population. Any that are beneficial are quickly picked up. However, since crossover is not present, they don't spread as quickly as they otherwise might, because they only become associated with already strong alleles by pure chance.

Make sense? I hope so. 8)

Cheers,

Timkin

From what I've experienced with genetic programming, I think it feels like a randomly_feed_selective brute force method... and it tends to get stuck in local minimals A LOT. In a run it may be able to find the solution to a simple problem immediately, and in another run it may take lot of time, or simply not find it at all.

I also think that with lots of parallel/processing power it might be useful. But I don't think one can do a much for game development with it with a todays home PCs.

Quote: Original post by Timkin
However, if you remove crossover from your operator set, you are left with only reproduction and mutation. Since mutation will typically only affect a very small percentage of genes in the population in any given generation, then the population as a whole selects only the better members already present. This is hill climbing to a local minima. Any mutations that are not beneficial will usually be rejected by reproduction before they spread into the population. Any that are beneficial are quickly picked up. However, since crossover is not present, they don't spread as quickly as they otherwise might, because they only become associated with already strong alleles by pure chance.

Make sense? I hope so. 8)

Cheers,

Timkin

No, I still do not understand.

I do not understand how cross-over solves the hill-climbing dilema. It seems just as locked in to this problem as mutation alone is.

I'm not sure why you say that beneficial changes will not spread quickly through the population; the 'transfer' rate should be the same.

What if, instead of doing 1 mutation, every so often you would mutate an entire 10% of a member. How would this differ from cross-over with regards to the above?


Kylotan:
Sure, for the first few generations (100 isn't very many).... and after that??? You are right about copying branches in a tree, but you could also just make that a form of mutation.

i.e.
Is there a requirement to take the data from member B and put it in to member A? Could we, just as effectively, copy a section from member A and paste it in to member A? Would this be considered cross-over?

Quote: Original post by RPGeezus
I do not understand how cross-over solves the hill-climbing dilema. It seems just as locked in to this problem as mutation alone is.

Mutation produces a new solution fundamentally similar to the old solution. If it is near a local maxima, then it is likely to approach that local maxima and survive, or move away from it and die.

Crossover produces a new solution, which is - for some definition of distance appropriate to your representation - located somewhere between 2 existing solutions, which may be very distant in terms of search space. Both may be in local maxima, but if those maxima are distinct then the offspring may be in neither, meaning you've 'broken free'.

Now, you might say "but I can do that with large mutations too". The problem there is that large variations as a result of mutation make it hard to exploit a local maximum (which might actually be the global one). Imagine your whole population, or a large part of it, is already near the global maximum: wild mutation will send their offspring all over the place. Crossover won't do that. On top of that, crossover introduces changes that are generally good (because the changes come from good parent solutions), whereas mutation introduces changes that are neutral.

Quote: What if, instead of doing 1 mutation, every so often you would mutate an entire 10% of a member. How would this differ from cross-over with regards to the above?

Although the implementation obviously can be tweaked to suit different circumstances, it makes no difference how you implement mutation to the theory of it all. Crossover/recombination performs a distinct task from mutation and in most cases, both are useful.

Quote:
Sure, for the first few generations (100 isn't very many).... and after that???

After that, crossover may not benefit you so much as the solutions start to converge, but it will also make fewer 'mistakes' than mutation does because it is recombining good values with other good values. Imagine you have 2 solutions on the global maximum: crossover will give you another maximal solution, yet mutation cannot. (Obviously, the reverse applies when you're at the global minimum... but that can be eliminated in time for the 2nd generation by the selection process so it's not a factor.)

Quote: i.e.
Is there a requirement to take the data from member B and put it in to member A? Could we, just as effectively, copy a section from member A and paste it in to member A? Would this be considered cross-over?

No, it's mutation.

Quote: Original post by Kylotan
Crossover produces a new solution, which is - for some definition of distance appropriate to your representation - located somewhere between 2 existing solutions, which may be very distant in terms of search space. Both may be in local maxima, but if those maxima are distinct then the offspring may be in neither, meaning you've 'broken free'.

But only early on.... We agree? :)

Quote: Original post by Kylotan
wild mutation will send their offspring all over the place. Crossover won't do that. On top of that, crossover introduces changes that are generally good (because the changes come from good parent solutions), whereas mutation introduces changes that are neutral.

That does not make sense to me. Adding too many copies of the same chromosome in an animal can be fatal. Biology aside, I don't see how randomly insterting duplicate copies of existing 'code' (code can mean anything) is somehow inclined to be a good thing. I understand that the 'code' segment itself maybe proven to work, but what evidence is there to suggest that it will work in a different context (i.e. different location in the 'code').

i.e. If I gave you a third arm, how would it be useful without changes to your nervous and circulatory system? It would be a hinderance without a full reworking of your brain.

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'? In that case, so may mutation. Is there a higher chance of a cross-over giving you solution closer to the global maximum? If so, how does it know it's not just around a local maximum?

Quote:

Quote: i.e.
Is there a requirement to take the data from member B and put it in to member A? Could we, just as effectively, copy a section from member A and paste it in to member A? Would this be considered cross-over?

No, it's mutation.

So pulling _identical_ pieces during cross-over is not crossover. Only pulling different pieces is cross-over? Does it matter if the I member A and member B and 99.9999% identical, and that every piece I copy from member A already exists in member B?

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.

I'm still not convinced. Sexual reporoduction is very rare in biology.... Even in humans it's something that very rarely ever happens.

I won't pretend to know GA in such detail. I only know their general purpose and a bit of how they work so don't any inspirational AI idea on my front.

I am a pretty big fan of Sudoku and I noticed something while looking at a Sudoku puzzle book. All the locations of the revealed starting numbers are symmetrical around the the diagonal from bottom-left to top-right.

Therefore you only need to decide half of the numbers you want to show in order to generate the puzzle. Just have a look at Sudoku.com, since I can't post a replication of the Sudoku puzzle.(Isn't that stupid!) The current puzzle is like this but I'm not sure about the others.

It also doesn't 'logical' to say that the placement of all the numbers has any effect on the difficulty. Then again. a lot isn't but still is. Looking at the book you see that as the difficulty increases, the number of visible numbers decrease(obviously), yet the number of different puzzles in each section seem to be the same.

The book I have is 'The Ultimate Book Of Sudoku' by Pete Sinden. I think he owns the SudokuMania website as well.

Quote: Original post by RPGeezus
But only early on.... We agree? :)

Agree on what? That crossover and mutation are the same? No, they're not. They are both search operators but they achieve different results in terms of the exploration of not only the state space but also of the objective function. Mutation guarantees that the solution generated by applying that operator to a current operator has a 'fitness' within bounds defined by the local gradient of the objective function and the mutation rate. For this reason, mutation can only ever perform gradient ascent/descent using a random walk. Crossover makes no such promises and is therefore not constrained to producing only hill climbing search of the objective space.

Quote:
Adding too many copies of the same chromosome in an animal can be fatal.

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

Quote:
Biology aside, I don't see how randomly insterting duplicate copies of existing 'code' (code can mean anything) is somehow inclined to be a good thing. I understand that the 'code' segment itself maybe proven to work, but what evidence is there to suggest that it will work in a different context (i.e. different location in the 'code').

No one is suggesting structural crossover. Think of crossover from its genetic counterpoint. If I take two humans and from them produce an offspring, the usual genetic processes will select for each gene, two of the 4 allele values (because we have haploid coding), one from the male parent and one from the female. Putting mutation aside, this is crossover performed at every site between genes. GAs simply limit this to one crossover site on the chromosome, to ensure that the search is not purely random. The affect of this is to preserve significant subsets of schema represented by the parents. The best way to understand GA operators is by their affect on the schema that a population instantiate. If you haven't read Holland's original work, I highly recommend it.

Quote:
If so, how does it know it's not just around a local maximum?

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?

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.

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.

Cheers,

Timkin

Quote: Original post by RPGeezus
Sexual reporoduction is very rare in biology.... Even in humans it's something that very rarely ever happens.

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