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.

Blokhead;

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.

check CPAN for CM::Permutation , it implements both Conjugation and Composition and also Commutator.

(Hmm, I didn't find the question hard to understand. But perhaps it had been updated before I read it.)

I'd mutate by swapping a random pair of adjacent items in the list. I'd recombine by assigning each element a number that is the average of its positions in the two orders and then putting the elements in an order that sorts these value:

my @mother= qw( a b d e c g f i h );
my @father= qw( b c a d e f h i g );
my %avgPos;
for my $av (  \@mother, \@father  ) {
    for my $i (  0 .. $#$av  ) {
        $avgPos{$av->[$i]} += $i/2;
    }
}
print " $_ => $avgPos{$_}\n"
    for  keys %avgPos;
my @son= sort { $avgPos{$a} <=> $avgPos{$b} } @mother;
print "( @son )\n";
__END__
 e => 3.5
 a => 1
 d => 2.5
 c => 2.5
 h => 7
 b => 0.5
 g => 6.5
 f => 5.5
 i => 7
( b a d c e f g i h )
[download]

You could flip a coin to pick @mother vs @father for the last step since modern Perl sort is "stable" now.

I also had no problem in understanding the question, and have been amused at how many monks are assuming that the use of genetic algorithms has anything to do with bioinformatics.

I don't know how many species you're aiming to attempt, but I would guess it's high enough you can't just keep a singleton registry of all tried genomes (or even a registry of digests of all tried genomes). tye's suggestion seems to limit the types of mutations (consecutive pair swaps). I'm a bit worried about how non-general that is, but we really don't have much to go on, for the actual problem at hand.

--
[ e d @ h a l l e y . c c ]

All possible permutations can be achieved only via swapping adjacent pairs.

I would think that an evolution algorithm is going to work better when the mutation of a more successful candidate is unlikely to be so large as to make the new candidate very unsuccessful. And it sounded like the importance of the ordering was likely of the rather mundane case of the position of an item in the list is what matters (absolute position and/or relative to surrounding items) -- as opposed to interesting mathematical characteristics like whether it is a derangement, what type of cycles it has, or if it involves an even or odd number of "swaps", etc.

So I suggested a way to have mutations that produce only small changes in the absolute and relative positions of items and to have recombination "average" the absolute positions so that the absolute and relative positions of the items in the parents are roughly preserved in the offspring.

There are a lot of assumptions in there, of course. zli034 can provide more information about how order impacts fitness if s/he wants to shift my assumptions.

It is also possible that only swapping adjacent pairs is too conservative and may lead to an evolution algorithm being stuck near a local maximum. It might be better to pick an item to swap at random [using a uniform distribution -- int(rand(100))] and then pick the other item to be swapped using a weighted distribution such that picking an adjacent item is the most likely but picking a far away item is possible, just unlikely.

Playing with that idea a bit, I came up with the following approach:

my $w= 2;
my $i= int( rand @list );
my $offset= 0+@list - log( rand( exp( (@list-1)*$w ) ) ) / $w;
$offset= int( $offset * (-1,1)[rand 2] );
my $j= abs( $i + $offset );
$j= @list - $j
    if  @list <= $j;
[download]

Set $w to a larger number to more heavily weight toward swapping adjacent items. Set $w to a smaller number (like 1/5) to make "wider" swaps more likely.

log rand exp $x gives a random number between 0 and $x (but less than $x) but with a strong preference for numbers close to $x. The larger $x is, the more the bias is towards $x. So multiply by a larger $w in log( rand exp $x*$w ) / $w increases the bias. So using $x=$n-1 then int($n-...) gives us 1..$n with a bias toward 1.

The abs and $j= @list - $j mean that trying to do an offset too far in one direction makes the offset "bounce off" the end of the list (rather than wrapping which could make a small offset pick a very far away item).

- tye        

It's possible this question is simply way over my head, but I can hardly tell what you're asking. It might help to tell us what you've tried implementing so far, and how close it is to what you want. Sample input and output might help. One of these might help you formulate your question more effectively:

• How do I post a question effectively?
• How (Not) To Ask A Question
• PerlMonks FAQ

Seconded; and given the contextual clues you might have better luck consulting a more specialized audience familiar with the domain in question (not that there's not biology people here, just your question was so steeped in cant you're not as likely to get help from a more generalist audience like PM).

The cake is a lie.
The cake is a lie.
The cake is a lie.

• how you are modeling a chromosome (is it just a string of CATG?)
• what you mean by 'mutation'
• what you mean by 'recombination'
• a reference to the 'Evolution' algorithm

ER

Question: If evolution is the holy grail of all creatures to survive inside this unpredictable world, can we use evolution to solve all our problems? Or else, can we demonstrate the weakness of evolution?

Wikipedia:
http://en.wikipedia.org/wiki/Genetic_algorithm


Perlmonks:
http://www.perlmonks.org/?node_id=298877

Would a species not evolving in response to a problem die out? Would this really be a "weakness of evolution" or simply a weakness of that species?

Step 1: evolve a room full of monkeys.

Step 2: give the monkeys your input string.

Step 3: wait.

Eventually the monkeys will generate all possible permutations of your input string. If your input string consists of a large enough pile of alphabet blocks, eventually they may give you the complete works of William Shakespeare as well.

If your monkeys starve to death before the algorithm completes, repeat step 1.

I think you might encounter the thermal death of the universe before the algorithm completes, but if that happens, don't come looking for me. :)

I'm not as into this as Tye seems to be, but I'm wondering if Memoize might not make your life easier. If there's some natural way you're thinking about the problem, but you're worried about repeated resulting permutations, maybe you could use the natural way of permuting and let Memoize prevent you from taking the performance hit.

It's just a brainstorm; you know your context better, so you'd have to decide for yourself