# Spectrum Allocation Based on an Improved Gravitational Search Algorithm
## 3 Technologies
### Algorithms
#### 3.2.2 GSA in IGSA  
The GSA, one of the high-efficient heuristic search algorithm, was first proposed by [PERSON], et al. in 2009 [19]. GSA is inspired by the Newtonian law and follows the motion law. In GSA, a particle is an agent of spectrum allocation solution, the process of finding the global optimal solution for objective functions that are transformed into movement in which all agents move towards the agents with heavier mass.Therefore, the position of an agent which is heaviest will be the close-to-optimal global allocation solution.  
Assuming a GSA system with \(N\) agents, position and velocity of the \(i\)-th agent can be defined as:  
\[X_{i}^{t}=(x_{i,1}^{t},x_{i,2}^{t},\ldots,x_{i,d}^{t},\ldots,x_{i,D}^{t}) \quad i=(1,2,\ldots,N), \tag{9}\]  
\[V_{i}^{t}=(v_{i,1}^{t},v_{i,2}^{t},\ldots,v_{i,d}^{t},\ldots,v_{i,D}^{t}) \quad i=(1,2,\ldots,N), \tag{10}\]where \(x_{i,d}^{t}\), \(v_{i,d}^{t}\) are respectively the position and velocity of the \(i\)-th agent in \(d\)-th dimension of \(t\)-th generation. The velocity of an agent in the next iteration is considered as a fraction of its current velocity added to its acceleration. Therefore, its position and its velocity could be calculated as follows:  
\[x_{i,d}^{t+1}=x_{i,d}^{t}+v_{i,d}^{t+1}, \tag{11}\]  
\[v_{i,d}^{t+1}=rand_{i}\times v_{i,d}^{t}+a_{i,d}^{t}. \tag{12}\]  
Moreover, resource allocation is actually a binary issue, nevertheless, the original GSA is a continuous algorithm for solving a continuous problem. Hence, the sigmoid function is adapted to design a binary gravitational search algorithm for settling the binary issue. Then a new update model for position and velocity is proposed:  
\[x_{i,d}^{t+1}=\begin{cases}1&rand()<S(v_{i,d}^{t+1}),\\ 0&rand()\geq S(v_{i,d}^{t+1}).\end{cases} \tag{13}\]  
\[sig(v_{i,d}^{t})=\frac{1}{1+exp(-v_{i,d}^{t})}, \tag{14}\]  
where \(rand_{i}\) is a uniformly distributed random number in the interval \([0,1]\); \(a_{i,d}^{t}\) is the acceleration of \(i\)-th agent in \(d\)th dimension at \(t\) time:  
\[a_{i,d}^{t}=\frac{F_{i,d}^{t}}{M_{i}^{t}}, \tag{15}\]  
\(F_{i,d}^{t}\) is the force exerted by the remaining population upon agent \(i\) at \(t\) time:  
\[F_{i,d}^{t}=\sum_{j\in\textit{Kbest},t,j\
eq i}rand_{j}G^{t}\frac{M_{j}^{t}M_{i }^{t}}{R_{i,j}^{t}+\epsilon}(x_{i,d}^{t}-x_{i,d}^{t}), \tag{16}\]  
\[R_{i,j}^{t}=||X_{i}^{t},X_{j}^{t}||, \tag{17}\]  
\[G^{t}=G(G_{0},t), \tag{18}\]  
\[G^{t}=G_{0}\times e^{-\frac{\mu}{t}}, \tag{19}\]  
where _Kbest_ is the set of first \(k\) agents with the best fitness value. \(R_{i,j}^{t}\) denotes the euclidian distance between agent \(i\) and \(j\). \(\alpha\) is a constant. \(G^{t}\) is the gravitational constant. \(t\) and \(T\) are the current iteration times and maximum iteration times. A heavier agent has a stronger attraction to others; the mass of each agent is obtained by calculating the fitness value of the agents. The mass of \(i\)-th agent \(M_{i}^{t}\) is updated as  
\[m_{i}^{t}=\frac{f_{i}^{t}-f_{\textit{worst}}^{t}}{f_{\textit{best}}^{t}-f_{ \textit{worst}}^{t}}, \tag{20}\]  
\[M_{i}^{t}=\frac{m_{i}^{t}}{\sum_{j=1}^{N}m_{j}^{t}}, \tag{21}\]  
where \(f_{i}^{t}\) represent the fitness value and mass of agent \(i\) at \(t\) time. Futhermore, \(f_{\textit{worst}}^{t}\) and \(f_{\textit{best}}^{t}\) are the worst and the best fitness value in all agents at \(t\) time, respectively:  
\[f_{\textit{worst}}^{t}=\min_{j\in\{1,2,\ldots,N\}}f_{j}^{t}, \tag{22}\]  
\[f_{\textit{best}}^{t}=\max_{j\in\{1,2,\ldots,N\}}f_{j}^{t}. \tag{23}\]