Crossover Techniques in GAs

Debasis Samanta

Indian Institute of Technology Kharagpur

dsamanta@iitkgp.ac.in

23.03.2024

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 1 / 58

Important GA Operations

1 Encoding
2 Fitness Evaluation and Selection
3 Mating pool
4 Crossover
5 Mutation
6 Inversion
7 Convergence test

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 2 / 58

Important GA Operations

1 Encoding
2 Fitness evaluation and Selection
3 Mating pool
4 Crossover
5 Mutation
6 Inversion
7 Convergence test

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 3 / 58

Reproduction in Genetic Algorithm

Reproduction:

Crossover

Mutation

Inversion

These genetic operators varies from one encoding scheme to another.

Binary coded GAs

Real-coded GAs

Tree-coded GAs

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 4 / 58

Mating Pool: Prior to crossover operation

A mating pair (each pair consists of two strings) are selected at

random. Thus, if the size of mating pool is N, then N2 mating pairs
are formed.[Random Mating]

The pairs are checked, whether they will participate in

reproduction or not by tossing a coin, whose probability being pc .
If pc is head, then the parent will participate in reproduction.
Otherwise, they will remain intact in the population. [Monte Carlo
Simulation]

Note :
Generally, pc = 1.0, so that almost all the parents can participate in
production.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 5 / 58

Crossover operation

Once, a pool of mating pair are selected, they undergo through

crossover operations.
1 In crossover, there is an exchange of properties between two
parents and as a result of which two offspring solutions are
produced.
2 The crossover point(s) (also called k-point(s)) is(are) decided
using a random number generator generating integer(s) in
between 1 and L, where L is the length of the chromosome.
3 Then we perform exchange of gene values with respect to the
k-point(s)

There are many exchange mechanisms and hence crossover

strategies.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 6 / 58

 Crossover Techniques in Binary Coded GA

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 7 / 58

Crossover operations in Binary-coded GAs

There exists a large number of crossover schemes, few important

of them are listed in the following.
1 Single point crossover
2 Two-point crossover
3 Multi-point crossover (also called n-point crossover)
4 Uniform crossover (UX)
5 Half-uniform crossover (HUX)
6 Shuffle crossover
7 Matrix crossover (Tow-dimensional crossover)
8 Three parent crossover

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 8 / 58

Single point crossover

1 Here, we select the K-point lying between 1 and L. Let it be k .

2 A single crossover point at k on both parent’s strings is selected.
3 All data beyond that point in either string is swapped between the
two parents.
4 The resulting strings are the chromosomes of the offsprings
produced.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 9 / 58

Single point crossover: Illustration

Before Crossover

Parent 1 : 0 1 1 0 0 0 1 0 Two diploid

from a
Parent 2 : 1 0 1 0 1 1 0 0 mating pair

Crossover Point - k

Select crossover points randomly

Two diploid
Offspring 1: 0 1 1 0 1 1 0 0
for two new
Offspring 2: offspring is
1 0 1 0 0 0 1 0
produced

After Crossver

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 10 / 58

Two-point crossover

1 In this scheme, we select two different crossover points k1 and k2

lying between 1 and L at random such that k1 ̸= k2 .
2 The middle parts are swapped between the two strings.
3 Alternatively, left and right parts also can be swapped.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 11 / 58

Two-point crossover: Illustration

Before Crossover

Parent 1 : 0 1 1 0 0 0 1 0

Parent 2 : 1 0 1 0 1 1 0 0

Crossover Point k1 Crossover Point k2

Select two crossover points randomly

Offspring 1: 0 1 1 0 1 0 1 0

Offspring 2: 1 0 1 0 0 1 0 0

After Crossver

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 12 / 58

Multi-point crossover

1 In case of multi-point crossover, a number of crossover points are

selected along the length of the string, at random.
2 The bits lying between alternate pairs of sites are then swapped.

k1 k2 k3

Parent 1 Offspring 1

Parent 2 Offspring 2

Swap 1 Swap 2

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 13 / 58

Uniform Crossover (UX)

Uniform crossover is a more general version of the multi-point

crossover.

In this scheme, at each bit position of the parent string, we toss a

coin (with a certain probability ps ) to determine whether there will
be swap of the bits or not.

The two bits are then swapped or remain unaltered, accordingly.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 14 / 58

Uniform crossover (UX): Illustration

Before crossover

Parent 1 : 1 1 0 0 0 1 0 1 1 0 0 1

Parent 2 : 0 1 1 0 0 1 1 1 0 1 0 1

Coin tossing: 1 0 0 1 1 1 0 1 1 0 0 1

After crossover

Offspring 1: 1 1 1 0 0 1 1 1 1 1 0 1

Offspring 2:
0 1 0 0 0 1 0 1 0 0 0 1

Rule: If the toss is 0 than swap the bits between P1 and P2

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 15 / 58

Uniform crossover with crossover mask

Here, each gene is created in the offspring by copying the

corresponding gene from one or the other parent chosen
according to a random generated binary crossover mask of the
same length as the chromosome.

Where there is a 1 in the mask, the gene is copied from the first
parent

Where there is a 0 in the mask, the gene is copied from the

second parent.

The reverse is followed to create another offsprings.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 16 / 58

Uniform crossover with crossover mask:
Illustration

Before Crossover

Parent 1 : 1 1 0 0 0 1 0 1

Parent 2 : 0 1 1 0 0 1 1 1

Mask 1 0 0 1 1 1 0 1

Offspring 1: When there is a 1 in the mask, the gene is

1 1 1 0 0 1 1 1 copied from Parent 1 else from Parent 2.

Offspring 2: When there is a 1 in the mask, the gene is

0 1 0 0 0 1 0 1 copied from Parent 2 else from Parent 1.

After Crossver

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 17 / 58

Half-uniform crossover (HUX)

In the half uniform crossover scheme, exactly half of the

non-matching bits are swapped.
1 Calculate the Hamming distance (the number of differing bits)
between the given parents.
2 This number is then divided by two.
3 The resulting number is how many of the bits that do not match
between the two parents will be swapped but probabilistically.
4 Choose the locations of these half numbers (with some strategies,
say coin tossing) and swap them.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 18 / 58

Half-uniform crossover: Illustration

Before crossover

Parent 1 : 1 1 0 0 0 0 1 0
Here, Hamming
distance is 4
Parent 2 : 1 0 0 1 1 0 1 1

Tossing: 1 0 1 1
If toss is 1, then swap the
bits else remain as it is

Offspring 1: 1 0 0 0 1 0 1 1

Offspring 2:
1 1 0 1 0 0 1 0

After crossver

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 19 / 58

Shuffle crossover

A single crossover point is selected. It divides a chromosome into

two parts called schema.

In both parents, genes are shuffled in each schema. Follow some

strategy for shuflling bits

Schemas are exchanged to create offspring (as in single

crossover)

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 20 / 58

Shuffle crossover: Illustration
Before crossover

P1 : 1 1 0 0 0 1 1 0

P2 : 1 0 0 1 1 0 1 1

K-point

P1' : 0 0 1 0 1 1 0 1
After shuffing bits
P2' : 0 1 1 1 0 1 0 1

Offspring 1: 0 0 1 0 1 1 0 1
Single point
Offspring 2: crossover
0 1 1 1 0 1 0 1

After crossver

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 21 / 58

Matrix crossover
The matrix crossover strategy is expained with the following illustration.

Rows..

I1: r11 r12 r13 r14 …... r1n

I2: r21 r22 r23 r24 …... r2n

P1: P2:
r11 r12 r13 r14 r21 r22 r23 r24 Two
dimensianal
..

..

..

..

..

..

..

..
representation
of the
..

..

..

..

..

..

..

..
chromosomes
..

..

..

..

..

..

..

..
r1n-3 r1n-2 r1n-1 r1n n×4
r2n-3 r2n-2 r2n-1 r2n n×4

Then matrices are divided into a number of non-overlapping zones

Two matrices
are divided
into a number
of non-
C1: C2: overlapping
zones and
shuffle
between them

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 22 / 58

Three parent crossover

In this techniques, three parents are randomly chosen.

Each bit of the first parent is compared with the bit of the second
parent.

If both are the same, the bit is taken for the offspring.

Otherwise, the bit from the third parent is taken for the offspring.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 23 / 58

Three parent crossover: Illustration

P1: 1 1 0 1 0 0 0 1

P2: 0 1 1 0 1 0 0 1

P3: 0 1 1 0 1 1 0 1

C1: 0 1 1 0 1 0 0 1

Note: Sometime, the third parent can be taken as the crossover mask.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 24 / 58

Comments on the binary crossover techniques

1 Non-uniform variation:
It can not combine all possible schemas (i.e. building blocks)

For example : it can not in general combine instances of

11*****1
and
****11**
to form an instance of
1 1 * * 1 1 * 1.

2 Positional bias:
The schemas that can be created or destroyed by a crossover
depends strongly on the location of the bits in the chromosomes.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 25 / 58

Comments on the binary crossover techniques

3 End-point bias:
It is also observed that single-point crossover treats some loci
preferentially, that is, the segments exchanged between the two
parents always contain the end points of the strings.
4 Hamming cliff problem:
A one-bit change can make a large (or a small) jump.
A multi-bits can make a small (or a large gap).
For example, 1000 =⇒ 0111
(Here, Hamming distance = 4, but distance between phenotype is
1)
Similarly, 0000 =⇒ 1000
(Here, Hamming distance = 1, but distance between phenotype is
8)

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 26 / 58

Comments on the binary crossover techniques

To reduce the positional bias and end-point bias, two-point

crossover and multi-point crossover schemes have been evolved.

In contrast, UX and HUX distribute the patterns in parent

chromosomes largely resulting too much deflections in the
offspring.

To avoid binary code related problem, gray coding can be used.

In summary, binary coding is the simplest encoding and its

crossover techniques are fastest compared to the crossover
techniques in other GA encoding schemes.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 27 / 58

 Crossover Techniques in Real Coded GA

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 28 / 58

Crossover techniques in Real coded GA

Following are the few well known crossover techniques for the
real-coded GAs.

Linear crossover
Blend crossover
Binary simulated crossover

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 29 / 58

Linear crossover in Real-coded GAs

This scheme uses some linear functions of the parent

chromosomes to produce the new children.

For example
Suppose P1 and P2 are the two parameter’s values in two parents,
then the corresponding offspring values in chromosomes can be
obtained as

Ci = αi P1 + βi P2
where i = 1, 2 · · · n (number of children).
αi and βi are some constants.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 30 / 58

Linear crossover: An example
Example :
Suppose P1 = 15.65 and P2 = 18.83
α1 = 0.5 = β1
α2 = 1.5 and β2 = −0.5
α3 = −0.5 and β3 = 1.5
Answer :
C1 = 0.5 × (P1 + P2 ) = 17.24
C2 = 1.5 × P1 − 0.5 × P2 = 14.06
C3 = −0.5 × P1 + 1.5 × P2 = 20.24

C2=14.06 C1=17.24 C3=20.42

10.0 P1=15.65 P2=18.83 25.0

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 31 / 58

Advantages and limitations

Advantages
1 It is simple to calculate and hence faster in computation
2 Can allow to generate a large set of offspring from two parent
values
3 Controls are possible to choose a wide-range of variations

Limitations
1 Needs to be decided the values of αi and βi
2 It is difficult for the inexperienced users to decide the right values
for αi and βi
3 If αi and βi values are not chosen properly, the solution may stuck
into a local optima.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 32 / 58

Blend crossover in Real-coded GAs

This scheme can be stated as follows.

1 Let P1 and P2 are the two parameter’s values in two parent’s
chromosomes, such that P1 < P2
2 Then the blend crossover scheme creates the children solution
lying in the range

⟨{P1 − α (P2 − P1 )} · · · {P2 − α (P2 − P1 )}⟩

where α is a constant to be decided so that children solution do
not come out of the range of domain of the said parameter.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 33 / 58

Blend crossover in Real-coded GAs

3 Another parameter γ has to be identified by utilizing the α and a

random number r in the range of (0.0, 1.0) both exclusive like the
following:
γ = (1 + 2α) r − α

4 The children solutions C1 and C2 are determined from the parents

as follows,
C1 = (1 − γ) P1 + γP2
C2 = (1 − γ) P2 + γP1

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 34 / 58

Blend crossover : An example

Example :
P1 = 15.65 and P2 = 18.83
α = 0.5 and γ = 0.6

New offspring
C1=16.60 C2=17.88

10.0 P1=15.65 P2=18.83 25.0

Parents

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 35 / 58

Simulated binary crossover in Real-coded GAs

This scheme is based on the probability distribution of generated

children solution from the given parents.

A spread factor α is used to represent the spread of the children

solutions with respect to that of the parents, as given below.
C1 −C2
α= P1 −P2

Here P1 and P2 are represent the parent points and C1 and C2 are
two children solutions.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 36 / 58

Simulated binary crossover in Real-coded GAs

Three different cases may occurs:

Case 1: α < 1 (Contracting Crossover)

The spread of children is less than the parents.

Case 2: α > 1 (Expanding Crossover)

The spread of children is more than the parents.

Case 3: α = 1 (Stationary Crossover)

The spread of children is same as that of the parents.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 37 / 58

Simulated Binary Crossover

Probability Distribution:

Case 1: For Contracting Crossover

C(α) = 0.5(q + 1)α2

Case 2: For Expanding Crossover

1
E(α) = 0.5(q + 1) αq+2

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 38 / 58

Simulated binary crossover in Real-coded GAs

Following steps are used to create two children solutions C1 and C2

from the parents P1 and P2 .
1 Create a random number r ∈ {0.0 · · · 1.0}
2 Determine α′ such that
R α′
0 C(α)dα = r , if r < 0.5
and
R α′
1 E(α)dα = r , if r > 0.5
3 Using the value of α′ obtain two children solution as follows
C1 = 0.5 [(P1 + P2 ) − α′ |P2 − P1 |]
C2 = 0.5 [(P1 + P2 ) + α′ |P2 − P1 |]

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 39 / 58

Simulated binary crossover in Real-coded GAs
Example:
P1 = 15.65
P2 = 18.83
q=2
α′ = 1.0772
Assuming expanding crossover with r > 0.5

offspring

C1=15.52 C2=18.95

10.0 P1=15.65 P2=18.83 25.0

parent

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 40 / 58

Advantages and limitations
Advantages
1 We can generate a large number of offspring from two parents.
2 More explorations with diverse offspring.
3 Results are accurate and usually terminated with global optima.
4 Termination with a less number of iterations.
5 Crossover techniques are independent of the length of the
chromosome.
Limitations
1 Computationally expensive compared to binary crossover.
2 If proper values of parameters involved in the crossover
techniques are not chosen judiciously, then it may lead to
premature convergence with not necessarily optimum solutions.
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 41 / 58
 Crossover Techniques in Order GAs

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 42 / 58

Crossover techniques in order GA
Any binary crossover techniques are not applicable to Order
coded GAs
Example
Reference: TSP
Consider any two chromosomes with Order-coded encoding scheme

A B C D E F G H
Before crossover

H G F E D C B A

K-point

A B C D E C B A
After Single point
binary crossover
H G F E D F G H

Here, the offspring are not valid chromosomes

Since, sequence of gene values are important, Real-coded

crossover techniques, which are to produce real number from two
given real numbers are also not applicable to Order-coded GAs.
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 43 / 58
Crossover techniques in order GA

Some important crossover techniques in Order-coded GAs are:

1 Single-point order crossover
2 Two-point order crossover
3 Partially mapped crossover (PMX)
4 Position based crossover
5 Precedence-preservation crossover (PPX)
6 Edge recombination crossover
Assumptions: For all crossover techniques, we assume the following:
Let L be the length of the chromosome.
P1 and P2 are two parents (are selected from the mating pool).
C1 and C2 denote offspring (initially empty).

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 44 / 58

Single point order crossover

Given two parents P1 and P2 with chromosome length, say L.

Steps:
1 Randomly generate a crossover point K such that (1 < K < L).
2 Copy the left schema of P1 into C1 (initially empty) and left
schema of P2 into C2 (also initially empty).
3 For the schema in the right side of C1 , copy the gene value from
P2 in the same order as they appear but not already present in the
left schema.
4 Repeat the same procedure to complete C2 from P1 .

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 45 / 58

Single point order crossover: Illustration

Example :

Crossover Point K

P1 : A C D E B F G H J I

P1 : E D C J I H B A F G

C1 : A C D E J I H B F G

C2: E D C J A B F G H I

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 46 / 58

Two-point order crossover

It is similar to the single-point order crossover, but with two k−points.

Steps:
1 Randomly generate two crossover points K1 and K2 . 1 < K1 ,
K2 < L
2 The schema in middle of P1 and P2 are copied into C1 and C2
(initially both are empty), respectively in the same location as well
as in the same order.
3 The remaining schema in C1 and C2 are copied from P2 and P1
respectively, so that an element already selected in child solution
does not appear again.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 47 / 58

Two-point order crossover: Illustration

Example :

K1 K2

P1 : A C D E B F G H J I

P1 : E D C J I H B A F G

C1 : E D C J B F G I H A

C2: A C D E I H B F G J

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 48 / 58

Precedence preservation order crossover

Let the parent chromosomes be P1 and P2 and the length of

chromosomes be L.
Steps:
(a) Create a vector V of length L randomly filled with elements from
the set {1, 2}.
(b) This vector defines the order in which genes are successfully
drawn from P1 and P2 as follows.
1 We scan the vector V from left to right.
2 Let the current position in the vector V be i (where i = 1, 2, · · · , L).
3 Let j (where j = 1, 2, · · · , L) and k (where k = 1, 2, · · · , L) denotes
the j th and k th gene of P1 and P2 , respectively. Initially j = k = 1.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 49 / 58

Precedence preservation order crossover

4 If i th value is 1 then
Delete j th gene value from P1 and as well as from P2 and
append it to the offspring (which is initially empty).
5 Else
Delete k th gene value from P2 and as well as from P1 and
append it to the offspring.
6 Repeat Step 2 until both P1 and P2 are empty and the offspring
contains all gene values.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 50 / 58

Precedence preservation order crossover :
Example

Example :

Random Vector σ 2 1 1 2 1 1 2 2 1 2

P1 : A C D E B F G H J I

P2 : E D C J I H B A F G

C1 : E C D J B F H A I G

C2: ?

Note : We can create another offspring following the alternative rule

for 1 and 2.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 51 / 58

Position-based order crossover

Steps :
1 Choose n crossover points K1 , K2 · · · Kn such that n ≪ L, the
length of chromosome.
2 The gene values at K1th , K2th · · · Knth positions in P1 are directly
copied into offspring C1 (Keeping their position information intact).
3 The remaining gene values in C1 will be obtained from P2 in the
same order as they appear there except they are already not
copied from P1 .
4 We can reverse the role of P1 and P2 to get another offspring C2 .

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 52 / 58

Position-based order crossover : Example

Let su consider three k −points namely K1 , K2 and k3 in this example.

K1 K2 K3

P1 : A C D E B F G H J I

P1 : E D C J I H B A F G

C1 : E C D J B I A H F G

C2: D E C B I F G A H J

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 53 / 58

Edge recombination order crossover

This crossover technique is used to solve TSP problem when the

cities are not completely connected to each other.

In this technique, an edge table which contains the adjacency

information (but not the order).

In the other words, edge table provides connectivity information.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 54 / 58

Edge recombination order crossover: Illustration
Example
Let us consider a problem instance of a TSP with 9 cities.
Assume any two chromosome P1 and P2 for the mating.

P1 : 1 2 4 6 8 7 5 3

P2 : 4 3 5 7 8 6 2 1

Connectivity graph:
2
6
1

4 8
3

7
5

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 55 / 58

Edge recombination order crossover: Illustration

Edge table for the connectivity graph:

City Connectivity

1 2 4 3

2 1 4 7 6
2
6
1 3 1 4 5

4 1 2 3 6
4 8
3
5 3 7 8
7
5 6 2 4 8

7 2 5 8

8 5 6 7

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 56 / 58

Edge recombination order crossover: Illustration
Steps:
Let the child chromosome be C1 (initially empty).
1 Start the child tour with the starting city of P1 . Let this city be X .
2 Append city X to C.
3 Delete all occurrences of X from the connectivity list of all cities
(right-hand column).
4 From city X choose the next city say Y , which is in the list of
minimum (or any one, if there is no choice) connectivity links.
5 Make X = Y [ i.e. new city Y becomes city X ].
6 Repeat Steps 2-5 until the tour is complete.
7 End
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 57 / 58
 Any questions??

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 23.03.2024 58 / 58