Code covered by the BSD License  

Highlights from
Speeding Up Optimization Problems with Parallel Computing

image thumbnail

Speeding Up Optimization Problems with Parallel Computing

by

Stuart Kozola

 

Files from the webinar: Speeding up optimization problems with parallel computing

Editor's Notes:

This file was selected as MATLAB Central Pick of the Week

crossoverNcK(parents,options,GenomeLength,FitnessFcn,unused,thisPopulation)
function xoverKids  = crossoverNcK(parents,options,GenomeLength,FitnessFcn,unused,thisPopulation)
% Oren Rosen
% 4/1/2008
% Copyright 2008 The MathWorks, Inc.
%
% This function is used for the N-choose-K bit-string genetic algorithm.
% The crossover algorithm is written to work on a population of length N
% bitstrings, each with exactly K bits equal to one. The children that are
% produced from each pair of parents will have the same bits for every
% element they agree on, and random choices of zeros and ones for
% the elements they don't agree on. The random choices are made in a way
% that the "K bits equal to one" constraint is automatically satisfied.
%
% This implementation was a quick and intuitive way to structure this
% function. It is by no means optimized and the end user is encouraged to
% experiment with other methods.

% How many children to produce?
nKids = length(parents)/2;

% Allocate space for the kids
xoverKids = zeros(nKids,GenomeLength);

% To move through the parents twice as fast as the kids are
% being produced, a separate index for the parents is needed
index = 1;

% *** Initialize ***
% Assumes all members of thisPopulation have the same number of ones.
num1s = sum(thisPopulation(1,:));
indexVec = 1:GenomeLength;
    
% for each kid...
for i=1:nKids
    
    % *** Get parents ***
    r1 = parents(index);
    index = index + 1;
    r2 = parents(index);
    index = index + 1;
    
    p1 = thisPopulation(r1,:);
    p2 = thisPopulation(r2,:);
    
    % *** Find Matching 1's and 0's ***
    % Ex: If           p1 == [ 1 0 1 0 0 1 1 0 0 0 ]
    %                  p2 == [ 1 0 0 1 0 0 1 0 1 0 ]
    %     Then matching1s == [ 1 0 0 0 0 0 1 0 0 0 ]
    %     Then matching0s == [ 0 1 0 0 1 0 0 1 0 1 ]
    matching1s = ~xor(p1,p2) & (p1 == 1);
    matching0s = ~xor(p1,p2) & (p1 == 0);
    
    % *** Find Matching Indices ***
    %     If       matching1s == [ 1 0 0 0 0 0 1 0 0 0 ]
    %              matching0s == [ 0 1 0 0 1 0 0 1 0 1 ]
    %     Then matching1sIndx == [ 1 7 ]
    %          matching0sIndx == [ 2 5 8 10 ]
    %         nonmatchingIndx == [ 3 4 6 9 ]
    matching1sIndx = indexVec(matching1s);
    matching0sIndx = indexVec(matching0s);
    nonmatchingIndx = setdiff(indexVec,[matching0sIndx,matching1sIndx]);

    % *** Create Child ***
    % Ex: If   num1s == 4
    %          matching1sIndx == [ 1 7 ]
    %          nonmatchingIndx == [ 3 4 6 9 ]
    %     Then numMatching1s == 2
    %     num1sToFill == 2
    %     Indx1sToFill == 2 random choices from [ 3 4 6 9 ]
    numMatching1s = numel(matching1sIndx);
    num1sToFill = num1s - numMatching1s;
    Indx1sToFill = randsample(nonmatchingIndx,num1sToFill);

    % *** Fill in 1s ***
    % Ex: If               p1 == [ 1 0 1 0 0 1 1 0 0 0 ]
    %                      p2 == [ 1 0 0 1 0 0 1 0 1 0 ]
    %     Then xoverKids(i,:) == [ 1 0 ? ? 0 ? 1 0 ? 0 ]
    %     With exactly 2 of the '?' equal to 1, the rest 0.
    xoverKids(i,matching1sIndx) = 1;
    xoverKids(i,Indx1sToFill) = 1;
end

Contact us