# Releasing Differentially Private Trajectories with Optimized Data Utility
## 4 Trajectory Synthesis
### Privately Selecting Utility-Optimized Candidate Obfuscated Locations
#### 4.3.2 Privately Selecting Candidate Obfuscated Locations  
The solutions of the multi-objective optimization problem include particle swarm, ant colony, and genetic algorithm [28]. Among these approaches, the genetic algorithm is well-known for its high performance. It is based on a natural selection process that mimics biological evolution. Recent work has demonstrated that accessing actual data without taking any privacy-protection measures could lead to compromise on individual privacy, so [PERSON] et al. [29] proposed a differentially private genetic algorithm. However, their work is not designed for high-dimensional data, such as trajectory, so we made an adaption, as follows, to support trajectory data. According to the multi-objective utility optimization problem defined in Equation (9), we define the objective function of the genetic algorithm, given by Equation (10), where \(\alpha\) indicates the data curator's preference on the geographical utility and \(1-\alpha\) the semantic utility. For example, suppose that the released data were used for early LBS that relied more on the geographical utility, e.g., points-of-interests extraction [30], then \(\alpha\) should be greater than \(1-\alpha\), namely, \(\alpha\in(0.5,1.0)\). The geographical distance and semantic distance in the equation are shifted and re-scaled so that they end up having the same range, \([0,1]\). \[q(L_{t}^{(opt)})=\alpha\sum_{i=1,l_{i}\in L_{t}^{(opt)}}^{M}dist_{sem}(l_{t},l _{i})+(1-\alpha)\sum_{i=1,l_{i}\in L_{t}^{(opt)}}^{M}dist_{sem}(l_{t},l_{i}) \tag{10}\]  
In addition, in the genetic algorithm, there exist four operations, namely, encoding, selection, crossover, and mutation. (i) The encoding operation represents the solution of the optimization problem by a location set. (ii) The selection operation randomly chooses one or more location sets that maximize the objective function from an intermediate set. (iii) The crossover operation randomly exchanges some locations in a location set with the counterpart in another location set. (iv) The mutation operation randomly replaces a location in a location set by another location. Note that the selection operation involves access to actual (private) data, thus it should be perturbed by random noise to ensure differentially private. In contrast, the other three operations only access the perturbed results, so no extra perturbation is required according to the post-processing property of differential privacy in Section 3. We formulate the procedure of privately selecting utility-optimized candidate obfuscated location set by Algorithm 3. ```
0: actual location \(l_{t}\), privacy budget \(e_{2}\), size of candidate obfuscated location set \(M\), number of intermediate sets \(m\), number of selected sets \(m^{\prime}\), number of iterations \(r\), the cluster \(C\) containing \(l_{t}\)
0: candidate obfuscated location set \(L_{t}^{(opt)}\)
1: // encoding operation
2: Initialize the intermediate set \(\Omega\) with \(m\) candidate obfuscated location sets randomly sampled from the cluster \(C\), where the size of each set is \(M\). 3:for\(i=1\) to \(r-1\)do
4: // selection operation
5: Initialize the selected set \(\Omega^{\prime}=\O\). 6:for each \(L_{t}^{(opt)}\in\Omega\)do
7: Compute \(\Pr(L_{t}^{(opt)})=\frac{\exp(\frac{\exp(l_{t}^{(opt)})}{2\Omega})}{\Sigma_{ L_{t}^{(opt)^{\prime}}\in\Omega}\exp(\frac{\exp(l_{t}^{(opt)})}{2\Omega})}\)
8:endfor
9: Randomly sample \(m\) sets from \(\Omega\) following \(\Pr(L_{t}^{(opt)})\) and put them into \(\Omega^{\prime}\). 10: Set \(\Omega=\O\). 11:for\(j=1\) to \(m^{\prime}/2\)do
12: Randomly select two sets \(L_{t}^{(opt)^{\prime}},L_{t}^{(opt)^{\prime\prime}}\in\Omega^{\prime}\). 13: // crossover operation
14: Randomly crossover \(L_{t}^{(opt)^{\prime}}\) and \(L_{t}^{(opt)^{\prime\prime}}\). 15: // mutation operation
16: Randomly mutate \(L_{t}^{(opt)^{\prime}}\) and \(L_{t}^{(opt)^{\prime\prime}}\). 17: Add \(L_{t}^{(opt)^{\prime}}\) and \(L_{t}^{(opt)^{\prime\prime}}\) into \(\Omega\).