1
$\begingroup$

I have just been thinking about the simulated binary crossover (SBX) operator used in the NSGA-II algorithm and other real-valued genetic algorithms; and i am wondering if there is any reason that there always needs to be a crossover from both parents to both children? do both children need to be the "opposite" of each other in order to preserve diversity? or is it something that is just assumed?

As far as i can tell, the SBX operator seems to basically work by flipping a coin for each indexed element along a pair of strings to decide if the operator is called, and if the coin flip is successful, it generates a pair of values that are close to the original parent values in accordance with some probability distribution, and either swaps them between the children (p1_i->c2_i | p2_i->c1_i), or inserts them into their respective children (p1_i->c1_i | p2_i->c2_i).. but the key being, that the two offspring are always the "inverse" of eachother..

eg:
p1 = [4 6 2 0 3] p2 = [7 1 9 8 5]
c1 = [4 1 9 0 3] c2 = [7 6 2 8 5]

(to make my point easier to explain, i have omitted the fact that the child values are usually perturbed slightly from their original parent values when using SBX - ie. I am taking a child value of 2.2 to mean the same as a parent value of 2)

You can see, in this way, c1 is the "inverse" of c2. Is there any reason why both children can't take on the characteristics of the same parent (p1_i->c1_i | p1_i->c2_i)?

eg:
p1 = [4 6 2 0 3] p2 = [7 1 9 8 5]
c1' = [4 6 9 0 5] c2' = [4 1 2 0 5]

I think I understand why this isn't the case with standard binary crossover, as you are dealing with blocks of values, but with real valued crossover you are taking each individual element in the string separately, so why can't both children take on the same value with a certain probability?

The only reason that I can think of is that it might be in order to maintain a higher diversity among the child solutions; and if a solution such as c2' was required, then it must come from a different crossover event in the future.

Is my thinking on the right track? or is there another reason?

EDIT:
I suppose the solution to this would be to generate two potential child values per crossover but only one child, which tosses a coin to see which of the potential values it gets; however this would require twice the number of crossover operations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.