# A Multi-Agent System for the Dynamic Emplacement of Electric Vehicle Charging Stations
## 3 Proposal and Methodology
### The Emplacement Optimizer Agent
#### 3.2.2 Genetic Algorithm  
Genetic algorithms consist of general algorithms of optimization and learning based on evolutionary processes present in nature. This type of algorithm gradually converges towards high-quality solutions through the application of a set of operators. Another characteristic of genetic algorithms is their ability to solve problems with near-optimal solutions in solution spaces where a brute force algorithm would take too long. In the case of searching for the best EV charging station configuration, if we had 100 potential locations (Pols) where we could place a EV charging station and we would like to select 20, we would have to analyze \(100!/(20!(100-20)! )=5.36\times 10^{20}\) possible configurations. Given this scenario, the fact of using a genetic algorithm allows us to use a heuristic dedicated to the stochastic search that reaches near optimal solutions. To solve the problem of the configuration of stations, we proposed a genetic algorithm that generates sets of solutions (i.e., generations), where each generation inherits the properties of the best solutions (i.e., configurations) of the previous one. Initially, the algorithm creates an initial random population of individuals \(N\). Each individual is a solution to the problem (i.e., configuration \(C_{i}\)) (see Figure 2). In the scenario of EV charging stations, the size of the chromosome is the number of possible locations, i.e., \(P\). The value of a gene within a chromosome indicates whether that location (\(p_{i}\)) will be used to locate one or more charging stations (\(s_{i}\)) or none. The fitness function evaluates the quality of the solutions, that is, the quality of the individual (i.e., configurations \(C_{i}\)). In our problem, the fitness function corresponds to the usefulness of placing charging stations in the selected points. This function considers different attributes described above (\(p_{i}=\{a_{1},a_{2},\ldots,a_{n}\}\)) balanced by weights. Genetic operators are applied to existing individuals to generate new individuals. The proposed genetic algorithm considers the following genetic operators:  
* Selection. The best individuals according to the fitness measure are selected to pass their genes to the next generation of the algorithm. This is done before applying the crossover operator. In our implementation, we used the tournament selection method, which creates several random groups of individuals, called tournaments, and selects the best one of each group. * Crossover. Two parents are selected and a new individual child is created by combining the genes of the parents. Among the different crossover methods that exists, we used the cross uniform, which swaps genes from parents taking a uniform number of genes from them. * Mutation. A new individual is generated by mutating some of the genes of a selected individual. This operator is used to maintain genetic diversity from different generations. Mutation is applied during evolution according to a probability which must be set low. The proposed genetic algorithm performs as follows (see Algorithm 1). Initially, a population is randomly generated. This population consists of a set of possible configurations of EV charging stations. During each iteration (i.e., generation) of the algorithm, a randomly selected genetic operator is applied to each individual in the population.