Genetic Algorithms: Crossover

The method of crossover remains fairly constant regardless of the problem and scope. Crossover is achieved by first selecting a crossover point within a pair of defined and unique organisms P1 and P2 (which are the equivalent of parents for the crossed over parent). The chromosomes are then split at the selected crossover point. The second half of P2 (P2H2)  is then appended to the first half of P`1  (P1H1) to make one child chromosome (C1). The second child (C2) is made by appending the second half of P1 (P1H2) to the first half of P2 (P2H1). There are bound to be duplicate nodes in each of the halves, so, in that case it is necessary to take a random node from the graph that isn’t present in either of the halves of the chromosomes that are be crossed over. Below is an example of two parent chromosomes being crossed over:

Screen Shot 2015-08-06 at 1.00.55 AM

As witnessed, crossover is a fairly static process in TSP. However the method of determining a crossover point per pair of parents to be crossed over can be dynamic in one of two ways:

  1. Random Crossover Point – In this method the crossover point is found by selecting an arbitrary random point within the middle 50 percent of the chromosome.
  2. Strict Center Crossover Point – In this method the crossover point is always the same for every crossover operation. The crossover point is the median of the chromosome.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s