mutation operation

[Vikas Agrawal]

May be someone can help me this one. Let's say I have a list of cities to be visited: [Amsterdam, Athens, Berlin, Brussels, Dublin, London]

I know I can use ListOrderMutation and/or ListOrderCrossover. My question is what if I just do Collections.shuffle() for mutation operation. Because the whole idea of Mutation and/or Crossover is to change the sequence of cities anyway.

I am trying to understand the benefit of using ListOrderMutation combined with ListOrderCrossover instead of using Collections.shuffle(). I am new to this field. So if someone can please explain this, I would greatly appreciate it.

Also I have a peculiar constrain in the sequence in which these cities need to be visited. Let's say that you have to visit London before you visit Athens. How to incorporate this in the mutation operation. What I am currently doing is just the mutation operation and in it, I am just randomly shuffling the sequence of cities using Collections. shuffle() and then checking for any violation of constraints like London has to be visited before you can visit Athens.

Any suggestions will be greatly appreciate.

Thanks in advance.

Vikas

[Paul]

The notion behind mutation is to change the solution a little. Other than in comic books (and related movies), mutating a mild-mannered physicist should not produce an entirely new species (see: The Incredible Hulk). The ListOrderMutation operator gives you granular control over how much a permutation will change as the result of mutation. Collections.shuffle() will hand you an entirely new permutation; in evolutionary terms, I think it is closer to immigration than to mutation. As for crossover, the underlying concept is that the parents have pretty good genes, and you want to preserve most of that structure in the offspring. In this case, that means that chunks of the parental sequences represent desirable orderings. ListOrderCrossover preserves chunks (whether they're the right ones or not is a matter of chance), whereas shuffling preserves nothing.

As far as the constraint goes, I would mutate, confirm that the constraint is met, and if not discard the mutation and either mutate again or just leave the individual unchanged.

Paul

[Vikas Agrawal]

Thanks Paul for the explanation. That really helps.

Vikas

[klaas hoelscher]

Using shuffle kind of defeats the purpose of evolution, since nothing gets passed from parents to children - its more of a random search.

As of 0.71 you could use an EvolutionStrategyEngine with plus-selection (preserving fit "parents" from current Generation)  or an evolve() call

with an elite count of >0 keep the best individuals, while any list with the wrong order of visits would get an fitness scrore of 0.

Regards,

Klaas

2014/1/14 Vikas Agrawal <avi...@gmail.com>

--
You received this message because you are subscribed to the Google Groups "Watchmaker Framework for Evolutionary Computation" group.
To unsubscribe from this group and stop receiving emails from it, send an email to watchmaker+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Rick Cromer]

If I'm generated a program to predict future stock prices based on historical data, does the shuffle strategy make more sense since there may not be much value to part of an equation?

Rick

[klaas hoelscher]

Well, if your algorithm already works, i suggest that send me the code..for an educated opinion ;-)

To offer a more serious answer: If have an algorithm in mind that fits the evolution-algorithm scheme, you sure could use a framework like watchmaker. Just using shuffle() on each generation is a random search that also forgets the best results each turn.

Using shuffle() with eliteCount oder plus-Selection at least retains the best individuals.

While you may want some shuffling going on (especially for the first turn ;-) ), you want to use CrossOver or Mutation for reasons Paul explained above.

To use them, you need several factors in for fitness score, so each one may be mutated, inherited, crossed into offspring etc.

Regards,

Klaas

2014/1/15 Rick Cromer <rcr...@avioconsulting.com>

[Vikas Agrawal]

Thanks to everyone. I really am learning. But I fee that when you combine mutation and crossover together, and in crossover if you are doing multiple point crossover, that is pretty close to shuffling. How much ordering/sequencing will be preserved anyway?

[Vikas Agrawal]

What do you mean by "As of 0.71"?

[Paul]

From version 0.71 of Watchmaker Framework onward.

[Paul]

Crossover is a bit like eating. Eat too little/move too little in crossover and you starve/stagnate. Eat too much/move too much and you become obese/turn into random search. Somewhere in between is the right amount. With multi-point crossover, I would be wary of swapping too much at a time.

Mutation is intended to be used sparingly. The majority of individuals should not mutate, and those that do mutate should only change a little (most of their encoding should remain intact).

Remember: the fact that the software allows you to swap a lot of stuff during crossover or mutate the daylights out of every individual does not mean you should do that.

Paul

[klaas hoelscher]

In addition to Paul explanations i use another food analogy; imagine you try to generate a cooking recipe by evolution. Lets say you have a 10 element genome, and you use the first 3 entries to change parameters of the soup, 4 for the main course, 3 for the dessert.

Luckily, a member of the population has a great dessert. We want to generate new members for the next generation, so if the last 3 dessert entries are crossed into the children, we can be sure that the dessert will be as good as the current one.

If the main course is already pretty good, you could try a small change (little bit of salt, change some spices, 5mins more in the oven), you would randomly select one of the 4 entries for the main course and change the value, while the rest stays intact. this would be a ,utation.

More abstract, see http://hotrodanglican.blogspot.de/2010/11/on-being-stuck-in-local-optimum.html (just random google result) for local vs global optimization . Mutating helps you to get to the nearest optimum- e.g. the optimal amount of salt in the main course for the given other ingredients of the main course.

(The fitness function does not have to be differentiable, the graph may suggest that)

regards,

Klaas 

2014/1/17 Paul <paul_...@att.net>

--

You received this message because you are subscribed to the Google Groups "Watchmaker Framework for Evolutionary Computation" group.

[Vikas Agrawal]

Thank you guys for the explanation. That makes sense to me now.

[Vikas Agrawal]

>>As far as the constraint goes, I would mutate, confirm that the constraint is met, and if not discard the mutation and either mutate again or just leave the individual unchanged.

How about first mutate it, and they apply the heavy penalty for violating the constraints? For e.g., if the sequence constraint (i.e. first London and then Athens) if violated, then apply penalty of 5000 miles for each violation.

On Tuesday, January 14, 2014 11:56:52 AM UTC-5, Paul wrote: