Crossover operators play a very important role by creation of genetic algorithms (GAs) which are applied in various areas of computer science, including combinatorial optimization. In this paper, fifteen genetic crossover procedures are designed and implemented using a modern C# programming language. The computational experiments have been conducted with these operators by solving the famous combinatorial optimization problem – the quadratic assignment problem (QAP). The results of the conducted experiments on the characteristic benchmark instances from the QAP instances library QAPLIB illustrate the relative performance of the examined crossover operations.
All crossover procedures are publicly available with the intention that the GA researchers will choose a procedure which suits the individual demand at the highest degree.
Many optimization problems belong to the class of NP-hard problems (Garey and Johnson,
The GA developers are constantly seeking to enhance the performance of GAs. The goal is to create the genetic algorithms that are in competitive advantage with respect to other types of (meta)heuristic optimization algorithms. To achieve this goal, there is a high need in developing and investigating the essential “building components” of the genetic algorithms, among others, the crossover (recombination) operators (Herrera
The crossover operators (along with mutation operators) constitute the basis for successful functioning of GAs (Misevičius
In this paper, we consider, in particular, the genetic crossover operators of different kind and expose the results obtained from the numerical experiments with these operators. Although the principles of functioning of the majority of the considered operators are not new, the crossover implementations in modern C# programming language appear quite original. We also propose three innovative crossover operations.
First, we offer an enhancement of the so-called swap-path crossover – swap-path descent crossover – which benefits from taking into account the problem-specific information.
Second, the so-called universal crossover operator is proposed, where the goal is to provide more flexibility and versatility in the crossover process.
Third, a gene translocation procedure is introduced, which is non-traditional in the sense that it is based on “many-parents-many-children” approach, rather than a usual “two-parents-one-child” scheme.
All these crossover operators are publicly available for the researchers who want to contribute to the further progress of genetic and evolutionary computation.
The paper is structured as follows. Firstly, some definitions are given and basic features of the crossover operations are described. Then, the crossover operator details are provided. The newly proposed crossover operators are marked with the symbol ‘⋆’. Finally, the results of experimental comparison of the considered crossover procedures are presented. The paper is completed with concluding remarks.
In the most general case, the crossover process enables to transmit the genetic code of two or more agents (called parents) to one or more successors (called children) in a specified deterministic-like way. Ideally, in the crossover operation, the chromosomes of two parents are recombined in such a way that the child’s chromosome contains only the parents’ genes. This is the main distinguishing feature of crossover process and, thus, crossover operation is quite opposite to mutation, which is of pure stochastic nature. However, it should be noted that the crossover process can involve indirect randomness due to explicit and implicit mutations (Misevičius,
Let us consider (without a significant loss of generality) the crossover operators intended for the permutation-based combinatorial optimization problems. Remember that the permutation
Formally, the crossover operator must ensure that the offspring’s chromosome necessary inherits the genes which are common for both parents, i.e.:
Every element in the permutation is unique and the crossover operation should address this aspect. It doesn’t concern the bit strings. Meanwhile, in the case of permutations, some discrepancies are possible, i.e. the so-called “foreign” (random) genes may occur. This does not mean that the crossover is incorrect – simply, this is caused by specific properties of permutations.
A plenty of variants of various computer realizations of crossover operators exist, depending on the details and peculiarities of implementation. The most recent detailed surveys on crossover operators can be found in Umbarkar and Sheth (
This is very likely the most commonly used crossover operator for the genetic algorithms (Goldberg,
A slight disadvantage of the straightforward one-point crossover lies in tendency of having certain genes more “ordered” than others (compare, for example, the gene sequences “82396” and “1475” in Fig.
Graphical illustration of one-point crossover.
The two-point crossover works similarly to the one-point crossover, except that two crossover points
The principle of the uniform crossover is also simple (Syswerda,
The uniform crossover can be modified in such a way that the probability of the assignment of genes is no longer equal to
Graphical illustration of uniform crossover.
The shuffle crossover is obtained by randomly reordering the parents’ genes before applying the uniform crossover (Caruana
Graphical illustration of shuffle crossover.
Partially-mapped crossover (PMX) can be seen as a modified variant of the
Graphical illustration of partially-mapped crossover.
Swap-path crossover (SPX) (Glover,
Graphical illustration of fragment of swap-path crossover.
A modification to the standard SPX can be achieved when the best offspring (with respect to the fitness of the offspring The fitness of an individual is associated with the value of an objective function of an optimization problem.
The cycle crossover (CX) (Oliver
Graphical illustration of cycle crossover.
The cohesive crossover was proposed by Z. Drezner to efficiently recombine individuals’ genes by solving the quadratic assignment problem. In this case, the appropriateness of the genes – which is calculated according to the problem data – is taken into consideration. From the several recombinations of genes, the recombination is selected that minimizes the objective function. The details of implementation of the cohesive crossover are described in Drezner (
In the multi-parent crossover, several (or all) members of a population participate in creation of the offspring (Eiben
Graphical illustration of multi-parent crossover.
The probability
The swap-path descent crossover (SPDX) is similar to the heuristic swap-path crossover in that it takes into consideration the values of the objective function. The SPDX operator resembles the descent local search (hill-climbing) procedure in some sense. The advantage of this operator is in the dynamic evaluation of the offspring fitness: only the gene interchanges that improve the value of the objective function and lead to a better fitness of the offspring are accepted.
The universal crossover (UNIVX) distinguishes for its versatility and the possibility of flexible usage. It is somewhat similar to what is known in the literature as a simulated binary crossover (Deb and Agrawal,
Our operator is based on the use of a random mask. There are four controlling parameters:
The illustrative example of the universal crossover with the parameters
Graphical illustration of universal crossover.
So far, a single child is created from two or more parents. In the gene translocation (GT) procedure, many children are produced from many parents. The GT procedure is performed in an iterative way. The total number of iterations is equal to
An illustrative example of the GT procedure with the parameters
Graphical illustration of gene translocation.
We have conducted the computational experiments in order to compare the efficiency of the considered crossover operators. The experiments have been carried out on the basis of the difficult combinatorial optimization problem – the quadratic assignment problem (Çela, The source texts (in C# programming language) of the crossover operators for the QAP can be found at: http://www.personalas.ktu.lt/˜alfmise/.
1) one-point crossover – 1PX;
2) modified one-point crossover – M1PX;
3) two-point crossover – 2PX;
4) uniform crossover – UX;
5) quasi-uniform crossover – QUX;
6) shuffle crossover – SX;
7) partially-mapped crossover – PMX;
8) swap-path crossover – SPX;
9) heuristic swap-path crossover – HSPX;
10) swap-path descent crossover – SPDX;
11) cycle crossover – CX;
12) cohesive crossover – COHX;
13) multi-parent crossover – MPX;
14) universal crossover – UNIVX;
15) gene translocation – GT.
All the above crossover operators have been tested using the genetic algorithm, which was implemented in C# programming language by A. Misevičius and D. Kuznecovaitė. In this algorithm, the number of generations is equal to 100 and the population size is equal to 10. The crossover operators were run 10 times with the different chromosome pairs during each generation of GA (thus, each crossover procedure was run 1000 times on every benchmark instance). (The exception was gene translocation, which was run 100 times.) The experiments were performed on a 3.1 GHz personal computer.
In the experiments, we used the following criteria for the evaluation of the efficiency of the crossover operators: 1) the minimum deviation (
We have utilized two different types of benchmark instances: tai10a (
For the sake of more fairness, the following three different variants of the genetic algorithm were examined: 1) the standard genetic algorithm without mutation; 2) the standard genetic algorithm with a mutation procedure; 3) the hybrid genetic algorithm with an integrated local search procedure. Mutation is operationalized by the use of random pairwise gene interchanges, meanwhile the local search uses deterministic gene exchanges which improve the fitness of an individual.
Results of the comparison of crossover operators for the instances tai10a, tai10b (GA variant 1).
tai10a | tai10b | |||||||
11,01 | 20,80 | 25,69 | 17,28 | 24,29 | 30,20 | 62,58 | 49,54 | |
12,11 | 21,66 | 24,51 | 16,45 | 24,29 | 30,20 | 62,58 | 49,54 | |
19,99 | 24,50 | 16,67 | 13,80 | 41,98 | 46,44 | 38,18 | 32,95 | |
17,46 | 20,33 | 19,07 | 17,74 | 38,65 | 42,57 | 40,78 | 36,56 | |
21,57 | 26,17 | 15,21 | 12,29 | 47,02 | 52,74 | 34,48 | 27,47 | |
20,07 | 23,60 | 26,58 | 14,62 | 15,84 | 33,64 | 62,60 | 45,68 | |
15,50 | 18,09 | 21,00 | 19,98 | 30,37 | 35,31 | 47,82 | 43,88 | |
12,65 | 16,73 | 23,93 | 21,37 | 26,20 | 31,40 | 51,71 | 48,17 | |
18,28 | 22,63 | 31,27 | 15,53 | 21,33 | 30,25 | 56,60 | 49,48 | |
20,00 | 30,74 | 16,66 | 8,36 | 47,98 | 67,23 | 33,80 | 16,42 | |
20,86 | 22,50 | 57,09 | 58,93 | |||||
15,44 | 17,72 | 21,07 | 20,35 | |||||
21,37 | 24,44 | 15,39 | 13,85 | 52,82 | 54,88 | 30,51 | 25,70 | |
Results of the comparison of crossover operators for the instances tai10a, tai10b (GA variant 2).
tai10a | tai10b | |||||||
0,00 | 1,03 | 100,00 | 90,70 | |||||
0,43 | 1,94 | 73,42 | 68,97 | 0,00 | 1,08 | 100,00 | 90,62 | |
2,30 | 3,45 | 70,97 | 66,95 | 0,28 | 1,65 | 93,17 | 89,53 | |
0,00 | 0,96 | 100,00 | 90,84 | |||||
0,45 | 1,81 | 73,38 | 69,16 | |||||
2,30 | 3,66 | 70,97 | 66,68 | |||||
2,43 | 3,88 | 70,81 | 66,38 | 0,00 | 0,96 | 100,00 | 90,84 | |
0,64 | 2,07 | 73,13 | 68,81 | 1.65 | 2,58 | 91,11 | 88,80 | |
0,59 | 2,11 | 73,19 | 68,74 | 0,00 | 0,96 | 100,00 | 90,84 | |
0,00 | 0,95 | 100,00 | 90,86 | |||||
0,00 | 3,44 | 100,00 | 66,96 | 0,28 | 2,11 | 93,17 | 88,66 | |
3,33 | 5,24 | 69,67 | 64,62 | 0,00 | 1,05 | 100,00 | 90,68 | |
2,43 | 5,40 | 70,81 | 64,42 | |||||
2,43 | 4,18 | 70,81 | 65,99 | 0,00 | 0,96 | 100,00 | 90,84 | |
0,92 | 2,94 | 72,76 | 67,63 | 0,00 | 1,13 | 100,00 | 90,52 |
The obtained results of all performed experiments are presented in Tables
After analysis of the experimental results, the most essential observations are as follows.
The obtained results are very influenced by the size and nature of test data. The large instances are more difficult to solve when comparing to smaller instances. Also, it seems that the random medium- and large-scale instances are harder than their real life counterparts. This is true for all the crossover operators.
Results of the comparison of crossover operators for the instances tai30a, tai30b (GA variant 2).
tai30a
tai30b
5,82
6,68
16,40
13,28
4,18
4,63
93,32
91,85
6,73
7,22
15,44
12,71
7,56
7,67
98,49
86,32
5,49
6,93
16,75
13,01
12,42
12,89
82,07
77,53
6,39
7,28
15,80
12,65
4,17
5,01
93,33
91,14
6,83
7,59
15,33
12,32
6,51
7,55
15,67
12,37
5,35
5,60
91,62
89,94
7,15
7,57
15,00
12,35
6,74
7,04
89,64
87,45
7,94
8,28
87,98
85,25
4,51
5,73
17,00
13,97
6,30
6,76
15,89
13,20
9,49
10,77
95,88
88,00
9,11
9,26
96,38
83,55
6,68
7,88
15,50
12,02
7,77
7,85
98,21
86,01
6,84
7,76
15,33
12,14
12,72
12,83
81,70
77,62
7,60
8,21
14,54
11,68
9,13
9,41
96,36
84,30
Results of the comparison of crossover operators for the instances tai50a, tai50b (GA variant 2).
tai50a
tai50b
8,70
8,98
13,32
10,35
8,13
9,15
65,02
55,71
7,16
7,92
14,90
11,42
8,84
9,67
64,08
54,97
8,13
8,67
13,90
10,66
7,31
7,96
66,13
57,43
8,41
8,89
13,62
10,43
9,78
10,74
62,84
53,48
8,68
9,03
13,35
10,29
6,12
7,92
67,77
57,49
6,65
7,32
15,42
12,06
11,78
13,33
60,28
49,97
7,91
8,59
14,13
10,74
6,33
6,40
67,48
59,75
6,88
7,59
14,18
11,77
8,07
8,62
65,10
56,47
7,76
8,65
14,28
10,68
8,93
10,04
63,96
54,46
12,45
12,79
59,45
50,69
9,17
9,58
12,85
9,74
7,15
7,73
14,91
11,62
7,32
7,63
66,12
57,91
9,26
9,61
12,77
9,71
10,69
12,25
61,67
51,42
The main differentiation in the results is due to distinct configurations of the inner structure of the genetic algorithm, rather than due to the crossover operations themselves. Presumably, not only the crossover operator, but also mutation is important. The crossover enables to diversify the search process, it is explorative and can discover new regions in the search space. Meanwhile, the mutation allows to intensify the search process, it is rather exploitative and creates random, but small diversions staying near (in the neighbourhood of) the parent. Both have their role. They complement each other; there exists a mutual interaction between them, which increases the overall performance of the genetic algorithm.
Results of the comparison of crossover operators for the instances tai10a, tai10b (GA variant 3).
tai10a
tai10b
0,00
1,01
100,00
97,57
0,00
1,12
100,00
98,82
0,00
1,06
100,00
97,45
0,00
1,05
100,00
98,90
0,00
1,04
100,00
97,50
0,00
1,26
100,00
98,67
0,00
1,01
100,00
97,57
0,00
1,28
100,00
98,65
0,00
0,92
100,00
97,80
0,00
0,87
100,00
97,91
0,00
0,97
100,00
98,98
0,00
0,87
100,00
97,91
0,00
1,43
100,00
98,49
0,00
1,38
100,00
96,70
0,00
1,10
100,00
98,84
0,00
0,98
100,00
99,02
0,00
1,46
100,00
96,51
0,00
1,17
100,00
98,76
0,00
1,04
100,00
97,49
0,00
0,75
100,00
98,20
0,00
0,94
100,00
99,01
0,00
0,99
100,00
98,95
0,00
0,75
100,00
98,20
0,00
1,24
100,00
98,69
Results of the comparison of crossover operators for the instances tai30a, tai30b (GA variant 3).
textbftai30a
tai30b
2,12
2,26
88,83
89,18
0,19
0,26
99,68
99,75
1,55
1,96
91,83
90,60
0,17
0,30
99,71
99,71
1,40
1,51
97,66
98,56
1,28
1,70
93,23
91,84
2,04
2,65
89,21
87,31
1,40
1,62
97,65
98,45
1,43
1,53
92,47
92,66
0,00
0,05
100,00
99,95
1,45
1,84
92,35
91,17
1,40
1,46
97,66
98,61
3,00
3,84
84,14
81,56
1,70
2,79
97,16
97,34
0,00
0,08
100,00
99,92
2,24
2,75
88,15
86,80
1,40
2,07
97,65
98,03
0,94
1,27
95,05
93,91
2,22
2,54
96,29
97,58
1,00
1,42
94,72
93,18
1,59
1,94
91,62
90,69
1,39
1,86
92,66
91,07
0,11
0,20
99,82
99,81
The results clearly demonstrate that the hybrid genetic-local search algorithm outperforms the standard variant of the genetic algorithm with respect to all examined criteria. Thus, the deterministic intensification, i.e. local search, is evidently more helpful than the stochastic intensification, i.e. mutation.
The differences in the effectiveness of particular crossover operators are not statistically very significant. These differences are even more minimized if crossovers are tested in the “hybrid environment”. Still, it can be observed that the multi-parent crossover and especially the swap-path descent crossover – which uses the heuristic information – seem, on average, to be superior to other operators. Further experiments could be recommended in order to corroborate this observation.
Despite the limited extent of our experiments, the scope of applications of the considered crossover operators is not constricted to the permutation-based problems as long as bit-string genetic algorithms are utilized. Regardless of the differences of implementation, the principles of functioning of these crossovers (possibly with the exception of heuristic crossovers) are rather general and invariant. This is especially true for our proposed universal crossover that is straightforwardly replicable to bit-string GAs, which, in turn, are applicable to both combinatorial and continuous optimization problems.
Results of the comparison of crossover operators for the instances tai50a, tai50b (GA variant 3).
tai50a | tai50b | |||||||
2,47 | 2,67 | 86,91 | 86,82 | 0,41 | 0,44 | 99,28 | 99,37 | |
2,06 | 2,23 | 89,04 | 88,99 | 1,01 | 1,03 | 98,22 | 98,53 | |
2,60 | 2,76 | 86,17 | 86,38 | |||||
1,19 | 1,24 | 97,91 | 98,23 | |||||
1,97 | 2,10 | 89,56 | 89,65 | 1,24 | 1,27 | 97,82 | 98,19 | |
2,00 | 2,20 | 89,38 | 89,14 | 1,49 | 1,52 | 97,38 | 97,83 | |
1,78 | 2,23 | 90,53 | 89,01 | 0,78 | 0,81 | 98,63 | 98,84 | |
3,53 | 4,05 | 81,25 | 80,00 | 1,84 | 3,96 | 96,77 | 94,34 | |
2,55 | 2,85 | 86,45 | 85,93 | 0,60 | 0,68 | 98,94 | 99,03 | |
2,13 | 2,41 | 88,68 | 88,11 | 0,67 | 0,70 | 98,82 | 98,99 | |
2,44 | 2,52 | 87,06 | 87,57 | 0,63 | 0,64 | 98,90 | 99,08 | |
1,58 | 2,08 | 91,60 | 89,71 | 1,46 | 1,51 | 97,44 | 97,85 | |
1,83 | 2,10 | 90,26 | 89,63 | 0,46 | 0,48 | 99,20 | 99,31 |
In this paper, fifteen crossover operators for genetic algorithms were investigated. The investigation has been carried out on the quadratic assignment problem, which is a representative example of the challenging permutation-based combinatorial optimization problems.
We experimented with the point-based crossovers, uniform crossovers, shuffle crossover, partially-mapped crossover, swap-path crossovers, cycle crossover, cohesive crossover, multi-parent crossover, among others. In addition, we have introduced the enhanced swap-based crossover (swap-path descent crossover), in which the improvements of the values of the objective function are taken into consideration. Also, we propose the so-called universal crossover, which can be flexibly adapted to meet the requirements/requests of the algorithm’s user. Additionally, the gene translocation procedure is presented, in which many parents produce many children during each generation of the genetic algorithm.
We expect that the considered crossover procedures, along with the proposed new ones, will be beneficial for the solution of a wide class of optimization problems. Problem-oriented, heuristic crossover procedures seem to be a good alternative to canonical, general-purpose crossover operators. It also seems that the attention should be focused on the deterministic local search procedures, thereby capitalizing on the synergy of recombination (diversification) and intensification in genetic algorithms.