• Create Account

# Genetic Algorithm and Sudoku

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

64 replies to this topic

### #41RPGeezus  Members   -  Reputation: 216

Like
0Likes
Like

Posted 24 November 2005 - 10:50 AM

Quote:
Original post by Kylotan
Quote:
 Original post by RPGeezusWould 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."

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

And "Cross-over alone, by neccessity, excludes many types of problems from the mix as encoding is a limiting factor."? :D

Quote:
 Original post by KylotanI say no to the 3rd [less cycles] because crossover - where applicable - makes better use of the information encoded in your population than mutation does.

_IF_ all other requirements are met.

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

ONLY if the operands that make up the solution are not bound by order of appearance. Then yes, there is a chance.

Quote:
 Original post by KylotanMutation does not do anything to explicitly facilitate that.

Mutation works with a single line of ancestors. A familiy rope -vs- a family tree. Concievably you are using half the code per ancestor (per ancestor) you could have used, BUT, are a gauranteed that the code you do have is statistically more significant. Sound reasonable?

Why limit cross-over to two parents? Why not 3, 4, 5 or 100? Why two? It would stand to reason that two should be the least you would want, but not the neccesarily the optimium number.

Quote:
 Original post by KylotanThey're [poker hands] 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.

You could make mutation work without having to worry about how 'orthagonal' the encoding was. If your GA evolved a compressed respresentation of a poker hand (which would be later expanded during the evaluation), or your evaluation function was dynamic, you could reach a global maximum from any starting position. The draw back would be wasted space in your compressed representation of the solution (like unreachable code).

For this to happen cross-over would not work so well.

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

Cross-over cares about how many best solutions there are.

Maybe we're in disagreement because of our point-of-view. It would seem a system designed to work best with mutation will be a poor system for cross-over. It only would seem to work one way though-- would a system designed to work with cross-over limit the effectiveness of mutation?

Will

### #42Timkin  Members   -  Reputation: 864

Like
0Likes
Like

Posted 24 November 2005 - 12:57 PM

Quote:
 Original post by RPGeezuswould a system designed to work with cross-over limit the effectiveness of mutation?

Quite the opposite. Crossover enhances mutation by providing a rapid means of distributing beneficial mutations into the population and provides the mechanism to maximise the correlation between beneficial mutations and beneficial substrings (good quality partial solutions).

Will, I definitely think you should read up on Holland's schemata theorom.

Cheers,

Timkin

### #43Kylotan  Moderators   -  Reputation: 3338

Like
0Likes
Like

Posted 24 November 2005 - 09:18 PM

Quote:
 Original post by RPGeezusAnd "Cross-over alone, by neccessity, excludes many types of problems from the mix as encoding is a limiting factor."? :D

Of course it does. But that applies to all methods. Some methods can be stretched to 'work' in any given situation at the expense of optimality. eg. Mutation can be broadened so that it becomes little better than a random search, then it is guaranteed to work...eventually..., but it is no better then than picking random solutions from a hat. All methods have situations they are good at and those they are bad at.

Quote:

Quote:
 Original post by KylotanI say no to the 3rd [less cycles] because crossover - where applicable - makes better use of the information encoded in your population than mutation does.

_IF_ all other requirements are met.

Search is all about matching a method to the requirements. There is no one method that is statistically better than any other when measured over all possible problem types. Wolpert and Macready's work will elaborate on this if you're interested.

Quote:
 You could make mutation work without having to worry about how 'orthagonal' the encoding was.

Yes, you could, but that's not the point. You can make a linear search work without worrying about the encoding either. Or a random search. But those are rarely optimal. Neither is relying purely on mutation in many situations. The question is, is this the best approach for the given problem? In your problem, with your representation, crossover is not much use. That's not a problem with crossover.

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

Cross-over cares about how many best solutions there are.

No, it doesn't, and you've not produced evidence to back that assertion. The number of separate maxima are irrelevant. What is important is how the fitness landscape is shaped, as that dictates how the solutions will converge. As far as shape is concerned, it's assumed that there are numerous maxima (best or otherwise), each of which are handled identically. If there was only one maxima, and you knew this, then you'd just use hill-climbing or something simple like that.

### #44RPGeezus  Members   -  Reputation: 216

Like
0Likes
Like

Posted 25 November 2005 - 05:23 AM

Quote:
Original post by Timkin
Quote:
 Original post by RPGeezuswould a system designed to work with cross-over limit the effectiveness of mutation?

Quite the opposite.

My question was rhetorical. I've been saying all along that mutated clones are king. ;)

Quote:
 Original post by TimkinCrossover enhances mutation by providing a rapid means of distributing beneficial mutations.

Sure, I agree with you. It can, under the right circumstances. I'm not arguing about if it can work, just that the requirements for it to happen are so huge, and mutatation does not have those same requirements.

Again, I have to ask, why limit cross-over to two parents? Why not 5, 6, or 30?

I'll take a stab in the dark and propose that the number of dimensions in your solution space (if one could even know this) is also the optimal number of 'parents' per 'child'.

Quote:
 Original post by KylotanMutation can be broadened so that it becomes little better than a random search, then it is guaranteed to work...eventually..., but it is no better then than picking random solutions from a hat.

I think you're down playing the utility of mutation. Cross-over will not work without mutation-- as Timkin has said Cross-over enhances mutation.

Quote:
 Original post by KylotanThe number of separate maxima are irrelevant

I disagree, and here is why.

Seprate global maxima are more likely to have solutions which are NOT related. Taking components from a solution at one maxima and mixing it with another is very likely to only give you a solution that is at NEITHER maxima.

The 'shape' of your solution space will not be conducive to the crossing of solutions if there is more than one maxima.

Here is a poor ASCII picture of a hypothetical solution space:

     A             B     .'.           .'....'   '.........'   '.....

Any point between maxima A and maxima B is more inclinded be further away from either maxima.

If, on the other hand, a mutation occures on a member already close to a maxima, it is more likely to still be close to that maxima.

The more maxima you have the worse this problem gets.

Maybe an easy way of thinking about it to look at it like image processing operators-- you can blur and you can sharpen. At some point blurring will be a bad thing... We want sharp.

Quote:
 Original post by KylotanIf there was only one maxima, and you knew this, then you'd just use hill-climbing or something simple like that.

That's what I said. :)

Quote:
 Original post by RPGeezusif a problem only had ONE best solution you probably wouldn't be using something like GA's to find it...

I brought this up because of the Poker example, to which you replied:

Quote:
 Original post by KylotanThey're a poor example of what you'd use a GA for, because of the heavily discontinuous search space

What makes the search space so discontinuous-- Multiple 'best' answers (aka global maxima).

Will

### #45Jotaf  Members   -  Reputation: 280

Like
0Likes
Like

Posted 25 November 2005 - 12:30 PM

Sorry for skimming over this thread :)

Start with a known, solved sudoku puzzle. You could have a list of these, but one is enough (even if it's a trivial one). Then iterate over a few hundred thousand modifications to this puzzle, the only constraint is that after each one the puzzle must still be considered solved. Things like switching around numbers and stuff. After this, chose some numbers to hide randomly and voila!

This is a good recipe for most puzzle games, I'm sure it will work just fine for Sudoku :)

### #46RunningInt  Members   -  Reputation: 133

Like
0Likes
Like

Posted 25 November 2005 - 03:38 PM

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

I wouldn't propose making all mutations massive. Instead I would replace crossover with a mutation operator which had a random size. So some mutations would be slight allowing exploitation and some mutations would be large allowing exploration.

The only unique benefits I can see with crossover is first the potential that crossing the best attributes of two parents will produce even fitter offspring. But I wonder how likely is this compared to the chance of macromutation producing fitter offspring. Second crossover allows changes to spread faster (but only if crossover is producing anything useful).

### #47Timkin  Members   -  Reputation: 864

Like
0Likes
Like

Posted 27 November 2005 - 01:20 AM

Quote:
 Original post by RPGeezusI've been saying all along that mutated clones are king. ;)

You're missing the point. Clones occur most frequently when the population is near convergence, irrespective of what point in the state space the population has converged upon.

Quote:

Quote:
 Original post by TimkinCrossover enhances mutation by providing a rapid means of distributing beneficial mutations.

Sure, I agree with you. It can, under the right circumstances.

You seem to be convinced that crossover works only under very limiting constraints and in very narrow contexts. This point of view simply isn't supported by the literature, nor the mathematics. Crossover is a more effective operator for searching the state space in a directed manner (where the direction is provided by the population, which represents the successful aspects of the search so far) than mutation is. Mutation is not directed at all and thus MUST rely on some other operator, such as selection, for it to work. Otherwise, mutation is just drawing rabits out of the hat, hoping to get the right one.

Quote:
 Again, I have to ask, why limit cross-over to two parents? Why not 5, 6, or 30?

Because crossover between two parents preserves as many schemata presently in the population as possible, while possibly forming new schemata which can be evaluated during selection.

Quote:
 I'll take a stab in the dark and propose that the number of dimensions in your solution space (if one could even know this) is also the optimal number of 'parents' per 'child'.

That doesn't make sense to me. The 'solution' is a point in the state space (or any point within a finite volume). This point (or volume) will have as many dimensions as the state space (unless it is a submanifold of the state space, in which case you encoded too much information into the problem and should have mapped the input space first to a lower dimension).

Quote:
 I think you're down playing the utility of mutation. Cross-over will not work without mutation-- as Timkin has said Cross-over enhances mutation.

You're putting words into my mouth that I never intended. You're suggesting that crossovers role is only to enhance mutation, which you suggest is doing the grunt work of the search. Quite the opposite is true. Crossover does the grunt work, mutation just adds the spice (and another stochastic element in the generation of candidate solutions).

Quote:

Quote:
 Original post by KylotanThe number of separate maxima are irrelevant

I disagree, and here is why.

Seprate global maxima are more likely to have solutions which are NOT related. Taking components from a solution at one maxima and mixing it with another is very likely to only give you a solution that is at NEITHER maxima.

That totally depends on the volume of state space that the maxima encompasses.
Quote:
 The 'shape' of your solution space will not be conducive to the crossing of solutions if there is more than one maxima.

Again not true. GAs work very well on multimodal objective functions. In fact, they work better than many other techniques. The rate of convergence on the true global maxima will be proportional to the gradient on the submanifold that connects each of the peaks of the local maxima.

Quote:
 Here is a poor ASCII picture of a hypothetical solution space: A B .'. .'....' '.........' '.....

And if A were slightly higher than B, or vice versa, mutation would typically fail to solve this problem, since selection pressure would mitigate any beneficial mutations that enabled a single candidate solution to hop into the other maxima. The probability of reproducing that single chromosome would be insignificant unless the population was already well populated by candidates within the confines of the region housing the global optima. Again, in this situation, crossover will find the maxima more quickly than mutation will.

Quote:
 Any point between maxima A and maxima B is more inclinded be further away from either maxima.

Any candidate solution generated that fell outside of A or B would be rejected very quickly by selection. The population consists of more than 1 candidate solution for just this reason... so that failed attempts don't significantly affect convergence speed.

Cheers,

Timkin

### #48Kylotan  Moderators   -  Reputation: 3338

Like
0Likes
Like

Posted 28 November 2005 - 02:37 AM

Quote:
 Original post by RPGeezusSeprate global maxima are more likely to have solutions which are NOT related. Taking components from a solution at one maxima and mixing it with another is very likely to only give you a solution that is at NEITHER maxima. ...Any point between maxima A and maxima B is more inclinded be further away from either maxima.

Yes, but for every pairing of solutions that are near the top of different maxima, there is likely to be several pairings that are on either side of the same maxima, and end up exploiting that one as a result. Just as with mutation, the selection operator is necessary here to augment the procedure.

Quote:
 If, on the other hand, a mutation occures on a member already close to a maxima, it is more likely to still be close to that maxima.

On the other other hand, if you're on a local maxima, and the global maxima is distant from the greater one in search space, a mutation is less likely to find that global maxima. Neither method is 'better'; neither works well without the other.

Quote:

Quote:
 Original post by KylotanIf there was only one maxima, and you knew this, then you'd just use hill-climbing or something simple like that.

That's what I said. :)

Maybe I wasn't clear. GAs are perfectly well suited to problems with one single maximum value, but often, if you know in advance that there is only one, it may be worth trying something else, especially if you also know that the fitness landscape is fairly smooth. Quite often it might be the case that there is only 1 global maximum but you don't know about that beforehand - you just want to find as good an answer as possible in a certain time.

Quote:
Quote:
 Original post by KylotanThey're a poor example of what you'd use a GA for, because of the heavily discontinuous search space

What makes the search space so discontinuous-- Multiple 'best' answers (aka global maxima).

No... a problem can have an infinite number of best answers and yet still be totally continuous. The mathematical definition of continuous is important here. eg. What value of x gives you the highest result from sin(x)? In this example, a tiny change in x yields a tiny change in sin(x). Poker is totally different - the smallest possible change, such as changing one card up or down a suit or number, changes the value of the hand significantly in most cases.

### #49RPGeezus  Members   -  Reputation: 216

Like
0Likes
Like

Posted 28 November 2005 - 06:07 AM

Quote:
 Original post by RunningIntThe only unique benefits I can see with crossover is first the potential that crossing the best attributes of two parents will produce even fitter offspring.

Thats the way I see it too. There is some potential, if everything is in place.

Quote:
 Original post by RunningIntBut I wonder how likely is this compared to the chance of macromutation producing fitter offspring.

Good question.

Quote:
 Original post by TimkinYou seem to be convinced that crossover works only under very limiting constraints and in very narrow contexts.

For cross-over to work we must satisfy some not-so-trivial criteria. I thought we were all on agreement in this regard, at least semantically.

Quote:
 Original post by TimkinThis point of view simply isn't supported by the literature, nor the mathematics.

It certainly is, as you have pointed out. Just because you would think of using GA's for a non-orthagonally encoded problem as faux-pas doesn't mean those problems cease to exist.

Maybe you disagree with me because you feel like I'm hitting a thumb-tac with a sledeg-hammer (i.e. wrong tool for the job)? :)

Quote:
 Original post by TimkinMutation is not directed at all and thus MUST rely on some other operator, such as selection, for it to work. Otherwise, mutation is just drawing rabits out of the hat, hoping to get the right one.

We need selection anyway. How is this a bad thing?

Quote:
Original post by Timkin
Quote:
 Again, I have to ask, why limit cross-over to two parents? Why not 5, 6, or 30?

Because crossover between two parents preserves as many schemata presently in the population as possible, while possibly forming new schemata which can be evaluated during selection.

That doesn't make any sense to me, Tim. Why would 3 parents be less effective than 2? If I cut a pie in 2 or in 10, it's still all part of the same pie. The number '2' would be suspicious to someone looking for evidence of anthropomorphic biases...

Quote:
Original post by Timkin
Quote:
 I think you're down playing the utility of mutation. Cross-over will not work without mutation-- as Timkin has said Cross-over enhances mutation.

Crossover does the grunt work, mutation just adds the spice (and another stochastic element in the generation of candidate solutions).

My apologies. Didn't mean to take your words out of context.

Will cross-over, without mutation, ever find a solution?

Will mutation, without cross-over, ever find a solution?

Quote:
 Original post by TimkinAgain not true. GAs work very well on multimodal objective functions. In fact, they work better than many other techniques. The rate of convergence on the true global maxima [.....]

We're talking about a problem with more than one global maxima. In the hypothetical example there is more than one true global maxima.

Quote:
 Original post by TimkinAnd if A were slightly higher than B, or vice versa, mutation would typically fail to solve this problem,

There are ways to allow mutation alone to climb out of local maxima. I think thats what alleles, in biology, would facilitate.

Quote:
 Original post by KylotanYes, but for every pairing of solutions that are near the top of different maxima, there is likely to be several pairings that are on either side of the same maxima

I agree with you. I was narrowing my view to a specific case of two maxima to illustrate a point.

Would you agree that, as the number of global maxima increases the odd's of a correct pairing go down? I'm not sure where I'm going with this. lol. :) So being to the left, or the right of a maxima could still put you to the left or the right of yet another maxima.... Does any of what I'm saying make any sense? :D

Quote:
 Original post by KylotanOn the other other hand, if you're on a local maxima, and the global maxima is distant from the greater one in search space, a mutation is less likely to find that global maxima. Neither method is 'better'; neither works well without the other.

Yes. I agree with you, except that you can use mutation without cross-over. Cross-over will spread the mutation across members, at the beginning, until the population starts to settle on one solution. Selection / cloning will spread the information too, just no between different members.

Will

### #50Timkin  Members   -  Reputation: 864

Like
0Likes
Like

Posted 28 November 2005 - 01:47 PM

Quote:
 Original post by RPGeezusFor cross-over to work we must satisfy some not-so-trivial criteria. I thought we were all on agreement in this regard, at least semantically.

No, I don't see agreement on this point. From my experience, crossover will always be effective on problems that are solveable by a directed random walk and crossover will perform better than said random walk. On problems that are not solveable by a directed random walk, then a random walk is your only option and so the point is moot (nothing other than mutation, which is semantically equivalent to randomly generating a solution), will work. Such problems are typically identified by very narrow, sparsely distributed optima in the objective space, which have always been very difficult to solve using optimisation techniques. If you want a good solution for such problems, check out Terence Kwok's work on combining simulated annealing and self organising maps. He uses edge-of-chaos behaviour to generate all solutions of problems such as N-queens very rapidly.

Quote:
 Original post by TimkinIt certainly is, as you have pointed out. Just because you would think of using GA's for a non-orthagonally encoded problem as faux-pas doesn't mean those problems cease to exist.

I never said you couldn't or shouldn't use them on such problems. Only that such problems will be more conducive to being solved by GAs that use single point crossover.

Quote:
 Original post by TimkinBecause crossover between two parents preserves as many schemata presently in the population as possible, while possibly forming new schemata which can be evaluated during selection.

That doesn't make any sense to me, Tim. Why would 3 parents be less effective than 2? If I cut a pie in 2 or in 10, it's still all part of the same pie. The number '2' would be suspicious to someone looking for evidence of anthropomorphic biases...
[/quote]

Okay, a brief introduction to Schema Theory...

Consider the two binary strings
    101100110    110101100

If we consider the set of possible offspring generated by crossover, we get the following, where '#' means 0 or 1:
    1##10#1#0

This is a schema (a template) for the result of crossover. If we add a third member to the popultion, say '010111000', then the set of schemata represented by the population, taken pairwise, is
    1##10#1#0    ###1####0    #101#1#00

These schemata represent the possible next generation of candidate solutions (ignoring for the moment mutation) that the GA can produce using pairwise crossover (they are a roadmap as to where one might find an optima). From this perspective, we can see how crossover preserves associations of bits present in a schema. Holland showed that it is indeed schema (and their relative fitness) that represent the qualtiy of knowledge regarding the optimal solution. It should be fairly obvious that '#########' represents a purely random solution set spanning the entire state space, which holds no useful knowledge of where to look for the optimal solution, since the fitness of members of this set encompasses the entire objective function.

So, now take our original 3 candidate solutions as a triplet. The schema resulting from this tuple is '###1####0', which, as you can see, is the worst (most general) schema from the pairwise set. Candidate solutions generated by producing offspring from a 3 way crossover would be randomly selected from this set and thus, would randomly select one of the possible fitness values spanned by this set. The probability of producing good quality offspring would be less than if pairwise crossover were performed.

GAs preserve good quality schema and indeed, theysearch through the schemta present in the intial population to find an optimal solution (so you can see the importance of the initial population).

Mutation disrupts a schema. However, if used at a low level, it does not generally remove a schema from the population. Furthermore, mutation can help to produce schema that might not have been present in the initial population, or that might have died out along the way due to unintended selection biases.

Understanding schemata is the key to understanding how the canonical operators affect the search of the state space... and thus, how changing those operators will affect the efficiency of the search.

Quote:
 Will cross-over, without mutation, ever find a solution?

If will find the best solution available given the initial information contained in the population. See above.
Quote:
 Will mutation, without cross-over, ever find a solution?

Possibly... and that is the best that can be said. There are no guarantees that you will stumble across the solution. Indeed, if your random number generator is poor, or your state space large (or both), you might go round in circles and never find it.

Quote:
 We're talking about a problem with more than one global maxima. In the hypothetical example there is more than one true global maxima.

If they are both (all) global maxima, then you cannot care which global maxima you attain, since from the point of optimisation, you found the global maxima whenever you find any of the global maxima. If your task was to find ALL global maxima then this isnt, strictly speaking, an optimisation problem and very few optimisation algorithms will be useful, since such problems are typically NP-hard (and I think in that case the discussion is moot). See the aforementioned work of Terry Kwok for how to tackle such problems effectively.

Cheers,

Timkin

### #51RPGeezus  Members   -  Reputation: 216

Like
0Likes
Like

Posted 28 November 2005 - 03:55 PM

Quote:
Original post by Timkin
Quote:
 Original post by RPGeezusFor cross-over to work we must satisfy some not-so-trivial criteria. I thought we were all on agreement in this regard, at least semantically.

No, I don't see agreement on this point. From my experience, crossover will always be effective on problems that are solveable by a directed random walk and crossover will perform better than said random walk.

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

and proceeded to highlight proper schema encoding.

I consider this non-trival.

Quote:

Quote:
 Original post by TimkinBecause crossover between two parents preserves as many schemata presently in the population as possible, while possibly forming new schemata which can be evaluated during selection.

That doesn't make any sense to me, Tim. Why would 3 parents be less effective than 2? If I cut a pie in 2 or in 10, it's still all part of the same pie. The number '2' would be suspicious to someone looking for evidence of anthropomorphic biases...

Quote:
 Original post by TimkinOkay, a brief introduction to Schema Theory......

Sorry, I can't say I fully understand your example. The masking you describe is only masking if we use binary states.

i.e.

cat dog    bear  ratcat monkey owl   rat

The child could be:

cat dog/monkey bear/owl rat

but never

cat turkey rabbit rat

Doesn't this satisfy "GAs preserve good quality schema"? Adding a third parent wouldn't change that.

When, earlier, I said that the optimal number of parents might be related to dimensions in solution space I was considering the following:

a = f( x, y, z);

wher x, y and z are a number between -1 and 1.

I want x, y, and z so that a = some number.

member 1 has the X part solved (magically), member 2 has the y part solved, and member 3 has the z part solved. Allowing 3 parents I could actually get the correct solution right away. Given two parents I would require at least two generations.

Quote:
Original post by Timkin
Quote:
 Will cross-over, without mutation, ever find a solution?

If will find the best solution available given the initial information contained in the population. See above.

I take it you mean 'no, unless.......'.

Quote:
Original post by Timkin
Quote:
 Will mutation, without cross-over, ever find a solution?

Possibly... and that is the best that can be said.

The same can be said of using mutation AND cross-over. I'll take your answer as 'regretfully yes'.

Quote:
Original post by Timkin
Quote:
 We're talking about a problem with more than one global maxima. In the hypothetical example there is more than one true global maxima.

If they are both (all) global maxima, then you cannot care which global maxima you attain,

I do care, because if we're talking about swaping components of solutions, and those componets deal with solutions located at different global maxima, then they will be incompatible. By 'will' I mean 'will likely'.

Will

### #52giveblood  Members   -  Reputation: 100

Like
0Likes
Like

Posted 28 November 2005 - 04:06 PM

wowww i actually was thinking about making a sudoku solver program today and was just about to start writing it. Just wanted to check the active topics real quick and saw other people make programs around it too.
-Chris

### #53giveblood  Members   -  Reputation: 100

Like
0Likes
Like

Posted 28 November 2005 - 04:21 PM

Sorry if i'm missing something (i did skip over a lot of what i thought was irrelevant to what i'm about to ask) but if you MAKE the puzzle by starting with a completed one and taking away some values, what prevents you from creating a puzzle with more than oen solution? Surely there has to be a certain way you have to make them blank, right? I havent tried this yet so I don't know if it's true, it just seems like a possibility to me.
-Chris

### #54Timkin  Members   -  Reputation: 864

Like
0Likes
Like

Posted 28 November 2005 - 06:49 PM

Quote:
 Original post by RPGeezusYou had said earlier that:"your attributes should be as orthogonal as possible."

Again you're not taking that in the context of what I wrote. Any state space can be mapped into an orthogonal space (or locally orthogonal space) prior to encoding... and in these spaces, the rate of convergence of the GA will be higher (so crossover could be said to be more effective).

Quote:
 Sorry, I can't say I fully understand your example. The masking you describe is only masking if we use binary states.

...a common misconception regarding GAs. Any string made up of characters of cardinality >2 can be mapped into a string with characters of cardinality 2. That is, I can trivially represent the gene 'cat' and its alleles ('tabby','moggy' and 'tom', for example ;) ) using the binary sequences '10','01' and '11' (or any other sequence I choose). Any set of tokens that you wish to use for your domain can be mapped into binary strings and thus I can still discuss the merits of the search algorithm applied to your example, but do so in the space of binary encoding strings.

Quote:
 Doesn't this satisfy "GAs preserve good quality schema"? Adding a third parent wouldn't change that.

Yes, it would. Consider the schema you get if the third parent you select for the tuple is 'goat turkey fox elephant'. What are the set of offspring now? And what values of the objective function would be found in that set? The variance of the objective function over the offspring set is a measure of the quality of the schema represented in the parents. The larger the offspring set, the more likely a higher variance (and vice versa).

Quote:
 When, earlier, I said that the optimal number of parents might be related to dimensions in solution space I was considering the following:a = f( x, y, z);wher x, y and z are a number between -1 and 1.I want x, y, and z so that a = some number.member 1 has the X part solved (magically), member 2 has the y part solved, and member 3 has the z part solved. Allowing 3 parents I could actually get the correct solution right away.

That's simply not true, since you can make no assumptions about whether the correct (solved) part of each parent chromosome will end up in the offspring. Furthermore, you're assuming that you are performing multi-site crossover, which is not a canonical operator.

Quote:
 I take it you mean 'no, unless.......'.

No, that's not what I'm saying. What I said was that crossover will find the optimal solution represented by the initial population. To borrow from your example earlier... if your initial population didnt contain the allele 'hound' for the dog gene, but this was the value of the allele in the global maxima, then obviously crossover cannot find that global maxima. However, it will allow you to find the string of highest fitness that IS contained within the set defined by the combinations of alleles in the initial population. Make sense?

Quote:
 The same can be said of using mutation AND cross-over. I'll take your answer as 'regretfully yes'.

You're doing it again! No, thats NOT what I said. In the absence of selection pressure, neither method is anthing better than randomly generating guesses at the answer. With the above caveat regarding crossover, they both are unlikely to find the global maxima. If we permit selection pressure, then mutation is still just randomly generating solutions with no regard to the solutions already tried. Crossover however makes use of the fact that you've already done testing and work in previous generations.

Quote:
 I do care, because if we're talking about swaping components of solutions, and those componets deal with solutions located at different global maxima, then they will be incompatible. By 'will' I mean 'will likely'.

They're not incompatible at all, just less 'fit', in which case they'll be discarded through selection, just as they would be if the mutation were unfit. No one ever claimed that a GA (and in particular crossover) only ever produced candidate solutions at each generation that had higher fitness than the previous generation. The only claim made by a GA is that the expected fitness of the population at each iteration is monotonically increasing.

Cheers,

Timkin

### #55RPGeezus  Members   -  Reputation: 216

Like
0Likes
Like

Posted 30 November 2005 - 07:40 AM

Quote:
 Original post by Timkin and in these spaces, the rate of convergence of the GA will be higher (so crossover could be said to be more effective).

If I understand correctly, the degree to which the encoding is orthagonal is proportional to the effectiveness of cross-over.

Quote:
 ...a common misconception regarding GAs. Any string made up of characters of cardinality >2 can be mapped into a string with characters of cardinality 2. That is, I can trivially represent the gene 'cat' and its alleles ('tabby','moggy' and 'tom', for example ;) ) using the binary sequences '10','01' and '11' (or any other sequence I choose). Any set of tokens that you wish to use for your domain can be mapped into binary strings and thus I can still discuss the merits of the search algorithm applied to your example, but do so in the space of binary encoding strings.

I don't see it... Treating my operands like binary strings at a binary level changes the entire behaviour.

cat dog rat .... octopus
1011 1000 0100 .... 1111

If I say cat/rat, I'm not saying all values between 0100 and 1011. I'm not saying 0/1 0/1 0/1 0/1... I am specifically saying nibble 1011 _or_ nibble 0100, not a combination thereof.

If my encoding is specific, as in cat / dog / rat / octopus then I litereally mean I want crossover to chose ONE OF but not a mixture of or a range of values in between. The high-level representation serves to eliminate options. Just representing it as binary, and allowing the GA to work with the binary, does not let us eliminate options.

Quote:
Original post by Timkin
Quote:
 Doesn't this satisfy "GAs preserve good quality schema"? Adding a third parent wouldn't change that.

Yes, it would. Consider the schema you get if the third parent you select for the tuple is 'goat turkey fox elephant'. What are the set of offspring now? And what values of the objective function would be found in that set? The variance of the objective function over the offspring set is a measure of the quality of the schema represented in the parents.

The larger the offspring set, the more likely a higher variance (and vice versa).

I still do not see how this changes the schema. All of the same operands exist, in the same order they appeared in the original three parents, but in a different combination.

Quote:
Original post by Timkin
Quote:
 When, earlier, I said that the optimal number of parents might be related to dimensions in solution space I was considering the following:a = f( x, y, z);...

That's simply not true, since you can make no assumptions about whether the correct (solved) part of each parent chromosome will end up in the offspring.

This is no different than with two parents. We can make no assumptions about whether the correct (solved) part of each parent chromosome will end up in the offspring.

Quote:
 Original post by TimkinFurthermore, you're assuming that you are performing multi-site crossover, which is not a canonical operator.

I don't know what you mean by this.

Quote:
Original post by Timkin
Quote:
 I take it you mean 'no, unless.......'.

No, that's not what I'm saying. [...] it will allow you to find the string of highest fitness that IS contained within the set defined by the combinations of alleles in the initial population. Make sense?

That's what I understood the first time. I was trying to be funny, but I guess it didn't come across well via text. :)

We'll get the best solution possible given the current operands that exist. If we're missing an operand then...... At which point crossover will just be working to randomize the order of the operands.

Quote:
Original post by Timkin
Quote:
 The same can be said of using mutation AND cross-over. I'll take your answer as 'regretfully yes'.

In the absence of selection pressure ....

What, exactly, do you mean by this? We always have selection pressure-- the fit stay and multiply.

Quote:
 Original post by Timkinthey both are unlikely to find the global maxima. If we permit selection pressure, then mutation is still just randomly generating solutions with no regard to the solutions already tried.

With mutation, a child is still mostly it's parent. Doesn't this mean that it is an attempt to refine an already tried solution?

If we permit elitism (which is a pretty common practice I think) then we establish a nice baseline for testing out these new changes.

Quote:
Original post by Timkin
Quote:
 I do care, because if we're talking about swaping components of solutions, and those componets deal with solutions located at different global maxima, then they will be incompatible. By 'will' I mean 'will likely'.

They're not incompatible at all, just less 'fit', in which case they'll be discarded through selection, just as they would be if the mutation were unfit. No one ever claimed that a GA (and in particular crossover) only ever produced candidate solutions at each generation that had higher fitness than the previous generation. The only claim made by a GA is that the expected fitness of the population at each iteration is monotonically increasing.

No problem-- maybe I'm looking at it from a different perspective. You say less fit, I say not compatible, which means less fit to the evaluation function.

Crossing over a member at peak A with a member at peak B is very unlikely to produce a good candidate, as they are both set on very different goals. They have a high likelyhood of being incompatible. Cross a BMP with an EXE and you'll likely get neither a pretty picture or a working application. This is all I'm saying.

If the members were clustered around the same peak then I could see crossover working well.

Will

### #56Timkin  Members   -  Reputation: 864

Like
0Likes
Like

Posted 30 November 2005 - 02:35 PM

Quote:
 Original post by RPGeezusIf I understand correctly, the degree to which the encoding is orthagonal is proportional to the effectiveness of cross-over.

As a general rule, I would say yes... but I'm not certain that it's an absolute.

Quote:
 I don't see it... Treating my operands like binary strings at a binary level changes the entire behaviour.

Only if you fail to encode correctly, so that there is a 1-1 mapping from your 'label' encoding to the binary encoding. 'cat' and 'dog' are just labels, as are '00' and '010'. So long as there are no binary alleles without corresponding 'string' alleles, then which I use is irrelevant.

Quote:
 If my encoding is specific, as in cat / dog / rat / octopus then I litereally mean I want crossover to chose ONE OF but not a mixture of or a range of values in between.

...and obviously crossover can be chosen only to apply at gene boundaries. If you crossover between boundaries (and meet the stipulation of a 1-1 mapping), then crossover is performing selective mutation (ie. its mapping the 'split' allele to another allele (depending on the other part of the allele string it receives from the parent) as well as crossing the tails of the two chromosomes. This is where your confusion lies. It's difficult to imagine this working if my encoding is 'tabby', 'moggy' and 'tom', but not difficult if my encoding is '00', '01', etc.

The high-level representation serves to eliminate options. Just representing it as binary, and allowing the GA to work with the binary, does not let us eliminate options.

Quote:
 I still do not see how this changes the schema. All of the same operands exist, in the same order they appeared in the original three parents, but in a different combination.

Remember that the schema represents the possible set of allele values for that set of chromosomes. So, if each of the parents has the same allele for the gene 'cat', then the schema will have that allele. If any one parent has a different allele than the others, then the schema will have a wildcard. The larger the set of chromosomes considered, the more likely that the schema representing that set will have more wildcards. Subsequently, my comments about the type of offspring that set will produce stand. Indeed, this is the whole point of GAs. As the population nears convergence, the population schema is refined (the number of wildcards are reduced) until, at convergence, the only possible offspring (ignoring mutation during reproduction) is a copy of the parents.

Obviously, all pairwise schema still exist if you have 3 parents... but if you have 3 parents, then pairwise schema don't count, because presumably you're using all 3 parents in reproduction at the same time (the GA-orgy!). Otherwise, you're just doing pairwise reproduction. See my point?

Quote:
 This is no different than with two parents. We can make no assumptions about whether the correct (solved) part of each parent chromosome will end up in the offspring.

Absolutely. But the probability of it happening is higher. (1/2 vs 1/3).

Quote:
 Crossing over a member at peak A with a member at peak B is very unlikely to produce a good candidate, as they are both set on very different goals.

I don't think that's absolutely true. In certain problems that have multiple global maxima (for example, those where any 'solution' is a global maxima, such as N-queens), there may indeed be properties common to every solution. Thus, crossing over any two solutions may preserve those properties. I can't back this up with hard evidence, but Terry Kwok's work seems to suggest that, at least for problems like N-queens, there is a sort of subspace made up of all solutions that his algorithm can work on. Certainly, the rate of finding solutions is proportional to the number already found. Admittedly his isn't a GA approach, but it may be the case that appropriate encodings exist for GAs for such problems where this 'subspace' property can be exploited. Maybe not though.

Cheers,

Timkin

### #57Jotaf  Members   -  Reputation: 280

Like
0Likes
Like

Posted 03 December 2005 - 02:11 AM

Quote:
 Original post by TimkinSo, now take our original 3 candidate solutions as a triplet. The schema resulting from this tuple is '###1####0', which, as you can see, is the worst (most general) schema from the pairwise set. Candidate solutions generated by producing offspring from a 3 way crossover would be randomly selected from this set and thus, would randomly select one of the possible fitness values spanned by this set. The probability of producing good quality offspring would be less than if pairwise crossover were performed.

Ok, let me just point out one tiny little detail :)

You're assuming that a # means there's a 50% chance of occuring a 1 (P(1)=50%) and 50% of a 0 (P(0)=50%). This is how you arrived at your conclusion: information is lost. The thing is, if you're chosing from 3 parents, and for example one of them has a 0 and two of them have 1s, the probabilities are actually: P(0)=33% and P(1)=67%. So it still preserves the information you said was lost. It's still arguable whether 3 parents are better or worse than 2.

### #58Jotaf  Members   -  Reputation: 280

Like
0Likes
Like

Posted 03 December 2005 - 02:18 AM

(I hate paralel discussions in the same thread but what the heck)

Quote:
 Original post by givebloodSorry if i'm missing something (i did skip over a lot of what i thought was irrelevant to what i'm about to ask) but if you MAKE the puzzle by starting with a completed one and taking away some values, what prevents you from creating a puzzle with more than oen solution? Surely there has to be a certain way you have to make them blank, right? I havent tried this yet so I don't know if it's true, it just seems like a possibility to me.

I don't think you have to do that. If there's another way to solve the puzzle and you found it, kudos to you :P It's a good thing in my opinion and I don't think no one will argue that a Sudoku puzzle generator will *have* to ensure there's only one solution. My proposed algorythm is simple and neat (and it's not mine :P ) and I'd be surprised if it's not the most common out there.

### #59 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 03 December 2005 - 10:10 PM

All of this is of course in my humble opinion, but I figure I will give my two cents anyways.

I have quite a lot of experience with GA's going back into the late 80's. I guess the darwinian romance has worn off.

One of my biggest pet peves is the reliance on 'real world' visualizations of what GA's are supposedly implimenting, and then blindly implimenting them. A Genetic Algorithm is nothing more than a generalized directed stochastic search.

What defines a GA is how you move from one population to another.

Population(t+1) = GA(Population(t))

This GA() function must satisfy a few various well known properties, but none of them has the notion of a 'generation' in it. The DNA is not a description of an individual. It is a piece of information that can be used in a directed search.

Keep thinking 'directed search.'

Why exactly should we divide the creation and destruction of this information into large scale changes? After producing a new piece of information, don't you want to use it immediately?

Most people seem to be doing:

10 Produce a lot of new information from the set of retained information
20 Merge it all into the set of retained information
30 Goto 10

10 Produce a new piece of information from the set of retained information.
20 Merge it into the set of retained information
30 Goto 10

Or in GA speak:

10 Produce a new member of the population using crossover and/or mutation.
20 Merge Sort the member into the population, throwing out the worst member.
30 Goto 10

The generation method with regard to algorithm implimentation is a needless complication at best (can anyone justify it?) and detrimental to efficiency at worst.

As far as crossover goes.

Crossover can be completely useless or extremely valuable. There seems to be no middle ground here. This depends on the specific problem set. In general, when crossover isnt a valuable commodity, you should not be using a genetic algorithm.

What does crossover do?

Technically: Crossover takes two strings of information and attempts to form a union between them, in the off chance that a more correct string of information can be derived from such unions.

In those cases where crossover isnt doing its job (and there happens to be work to be done), it is because the breeding population isnt diverse enough. Population diversity is critical in all areas of GA's. Keep thinking 'directed search.'

Without diversity and crossover, all you have is a stochastic hill climber.

I have been measuring diversity using the mean squared difference between the DNA in the breeding population.

When the diversity approaches zero, I know that its time to stop running the genetic algorithm.

I don't know if the best solution has been found or not, but I know its now in a stochastic hill climb and I know *for certain* that there are algorithms that perform a lot better than a stochastic hill climb that I can seed with the information attained thus far.

- Rockoon (Joseph Koss)

### #60Timkin  Members   -  Reputation: 864

Like
0Likes
Like

Posted 04 December 2005 - 02:32 PM

Quote:
 Original post by JotafYou're assuming that a # means there's a 50% chance of occuring a 1 (P(1)=50%) and 50% of a 0 (P(0)=50%).

No, I'm not assuming that. I'm simply saying that '#' is a wildcard, meaning that any gene depicted with that allele in the schema can take on any of its allele values in the chromosome. As to the probability of each allele value, that obviously depends on the frequency of specific allele values in the (sub)population that the schema represents (so I'm not assuming 2 or even 3 members... I'm not assuming any number at all).

Quote:
 This is how you arrived at your conclusion: information is lost.

No, it isn't, since you were wrong about my first statements. A schema doesn't represent 'information lost'.

Timkin

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS