# Metaheuristics for the Minimum Time Cut Path Problem with Different Cutting and Sliding Speeds
## 3 Evolutionary Metaheuristics for MTCP
### A BRKGA-Based Approach  
Genetic algorithms with random keys (RKGA) were introduced by [44] to deal with combinatorial optimization problems involving representation adapted to sequencing. In an RKGA, each chromosome is represented as a vector of real numbers in the range \([0,1[^{n}\), where \(n\) is the problem's dimension. A decoder receives a chromosome and maps it into a feasible problem solution. [PERSON] [45] proposed the Biased Random-Key Genetic Algorithm (BRKGA), in which the individuals are selected in the recombination process, and it also contains the highlighted function of the probability of inheriting information from the parents (\(p_{a}\)).  
This study used the BRKGA due to its tolerance to several optimization problems, assuming that two elements of its framework must be represented [46]: a compatible decoder, featured in this section, and a representative fitness function, trying to minimize Equation (1), for this problem. Figure 8 illustrates the BRKGA heuristic and its parameters: the size of the population (\(P\)), the proportion of the population in the elite (\(P_{e}\)), and the number of new random individuals that will be included in the new population (\(P_{m}\)).  
An important characteristic of BRKGA is the parameterized uniform crossover [47]. In this crossover type, one of the parents is extracted from the elite group, while the second parent is extracted from the non-elite set. This enables the BRKGA heuristic to mitigate a premature genetic convergence. On the other hand, it requires the calibration of the \(p_{a}\) parameter that can affect the overall performance. This peculiar parameter of the BRKGA ensures that the child individual inherits more characteristics of an elite parent. One parent is always selected (with replacement) from the elite solutions group, and the probability that the child inherits the key of the elite parent >0.5. According to [PERSON] [45], this is a differentiating factor in favor of faster convergence when compared to RKGA [44].  
Each gene in the chromosome representation for individuals in the BRKGA contains a real value in the range [0.1). For example, Figure 9 illustrates how random keys represent alleles for each chromosome. In our proposed strategy, the value of each gene \(chrom(i)\) was used by the decoder to determine the order and the cuts and movements' directions.  
Figure 8: A flowchart of BRKGA and parameters.  
Therefore, the decoder operated as follows: first, the initial \(n\) genes for each chromosome are sorted upwards, corresponding to the cut order. Then, for each of the remaining genes (\(n+1,\ldots,2n\)), the following function is used to determine the cuts' direction.  
\[f(chrom(i))=\left\{\begin{array}{ll}0,&\text{if }chrom(i)<0.5\\ 1,&\text{otherwise}\end{array}\right.\]  
Figure 9 presents the encoding process from random keys to process an individual. Note that this process depends on problem specifications. For this reason, we illustrated this process separately from Figure 8. The input module saves the SVG file (layout) information like the edges for a cut. The dimension of the array depends on such a value. It is noteworthy that the part of the vector representing the directions does not participate in the keys' ordering, being decoded only by the function _f(chrom)_. In this way, sorting random keys (ascending order of keys) results in the sequencing of edges visits. After that, the decoder presents a solution containing a sequence of movements for the input layout and the fitness function defined by Equation (1), which can calculate the time required for each individual.  
In this context, we use Section 4 to present our GA and BRKGA approaches' parameters and the cutting(\(\pi\)) and moving speeds(\(\mu\)), inherent in MTCP, for all computational tests applied.