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;
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
In reply to Re^3: How to evolve a permutation? (swap, sort)
by tye
in thread How to evolve a permutation?
by zli034
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |