Quote: Original post by Daerax

Quote: Original post by alvaro
Actually, no. Imagine you are trying to optimize the strength of a poker bot. The only measure of strength you have is matching one bot against another for a number of hands and seeing who makes money off of whom. I don't see what a finite difference have to do with anything.

off topic but are you making a poker bot?

No. I thought about it for a while and I will probably get to it some day. But I have too many other projects right now and too little time to finish them. My job is getting in the way of my hobbies once again!

Quote: Original post by Kylotan

Quote: Original post by willh

Quote: Original post by Kylotan
Firstly, you missed crossover - without that, it's not a GA.

Crossover is just another form of mutation.

No, it's not.

Crossover and mutation both change the solutions to explore the search space but they are completely distinct in their purpose, which is why you can't leave one out and talk as if you're still using a GA

Crossover IS a mutation operation. This is a mathematical certainty.

Quote: Original post by Kylotan
That member of the population is chosen using some routine that favours members with higher fitnesses. Therefore the parts of the solutions that are better persist unchanged into future generations.

The logical conclusion of this is that all members will eventually become nearly identical. At this stage cross-over will have little effect as it becomes no different than a 'simple' mutation operation.

Quote: Original post by Kylotan
This is critical as it speeds up convergence, which is its primary purpose - it takes 2 solutions which have often optimised different dimensions of the problem and combines them into 1 solution. Mutation alone cannot do this.

That is not necessarily true for two reasons.

1. It is very possible for a mutation operation to introduce the exact same effect as would have happened with crossover.

2. If you look at convergence as TIME spent (i.e. milliseconds) and not generations required, then having an effective crossover scheme (which may work very well for the first few generations of a population) could actually result in a decrease in convergence time. This is due to the number of poor candidate fitness evaluations that are required for each generation, resulting in wasted cycles. It's like exploring obviously dumb moves in a gametree-- wasted time with no return.

In other words, an environment having 2,000,000 members that convereged in 10 generations sounds a lot better than one that took 10,000 generations to reach the same goal-- but if the 10,000 generation one took 5 minutes and the 10 generation one took 5 hours, then they don't stack up so well.

Quote: Original post by Kylotan
Genetic algorithms require crossover, mutation, and selection. Without implementing crossover properly you've pretty much crippled selection too and all you're left with is a mostly random form of beam search, which of course is going to be worse than pretty much any other algorithm you might throw at it. If that is how people use GAs then it is not at all surprising that they get poor results.

We'll have to agree to disagree that crossover is required for a GA; it's not a requirement in nature so I don't see why it should be a requirement when talking of algorithms.

In practical terms I do not think it is important to always include crossover in to a framework. You could go a step further and include multiple different crossover strategies (one point, two point, etc..) but in many cases I think the effort would be better spent on implementing more intelligent mutation operators (or any number of things).

Quote: Original post by willh

Quote: Original post by Kylotan
This is critical as it speeds up convergence, which is its primary purpose - it takes 2 solutions which have often optimised different dimensions of the problem and combines them into 1 solution. Mutation alone cannot do this.

That is not necessarily true for two reasons.

1. It is very possible for a mutation operation to introduce the exact same effect as would have happened with crossover.

2. If you look at convergence as TIME spent (i.e. milliseconds) and not generations required, then having an effective crossover scheme (which may work very well for the first few generations of a population) could actually result in a decrease in convergence time. This is due to the number of poor candidate fitness evaluations that are required for each generation, resulting in wasted cycles. It's like exploring obviously dumb moves in a gametree-- wasted time with no return.

mathematical certainty is a term I have always found redundant.

A genetic algorithm with no crossover is a waste of time, there is no point maintaing multiple solutions. at this point you may as well be using another algorithm, SA say.

Certainly you can look at cross over as a type of mutation just as you can look at them both as a probing blind search, randomly looking for serendipitous solutions near a point. GA are not related to nature so what you find in nature has no impact here, saying cost minimization and random combination of list elements is genetics is like saying drawing a square and building a house is the same since they both contain a four sided polygon.

Your point 2 is interesting because studies show that GA performs better for certain problems over long runs than SA (no crossover) which tends to arrive at and settle near its optimal solution quicker. A cleverly coded crossover could be the difference here, for certain problems. Although SA also sometimes outperforms GA for reasons you mention, as always there is no clear winner.

If you look at my earlier post you will see that I do not disagree with you in essence. Just in presentation. I agree that crossover is not necessary for this type of stochastic search (again , ala SA) but if your *Genetic* Algorithm doesnt do this then you have no business calling it such.

Quote: Original post by willh
Crossover IS a mutation operation. This is a mathematical certainty.

The two concepts are different in the algorithmic sense. Of course it would be possible, if you wrote your mutation operation in a certain way, to alter a solution such that it could change in a similar way to applying a crossover operation. But the chance of a typical mutation creating the same change as a typical crossover would make would be tiny. The point of crossover is to make use of the information elsewhere in the population, and the point of mutation is to introduce new information. The fact that these two can possibly overlap in their result is not terribly relevant.

Quote:

Quote: Original post by Kylotan
That member of the population is chosen using some routine that favours members with higher fitnesses. Therefore the parts of the solutions that are better persist unchanged into future generations.

The logical conclusion of this is that all members will eventually become nearly identical. At this stage cross-over will have little effect as it becomes no different than a 'simple' mutation operation.

Yes, they typically become closer together. That's convergence, and is exactly what you're looking for. Compare to other optimisation algorithms which typically just follow a single solution from start to end - they only had 1 possible option all the time, not just near the end. And of course convergence slows down as the algorithm progresses - this too is quite common in optimisation problems. Once you home in on the optimum there is often less room to improve.

But it doesn't become the same as a simple mutation operation. Quite the opposite in fact - as the solutions converge, mutation will produce quite different results to crossover.

Quote: 2. If you look at convergence as TIME spent (i.e. milliseconds) and not generations required, then having an effective crossover scheme (which may work very well for the first few generations of a population) could actually result in a decrease in convergence time. This is due to the number of poor candidate fitness evaluations that are required for each generation, resulting in wasted cycles. It's like exploring obviously dumb moves in a gametree-- wasted time with no return.

Compare this with many other optimisation algorithms, which don't even have a game tree - they just explore one promising looking route and often need some sort of added stochastic element or restarting procedure to get them out of local extrema.

Fitness evaluations in GAs are not particularly different from heuristics in other search or optimisation algorithms. Their usefulness is proportional to the quality of the heuristic.

Selection is only as expensive as you make it, also - tournament selection is incredibly cheap for example.

Quote: We'll have to agree to disagree that crossover is required for a GA; it's not a requirement in nature so I don't see why it should be a requirement when talking of algorithms.

Genetic algorithms use a biological metaphor to explain their constituent parts, that's all. It doesn't mean that anything that may exist in biology makes up a valid GA.

Quote: In practical terms I do not think it is important to always include crossover in to a framework. You could go a step further and include multiple different crossover strategies (one point, two point, etc..) but in many cases I think the effort would be better spent on implementing more intelligent mutation operators (or any number of things).

Without crossover you're not sharing useful information across the population, so there is little point maintaining that population. If you have a problem where there is no useful information to share, that's fine, but I can't think of one myself. If such a problem did exist then it would probably be better to run many instances of a cheaper single-member optimisation algorithm serially rather than dressing it up as a GA.

While I don't agree with everything in this article, I thought it might be useful to share this bit from Wikipedia regarding Genetic Algorithm

Quote: Wikipedia Genetic Algorithm
Reproduction
Main articles: Crossover (genetic algorithm) and Mutation (genetic algorithm)
The next step is to generate a second generation population of solutions from those selected through genetic operators: crossover (also called recombination), and/or mutation.

(Bold added for emphasis)

Daerax: I have a hard time accepting that the Genetic in Genetic Algorithm has no relation to the biological term 'Genetic'. Having read (one of) John Hollands descriptions first-hand, and the amount of space devoted to discussing biological genes, I'm pretty sure he would agree.

Quote: Original post by Kylotan
But it doesn't become the same as a simple mutation operation. Quite the opposite in fact - as the solutions converge, mutation will produce quite different results to crossover.

For a problem where population convergence and high-fitness are both achieved at approximately the same time then I agree with you. If population convergence happens before high-fitness then I still hold that crossover essentially becomes a simple mutation operation. There has a been a lot of research put in to strategies to maintain popluation variance specifically for this reason.

Quote:
Selection is only as expensive as you make it, also - tournament selection is incredibly cheap for example.

Some problems are expensive to evaluate and there is no way around it. Complex simulations, large data crunching exercises, etc.. I think we agree at this point, we're just looking at it from different angles.

Quote:
If you have a problem where there is no useful information to share, that's fine, but I can't think of one myself. If such a problem did exist then it would probably be better to run many instances of a cheaper single-member optimisation algorithm serially rather than dressing it up as a GA.

I can think of quite a few actually. As a complex problem space is 'explored' there are times when having fewer members is more effecient. There are also times where it is neccessary to branch out and 'explore' different variations on the same theme.

In fairness, I have always included crossover in my own frameworks. I also track how often each mutuation operator causes an improvement in fitness; crossover is (almost) always the least effective.

willh I am not sure what you are saying. Your arguments are correct but your conclusion doesn't fit. You say you always implement crossover and yet are trying to argue that crossover and mutation are the same thing. When it is clearly not the case and certainly *should* not be the case. Otherwise you are doing it wrong. The only way they could be the same is if you were taking a broad sweeping view of both mean creating new lists, say. But that is missing the forest for the tree, the point of multiple solutions is crossover (recombining elements across lists vs. selecting elements near a point in a list) to increase the chance of stumbling near a global optimum.

As for the original paper. Original papers are good to read because they are much less dry and provide insight and motivation than later distillations. But they are often much more bloated as they contain the raw, unpolished inspirations. As Kylotan said the biology is just a metaphor that guided the original work. Just as Immune systems insipire the Negative Selection Algorithm. I could just as easily call crossover as cross list recombination and mutation as Rearrangement via Random Neighbourhood Point Sampling. This doesnt make GA biological any more than playing Operation prepares you for heart surgery.

Quote: Original post by Kylotan
Without crossover you're not sharing useful information across the population, so there is little point maintaining that population. If you have a problem where there is no useful information to share, that's fine, but I can't think of one myself. If such a problem did exist then it would probably be better to run many instances of a cheaper single-member optimisation algorithm serially rather than dressing it up as a GA.

Its a matter of runtime. Clearly both would eventually arrive at the same result giving enough time but there are some problems where maintaining multiple solutions are distracting. One example from personal experience is when tuning some model where there is only one 'answer' and taking even a few step away results in wildly divergent answers. Here, keeping multiple solutions is detrimental and increases runtime drastically. Where as something like optimizing a schedule is better fitted to the GA approach.

Nonetheless to get around the weakness of not having multiple solutions in SA I retain a best second solution where the probability of restarting from that point increases as the time without a better find increases. Also attenuating range of search as Temperature cools is useful.

Quote: Original post by Daerax
willh I am not sure what you are saying. Your arguments are correct but your conclusion doesn't fit.

If we agree that:
a. Mutation can give the same results as crossover.

b. Omitting crossover does not necessarily invalidate some of the other positive (and fruitful) aspects of GA/EP/'Dice rolling' for a specific problem.

then I don't think we have any disagreement. I didn't say 'never use crossover'. I just said that it's not always necessary. (I implement it in my own frameworks out of habit BTW).

I think the argument originated with the claim that 'its not a GA if there is no crossover'. I disagree with that claim for reasons stated previously but will elaborate:

Bob is using a GA to solve some problem.
1. Bob has implemented crossover and 5 types of mutation.
2. By generation 100 an acceptable fitness has been achieved for Bobs problem.
3. In all 100 generations, crossover did not once produce any fruitful result and did not actually contribute to the solution.

Given 1,2, and 3, did Bob use a GA to reach his solution? Would it have been any less a GA if Bob simply omitted crossover given that the results would be identical?

You could argue that the the crossover/genome was poorly implemented; for reasons which I've already provided this is not always the case.

Again, No argument. You make sense. This is a matter of semantics. If you strip away the metaphors of mutation and crossover and instead look at it at a pure algorithmic level then you see that what you have is either

a) something similar but not equivalent to a genetic algorithm with cycles and memory wasted on a superfluous function (crossover) and maintaining multiple solutions

b) a badly implemented crossover function.

Thus in conclusion it appears your definition of GA is broader than everyone who disagrees with you (and most literature I have run into), you use it more as a covering term rather than focusing on the specific algorithmic properties.

Quote: Original post by Daerax
If you strip away the metaphors of mutation and crossover and instead look at it at a pure algorithmic level then you see that what you have is either

a) something similar but not equivalent to a genetic algorithm with cycles and memory wasted on a superfluous function (crossover) and maintaining multiple solutions

b) a badly implemented crossover function.

I haven't said anything to that effect.

Quote: Original post by Daerax
Thus in conclusion it appears your definition of GA is broader than everyone who disagrees with you (and most literature I have run into), you use it more as a covering term rather than focusing on the specific algorithmic properties.

I can assure you that GA w/o crossover is very much in the literature; it has been a topic of debate for some time. Maybe you're not reading the right material? Pretty much everything I've written as part of this thread has already been talked about in 'the literature'.

You're insisting on a rigid definition that necessarily includes crossover. I reject this definition while maintaining that the baby is still safely in the proverbial tub. You're also insisting that this view is somehow concrete and the only legitimate one; while that may be true within the GD community, it is certainley not the case!

In your view, what type of crossover is required for something to qualify as a GA? How flexible are you willing to be with your crossover operator while still having, what you would consider, a GA?

In terms of your own GA implementation, what is the goal of crossover?

[Edited by - willh on July 26, 2010 1:34:15 PM]

See kids, this is where GA/DP/ANN leads: semantics arguments over ill-defined methods that gives poor results and takes so much time and hacks and tweaks just to make it work that you could have coded a straightforward solution a hundred times over instead.