Introduction to Soft Computing

Prof. Debasis Samanta

Department of Computer Science & Engineering
Indian Institute of Science, Kharagpur

Lecture – 21
GA Operator: Crossover (Contd.)

In this lecture, we shall try to learn the crossover technique; the crossover technique
applicable to the real coded GA.

(Refer Slide Time: 00:31)

Now, there are three broad techniques which are followed to perform the crossover operation
in case of real coded GAs. The three techniques are linear crossover, blend crossover, binary
simulated crossover. So, these cross over techniques are based on the different policies in
fact, so we learn the different policies that is here. Let us, first learn about linear cross over
technique for the real coated GA.
(Refer Slide Time: 01:00)

So, in this technique, we use some linear function that is why the name is called linear
crossover; linear function of the parent chromosomes to produce the new children. So, we can
discuss the technique better with an example; suppose, P1 and P2 are the two
parameter values in two parents, basically they are the 2, any 2 genes values belong to two
different parents P1 and P2 . Then, the corresponding offspring values say it is Ci

can be obtained using this formula. The formula says, that Ci =α i P1+ βi P2 . Here, P1 is

the gene values in parent P1 and P2 is the gene values for the parent P2 . So, it is

like this, if this is the chromosome belongs to one parent P1 and these are another
chromosome belongs to another parent P2 .

So, for any gene value this one and this one, so it is basically P1 and P2 . So, any two

value gene values this one and this one, we denote this as a P1 and we denote this as a
P2 . So, having this structure, so that means, we want to calculate the gene values for the

i th chromosome, which belongs to the i th children; that means, here one or more
children can be produced. So, here we are considering how from the two parents P1 and
P2 values the n number of children can be produced.

Now here, so the production is basically based on two parameters. These two parameters are
called α and β . For the i
th
children we will use αi and β i . So, these are the

values αi and β i , if you want to produce n number of children will be decided by the
user. So, it is give the responsibility decide the values of α and β s in order to produce
the children.

So, this is the formula that is there, this formula is basically for how this i th children's gene
value can be calculated.

(Refer Slide Time: 03:29)

So, let us have an example. Say suppose, this is the one gene value belongs to the parent
P1 and another gene value belongs to parent P2 is 18.83 and we are considering
several cases or different values of α and βs . So, first case, let us take this is the value
of α and β , in this case we take the two equal values which is 0.5 and then another
case, where we take another α and β value and then third instance we can consider this
one.

So, if we decide 3 set of values for α and βs , then we will be able to produce three
children. So, how the three children can be produced in terms of this α , β values and
given the gene values for the P1 and P2 is shown here. So, this is the first case, where
the α ∧β=1 . So, it gives this is the gene value and for the 2nd case the α =¿ 1.5 and
β=¿ - 0.5. So, it gives these values and the 3rd case α is - 0.5 and β is 1.5, it
will produce these value.
Now, so you have learned about how the linear function. So, these are the basically these are
the linear function that is followed here. So, these are the linear functions and in terms of
linear function we are able to calculate the children solution.

Now, here the different values of α , β has their own significance; have their own
significances for example, here if we take α , β like this, then we will see that the
children's value will be, so this is the parent value P1 and this is a parent value P2 . So,
if we take the α , β is like this, then the children will be within this. For example, in
this case the children value is this one.

Now, if we take α , β like this one, α is heavy then β too, then the children will
be beyond the P1 . Similarly, if we take this one α and β is this one, this case then it
will this one. So, depending on the different values of α and β , so the children solution
will be either here or here or here or within any regions, right within any point in the three
regions can be considered. So, that is the importance of the different values of α and β
. That means, if you have a good knowledge about the different what is called the values, a
range of values, then you will be able to generate the different children's accordingly.

(Refer Slide Time: 06:34)

So, this is the idea about linear crossover, it is a very simple, but it has many advantage as
well as limitation. The first is that, it is very simple to calculate because it uses a linear
function and calculation of a linear function is straight forward and that is why this technique
is very fast so for the computation is concerned and as we change the different values of α
and βs , we will be able to generate large set of offspring from only two parents. So, this is
the one advantage.

So, we can generate as many as solutions from the two parents and so this basically results
population exploration and then, controls are possible to choose a wide range of change
variations as I said in the last example, some values within the values P1 and P2 , some

values beyond P2 , some values beyond P1 . So, all these things can be possible, if we
choose the values of α , β properly.

Now, here these are the advantage of course, the simplicity is the most important advantage
in this case; however, it has certain limitation as well. The first limitation is basically the
programmer should decide the values of α , β s and that is really headache for the
programmer and in case of the programmer experience, then deciding right values for alpha
and beta is really tedious job for the inexperienced user and more serious limitation is that if
you do not choose the values properly, then the solution that will produce may leads to either
premature convergence or stuck into a local optimum. So, there is a chance that this solution
may not I mean with this cross over technique, the solution may not be optimum always. So,
this is the advantage and limitation for the linear crossover technique. Now, another
technique basically tried to address all those limitations, this technique is called the blend
crossover; blend crossover in real coded GA.

(Refer Slide Time: 08:32)

Now, we can explain this strategy like this, again will consider two gene values from parent
P1 and P2 , let they are represented as P1 and P2 and for simplicity will assume

that P 1< P 2 .

Then, the blend crossover scheme it basically objective of the screen to create the children
solution within the range, one is, this is the lower range and this is upper range within the
range P2−α ( P2−P1 ¿ and these are lower range and this is the upper range P2−α (
P2−P1 ¿ . Here, the α value is basically decided by the programmer; that means how
much you want to have the region wider or narrower, so that α value will decide.

So, it is basically is a constant and this constants should be decided by the programmer before
using this operation. Once the α value is known to us, then we will be able to follow this
technique.

(Refer Slide Time: 09:34)

Now, this technique is basically calculates another parameters; now we denote this parameter
as a γ and this parameter is denoted in terms of another random number r . So, α is
already known, r a random number is generated a random, this random number r
should be in the range 0.0 to 1.0 and then based on this r and α is already known to us,
will be able to decide the value of gamma.
So, basically gamma is, in this case, a random value inside because r , as it is r is a
random number and α is a constant, so gamma again it is a random number. Now, having
this gamma random number, any two children C1 and C2 can be calculated taking the
confidence of the gene values of P1 and P2 , which is shown here. For example, so
( 1−γ ) P1+ γ P2 and the another solution is ( 1−γ ) P2+ γ P1 . So, changing the values of
P1 and P2 like this, we will be able to calculate this one.

Now here, the unlike in case of linear crossover technique, we can generate a large number of
solutions C1 , C2 , C3 if we take the different random values in fact. So, taking the
different random values, we will be able to have the different γ values and the different
values will produce the different solutions according to this blend crossover technique. So,
this is the scheme in fact, in case of blend crossover technique.

(Refer Slide Time: 11:11)

Now, let us illustrate this technique with an example, here is a simple example, let the gene
value which is belongs to the parent P1 is this one and another gene value belongs to
parent P2 is this one, we consider alpha is 0.5 and gamma based on some random number,
which is not mentioned here say that gamma at the moment is obtained as 0.6.

Now, with this we will be able to calculate the C1 , that is ( 1−γ ) P1+ γ P2 - P1 and
this is basically the value that can be obtained for the one solution and another solution.
If we take some another random number, which will give an another γ , then another
solution can be this sides or another solution can be this sides can be obtained. So, this way
we will be able to generate a large number of solutions like a linear crossover, but only in
terms of a probabilistic way random number.

(Refer Slide Time: 12:11)

Now, so this is the plane cross over. Again, it has the limitation. It is also simple because it
also follows linear one equation for the calculation and like linear crossover, it is also known
to be a faster one technique and like linear crossover. It also produces a large set of offspring
from any two parent values and controls are possible because here the wide range of
variations can be possible, if we choose enough random number as we wish. So, this is the
limitation. Like linear crossover technique, it is also the, is a good point of this technique is
that it is simple and then fast.

However, it has the limitation, the first limitation is α , but again you can note that α
can be chosen with certain calculation, that how much the range that you want to have? So,
that α can be obtained little bit by a prior calculation and then so α calculation is not a
big issue. Now, so α the calculation can be done by some estimation, then γ also can be
done with the help of α values which are obtained and then just generating a random
number.
So here, α and γ can be decided, but it can be decided little bit calculated manner as it
is not possible in linear crossover. So, this is the one difference between linear crossover and
blend crossover. Again, for the inexperience user, deciding α is little bit difficult.
Although, it is not as such difficult as the linear crossover technique. So, it is little bit simpler
for the user to decide the α value in fact and obviously, the α and γ are the two
deciding values in order to decide the right chromosome values for the children. So, if we do
not decide α and γ values properly, then it may lead to premature convergence as well
as stuck to a local optimum solution. So, this is the blend crossover technique and we can
understand that it has little bit it, it is comparable you compare to the linear crossover
technique.

(Refer Slide Time: 14:37)

Now, we will discuss another technique. This is basically another statistical technique also
called and it is called the binary simulated crossover technique and so in the binary crossover
simulated techniques, the idea is more what is called a statistical in nature, is it gives I mean
variation; more variation compared to the linear and blend crossover. However, this technique
is little bit computationally expensive and you will discuss it about.

So, this scheme, the simulated binary crossover is based on the concept of probability
distribution and then, they basically follow certain probability distribution function to
generate the children solution, that is the one advantage and it has been observed that if we
use the probability distribution function rather than the simple random number as we have
discussed in blend crossover, it basically produce the better result and can avoid or can
address the premature convergence and then start to the local optima. So, this technique is
preferable in the sense that it gives better solution, then the solution that can be obtained
following the linear crossover technique and blend crossover technique.

Now, the basic idea in this technique is basically, it considers one factor, it is called the spread
factor. So, it is spread factor and denoted as alpha, the spread factor can be calculated by this
formula. We have to assume any two C1 and C2 , that means, how much variations in

the children's solution that you want to have and these a P1 and P2 are the input value

that you are having, then knowing or anticipating these are the C1 and C2 value, then
you can calculate α . So, α calculation is basically under your control that how much
division between the children solution that you want to have and decide, that will decide the
values of alpha. So, α is a little bit can be calculated, so in that case user does not have to
be an experienced user in fact.

So, once the α , the spread factor is calculated, then we will be able to calculate the
solution; children solutions which can be, which has the three different situation. So, will
discuss about the three cases.

(Refer Slide Time: 16:39)

So, three different cases mean if α < 1 , then the simulated binary crossover is called
contracting crossover, so in fact, in case the spread of children is less than the parent.
(Refer Slide Time: 16:57)

So, is basically if this is the parent P1 and parent P2 , then C1 and C2 will be

within this one. So, it is called the contract that means within the parent P1 and P2 .

On the other hand, case 2, if, so case 1 is basically α < 1, it is called the contracting
crossover. In this case, the P1 and P2 are the two parent values, then the C1 and
C2 can be obtained anywhere in between the parent and P1 and P2 .

Now, the second case is case 2, in this case α>1 and in this case it is called expanding
cross over. So, expanding crossover means if it is the P1 and P2 then C1 will be
calculated beyond P1 and P2 here or there.
(Refer Slide Time: 17:58)

So, these are the expanding and the 3rd case is if α =1 and eventually α =1 means
P1 , P 2 and then C1 and C2 . So, this is not a useful fact because it will not
produce any variation. So, usually this technique is not considered or the α =1 is not they
acceptable value. So, will consider only this is alpha using these two cases that is α<1
than 1 and α > 1 , that is either contracting cross over or we have to use a simulated binary
crossover as a expanding crossover.

Now, let us see, how the different crossover can be realised. Now, as I told you simulated
binary crossover basically follow a probability distribution function and so here actually the
probability distribution function you can choose any probability distribution function, but it is
recommended to follow the two specific probability distribution functions they are basically
called C ( α )∧E(α ) .

C (α ) the probability distribution function is usually followed for contracting crossover

whereas the E(α ) , the another probability distribution used for the expanding crossover.
Now, so the probability distribution function that it is followed in case of contacting
crossover is shown here. So, this is a function description for a given values of α ; α is
already known to us and they it consider q is a constant, the constant can be decided by
the user based on the users experience. Similarly, in terms of q if the α is known then
this is basically the another probability distribution function this one.
Now, here these are the two recommended probability distribution function, other probability
distribution function like Gaussian distribution or some other distribution function also can be
followed. Anyway, we will consider these are the two recommend probability distribution
function to calculate the children solution following the contracting crossover and then
expanding crossover, let us see how these can be done.

(Refer Slide Time: 19:59)

Now, we will consider the contracting crossover first. So, here basically the three steps are to
be followed. So, the first step is that, we have to generate a random number r , that is the
random number r . We, this is a first step; generate random number r in between 0 and
1.0, then we have to determine α ' , how the value of alpha dash can be determined? α'
is a value that can be determined using this function.

So, it is basically area, so if this is the probability distribution function and then area covered
by these value into 0 and α ' , so that this area is basically = r . So, if r <0.5 and in
case of if r , the random number that we have generated here, if it is ¿ 0.5 , then will
calculate this one.
(Refer Slide Time: 21:00)

So, it is basically in this case the distribution function it is like this, if this is the distribution
function and then it is basically say 1 and then it is basically α ' , then we will calculate
this α ' value following this expression, if this one.

Now here, so basically the idea is that the r <0.5 the chance that 50% will be belongs to
the contracting crossover and then r >0.5 that means, another 50% will have the chance to
have the expanding; what is called the expanding crossover. So, both way, both expanding
and then contracting cross over can be followed to calculate the two values α' according
to this distribution function. One α' is known to us, then any two children can be
calculated using this formula. So, this is the formula recommended by the developer of
simulated binary crossover, this is the formula you have to just follow it.

So, the formula says that is 0.5 and then value of P1 + P2 - α ' and then it is a what
is called the absolute difference between the parent values. Similarly, taking the + sign, the
another will be obtained. So, this way the two solution C1 , C2 can be obtained based
on the contracting as well as expanding depending r different values, so this way this they
will give. Now, here actually this technique is good, good because we do not have to take any
parameters that is required both in linear crossover as well as blend crossover except only the
calculation or computation. The computation because this operation or this operation is
basically is a computationally expensive operation, but if you able to do it right then all this
things are pretty simple and then it is useful and more effective; effective in the sense that it
gives better result compare to the linear crossover and then binary crossover technique.

(Refer Slide Time: 22:57)

Now, finally, I would like to give an illustration of the simulated binary cross over technique.
So, let us see these are the two parent gene values P1 and P2 and we assume q=2
is a defined constant that can be varied if you want to have the different results like, it is
basically the q value is decided by trial and error, that means, if you take very large values
of q whether it is quickly converged or if it is a small value then it can converge with a
better solution and all these things. So, here little bit experience of the user is required,
usually the user can gather experience by means of trial and error method, that means, they
have to run the same program for several cases with different values and for a certain value it
will be better result it is taken as that value as the standard value.

Anyway, so suppose q=2 known to you and then α' can be calculated based on the
random number generation and then the probability distribution function that we have
discussed and having these value for example, in this case, so r is 0.5 which gives α'
according to the expanding function, then the two values can be obtained, now one is C1
using the formula that we have already discussed and as I told you r >0.5 , so it is
expanding, that means, this is the P1 and P2 , it will calculate the chromosome any one
region within this region.
(Refer Slide Time: 24:32)

So, this is the idea about the simulated binary crossover techniques that is there and now,
simulated binary crossover has a number of advantages compared to the previous two
techniques that we have discussed and as in case of linear crossover and blend crossover in
this technique also, we will be able to generate large number offspring from 2 parents. So, in
that case what we have to do is that we have to generate as many as random number as many
we want to have the children's and it in fact allows more exploration with diverse values of
offspring, which is comparable to the both linear as well as the binary the blend crossover
technique.

Here the results, usually gives more accurate results compare to the linear and blend
crossover techniques and usually it gives the global optima, whereas other two techniques
usually stuck into the local optima and it basically terminates with a less number of iterations
because number of iterations that is required to run the GA is it is in fact, observe that more in
case of linear than blend crossover. So, in that sense it is also cost effective, although it is the
costly operation in case of crossover, but so far the GA iteration is concerned it require less,
so that means, effectively it is a faster GA algorithm than the crossover technique if we
follow linear and blend cross over technique.

And here, actually crossover techniques are independent of the length of the chromosome,
whatever be the values of the chromosome, that means, the parent values have many number
of gene absolutely no problem, we will be able to run effectively using the same techniques.
So, it is fast in that case because the same alpha dash that can be used to calculate the
different gene values for the chromosomes, if we take the different this one. So, in the same
line we will be able to follow, no need to discuss, no need to consider the different gene
'
values and the different α and then different random number generation, it is not required.
So, in one set the same α ' can be used to calculate the different gene values for the
offspring for the different parent values or different parent values of the different genes.

(Refer Slide Time: 26:46)

So, this is the advantage of this one. However, it is suffering for another limitation as well as
computationally expensive compared to the binary crossover technique. I am now comparing
not the linear crossover or blend crossover, but the binary cross over which we followed in
case of the binary coded GA. So, if we see, all the binary cross over techniques are very fast
and straight forward and pretty simple also, whereas this similar type binary crossover is little
bit computationally expensive.

Now, again there is a decision regarding the probability distribution function, if you do not
choose the proper probability distribution function or if you do not choose the q values,
that is required in case of I mean in probability distribution function decision, then you may
lead to an erroneous results and premature convergence. So, user needs to be little bit careful
about choosing the right values of probability distribution; right probability functions for
contracting as well as expanding function and also the correct values the q that is to be
used in the probability distribution function.
So, this is the technique that we have discussed so far the simulated binary crossover is
concerned and so we have so far discussed about the two different GA technique, one is the
binary coded GA, another is real coded GA and there are several crossover operations. We
have learned in binary coded GA and then, just now we have learned about the crossover
techniques in the real coded GA. There is another GA encoding scheme which we will
discuss, this is the order GA and we will discuss the crossover techniques that is required for
the order GA in the next class.

Thank you.