# A Two-Stage Co-Evolution Multi-Objective Evolutionary Algorithm for UAV Trajectory Planning
## 2 Related Research Background
### Constrained Multi-Objective Optimization Problem  
Unlike unconstrained single-objective optimization problems, constrained multi-objective optimization problems (CMOPs) need to satisfy different constraints and optimize multiple objectives, which are usually coupled and in competition with each other, i.e., an increase in the performance of one optimization objective may cause a decrease in the performance of other optimization objectives.  
The final solution of CMOPs is not just an optimal solution but a set of Pareto-optimal solutions consisting of compromise solutions [16; 17; 18]. CMOPs originated for the determination of the optimal design, modeling, and planning of complex systems, and they are now widely used in a variety of practical works, such as the design of urban bus routes [19], the optimization of the gait of bipedal robots [20], the resource allocation and scheduling of unmanned aerial vehicles, etc., [21]. CMOPs can be defined as follows [22; 23]:  
\[\begin{array}{ll}\text{Minimize}&F(x)=\left(f_{1}(x),\ldots,f_{m}(x)\right)^{ \text{T}}\\ \text{subject}&x\in S,\\ &g_{i}(x)\leq 0,i=1,\ldots,p\\ &h_{j}(x)=0,i=p+1,\ldots,q\end{array} \tag{1}\]where \(F(x)\) denotes the objective function vector, \(f_{m}(x)\) denotes m simultaneous optimization objectives to be optimized. \(x=\left(x_{1},\ldots,x_{n}\right)^{T}\) is the n-dimensional decision vector, \(n\) is the number of decision variables, \(x\in S,S\) denotes the search space, and \(g_{i}(x)\) and \(h_{j}(x)\) are the \(i\)-th inequality and \(j\)-th equation constraints, respectively. \(p\) denotes the number of inequality constraints, \(q\) is the number of constraints.  
For solution \(x\), its overall constraint violation (CV) can be calculated as follows:  
\[\mathrm{CV}(x)= \sum_{i=1}^{p}\max\{0,g_{i}(x)\}+\sum_{j=p+1}^{q}\max\{0,\left|h_{ j}(x)\right|-\eta\} \tag{2}\]  
where \(\eta\) is a very small positive value, usually \(\eta=10^{-6}\), and it converts an equality constraint to an inequality constraint. If \(CV(x)=0\), then solution \(x\) is a feasible solution; otherwise, \(x\) is a non-feasible solution. Meanwhile, the dominance relationship is the focus of multi-objective evolutionary algorithms (any two decision variables \(x,y\in\Omega\)) if the following is true:  
\[\left\{\begin{array}{ll}f_{i}(x)\leq f_{i}(y),\ \forall i\in\{1,2,\ldots,m\} \\ f_{j}(x)\leq f_{i}(y),\ \forall j\in\{1,2,\ldots,m\}\end{array}\right. \tag{3}\]  
Then, \(x\) is said to dominate \(y\), which is denoted as \(x\prec y\). If \(x\) and \(y\) do not dominate each other, then \(x\) and \(y\) are said to be Pareto non-dominated.  
Figure 1 is a schematic diagram of a CMOP for generating feasible solutions. Figure 1 represents the constrained multi-objective decision space. Figure 1 represents the objective space; the blue points within the elliptical dashed lines represent the Pareto-optimal solutions, and the red curves represent the Pareto front. Note that the set of Pareto-optimal solutions refers to the constrained subset of the decision space, while the Pareto front is composed of the constrained subset in the objective function space.