Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses

Re: How to evolve a permutation?

by blokhead (Monsignor)
on Feb 14, 2008 at 21:59 UTC ( #668039=note: print w/replies, xml ) Need Help??

in reply to How to evolve a permutation?

I'll echo kyle's sentiments that your post is a little vague...

This is my understanding of your question:

  • you want to evolve "permutation" objects
  • you apparently represent a permutation as a list
  • a crossover (recombination) of 2 permutation lists is not guaranteed to remain a permutation list.

OK, so let's think of a different kind of combination operation, one which preserves the permutation nature. How about:

Composition. Given permutations α and β, their composition αβ is also a permutation.

  • Possible pitfalls: it's likely that the resulting permutation won't share high-fitness features of its parents, depending on your fitness measure.

Conjugate: Given permutations α and β, combine them as β α β-1, also a permutation.

  • Possible pitfalls: resulting permutation is in the same conjugacy class as α, and therefore has the same cycle structure. The features of β don't have much effect on the result of this operation. Because this operation has some asymmetry, maybe flip a coin to see which parent will get to be the "dominant" parent.

Ok, so I can only think of 2. Maybe try out both? I bet the second one would be nice if your fitness function rewards permutations that have cycles of the appropriate sizes.

If you really insist that your combination operation should be a list crossover, then you can certainly fix it to always produce a permutation. Who says that the crossover operation should be deterministic? After combining the two lists, find all the duplicates. Delete all but one of each duplicated item (you can chose which positions to remove randomly if you like), and fill in all the remaining empty spots with a random permutation of the items that are missing. This seems like a reasonable way to keep a lot of the features of the parents, keep the spirit of the list-crossover operation, and preserve permutation-ness.


Replies are listed 'Best First'.
Re^2: How to evolve a permutation?
by zli034 (Monk) on Feb 14, 2008 at 22:59 UTC


    Thank you for your ideas. Yes, normal crossover and mutation can't maintain a permutation list which doesn't have repeats. This was I meant.

Re^2: How to evolve a permutation?
by spx2 (Deacon) on Dec 31, 2009 at 19:59 UTC
    check CPAN for CM::Permutation , it implements both Conjugation and Composition and also Commutator.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://668039]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (5)
As of 2021-02-27 16:11 GMT
Find Nodes?
    Voting Booth?

    No recent polls found