# A Simulated Annealing Algorithm for the Generalized Quadratic Assignment Problem
## 3 Methods
### Simulated Annealing Algorithm  
As stated earlier, the objective of this research is to present simple but very effective approximation algorithms for solving real-world, large-size GQAP instances quickly without spending a lot of time setting the algorithm parameters. Therefore, an SA algorithm is developed for the GQAP, since it requires setting fewer algorithm parameters, compared to many of the other algorithms available in the literature. Furthermore, it is easier to implement (i.e., understand and code) compared to other algorithms. The proposed SA heuristic algorithm is a direct application of SA to the GQAP, and it attempts to solve the COP model given in Equations (9) and (10) using the solution representation in Equation (8). Unlike complete enumeration which considers all possible \(N^{M}\) solutions, SA considers exploring different areas of the solution space effectively, since it is computationally intractable to explore the entire solution space even when \(N\) (number of locations) and \(M\) (number of facilities) are relatively small. For example, if \(M=15\) and \(N=10\), there are \(1.0\times 10^{15}\) possible solutions. In summary, the proposed SA algorithm explores areas of the solution space as follows. Given an initial solution \(\mathbf{S_{0}}\), solutions near this solution (i.e., in the neighborhood of solution \(\mathbf{S_{0}}\)) are explored by performing an operation (or move) on \(\mathbf{S_{0}}\). There are two types of moves. 1. Shift move consists of changing the assigned location of a facility to a different location. For example, in a solution \(\mathbf{S_{0}}\), an assignment which assigns facility \(i\) to location \(k\) (i.e., \(s(i)=k\)) is changed where facility \(i\) is reassigned to a different location \(k^{\prime}\) (i.e., \(s(i)=k^{\prime}\)) which gives the neighboring solution \(\mathbf{S}\);
2. Swap move consists of exchanging the assigned locations of two facilities assigned to different locations (e.g., in a solution \(\mathbf{S_{0}}\), \(s(i)=k\) and \(s(j)=l\) are changed to \(s(i)=l\) and \(s(j)=k\) which gives the neighboring solution \(\mathbf{S}\)). The proposed SA algorithm randomly selects only one move to perform at each iteration. If a move produces an infeasible solution based on location capacity constraints (10) in the COP model, then another randomly generated move is selected until the move produces a feasible solution \(\mathbf{S}\). The solution \(\mathbf{S}\) is accepted as the new solution \(\mathbf{S_{0}}\) if either the solution \(\mathbf{S}\) is better than solution \(\mathbf{S_{0}}\) (i.e., \(TC(\mathbf{S})<TC(\mathbf{S_{0}})\)) or the solution \(\mathbf{S}\) is not better than \(\mathbf{S_{0}}\) given a certain condition. In the latter case, the solution \(\mathbf{S}\) is accepted as the new solution \(\mathbf{S_{0}}\) if a randomly generated number between zero and one (i.e., rand(0, 1)) is less than the probability \(p\), the probability of accepting a non-improving solution \(\mathbf{S}\) where \(p\) is given as follows. \[p=exp(-\Delta TC/T) \tag{11}\]  
Note, \(\Delta TC=TC(\mathbf{S_{0}})-TC(\mathbf{S})\), \(T\) is the current temperature and \(exp\) is the exponential function. When the temperature \(T\) is high, which is at the beginning of the search, the probability \(p\) of accepting a worse solution \(\mathbf{S}\) as the new \(\mathbf{S_{0}}\) is high, which allows the search to jump to different areas of the solution space. This allows the algorithm to search the solution space without quickly converging to a poor local optimum. After a certain number of iterations, \(N_{T}\), at the current temperature \(T\), the temperature is reduced using the following equation where \(0<\alpha<1\). Note, \(\alpha\) is called the cooling ratio. \[T=\alpha\times T \tag{12}\]  
For a slow reduction in temperature \(T\), consider \(\alpha\geq 0.90\).