# Joint Power Charging and Routing in Wireless
## 3 Optimization Algorithms
### Joint Optimization of Routing and Charging
#### 3.2.4 Replacement  
After generating a new population through the crossover and mutation operators, an elitist model-based replacement is employed to update a certain number of individuals in the old population with the new generated individuals. The low-quality individuals with low fitness values in the parental population are replaced by their children in the next generation.  
Now, we have designed the key components of the GA operation, which are the individual encoding, population initialization, selection, crossover, mutation, and replacement operation. The joint optimization of routing and charging based on the GA is depicted in Algorithm 3, where \(G\) is the given number of generations, \(R\) is the population size, \(q_{c}\) is the crossover probability, and \(q_{m}\) is the mutation probability.  
```
Set \(g=1\).  Generate initiation population \(\mathcal{R}\) using Algorithm 2.  Calculate the fitness value of each individual in \(\mathcal{R}\) using Algorithm 1. while\(g\leq G\)do  Set \(\mathcal{R}^{\prime}=\Phi\). for\(i=1\)to\(R/2\)do  Select two parents \(p_{1}\) and \(p_{2}\) from \(\mathcal{R}\) using roulette wheel selection method. \(r_{2*i-1}=p_{1}\) and \(r_{2*i}=p_{2}\).  Cross \(r_{2*i-1}\) and \(r_{2*i}\) using single-point crossover strategy with probability \(q_{c}\), and produce two children \(r^{\prime}_{2*i-1}\) and \(r^{\prime}_{2*i}\).  Repair elements in \(r^{\prime}_{2*i-1}\) and \(r^{\prime}_{2*i}\) if needed.  Mutate \(r^{\prime}_{2*i-1}\) and \(r^{\prime}_{2*i}\) using mutation strategy with probability \(q_{m}\). \(\mathcal{R}^{\prime}=\mathcal{R}^{\prime}\cup\{r^{\prime}_{2*i-1},r^{\prime} _{2*i}\}\).  Calculate the fitness value of each individual in \(\mathcal{R}^{\prime}\). end  Set \(g=g+1\).  Replace the individuals with low fitness values in population \(\mathcal{R}\) with the children in offspring \(\mathcal{R}^{\prime}\) using Algorithm 1. end  Return the fittest individual in \(\mathcal{R}\).
```  
**Algorithm 3**Joint optimization based on genetic algorithm  
In the proposed GA-based optimization, the computational complexity is dominated by the complexity in evaluating the fitness of Algorithm 1, which has to be evaluated \(R\) times in each iteration. The time complexity for calculating the fitness function of the resident locations is \(O(N)\) within an iteration. Aside from this, a GA-based approach also depends on other factors, which are difficult to clearly enumerate, such as strategies to generate a new population, and the tolerance allowable for cumulative changes in the fitness values [40]. Excluding these parameters, the total complexity of our algorithm is \(O(G(NR+R^{2}))\). Similarly to that in [12; 19; 41], our algorithms are performed in an offline manner. We assume the algorithm is executed at the sink node until the optimal routing tree and charging schedule are obtained. After that, the obtained routing tree is sent back to all the sensors via broadcasting, and the resident locations and traveling path are sent to the mobile charger. To run our algorithm, the sink node needs to collect the ID and location of each sensor. After receiving the results, one sensor can quickly find its forward sensor by only exchanging its IDs with its neighbors.