## 4 Algorithm
### Discrete Particle Swarm Optimization
#### 4.2.3 Fitness Function  
The mutation and crossover operators can not only preferably maintain the population diversity, but also make offspring population maintain the preferable characteristics. As in nature, the difficulty of DPSO is to provide the possible driving mechanism for better individuals to survive. Figure 4: Illustration of crossover operation. Figure 3: Illustration of mutation operation. Evaluation is to associate each individual with a fitness value that reflects how good it is based upon its achievement of the objectives. The higher the fitness value of an individual is, the higher its chances of survival, reproduction and its representation in the subsequent generation are. As the problem (9) is a single-objective optimization one, we just use the energy consumed by the constructed tree, namely Equation (8), to evaluate relative merits of each particle, but the problem (10) is a multi-objective optimization one, so we cannot merely use single objective value like energy or lifetime to evaluate the particle. To our knowledge, there are a lot of methods to deal with multi-objective optimization problems such as the weighted-sum method, the compromise approach method, the utility-function method and so on. In this paper, the phenotype sharing function with Pareto conception [37] is adopted to comprehensively compute the fitness of the particle:  
_Definition 4 (Pareto Dominance)_: A vector \(v=(v_{I}\), \(v_{2}\),..., \(v_{n})\) is said to dominate \(u=(u_{I}\), \(u_{2}\),, \(u_{n})\) (denoted by \(u\prec v\)) if \(\forall i\in\left\{1,2,\cdots,n\right\},u_{i}\leq v_{i}\wedge\exists i\in \left\{1,2,\cdots,n\right\},u_{i}<v_{i}\). Based on Definition 4, a feasible solution \(v\) is said to be non-dominated with respect to the set \(\Omega\), if there does not exist another \(u\in\Omega\) such that \(u\succ v\). Furthermore, the feasible solutions that are non-dominated within the entire search space are called the Pareto optimal solutions. In this paper we call the particle \(i\succ j\) when there satisfies that:  
\[ \begin{array}{c}l\left(tree\left(i\right)\right)\geq l\left(tree\left(j \right)\right)\\ E\left(tree\left(i\right)\right)\leq E\left(tree\left(j\right)\right)\\ \left|E\left(tree\left(i\right)\right)-E\left(tree\left(j\right)\right) \right|+\left|l\left(tree\left(i\right)\right)-l\left(tree\left(j\right) \right)\right|\
eq 0\end{array}  \tag{17}\]  
where \(tree(i)\) represents the route tree structure decoded from the particle \(i\). _Definition 5 (Target Distance \(fd_{ij}\)): \(fd_{ij}\)_ is the distance between the two particles \(i\) and \(j\). Supposed that the distance has \(m\) dimensions which are noted as \(f_{i}d_{ij},f_{2}d_{ij}\),...,\(f_{m}d_{ij}\) respectively, and:  
\[ \begin{array}{c}f_{d_{ij}}=f_{i}d_{ij}+f_{i}d_{ij}+...+f_{m}d_{ij}=\left|f_ {i}\left(x^{i}\right)-f_{i}\left(x^{i}\right)\right|+\left|f_{z}\left(x^{i} \right)-f_{z}\left(x^{i}\right)\right|+...+\left|f_{n}\left(x^{i}\right)-f_{m} \left(x^{i}\right)\right|,i\
eq j.\end{array}  \tag{18}\]  
_Definition 6 (Dominance Measure \(D(i)\)): \(D(i)\)_ denotes the state of domination the \(i\)-th particle with respect to the current population, and:  
\[ \begin{array}{c}D(i)=\sum\limits_{j=1}^{p}nd\left(i,j\right)\end{array}  \tag{19}\]  
where \(nd(i,j)\) equals to one if particle \(j\) dominates particle \(i\), and zero otherwise. _Definition 7 (Sharing Function \(sh(fd_{ij})\))_:  
\[ \begin{array}{c}sh\left(f_{d_{ij}}\right)=\begin{cases}1,&\text{if }fd_{ij}\leq\sigma_{s}\\ 0,&\text{otherwise}\end{cases}\end{array}  \tag{20}\]  
where \(\sigma_{s}\) is a sharing parameter. _Definition 8 (The Neighbor Density Measure \(N(i)\)): \(N(i)\)_ associated with particle \(i\) is defined as:  
\[ \begin{array}{c}N\left(i\right)=\sum\limits_{j=1}^{p}sh\left(f_{d_{ij}}\right) \end{array}