Crossover Operator — The Heart of Genetic Algorithm
Learn how to implement a crossover operator in python
History of the Genetic Algorithm (GA) dates back to the 1960s, and since then people around the world have used it to solve search and optimization problems. It is because the Genetic Algorithm is pretty easy to learn and has a faster rate of deployment. Therefore, the Genetic Algorithm has become one of the most popular algorithms for people from academics and industry.
Genetic Algorithm composes of three operators: Selection, Crossover, and Mutation. Each operator has its own role to play and is equally important. However, in this article, the focus is on the Crossover Operators and how to implement it in python with a simple example.
So, let's begin with the three most popular crossover operators.
Single Point Crossover Operator
“Information exchange at a single point”
In a single-point crossover, a crossover point is randomly generated which determines the point for exchange of information between parents to form children. For example, when the crossover point generated is 2, all information from index 3 onwards are exchanged between the two parents to form children, as shown below.
To implement the single-point crossover, the following python code can be used. A single_point_crossover function is defined where arguments A & B represent the parents, x denotes the crossover point, and A_new & B_new represent the children.
Multi-Point Crossover Operator
“Information exchange at multiple points”
In a multi-point crossover, multiple crossover points are randomly generated which determines the points for exchange of information between parents to form children. This results in the exchange of information between the crossover points.
To understand this in a simple fashion, consider 2 crossover points 2 & 6. And then perform single-point crossover at crossover points 2 & 6 sequentially on the parents to form children. Thus, a two-point crossover can simply be considered as a single-point crossover executed over two different crossover points.
Note: A two-point crossover is a multi-point crossover technique with two crossover points
To implement the two-point crossover, the following python code can be used. A multi_point_crossover function is defined where incoming arguments A & B represent the parents, X denotes an array of crossover points, and returning A & B represent the children. It can be observed that for each crossover point in X, single_point_crossover operation is performed.
Uniform Crossover Operator
“Information exchange based on probability”
In the uniform crossover, information exchange between parents takes place based on some probability values. A probability matrix of length same as the parents is randomly generated. If the probability value exceeds a predefined threshold at one or more index, information is exchanged at those indexes between parents to form children.
To implement the uniform crossover, the following python code can be used. A uniform_crossover function is defined where incoming arguments A & B represent the parents, P denotes the probability matrix, and returning A & B represent the children. It can be observed that the information between parents is exchanged at the indexes where probability is less than the threshold (0.5) to form children.
Note: Threshold values less or greater than 0.5 can be considered
BONUS: Other Crossover Operators across the Aisle
Besides these, there are many several other crossover techniques such as partially mapped crossover (PMX), cycle crossover (CX), order crossover (OX), etc. These techniques are much more complex compared to a single point and multi-point crossover technique.
Verdict!
So which one should one choose? Frankly, it depends on the problem you choose and the result you get. Usually, most people start with single-point crossover and move to multi-point or uniform crossover if any improvement is obtained. Further, custom crossover techniques can also be devised based on the problem. Hopefully, this helps.
Image Sources:
- Single, Two-Point and Uniform Crossover https://providing.blogspot.com/2015/06/genetic-algorithms-crossover.html?m=1
