CODEWITHSUNDEEP
genetic-algorithm
AMG CE
AMG CE

Reputation: 11

How do I apply order crossover in GA when genes in chromosomes are not unique?

In genetic algorithms (GA), order crossover (OX) typically applies to chromosomes with unique genes. According to this paper, OX is applied to chromosomes that look like this {3, 1, 2, 1, 1} using these instructions:

(a) Randomly choose two cut-off points in the string.

(b) Copy the elements of the first parent that are found between the two
    cutoff points in the first offspring.

(c) Copy the elements that still have not been included in the first offspring
    as follows:

    (c.1) Start from the second cutoff point of the second parent.

    (c.2) Copy the elements not included in the first offspring, respecting
          the order in which the elements appear in the second parent.

    (c.3) Once the list of the second parent is finished, continue with the
          first elements (as in a circular arrangement).

(d) The second offspring is created in a similar way (steps b and c), inverting
    the role of the parents.

The problem discussed in this paper is the generalized minimum spanning tree problem (GMSTP), where graph is divided to clusters of vertices and a MST needs to be constructed by only one vertex from each cluster. In the paper, each element in the chromosome represents a cluster, and each value of the element is the selected node of the cluster to construct the GMST.

OX preserves the order of genes in parent 2. That could be understood in e.g. when solving travelling salesman problem (TSP) using GA where each value of the chromosome represents a node (a city). However, when it comes to GMSTP, it is vague to me as the order of clusters is always the same.

[Edit]

Example on OX:

Parent1 = { 1 2 3 4 5 6 7 8 9 }
Parent2 = { 3 2 8 1 4 9 6 5 7 }

after 2 random cut-off points

Parent1: { 1 2 | 3 4 5 6 | 7 8 9 }
Parent2: { 3 2 | 8 1 4 9 | 6 5 7 }

Copy genes between the two cut-off points of the 1st parent
Child1:  { x x | 3 4 5 6 | x x x }

Copy the rest of genes of the 2nd parent starting from the 2nd cut-off point,
excluding genes already in the child as well as preserving order 
Child1:  { 1 9 | 3 4 5 6 | 7 2 8 }

(Do the same for Child2 swapping the parents)

Now, try to apply OX on this set of genes:

Parent1: { 3 1 2 1 1 }
Parent2: { 3 2 2 1 4 }

I do not see a way of doing that, however, researchers said they used OX here.

Upvotes: 0

Views: 722

Answers (1)

AMG CE
AMG CE

Reputation: 11

One way to implement OX on such chromosomes is to proceed as normal and if missing elements encountered, copy the original elements (from the 1st author's response on my question).

Solving the example in the question with the new instruction is as follow:

Parent1 = { 3 1 2 1 1 }
Parent2 = { 3 2 2 1 4 }

after 2 random cut-off points

Parent1: { 3 | 1 2 | 1 1 }
Parent2: { 3 | 2 2 | 1 4 }

Copy genes between the two cut-off points of the 1st parent
Child1:  { x | 1 2 | x x }

Copy the rest of genes of the 2nd parent starting from the 2nd cut-off point,
excluding genes already in the child as well as preserving order 
Child1:  { x | 1 2 | 4 3 }

Copy original values to the missing elements
child1:  { 3 | 1 2 | 4 3 }

The same for Child2 swapping the rules of the parents
child2:  { 3 | 2 2 | 1 3 }

Upvotes: 1

Related Questions