Re^2: How to evolve a permutation? (swap, sort)

in reply to Re: How to evolve a permutation? (swap, sort)
in thread How to evolve a permutation?

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 ]

Comment on Re^2: How to evolve a permutation? (swap, sort)

Replies are listed 'Best First'.
Re^3: How to evolve a permutation? (swap, sort) by tye (Sage) on Feb 15, 2008 at 19:17 UTC
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	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^3: How to evolve a permutation? (swap, sort)
by tye (Sage) on Feb 15, 2008 at 19:17 UTC

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

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom