Vectorization Help...I think
in [Matlab]
|
From: Roger Stafford on 18 Jul 2010 01:10 "Jonny O'Connell" <jonnydotoconnelldotx(a)gmail.com> wrote in message <i1tpaj$kl0$1(a)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
From: Roger Stafford on 18 Jul 2010 02:34 "Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <i1u2be$sdc$1(a)fred.mathworks.com>... > "Jonny O'Connell" <jonnydotoconnelldotx(a)gmail.com> wrote in message <i1tpaj$kl0$1(a)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 - - - - - - - It didn't strain my brain cells as much as I feared. In place of [~, locations] = ismember(secondParent, firstParent); just put locations = 1:n; locations(firstParent) = locations; % <-- Gets inverse of firstParent locations = locations(secondParent); and voila, you have the same 'locations' array as with 'ismember'. (This is of course assuming that 'firstParent' and 'secondParent' are both permutations on 1:n.) Each of these three lines is an order n algorithm, so for large n they should be faster than 'ismember'. The 'ismember' function is intended for more difficult problems where the two arguments are not merely the same set in different orderings. Also it unnecessary to replace the zeros in 'offspring' with original values from 'secondParent'. Just copy 'secondParent' over to 'offspring' in the beginning and your while loop will later simply replace those that are encountered with 'cycleIndex' while the rest remain as the original 'secondParent' values. No need to do 'ismember' here either. That gives you an overall order n algorithm. Roger Stafford
From: Bruno Luong on 18 Jul 2010 03:47 Completely agree with Roger. If firstParent and secondParent are independent uniform permutations as generated with RANDPERM, then firstParent and locations are also independent uniform permutations. So further simplification would be generating firstParent and locations with RANDPERM, then obtaining secondParent by indexing: n = 100; firstParent = randperm(n); locations = randperm(n); secondParent = firstParent(locations); % then pass firstParent and locations (instead of secondParent) on your algorithm. Bruno
From: Jonny O'Connell on 18 Jul 2010 10:46
Thanks very much to you both! I've made the changes and they all work great! I can't unfortunately use the first and second parent generation you referred to Bruno as only on the first loop of my entire algorithm are they truly random, after that they evolve. I'll be honest it was a bit confusing what you were both saying, but stepping through it with the debugger for a while and I got there in the end! I appreciate you both going to the time to not only help me, but to also explain what you were doing. I'm a firm believer in teach a man to fish etc.. :) Thanks again, Jonny |