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 NchooseK bitstring 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

