Re: How to evolve a permutation?by blokhead (Monsignor)
|on Feb 14, 2008 at 21:59 UTC||Need Help??|
I'll echo kyle's sentiments that your post is a little vague...
This is my understanding of your question:
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.
Conjugate: Given permutations α and β, combine them as β α β-1, also a permutation.
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.