# Constrained Multi-Objective Optimization of Simulated Tree Pruning with Heterogeneous Criteria
## 2 Materials and Methods
### Optimization Method
```
1:Tree model \(\mathcal{T}\); heuristic constraints \([d_{\text{min}},d_{\text{max}}]\), \(A_{\text{max}}\), and \(m_{\text{min}}\); number of objective evaluations \(M\); objective functions \(\mathbf{f}\); meta-parameters \(\mathit{Ps},\mathit{Cr},\mathit{Mr},\mathbf{P}\) Output: non-dominated set of solutions \(\mathcal{X}\)
2:procedure\(\text{MO}(\mathcal{T},d_{\text{min}},d_{\text{max}},A_{\text{max}},m_{\text{min}},M, \mathbf{f},\mathit{Ps},\mathit{Cr},\mathit{Mr},\mathbf{P})\)
3:\(\mathcal{I}_{\text{cut}}\leftarrow\) list of possible cut locations in \(\mathcal{T}\) according to \([d_{\text{min}},d_{\text{max}}]\), \(A_{\text{max}}\), and \(m_{\text{min}}\)
4:\(\mathcal{P}^{(0)}\leftarrow\) initial population of random vectors \(\mathbf{x}_{i}^{(0)}(i=1,\dots,\mathit{Ps})\) sampled from \(\mathcal{I}_{\text{cut}}\)
5:\(\mathcal{X}\leftarrow\emptyset\)
6:for\(k=0\dots,M/\mathit{Ps}\)do
7:for\(\forall\mathbf{x}_{i}^{(k)}\in\mathcal{P}^{(k)}\)do
8:\(\mathcal{T}_{/x}\leftarrow\) prune \(\mathcal{T}\) according to \(\mathbf{x}_{i}^{(k)}\)
9:\(\mathbf{f}_{i}(\mathbf{x}_{i}^{(k)})\leftarrow\) evaluate \(\mathbf{f}\) on \(\mathcal{T}_{/x}\)
10:\(\mathcal{Y}\leftarrow\) non-dominated vectors in \(\mathcal{P}^{(k)}\)
11:\(\mathcal{Y}\leftarrow\) remove vectors from \(\mathcal{Y}\) that violate bounds of constraint objective \(f_{4}\)
12: update \(\mathcal{X}\) using \(\mathcal{Y}\)
13:\(\mathcal{P}^{(k+1)}\leftarrow\) apply evolutionary operators on \(\mathcal{P}^{(k)}\) using \(\mathit{Cr},\mathit{Mr}\) and \(\mathbf{P}\)
14:return\(\mathcal{X}\)
```  
**Algorithm 1** Multi-objective pruning optimization. The procedure then enters the optimization loop. The number of iterations \(N\) is either specified directly, or calculated from the maximum number of objective evaluations \(M\) as \(N=\frac{M}{\mathit{Ps}}\). Within the loop, three main steps are performed:  
1. The current population \(\mathcal{P}^{(k)}=\{\mathbf{x}_{i}^{(k)}\}\) is evaluated according to objectives \(\mathbf{f}\). 2. The set of non-dominated solutions is updated, using the constraint objective \(f_{4}\) to demote unsuitable solutions. 3. The next generation of solutions is produced by applying evolutionary operators to the current population. Evaluation of individual candidate solution \(\mathbf{x}_{i}\) is performed by pruning the tree model according to \(\mathbf{x}_{i}\), and computing the values of objectives on the resulting pruned tree. This  
Figure 4: Block diagram of the proposed multi-objective pruning optimization method. part of the computation is performed by the simulation model, and is independent of the used optimization algorithm. The set \(\mathcal{X}\) of non-dominated pruning solutions is updated next, which is a step that depends on the evolutionary method used. In NSGA-II, \(\mathcal{X}\) is updated with non-dominated solutions from the current population \(\mathcal{P}^{(k)}\). In SPEA2 and MOEA/D-EAM, the current archive \(\overline{\mathcal{P}}^{(k)}\) is used to update \(\mathcal{X}\) in each iteration. In both cases, solutions with objective value \(f_{4}\) below the prescribed limit are not included in \(\mathcal{X}\) even if non-dominated. The last step is the derivation of a new population \(\mathcal{P}^{(k+1)}\) from the current population \(\mathcal{P}^{(k)}\) using a method-dependent procedure. In all of our experiments, the following problem-specific implementations of evolutionary operators are used:  
* Selection of two parent vectors from the population (NSGA-II) or the mating pool (SPEA2 and MOEA/D-EAM). * Uniform crossover of parent vectors with probability \(Cr\). * Mutation of child vectors with change probabilities \(\boldsymbol{P}=\langle P_{\text{move}},P_{\text{add}},P_{\text{remove}}\rangle\) and mutation rate \(Mr\). The selection step is method-dependent. In NSGA-II [25] and SPEA2 [26], binary tournaments are used to select the parents from the population and the mating pool, respectively.