# Solving the Container Relocation Problem by Using a Metaheuristic Genetic Algorithm
## 4 A New Method for CRP Resolving Based on Genetic Algorithm
### A New Method for CRP Resolving
#### 4.2.4 Genetic Operators  
The genetic operators, crossover and mutation, are applied to the chromosomes selected in the selection procedure. The crossover operator crosses the genes of two selected chromosomes. In this way, two new chromosomes are created, each consisting of mixed genes from their parents. In this paper, the crossover with one crossover point is used, because it performs faster than any other type of crossover. Before performing the crossover, the crossover point must be determined. If the chromosome consists of \(n\) genes, the crossover point has a value in the range between 2 and n \(-\) 1. The value of the crossover point is determined by a random function. The pseudo code for the crossover process of our method is shown in Algorithm 3.  
```
1 Procedure crossover Data: C1 -- the vector of dimension \(|GN|\) representing the chromosome; C2 -- the vector of dimension \(|GN|\) representing the chromosome; \(GN\) -- number of genes within the chromosome; Result: X -- the vector of dimension 2 containing two chromosomes after crossover process
2 C1 -- Vector (\(GN\)); C2 -- Vector (\(GN\)); crossPoint -- randomNumber (1, \(GN\) - 2); // crossPoint -- the value of gene index from where the crossover begins for i -- 0 to crossPointdo
3 C1 -- C1? C2? C2? C2? C2? C1? C2? C1? C2? C1? C2? C1? C2? C1? C2? C1? C2?
```  
**Algorithm 3** Pseudo code of crossover process.  
An example of the crossover procedure is shown in Figure 10.  
At the beginning, chromosome1 has the values (3, 1, 0, 3, 0, 1, 3, 2, 0, 1) and chromosome2 has the values (0, 2, 3, 0, 2, 2, 2, 1, 3, 0). The crossover point is assigned the value of 4 (crossover is performed for genes on indices 5 to 9) by using a random number function. After performing the crossover operator between these chromosomes, the genes at indices 5 to 9 are interchanged, resulting in two new chromosomes: chromosome1 -- with values (3, 1, 0, 3, 0, 2, 2, 1, 3, 0) and chromosome2 -- with values (0, 2, 3, 0, 2, 1, 3, 2, 0, 1).  
The mutation operator mutates the genes of a chromosome (solution), i.e., changes the values of some genes within the chromosome to obtain a better chromosome than the original one. Before the mutation is performed, the index of the gene(s) that will be mutated must be defined. If the chromosome consists of n genes, the index can have a value between 1 and n. In addition, the probability of mutation must be defined (usually the probability is less than 5%). The pseudo code for the mutation process of our method is shown in Algorithm 4.  
Figure 11 shows an example of a mutation process. At the beginning, the chromosome has the values (3, 1, 0, 3, 0, 1, 3, 2, 0, 1). The index of the mutated gene gets the value 4 by using random number function. After performing the mutation operator on the mutated gene, the chromosome' has the values (3, 1, 0, 3, 3, 1, 3, 2, 0, 1).  
Figure 10: The one-point crossover example.  
What is important to emphasize, after mutation and crossover, is that all generated chromosomes remain feasible as potential solutions for the current CRP that is being solved. As stated before, the length of the chromosome (the number of genes) must be slightly longer relative to the number of containers within the bay considering the possibility of genes appearing within chromosomes that are not valid. In this way, any chromosome obtained by mutation, crossover or random generation remains feasible as a potential solution to the current CRP.