Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Vectorization Help...I think
Date: Sun, 18 Jul 2010 05:10:06 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 65
Message-ID: <i1u2be$sdc$1@fred.mathworks.com>
References: <i1sreb$6fs$1@fred.mathworks.com> <i1suli$mtn$1@fred.mathworks.com> <i1t9vc$k9s$1@fred.mathworks.com> <i1tcv2$m3m$1@fred.mathworks.com> <i1tpaj$kl0$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1279429806 29100 172.30.248.35 (18 Jul 2010 05:10:06 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sun, 18 Jul 2010 05:10:06 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:653969

"Jonny O'Connell" <jonnydotoconnelldotx@gmail.com> wrote in message <i1tpaj$kl0$1@fred.mathworks.com>...
> > ......
> >   I think there is much more that you can tell us about the statistics of your problem that would be useful in giving you reliable advice.
> > Roger Stafford
> 
> Okay I'll try and put what I'm doing into a bit of context. This function takes two permutations of size n (size normally in the range 100-500) generated using the 'randperm' function, to be the firstParent and secondParent.
> 
> Lets say we have the two parents:
> First:     8 7 6 4 1 2 5 3 9 10
> Second: 2 5 1 7 3 8 4 6 10 9
> 
> Taking a randomly selected starting point, that element from the first parent is copied into an 'offspring'. So say this algorithm chooses to start at index 3, 6 is copied into location 3 of an offspring.
> 
> Offspring: - - 6 - - - - - - -
> 
> The algorithm then looks at index location 3 in the second parent, and finds 1. It locates 1 in the first parent and copies that into the offspring, at its first parent index of 5.
> 
> Offspring: - - 6 - 1 - - - - -
> 
> It repeats, looks at index 5 in the second parent and finds 3. 3 is located in the first parent at index 8 and copied too the offspring.
> 
> Offspring - - 6 - 1 - - 3 - - 
> 
> Now when the algorithm comes onto the next loop of the cycle, and checks index 8 of the second parent it finds 6 which is the value it started with. At this point the cycle halts and any empty spaces are filled with values from the second parent.
> 
> Offspring: 2 5 6 7 1 8 4 3 10 9
> 
> My entire function to achieve this:
> 
> function offspring = cycle_crossover(firstParent, secondParent)
>    
>     % Initilisation of starting point and output matrix
>     seedNumber = randi(length(firstParent), 1, 1);
>     offspring = zeros(1, length(firstParent));
>     offspring(seedNumber) = firstParent(seedNumber);
>     currentNumber = seedNumber;
>     cycleIndex = 0;
> 
>     % Perform swapping until cycle is complete
>     [~, locations] = ismember(secondParent, firstParent);
>     while cycleIndex ~= seedNumber;
>         cycleIndex = locations(currentNumber);
>         offspring(cycleIndex) = firstParent(cycleIndex);
>         currentNumber = cycleIndex;
>     end
>     
>     % Keep remaining items in their original location  
>     zeroLocations = ismember(offspring, 0);
>     offspring(zeroLocations) = secondParent(zeroLocations);
> end
> 
> 
> I changed the 'copy remaining items' section code also based on what Bruno provided, and that too seemed to speed up significantly.
> 
> For the scenario laid out, is that how you believe the code should look?
> 
> Thanks again!
> 
> Jonny
- - - - - - - - - -
  If you are sure that both firstParent and secondParent will be permutations on the same integers 1 to n, that would take care of the two difficulties I listed earlier.  However, much more importantly than that, it should not be necessary to use ismember with its order n*log(n) algorithm in that case.  By taking the inverse of one of these permutations applied to the other one you can easily provide the equivalent of the 'location' array that ismember would otherwise furnish, and inverses of permutations require only an order n algorithm.  If n were large that could make an important difference in computation time required.

  I haven't worked out the details yet.  If in general you will need to use firstParent and secondParent arrays that are not restricted in the above respect, please let me know before I go to all the trouble of figuring it out.  My aging brain cells object to doing unnecessary work these days.

Roger Stafford