## 4 Design of Multi-Constraint Optimized Genetic Algorithm
### Task Planning Oriented Genetic Algorithm
#### 4.3.2 Optimized GA Operators under Multiple Constraints  
(1) Constrained population initialization  
As we all know, in GA, the first generation of population is always initialized randomly. The main advantage of this manner is that the diversity of population can be well guaranteed, similar to biological evolution. Of course, its disadvantage is also obvious that this manner may result in a long convergence time or even the failure of convergence. For this reason, we propose an initialization method with some constraints. Firstly, we employ a service status vector \(\lambda\) to record the status of all services in the pool, where \(|\lambda|\) is equal to the size of service pool, and each element \(\lambda[i]\) (\(i=1,2,...,|\lambda|\)) is initialized to be 0 (means available). When \(\lambda[i]\) is allocated to a chromosome bit, its value will be set to 1. Then, we employ **Constraint 8** to supervise the assigning procedure of a chromosome bit. it is obvious that via adjusting the value of \(\delta\), the randomness and certainty can be balanced. **Constraint 8 (Supervisory Assign)**: During initializing chromosomes of each populations, if and only if it exists at least one available service that corresponds to this bit, this bit can be set to 1 with a probability \(\delta\). (2) Hybrid selection operator  
Although the Roulette-wheel-selection is the typical mechanism in traditional genetic algorithms, it is not appropriate for this study because in the crossover and mutation operation, optimal individuals are easy to be eliminated, and the convergence speed of this mechanism is slow. To get rid of these potential problems, we designed a hybrid selection operator that gives full play to the advantages of both Binary Tournament selection and Elitist selection. As is well known, the obvious advantage of Binary Tournament selection is that it enables excellent individuals to enter the next generation of population with a greater probability, which is meaningful to speed up the evolution. On this basis, we further exploit the advantages of Elitist selection that it always replaces a certain number of individuals in the offspring population with some optimal individuals in the parent population. This is very important to guarantee the convergence. Of course, too much substitution will destroy the diversity of the offspring population, which may lead to the local optimal solution. Therefore, this proposed operator just replace the worst individuals in the offspring population with the best of its parent. (3) Constrained adaptive crossover operator  
To guide evolution in the direction of convergence, we designed a constrained adaptive crossover operator on the basis of adaptive crossover and one-point crossover [52]. Firstly, the adaptive crossover will dynamically adjust the crossover probability according to the maximum value, minimum value and average value of fitness of individuals in current population. In addition, as the average fitness value of the evolving population increases, the crossover rate decreases. In this study, we adopt Formula (6) to calculate the probability of crossover \(P_{c}\), where \(f_{max}\), \(f_{avg}\), and \(f_{min}\) represent the maximum, average, and minimum fitness values separately. Secondly, to guarantee the diversity of individuals and also the structure of cluster-based chromosome, this operator will cross two individuals in chromosome pieces, rather than bits. Additionally, the two offspring produced by crossover will compete with these two parents to enter the next generation population, the better two individuals will be selected into new generated population. \[P_{c}=\left\{ \begin{array}{ll}\frac{P_{c1}\times(f_{avg}-f^{\prime})+P_{c2} \times(f^{\prime}-f_{min})}{f_{avg}-f_{min}}&f^{\prime}<f_{avg}\\ \frac{P_{c2}\times(f_{avg}-f^{\prime})+P_{c3}\times(f^{\prime}-f_{avg})}{f_{ max}-f_{avg}}&f^{\prime}\geq f_{avg}\end{array} \right.