# Solution Algorithms for the Capacitated Location Tree Problem with Interconnections
## 4 CLTPI Solution Algorithms
### Biased Random-Key Genetic Algorithm (BRKGA)  
[PERSON] [35] first proposed Random-Key Genetic Algorithms for solving combinatorial optimization problems. Combinatorial optimization problems, by their nature, are integer-based, meaning that variables must take integer values. The algorithm encompasses a population of random vectors that encode the solution to the stated problem. Later, [PERSON] and [PERSON] [36] introduced the BRKGA, or Biased Random-Key Genetic Algorithm, for the first time. The BRKGA has been widely used in the context of combinatorial optimization problems like bin-packing problems [37], routing problems [38], clustering problems [39], regression testing [40], scheduling problems [41], and many other problems. Since the BRKGA has proven to be efficient in solving combinatorial optimization problems, frameworks and libraries have been developed, like the ones by [PERSON] and [PERSON] [42], [PERSON] et al. [43], [PERSON] and [PERSON] [44], and [PERSON] et al. [45], among others.  
The BRKGA has also been used in facility location and network design problems. In the context of facility location problems, it is essential to mention the works by [PERSON] [46], [PERSON] et al. [47], and [PERSON] et al. [48]. In the context of tree problems, there are also relevant works like the ones by [PERSON] et al. [20] and [PERSON] et al. [49].  
Random vectors are generally represented in the interval \([0,1]\) and are called chromosomes. Through the algorithm, a population evolves for several iterations (generations). In such algorithms, up to \(L\) populations with \(np\) individuals can be used, which evolve independently for a certain number of generations (\(IG\)). At this point, the best members of each population are introduced into the other populations to diversify them. This process is repeated every \(IG\) generation.  
On the other hand, bias in such algorithms is introduced by giving greater priority to parents with a better value in their objective function to pass on their genes to their descendants. The BRKGA starts by generating an initial population, \(IP\), of random vectors, \(v\), with values in the interval \([0,1]\). Then, every vector \(v_{i}\) in the population \(IP\) is subjected to a decodification procedure that returns a fitness value, \(fv_{i}\). Using \(fv_{i}\), the vectors \(v_{i}\) are sorted in ascending (minimization function) or descending (maximization function) order. Once ordered, the first \(p_{e}\) members are selected as the elite members of the population. The population \(IP\) in the generation \(g\) has \(p_{e}\) elite members and \(np-p_{e}\) non-elite members. To create the population \(IP\) in the next generation, \(g+1\), all elite members in the \(g\) generation are copied without modification. Then, a small number of \(p_{m}\) mutants is randomly generated and introduced into the population \(IP\). The other \(np-p_{e}-p_{m}\) individuals are created by using crossover. Crossover is performed by always using an elite member as a parent. The other parent could be either a non-elite or an elite member of the population. Elite parents have a greater priority, \(0.5>\rho_{e}<1\), to pass on their genes to a descendant. Figure 2 shows a graphical description of how the next generation \(g+1\) is created from the current generation \(g\).  
The BRKGA evolves until a stop criterion is met. The most common criterion is to stop after a given number of iterations without improvement is reached. In Figure 3, the flowchart of the BRKGA algorithm is shown.