# Caching Placement Optimization Strategy Based on Comprehensive Utility in Edge Computing
## 4 The Cache Placement Optimization Algorithm Based on Improved Tabu Search in Edge Computing
### The Pseudo-Code for the Cache Placement Algorithm Based on the Improved Tabu Search  
The pseudo-code for the cache placement algorithm based on the improved tabu search is shown in Algorithm 1.  
```
Input: the set of data blocks to be cached \(F(n)=\{f_{i}|i=1,2,\ldots,n\}\); the set of servers \(E(m)=\left\{e_{i}\middle|j=1,2,\ldots,m\right\}\). Output: the optimal solution Result for cache data placement;
1. Initialization: set \(tabuList[1,2,3,\ldots,n]=1\); \(p_{t}=0\); \(h=1\)
2. for each \(i\) do
3. Calculate the popular level \(Pop_{i}\) of the data block \(i\)
4. Calculate the value \(re_{i}\) of the remaining valid period ratio of each data block \(i\)
5. the data block value is saved in \(Epopset\)\(//\)\(Epopset\)\(\leftarrow\)\(Pop_{i}*re_{i}\)
6. end for each
7. for each \(j\) do
8. Calculate the replacement rate \(Rep_{j}\) for each server
9. keep the value \(Rep_{j}\) to the set \(Repset\)
10. end for each
11. for each \(i\) do
12. Calculate the span of the data block \(i\)\(//\) According to Formula (23)
13. Calculate the replacement rate \(Rep\)\(//\) According to Formula (24)
14. for each \(j\) do
15. if \(Rep_{j}\in\left[\lfloor Rep\rfloor,\lceil Rep\rceil\right]\)
16. keep \(j\) in the solution set Result.
17. end for each
18. end for each
19. Calculate the value of the comprehensive utility \(//\) According to Formula (19)
20. Calculate \(E_{\max}\) and \(E_{\min}\)\(//\) According to Formulas (20) and (21)
21. while the data blocks in \(E_{\max}\) and \(E_{\min}\) are not forbidden do
22. Calculate \(E_{\max}\) and \(E_{\min}\);
23. if \(h\leq x_{i}\) then
24. Using the disciplinary strategy choose \(E_{\min}=E_{s*(h)\%m}\)
25. end if
26. find \(f_{k}\) and \(tabuList[k]==1\) assigned to \(E_{\max}\);
27. set \(tabuList[k]=0\);
28. for \(l:=1\) to \(n\) and \(l\in FE_{\min}\), set \(q=1\) do
29. if \(f_{l}\) assigns to \(E_{\min}\) and \(tabuList[l]=1\) then
30. Calculate \(B_{lk}\) and \(B_{\delta k}\);
31. if \(B_{lk}\) and \(B_{\delta k}\) then
32. set \(q=l\);
33. end if
34. end if
35. end for
36. if \(MBT(k,l)\geq 0\) then \(//\) Calculate \(MBT(k,l)\) according to Formula (28)
37. set \(tabuList[q]=0\);
38. \(x_{\max}\leftrightarrow x_{\max}\)
39. \(x_{\min}\leftrightarrow x_{\min}\)
40. else
41. \(p_{t}=p_{t}+1\)
42. end if
43. end while
44. get the optimal solution Result.
```  
**Algorithm 1**The cache placement optimization algorithm based on improved tabu search  
In the optimization of the cache placement algorithm using improved tabu search, set the number of data blocks for cache placement to be \(n\), and the number of servers to be \(m\). Typically, the cache placement benchmark is satisfied \(n>m\). The time complexity of the algorithm in this paper mainly consists of two parts:1. The time complexity of obtaining the initial solution using the permutation-rate-based cache placement strategy is \(O(n*m)\).
2. The time complexity of optimizing the initial solution using the tabu list and the swap strategy based on the improved tabu search is \(O\left(n^{2}\right)\).  
Generally, the cache placement is \(n>m\) and the time complexity of an improved tabu-search-based cache placement algorithm is \(O\left(n^{2}\right)\).