# A Grid-Based Swarm Intelligence Algorithm for Privacy-Preserving Data Mining
## 4 Proposed MOPSO-Based Framework for Data Sanitization
### Evolution Process  
In the second evolution process, the particles are then evaluated to obtain better solutions for the next iteration. In an MOPSO-based framework, each particle can be represented as a possible solution with \(MDT\) vectors, and each vector has a transaction ID, which shows the transaction for deletion. Note that a vector in a particle can have a _null_ value. In the updating stage of the evolutionary process, the formulas are thus defined as follows:  
\[v_{i}(t+1)=(pbest-x_{i}(t))\cup(gbest-x_{i}(t)), \tag{12}\]  
\[x_{i}(t+1)=rand(x_{i}(t),null)+v_{i}(t+1). \tag{13}\]  
In the updating process, the designed GMPSO handles data sanitization in PPDM as a discrete problem. Thus, several parameters used in a traditional PSO are unnecessary in the designed GMPSO. For the updating process, the TIDs within the elder particle or _null_ value are then randomly chosen to fill in the size of the particle, which is shown in Equation (12). The results are then summed with the updated velocity of the particle, which is shown in Equation (13). This method increases the randomization of the exploration ability during the evolution process. For instance, supposing that the particle size is set as 4, a particle is initially set as \(x(t)\) = [1, 2, 5, 8]; _gbest_ is initially set as [0, 4, 0, 5], and _pbest_ is initially set as _pbest_ = [2, 1, 0, 6]. Note that 0 represents a _null_ value, which indicates that a non-transaction is selected for deletion. Thus, the particle can be updated as follows: \(v(t+1)\) = [[1, 2, 5, 8] - [2, 1, 0, 6]] \(\cup\) [[0, 2, 0, 5] - [1, 2, 5, 8]] = [5, 8] \(\cup\) [0] = [5, 8, 0]. Because the size of a particle is set as 4, we then randomly select one transaction from its elder content as \(rand(1, 2, 5, 8)\) (= 1). Thus, the particle is updated as [5, 8, 0, 1]. Because the MOPSO-based framework is used to solve a multi-objective problem, the _pbest_ of each particle cannot be simply determined based on the fitness value. Thus, the non-domination relation is adapted to obtain _pbest_ during the updating process. The local updating strategy is defined as follows:  
**Strategy 1** (Local Updating Strategy, LUS). : \[ \begin{split} pbest&\leftarrow\begin{cases}x(t+1)& \text{if}\,f(x(t+1))\succ f(pbest),\\ rand(x(t+1),pbest)&\text{otherwise.}\end{cases}\end{split} \] (14)  
Thus, if the current particle dominates its last _pbest_, the _pbest_ can be replaced by the current particle; otherwise, a random selection is then conducted to select a particle as _pbest_ for the next iteration. To obtain _gbest_, a global updating strategy is then designed to obtain a better updating solution during the evolution process. Using the designed GMPSO algorithm, a grid-based method is then assigned to a set of candidate particles, and each particle is then assigned with a probability based on the number of grids and the number of the particles in each grid. A random function is then performed to choose one of the candidate particles as _gbest_ based on their assigned probability. The global updating strategy can be stated as follows:  
**Strategy 2** (Global Updating Strategy, GUS). : \[ \begin{split} gbest\gets rand(p_{prob}).\end{split} \] (15)  
Without loss of generality, the multi-objective optimization problem with \(n\)-objectives (\(n\geq 2\)) to be minimized can be defined as:\[minf(x)=[f_{1}(x),f_{2}(x),\ldots,f_{n}(x)]^{T}, \tag{16}\]  
which is subject to \(\{g_{i}(x)\leq 0,i=1,2,\ldots,n_{g}\}\) and \(\{h_{j}(x)=0,j=1,2,\ldots,n_{h}\}\), and \(x\in\mathbb{X}\). Moreover, \(x\in\mathbb{X}\) is the vector of optimization variables; \(\mathbb{X}\subset\mathbb{R}^{n}\) is the optimized domain, which can be defined by the Cartesian product of the domain of each optimization variable. \(f(\bullet):\mathbb{X}\mapsto\mathbb{R}^{m}\) is the objective functions of the problem; \(g(\bullet):\mathbb{X}\mapsto\mathbb{R}^{n_{g}}\) and \(h(\bullet):\mathbb{X}\mapsto\mathbb{R}^{n_{h}}\) represents, respectively, the inequality and equality constraints of the problem.