Locality Sensitive Hashing-aware Fruit Fly Optimization Algorithm and its application in Edge Server Placement

doi:10.21203/rs.3.rs-1747879/v1

Download PDF

Research Article

Locality Sensitive Hashing-aware Fruit Fly Optimization Algorithm and its application in Edge Server Placement

https://doi.org/10.21203/rs.3.rs-1747879/v1

This work is licensed under a CC BY 4.0 License

You are reading this latest preprint version

As is well known that global optimization ability of Fruit fly Optimization Algorithm (FOA)is weak because it is easy to fall into local optimum. In this paper a Fruit Fly Optimization Algorithm based on Locality Sensitive Hashing-aware (LSHFOA)was proposed. The locality sensitive hashing mechanism to optimize the generation mechanism for swarm population individuals was used, which can improve the individual diversity of the population. Meanwhile, when the fruit fly population falls into local optimum, the locality sensitive hashing mechanism was adopted to change the population location, which is used for jumping out of local optimal limits. To verify the performance of LSHFOA, it was compared with FOA and its improvement algorithms CFOA, and IFFO with 8 representative benchmark functions. A large number of experimental results showed that LSHFOA has a faster convergence speed and higher precision of optimization for function optimization, especially in high-dimensional multi-peak functions. In the end, we apply this new Algorithm to solve the edge server placement (ESP) problem in the edge computing environment, the experimental results show that the new algorithm has excellent application effect.

Fruit fly Optimization Algorithm

locality sensitive hashing

swarm intelligence algorithm

global optimization capacity

Fruit fly optimization algorithm (FOA) is an intelligent optimization algorithm based on the foraging characteristics of fruit fly populations proposed by Wen chao Pan in 2012 [1]. This algorithm has been widely used in numerous scientific and engineering fields with its advantages of fast optimizing speed, simple operation, and few parameters, as well as the traditional intelligent optimization algorithms such as PSO [8], GA [9], and ACO [10]. For example, the literature[7] applied the FOA algorithm to the field of service computing firstly, and the algorithm was verified through a large number of experiments that proved it can be used to solve the service combination optimization problem and was recognized by peers [6]; the literature [3] proposed a multi-scale collaborative variation-based fruit fly optimization algorithm by improving the FOA algorithm and applied the algorithm to function optimization; the literature [11] introduced the FOA algorithm into neural network for parameter optimization and conducting a feasibility study for this scheme. In addition, FOA is also used in the field of edge computing. In [13], a cache placement algorithm with lower complexity is proposed by utilizing FOA.

However, the fruit fly optimization algorithm suffers from the tendency to fall into local optima, the inability to traverse the problem domain and poor stability and so on [2, 3]. Literature [2] proposed that the original fruit fly optimization algorithm cannot access the negative problem domain, i.e., the position of individual fruit fly cannot reach the negative domain, and therefore, it cannot be applied in some problems. For example, it cannot optimize for functions with negative definition domain. In the literature [3], it is concluded from the theoretical analysis that the result of FOA depended on the initial position of the population and the initial position of the population is random, i.e., the stability of FOA was poor and the global optimization capacity was weak. Therefore, in order to solve these shortcomings of FOA, the research for FOA algorithm is divided into two main aspects. On the one hand, it is necessary to reduce the dependence of fruit fly optimization algorithm on the initial position of the population so as to improve the performance of this algorithm. On the other hand, dynamically adjusting the radius of population generation is useful to escape from the local optimum limitation during fruit fly population. Among them, the literature [2] proposed a linear fruit fly optimization algorithm LGMS-FOA by improving the FOA population generation method to enhance the global optimization capacity of FOA. However, this method generates population individuals in an overly simple way and also suffers from the shortcomings such as weak global optimization capacity. To further remedy this drawback, a chaotic fruit fly optimization algorithm is proposed in literature [4]. The stability and optimization capacity of the algorithm are verified through extensive function tests based on the linear generation of population individuals. In addition, a fruit fly optimization algorithm with adaptive population size is proposed in [5] to solve the function optimization problem. In summary, although the fruit fly optimization algorithm has been widely used in many aspects, such as communication resources allocation and scheduling, computation offloading and caching schemes in mobile edge networks, it still has non-negligible shortcomings. In order to solve these shortcomings, some improvement algorithms have been widely studied in recent years. Although these improvement algorithms could solve the shortcomings of FOA to a certain extent, each improvement algorithm led to new shortcomings at the same time, such as the weak generalizability due to more parameters. In addition, many of the improved algorithms tend to focus on solving a certain class of problems, while neglecting other aspects of performance. For example, traditional FOA tends to be more suitable for optimization problems with positive problem domains and extreme value points close to the origin of the problem [2, 3].

In order to solve the weakness of the global optimization capacity of fruit fly optimization algorithm from other aspects and to improve the solution accuracy of fruit fly optimization algorithm in multi-polarity problems, this paper proposed a fruit fly optimization algorithm based on locality sensitive hashing, so that the algorithm can be better applied in distributed environment such as edge computing. The algorithm further improved the ability of fruit fly optimization algorithm to traverse the problem domain by introducing a locality sensitive hashing mechanism, establishing a locality sensitive hashing table of fruit fly population positions, and then using the table to reduce the candidate points of similar population positions. Thus, it can reduce the dependence of fruit fly optimization algorithm on the initial population positions and improve the global optimization capacity of FOA. In order to verify the performance of the algorithm in this paper, eight benchmark functions, covering single-dimensional and multi-dimensional, single-peak and multi-peak aspects, are selected for detailed comparison with the classical FOA improvement algorithms CFOA [4], IFFO [5].

This study detailed the implementation process of the traditional fruit fly optimization algorithm and the background knowledge of locality sensitive hashing, Locality sensitive hashing system and proposes the algorithm were introduced and were proved through a large number of experiments to be efficient.

2.1 Fruit fly optimization algorithm

FOA, as a population intelligence optimization method, works by describing the problem on an n-dimensional space as each fruit fly, and the position of the fruit fly represents a feasible solution to the problem. Furthermore, the current position of each fruit fly is measured by the fitness function, and the population position is changed by the individual's fitness. Then, a new population of fruit fly is generated. In this way, the fruit fly population gradually approaches the optimal solution of the problem. The specific implementation process is shown in Fig. 1.

The detailed optimizing process is as follow:

Step 1: Initial population location

$$\left\{\begin{array}{c}{x}_{axis}=rand\left(LR\right)\\ {y}_{axis}=rand\left(LR\right)\end{array} \left(1\right)\right.$$

Step 2: Generating individuals of the population

$$\left\{\begin{array}{c}{x}_{i}={x}_{axis}+rand\left(V\right)\\ {y}_{i}={y}_{axis}+rand\left(V\right)\end{array} \left(2\right)\right.$$

Step 3: Calculate the individual fitness of the population

$$\left\{\begin{array}{c}{DIst}_{i}=\sqrt[2]{{{x}_{i}}^{2}+{{y}_{i}}^{2}}\\ {S}_{i}=\frac{1}{{DIst}_{i}}\\ {Smell}_{i}=Fitness\left({S}_{i}\right)\end{array} \left(3\right)\right.$$

Step 4: Preservation of optimal Drosophila individuals

$$\left\{\begin{array}{c}\left[bestSmellbestdex\right]=\text{max}\left({Smell}_{i}\right)\\ Smellbest=\text{max}\left(bestSmell,Smellbest\right)\end{array} \left(4\right)\right.$$

Step 5: Generate new population locations

$$\left\{\begin{array}{c}{x}_{axis}={x}_{bestindex}\\ {y}_{axis}={y}_{bestindex}\end{array} \left(5\right)\right.$$

Step 6: Repeat Step 2 - Step 5 until the iteration conditions or accuracy requirements are met.

Where LR is the solving range, V is the population range radius, $Dis{t}_{i},{S}_{i},Fitness$ are the formulas for the fitness function, $\left[bestSmell bestindex\right]=\text{m}\text{a}\text{x}\left(Smel{l}_{i}\right)$,which present the individual optimal fitness va, ue and individual position in the current population, $Smellbest$ is the global optimal fitness value,${x}_{axis}$ is the x coordinate of the fruit fly population location, ${y}_{axis}$ is the y coordinate of the fruit fly population location.

2.2 Locality sensitive hashing

Hashing as an efficient method of data retrieval, mapping data to a hash table through a hash function can achieve a shift in search time from O(n) to O (1). Among them, locality sensitive hashing can further map high-dimensional massive data to approximate nearest neighbors to a locality sensitive hashing table. Then, it can quickly find similar data. There are basic ideas of locality sensitive hashing. One is that two adjacent data in high-dimensional data space will have a high probability to remain adjacent after being mapped to low-dimensional data space. The other is that two non- adjacent data will also have a high probability to be low-dimensional space. With this mapping, we can find the adjacent data points in the low-dimensional data space and avoid high-dimensional data space finding, where it would be time-consuming. A hash mapping with such a property is said to be locality sensitive. Take Fig. 2 as an example, there are four data blocks D₁, D₂, D₃ and D₄, where D₁ and D₂ are similar or close to each other. The four data blocks can be mapped into a locality sensitive hashing table by locality sensitive hashing. The mapping usually results in D₁ and D₂ being in the same or similar region, and then the gap with D₃ and D₄ is further widened.

From Fig. 2, it can be seen that similar data are mapped to similar regions through locality sensitive hashing operations. Further, through the analysis of FOA, it is easy to know that FOA has a strong dependence on the initial position of the population [3–5]. By adjusting the initial location of the populations, it is beneficial to enhance the global optimization capacity of FOA. At the same time, increasing the randomness of population positions or decreasing the similarity between population positions, can further enhance the global optimization capacity of FOA. The locality sensitive hashing operation of a set of population positions can obtain the similar population positions quickly and effectively. Then the population positions with larger gaps can be more conveniently selected to enhance the global optimization capacity of FOA.

2.3 Edge Server Placement

For the ESP problem, edge servers are usually deployed on the base stations or access points. Therefore, in each ESP scenario, it usually includes n base stations B={b₁ ,…,b_n}, and m edge servers S={s₁,…,s_m}. The ESP problem aims to place these m edge servers on those n base stations to serve its most users U={u₁,…,uc}. For each user ${u}_{k}\in U$, it can access a set of base stations, which is denoted by ${a}_{\{k,i\}}$, where ${a}_{\left\{k,i\right\}}=1$ indicates the user ${u}_{k}$ can access base station ${b}_{i}$, otherwise, ${a}_{\left\{k,i\right\}}=0$. Thus, the user-base station accessibilities can be modelled as a matrix A.

$$A=\left[\begin{array}{ccc}{a}_{\left\{\text{1,1}\right\}}& \cdots & {a}_{\left\{1,n\right\}}\\ ⋮& \ddots & ⋮\\ {a}_{\left\{c,1\right\}}& \cdots & {a}_{\left\{c,n\right\}}\end{array}\right]$$

Then, if an edge server has been placed on the base station ${b}_{i}$, denoted by ${p}_{i}=1$, all its users can be served, i.e., $\forall {u}_{k}\in U, {a}_{\left\{k,i\right\}}=1$. Thus, the objective of the ESP problem is to maximize the maximum number of served users,

$$O=\text{max}({\sum }_{\left\{{u}_{k}\in U\right\}}\text{min}({\sum }_{\left\{{b}_{i}\in B\right\}}{a}_{\left\{k,i\right\}}\cdot {p}_{i}, 1))$$

Where ${\sum }_{\left\{{b}_{i}\in B\right\}}{a}_{\left\{k,i\right\}}\cdot {p}_{i}$ is used to calculate the served times of ${u}_{k}$ by all edge servers. Then, $\text{min}({\sum }_{\left\{{b}_{i}\in B\right\}}{a}_{\left\{k,i\right\}}\cdot {p}_{i}, 1)$ = 0 means that ${u}_{k}$ cannot be served by any edge servers, otherwise, i.e., $\text{min}({\sum }_{\left\{{b}_{i}\in B\right\}}{a}_{\left\{k,i\right\}}\cdot {p}_{i}, 1)$ = 1 indicates that ${u}_{k}$ can be served.

3.1 FOA based on locality sensitive hashing mechanism

As seen from Section 1.2, the main idea of locality sensitive hashing is that if two data blocks in a high- dimensional space are close, the result of a locality sensitive hashing of that data block has a high probability of similar. If two data blocks are farther apart, the hash result will have a small probability of similar. Therefore, for the FOA algorithm, its core is to design the locality sensitive hashing function h(x).

Given an n-dimensional problem F(x₁,…,x_n) with problem domain $x\in {\left[{R}_{min},{R}_{max}\right]}^{n}$, given an existing solution as $X\text{'}=({x\text{'}}_{1},\dots ,{x\text{'}}_{n})$, and any other solution is $X=({x}_{1},\dots ,{x}_{n})$, then the problem F(x₁,…,x_n) relative to the solution $X\text{'}$ the locality sensitive hashing function of is

$$h\left(X|{X}^{{\prime }}\right)=\left[\frac{\sqrt[2]{\left({x}_{1}-{x}_{1}{\prime }\right)+\dots +\left({x}_{n}-{x}_{n}^{{\prime }}\right)}}{{E}_{n}}\right] \left(8\right)$$

where [value] denotes the integer part of the value, ${E}_{n}$ denotes the solution over head of the problem $F({x}_{1},\dots ,{x}_{n})$, the physical meaning is the range of each hashtable element. In short, the larger the value, the smaller the number of elements of the corresponding hash table. Meanwhile, the smaller the value, the more elements of the corresponding hash table. ${E}_{n}$ is calculated as follows.

$${E}_{n}=\frac{\sqrt[2]{{{(R}_{max}^{1}-{R}_{min}^{1})}^{2}+\dots +{{(R}_{max}^{n}-{R}_{min}^{n})}^{2}}}{w} \left(9\right)$$

Where w denotes the accuracy of the solved problem. It is used to control the range of each element of the hash table. For example, if given a two-dimensional (n = 2) problem F(x₁, ,x₂), its problem domain is $x\in {\left[\text{0,5}\right]}^{2}$, ${x}_{i}\in \left[\text{0,5}\right], i=\text{1,2}$, then the solution range of the problem F(x₁, ,x₂) is$\left(\text{0,0}\right),\dots ,\left(\text{5,5}\right)$, if given the parameter w=5, then ${E}_{n}$=$\frac{\sqrt[2]{50}}{5}$, i.e., the range of elements in each sensitive hash table is [[$\frac{\sqrt[2]{50}}{5}\text{*}(j-1)$],[$\frac{\sqrt[2]{50}}{5}\text{*}j$]], where j denotes the jth elements in the sensitive hash table, and if given the parameter w=10, then ${E}_{n}=\frac{\sqrt[2]{50}}{10}$, similarly, the range of elements in each sensitive hash table is [[$\frac{\sqrt[2]{50}}{10}\text{*}$],[$\frac{\sqrt[2]{50}}{10}\text{*}(j+1)$]]. Then, assuming that the current solution (i.e., for the population location in the FOA) is X=(0,0) and the target solution (i.e., the population location to be selected in the FOA) is X₁=(0,1),X₂= (1,0)༌X₃= (1,1)༌X₄= (0,2)༌ X₅= (2,0)༌ X₆= (2,2), then the sensitive hash, value cor, esponding, to the ta, get soluti, n(w=5) is $h\left({X}_{1}|X\right)=\left[\frac{5}{\sqrt[2]{50}}\right]=0$,$h\left({X}_{2}|X\right)=\left[\frac{5}{\sqrt[2]{50}}\right]=0$,$h\left({X}_{3}|X\right)=\left[\frac{10}{\sqrt[2]{50}}\right]=1$,$h\left({X}_{4}|X\right)=\left[\frac{20}{\sqrt[2]{50}}\right]=2$, $h\left({X}_{5}|X\right)=\left[\frac{20}{\sqrt[2]{50}}\right]=2$,$h\left({X}_{6}|X\right)=\left[\frac{40}{\sqrt[2]{50}}\right]=5$,Thus, the target solutions X₁ and X₂ are mapped into the first element of the locality sensitive hashing table, X₃ is mapped into the second element of the locality sensitive hashing table, the target solutions X₄ and X₅ are mapped into the third element of the locality sensitive hashing table, and the target solution X₆ is mapped into the sixth element of the locality sensitive hashing table. The graphical representation is shown in the following figure.

From Fig. 3, the locality sensitive hashing result of the target solution (the population location to be selected in the FOA) in this example is divided into four sensitive hashing table elements, i.e., elements $j\in J=\left\{\text{1,2},\text{3,6}\right\}$. Then, how to migrate the FOA population location is another key problem. In this study, the roulette technique for the target solution selection and migrates the selected target solution were used as the new FOA population location.

Roulette as a commonly used selection method, also known as proportional selection method. The basic idea of Roulette is that the probability of each population location point being selected is related to its corresponding edge weight value, which is performed in the following steps.

Step1: First determine the selection probability of each locally sensitive hash table element.

$${\alpha }_{j}={e}^{j},jϵJ \left(10\right)$$

Step2: Calculate the sum of the weights between all FOA population location points to be selected and the current fruit fly population location ${X}_{i}$:${\sum }_{\left\{j\in J\right\}}{\alpha }_{j}$

Step 3: Calculate the probability of each FOA population location point x being selected.

$${p}_{k}=\frac{{\alpha }_{k}}{{\sum }_{\left\{jϵJ\right\}}{\alpha }_{j}} \left(11\right)$$

Step 4: Calculate the cumulative probability of each FOA population location point to be selected.

$${{p}^{{\prime }}}_{k}=\frac{{\sum }_{j=1}^{k}{p}_{j}}{{\sum }_{jϵJ}{\alpha }_{j}} \left(12\right)$$

Step 5: Generate a random number θ with uniform distribution in the interval [0,1].

Step5: If $\theta \le {p}_{k}^{\text{'}}$ and ${p}_{k-1}^{\text{'}}\le \theta$, then element k of the locality sensitive hashing table is selected, and then, any FOA to be selected population location Xi in element k is randomly selected.

At this point, the new FOA population location has been selected.

Algorithm 1. LSHFOA

Input: benchmark function and definition D

Output: the optimal solution in the definition domain D

1: Initialize a set of (n) population location points$V=\{{X}_{1},{X}_{2},\dots ,{X}_{n}\}$

2: Select a population location point as the initial:

$\forall {X}_{i}\in V$

3: Loop $t\le iter$ Then

4: Generate population individuals (Pop)for point ${X}_{i}$ according to the population

5: Calculate the benchmark function value for each individual fruit fly

6: Preservation of optimal fruit fly individuals

7: If trapped in local optimum Then

8: Calculate the probability of selecting the location point of the population to be selected in FOA and the point Xi: {${\alpha }_{1},\dots ,{\alpha }_{n}$}

9: Roulette calculates the selection probability of each population location point: P= {${p}_{1},\dots ,{p}_{n}$}

10: Randomly generated selection probabilities${p}_{0}$

11: Selecting new population locations based on locality sensitive hashing table

12: End if

13: Update population location point${X}_{i}$

14: End Loop

15: Return the optimal solution

By means of roulette, the weight relationship between population location points can be mapped to the selection probability, and then random values are used for population location selection. This roulette selection method can, on the one hand, improve the selection probability of dominant population location points, i.e., satisfy the principle of optimization selection; on the other hand, roulette also has a chance to select other slightly inferior population location points, and this operation helps to enhance the diversity of fruit fly population locations and further ensures the global optimization capacity of the fruit fly optimization algorithm.

3.2 LSHFOA

In the improved fruit fly optimization algorithm (LSHFOA) proposed in this paper, locality sensitive hashing tables are used for the selection of Drosophila population locations, i.e., when the fruit fly optimization algorithm falls into a local optimum (usually measured by multiple population location invariance), the roulette mechanism is used for population location selection (according to locality sensitive hashing table). the pseudo-code representation of LSHFOA is shown in Algorithm 1[6–8].

Algorithm 1 shows that the time complexity of the algorithm is O (m₁m₂), i.e., the time consume of the algorithm is related to the population size m₁ and the number of iterations m₂. Therefore, in order to reduce the time consuming of the algorithm, the population size in the experiments of this paper is 50 and the number of iterations is 300. In order to cover more initial location points, the size of the initial population location set V is 50, i.e., the fruit fly population location locality sensitive hashing table contains a total of 50 points[9–11]. According to the execution flow of Algorithm 1, the flow chart of LSHFOA is shown in Fig. 4.

Where V in Fig. 4 denotes a set of fruit fly population location points, i.e., each vertex in the locality sensitive hashing table of fruit fly population location, X_i denotes any point of population location points in V, Pop denotes the set of population individuals generated according to the population location X_i with a scale of 50, and Fitness denotes the fitness value of each fruit fly individual on the benchmark function, i.e., the Step6- Step7 denotes the new population location selection scheme, i.e., the locality sensitive hashing table model with roulette wheel selection method[12–15].

In order to verify the performance of the proposed algorithm in this paper for optimization, this section conducts a comprehensive comparison with the improved algorithms of FOA, CFOA and IFFO, in eight commonly used benchmark functions. Firstly, this section lists the experimental environment and parameter settings of this paper; secondly, the eight benchmark functions are analyzed and demonstrated in detail; finally, a graphical presentation and detailed analysis are made based on the experimental results[16–18].

Table 1

parameter setting table
Algorithm	Parameters	Numerical value	Meaning
IFFO	V	1	Population radius
CFOA	$\text{cos}\left(ico{s}^{-1}\left({x}_{i}\right)\right)$	Chebyshev	Chaotic map function
LSHFOA	$\omega$	$10$	Question accuracy

Table 2

benchmark functions
Function	Dimensionality	Definition Domain	Minimum value
$F1=\left\|x\right\|$	$n=1$	$-10\le x\le 10$	$0$
$F2=sin\left(x\right)$	$n=1$	$-10\le x\le 10$	$-1$
$F3=xsin\left(x\right)$	$n=1$	$0\le x\le 20$	$-17.3076$
$F4={\sum }_{i=1}^{n}{x}_{i}^{2}$	$n=30$	${\left[-\text{10,10}\right]}^{n}$	$0$
$F5={\sum }_{i=1}^{n}\left\|{x}_{\text{i}}\right\|+{\prod }_{i=1}^{n}\left\|{x}_{i}\right\|$	$n=30$	${\left[-\text{10,10}\right]}^{n}$	$0$
$F6={\sum }_{i=1}^{n}({x}_{i}^{2}-10cos2\pi {x}_{i}+10)$	$n=30$	${\left[-5.12, 5.12\right]}^{n}$	$0$
$F7=-20\text{exp}\left(-0.2\sqrt[2]{\frac{{\sum }_{i=1}^{n}{x}_{i}^{2}}{n}}\right)-\text{exp}\left(\frac{{\sum }_{i=1}^{n}cos2\pi {x}_{i}}{n}\right)+20+e$	$n=30$	${\left[-\text{32,32}\right]}^{n}$	$0$
$F8={\left({x}_{2}-\frac{5.1}{4{\pi }^{2}}{x}_{1}^{2}+\frac{5}{\pi }{x}_{1}-6\right)}^{2}+10\left(2-\frac{1}{8\pi }\right)-cos{x}_{1}+10$	$n=2$	${\left[-\text{1,1}\right]}^{2}$	$-2$

4.1 Experimental environment and parameter settings

The experiments in this paper are based on Windows 10, 64-bit operating system, 16G memory, 2.4GHZ desktop computer, experimental programming language is C#, compiler is Visual Studio 2010. where the population size is 50, the number of iterations iter is 300, the initialized population location points are 50, each experiment is repeated 50 times, and the mean value is taken as the experimental result and plotted as the experimental performance graph. The other parameters set in the experiment are shown in Table 1.

4.2 Benchmark functions

In order to analyze the performance of the algorithm more comprehensively, the eight benchmark functions are divided into the following categories: single-dimensional single-peak function (F1), single-dimensional multi-peak function (F2, F3), multi-dimensional single-peak function (F4, F5), multi-dimensional multi-peak function (F6, F7) and two-dimensional combined function (F8). At the same time, the selected benchmark functions have both 0 (F1, F4, F5, F6, F7, F8) and non-0 (F2, F3, F8) extreme points in order to verify the global optimization capability of the algorithm in a more comprehensive way. The detailed benchmark functions are shown in Table 2. The dimension n indicates that the benchmark function has n variables, and is denoted as x₁,…,x_n, and the definition domain [-10,10] n indicates that each dimension in the benchmark function takes values in the range [-10,10], and the minimum value indicates the minimal value of the function in the current definition domain.

In order to solve the ESP problem by LSHFOA, we employ a new perspective to model the ESP problem.

Definition 1 Coding of Fruit Flies: Given a set of base stations B with a set of users and a set of edge server S, the coding scheme of each individual fruit fly dl is a tuple with m elements, denoted as, where, i.e., is 's placement decision with a value in .

Figure 5 provides an example of such a coding scheme for a fruit fly${d}_{l}$

As shown in Fig. 5, each fruit fly is coded by m elements, which indicate m edge servers. And, the value of each element varies among the base stations, i.e., 1, …, n. In this way, each fruit fly represents one feasible solution to the edge server placement problem. Then, each fruit fly changes based on the schemes of LSHFOA. In terms of the fitness function of ESP problem, it can be modelled as below to purse the objective of ESP problem, as shown in Eq. (13).

$$Fit\left({d}_{l}\right)={\sum }_{\left\{{u}_{k}\in U\right\}}\text{min}({\sum }_{\left\{{d}_{l}^{j}\in {d}_{l}\right\}}{a}_{\left\{k,{d}_{l}^{j}\right\}}, 1))$$

6.1 LSHFOA

In order to comprehensively analyze the experimental performance of the algorithm LSHFOA in this paper, comparison tests with IFFO and CFOA on the basis of Table 2 was performed, and the experimental results are shown in the following figures.

Figure 6 represents the experimental results of the single-dimensional single-peak function F1. Since the single-dimensional single-peak function is relatively simple, a set of classical functions was used randomly to test the performance of the algorithm. As can be seen from the figure, the algorithm in this paper is significantly better than IFFO in both the optimization accuracy and the optimization efficiency. Comparing to CFOA, the optimization efficiency is slightly lower while the final experimental results are similar. The experimental results of this group show that the algorithm of this paper also has good experimental results under the one-dimensional single-peak function test.

Figure 9 and Fig. 10 represent the multidimensional multi-peak test functions (F4 and F5). from Fig. 9, it can be seen that with the increase of iterations, the algorithm in this paper can rapidly reduce the experimental search accuracy. The benchmark function value rapidly decreases and the results are significantly smaller than CFOA and IFFO. Therefore, for the benchmark function F4, the algorithm in this paper has better experimental results with convergence speed. From Fig. 9, it can be seen that in the multi-dimensional multi-peak test function, although the initial Fitness value is larger than LSHFOA, the algorithm in this paper can quickly approach the optimal solution through the local sensitive hashing mechanism, so as to achieve similar optimization-seeking accuracy and optimization-seeking efficiency comparing to algorithms IFFO and CFOA. In summary, it can be seen from Fig. 9 and Fig. 10 that with the increase of iterations, the algorithm in this paper has excellent optimization-seeking accuracy and convergence speed in the multidimensional single-peak function test.

Figure 11 and Fig. 12 represent the multi-dimensional multi-peak test functions (test functions F6 and F7). Overall, it can be seen from the experimental results in Fig. 11 and Fig. 12 that the proposed algorithm in this paper can achieve significant advantages in the multi-dimensional multi-peak situation compared with the CFOA and IFFO. For example, as can be seen from Fig. 11, even though the initial population position LSHFOA is slightly worse than that of CFOA and IFFO, with the increase of the number of iterations, the optimization accuracy of this algorithm is gradually improved. After 50 iterations, the experimental results of this algorithm significantly outperform the comparative algorithms CFOA and IFFO. Therefore, for the benchmark function F5, the accuracy and efficiency of the experimental results are significantly better than the classical algorithms CFOA and IFFO, although the initial position of the algorithm is slightly worse. As can be seen from Fig. 13, for benchmark function F7, the algorithm in this paper outperforms CFOA and IFFO in terms of optimization results close to 0 (the most value of the function in the domain). In terms of the optimization efficiency, the accuracy of the feasible solution of this paper is higher than that of the comparison algorithm in about 20 iterations, which indicates that LSHFOA can achieve excellent optimization results and efficiency in high-dimensional multi-peak functions. In summary, for the multi-dimensional multi-peak problem, the algorithm in this paper can get better results. It can be seen that LSHFOA is more suitable for solving the high-dimensional multi-peak optimization problem.

Figure 13 represents the combination function of two- dimensional variables, and it can be seen from the figure that although the algorithm in this paper has a slightly worse optimization accuracy than IFFO, it significantly outperforms CFOA, that is LSHFOA can be applied in such problems. Combining the above several test functions, it can be seen that the algorithm in this paper can achieve significantly better experimental results than CFOA and IFFO in multi-peak situations, especially in high-dimensional multi-peak situations.

6.2 LSHFOA-ESP

To extensively evaluate LSHFOA-ESP's performance, we simulate a set of ESP scenarios in the experiments. We employ a Windows machine equipped with an Intel Core i7-7500 processor, and 16G RAM to perform the experiments. At the same time, a real-world dataset is applied to conduct the experiments. It has been widely used in edge computing environments [19–20]. Overall, this dataset includes a large number of real-world users and base stations in Melbourne Metropolis, Australia, including the geographical information of users and base stations, and the coverage of base stations.

Performance Metrics. Two metrics are employed to measure the effectiveness and efficiency of LSHFOA-ESP, including 1) the number of served users, and 2) the time consumption.

Comparison Approaches. In this paper, to evaluate the performance comprehensively, two state-of-the-art approaches and one baseline approach are employed as comparison approaches in this paper. All of them are implemented in Java.

RESP: This is a representative approach proposed very recently. It makes the first attempt to solve the robustness-oriented edge server placement problem, with the aim to maximize the overall robustness.

CRESP: This approach is an extension of, which focuses on the tradeoff between robustness and coverage. This is because maximizing the overall robustness only usually leads to a decrease in user coverage.

FOA-ESP: This is a baseline approach that tries to solve the edge server placement problem by using the classical FOA only[21–23].

Parameter Settings. In each experiment, n base stations are randomly selected from the dataset and c users are selected from the data set randomly as well, where base stations include the geographical locations and the coverage radiuses, users include the geographical locations. Then, based on those geographical locations of base stations and users and the radiuses of base stations, the user-base station accessibilities matrix can be built. Next, to test the performance of LSHFOA-ESP comprehensively, three parameters are varied, including 1) number of base stations (n); 2) number of edge servers (m) and 3) number of users (c). Accordingly, the experimental settings of those parameters are summarized in Table 1. LSHFOA-ESP iterates 300 times before giving out the solution. The number of fruit flies in each iteration is 50. Each time we vary one parameter and repeat the experiment 100 times, then the results are averaged.

Table 1

Experimental settings
	n	m	c
Set 1	100, 200, …, 800	40	4000
Set 2	400	10, 20, …, 80	4000
Set 3	400	40	1000, …., 8000

Generally, Figs. 14–16 show the effectiveness, measured by the number of served users, of all the approaches in Set 1, Set 2 and Set 3, respectively. From those figures, it is easy to see that the proposed approach, LSHFOA-ESP can serve the most users compared to other approaches. First, LSHFOA-ESP can find a solution to cover the most users, which is significantly greater than the classic FOA and its application to the ESP problem. This is because, as stated above, LSHFOA, as an extension of FOA, is designed to overcome the difficulties of FOA and aims to find the optimal solution. Thus, LSHFOA-ESP’s performance is better than FOA-ESP's, by 15.32%. Second, RESP serves the least number of users. The background reason is straightforward. That is, RESP is designed to maximize the overall robustness of edge servers, i.e., maximizing the overall served times of users instead of serving more users. Thus, edge servers are usually driven to be placed on a small group of base stations that have covered the greatest number of users. In this way, the overall robustness will be maximized. Obviously, LSHFOA-ESP outperforms RESP significantly, by 25.48%. Lastly, as an extension of RESP, CRESP is designed to balance the overall robustness and the number of served users. As a result, its number of served users achieves the second-highest performance. But it is still lower than LSHFOA-ESP by 8.32%.

Specifically, Fig. 14 shows that when the number of base stations increases in Set 1, the number of served users achieved by all the four approaches decreases. The background reason is analyzed as follows. As shown in Table 1, when the number of base stations varies, the number of edge servers and the number of users are fixed. In this case, a larger number of base stations will lead to a decrease in the number of users covered by each base station on averagely. As a consequence, selecting the same number of base stations, i.e., placing a fixed number of edge servers, usually results in a lower number of served users. But the results, as shown in Fig. 14, are gradually stabilized. This is because, the locations of base stations and users come from a real-world, and they are fixed. In this case, when nearly all the base stations have been selected, the geographical distributions of users are unchanged. Thus, the number of served users decreases first and then becomes stabilized. Figure 15 demonstrates that LSHFOA-ESP is capable of serving the most edge users when the number of edge servers varies. Compared to FOA-ESP, RESP and CRESP, LSHFOA-ESP outperforms them with significant advantages. Especially, when more and more edge servers are placed in a specific edge computing environment, the performance gaps between LSHFOA-ESP and FOA-ESP, RESP and CRESP increase gradually. This is because, given a fixed number of base stations, placing more edge servers will cover more base stations to serve more users. When the number of users increases in Set 3, the number of served users increases in all approaches, as shown in Fig. 16 The underlay reason is similar to that in Set 2. That is, more users are extracted from the real-world data, and each base station will cover more users in general. Thus, placing a fixed number of edge servers usually leads to an increase in the overall number of served users, as shown in Fig. 16. As shown in Fig. 16, our approach, LSHFOA-ESP can still find a solution to serve the maximum number of users. Therefore, as demonstrated in Figs. 14–16, the proposed approach, LSHFOA-ESP can be used to solve the edge server placement effectively.

In this paper, through the study of the fruit fly optimization algorithm (FOA), the optimization results of the FOA depends on the initial position highly, which leads to the reduction of the global optimization capacity of the fruit fly optimization algorithm. To further optimize the algorithm, this paper introduces a locality sensitive hashing mechanism to get rid of the influence of the initial position of the fruit fly population on the optimization result by constructing a locality sensitive hashing table and making the selection of the fruit fly population position when the FOA falls into a local optimum according to the roulette approach. To verify the performance of the algorithm LSHFOA proposed in this paper, a comparative study is performed with eight classical benchmark functions (covering single-dimensional and multi-dimensional, single-peak and multi-peak characteristics) and the improved algorithms CFOA, IFFO, and MSFOA of FOA. The experimental results show that the algorithm in this paper has better convergence speed and better optimization accuracy in the multi- dimensional multi-peak case compared with the comparison algorithm.

Although the algorithm in this paper can obtain high experimental results in multi-polar situations, there are some problems that can be further optimized. For example, when falling into local optimum the process of measurement of the FOA, the judgement of the position of fruit fly population proposed in this study remains unchanged for many times. The judgement tends to improve the accuracy and efficiency of the fruit fly optimization algorithm in finding the best result. Therefore, in future study, it is necessary to improve the judgement for the problem of falling into local optimum, so as to further improve the performance of this algorithm, and apply this algorithm to the edge computing environment.

Acknowledgments

The authors are grateful to the Faculty of Innovation Engineering in Macau University of Science and Technology, and School of artifical Intelligence and Big Data in Hefei University.

Authors Contributions Statement

All authors take part in the discussion of the work described in this paper. Qian Cao designed all the experiments, Qian Cao and Bo Liu wrote the main manuscript text, and Ying Jin prepared all the figures and tables. All authors reviewed the manuscript.

Funding

This work is supported by the Key Project of Nature Science Research for Universities of Anhui Province of China (No. KJ2020A0657), 2020 Quality Improvement Project of Chaohu University on Discipline Construction (No. kj20xqyx03) and The Provincial Natural Science Research Program of Higher Education Institutions of Anhui province（No. KJ2021A1030）

Competing interests

The authors declare no conflict of interest.

Pan W T. A new fruit fly optimization algorithm: taking the financial distress model as an example [J]. Knowledge-Based Systems, 2012, 26: 69–74.
Shan D, Cao G H, and Dong H J. LGMS-FOA: an improved fruit fly optimization algorithm for solving optimization problems [J]. Mathematical problems in engineering, 2013, 2013.
Zhang Y, Cui G, Wu J, et al. A novel multi-scale cooperative mutation fruit fly optimization algorithm [J]. Knowledge-Based Systems, 2016, 114: 24–35.
Mitić M, Vuković N, Petrović M, et al. Chaotic fruit fly optimization algorithm [J]. Knowledge-Based Systems, 2015, 89: 446–458.
Pan Q K, Sang H Y, Duan J H, et al. An improved fruit fly optimization algorithm for continuous function optimization problems [J]. Knowledge-Based Systems, 2014, 62: 69–83.
Jatoth C, Gangadharan G R, Buyya R. Computational intelligence based QoS-aware web service composition: a systematic literature review[J]. IEEE Transactions on Services Computing, 2017, 10(3): 475–492.
Zhang Y, Cui G, Wang Y, et al. An optimization algorithm for service composition based on an improved FOA [J]. Tsinghua Science and Technology, 2015, 20(1): 90–99.
Zhou J, Yang J, Lin L, et al. Local Best Particle Swarm Optimization Using Crown Jewel Defense Strategy[M]. Critical Developments and Applications of Swarm Intelligence. IGI Global, 2018: 27–52.
Gong D, Sun J, Miao Z. A set-based genetic algorithm for interval many-objective optimization problems [J]. IEEE Transactions on Evolutionary Computation, 2018, 22(1): 47–60.
Dorigo M, and Stützle T. Ant colony optimization: overview and recent advances [M] //Handbook of metaheuristics. Springer, Cham, 2018: 311–351.
Yang Fan, WANG Xiaobing, SHAO Yang. Grey Neural Network deformation prediction based on improved Fruit fly algorithm optimization [J]. Science of Surveying and Mapping, 2018, 43(2): 63–69.
YangF Wang, XandShao Y. Deformation prediction of grey neural network based on modified fruit fly algorithm[J]. Science of Surveying and Mapping,2018, 43(2): 63–69
Peng Aoao. Performance analysis in fog rapid access networks based on the stochastic geometry [M]. May 29,2019.
Yiwen Zhang, Jie Pan, Lianyong Qi, Qiang He. Privacy-Preserving Quality Prediction for Edge-based IoT Services[J]. Future Generation Computer Systems, Vol 114, January 2021, pp:336–348.
Huang, Jiwei and Tong, Zeyu and Feng, Zihan. Geographical POI recommendation for Internet of Things: A federated learning approach using matrix factorization[J]. International Journal of Communication Systems. doi:10.1002/dac.5161.
Y. Chen and F. Zhao and Y. Lu and X. Chen. Dynamic task offloading for mobile edge computing with hybrid energy supply[J]. Tsinghua Science and Technology, Volum 10, doi:10.26599/TST.2021.9010050.
Chen, Ying and Gu, Wei and Li, Kaixin. Dynamic task offloading for Internet of Things in mobile edge computing via deep reinforcement learning[J]. International Journal of Communication Systems, doi:10.1002/dac.5154.
Huang, Jiwei and Lv, Bofeng and Wu, Yuan and et al. Dynamic Admission Control and Resource Allocation for Mobile Edge Computing Enabled Small Cell Network[J]. IEEE Transactions on Vehicular Technology, pages:1964–1973, volume 71, 2022, doi:10.1109/TVT.2021.3133696.
Chen, Ying and Liu, Zhiyong and Zhang, Yongchao and Wu, Yuan and Chen, Xin and Zhao, Lian. Deep reinforcement learning-based dynamic resource management for mobile edge computing in industrial internet of things[J]. IEEE Transactions on Industrial Informatics, pages: 4925–4934, volume 17, 2021.
Jiajie. Xu and Dejuan. Li and Wei. Gu and et al. UAV-assisted Task Offloading for IoT in Smart Buildings and Environment via Deep Reinforcement Learning[J]. Building and Environment, 2022, doi:10.1016/j.buildenv.2022.109218.
Y. Chen and F. Zhao and X. Chen and Y. Wu. Efficient Multi-Vehicle Task Offloading for Mobile Edge Computing in 6G Networks[J]. IEEE Transactions on Vehicular Technology. Pages:4584–4595, volume 71,2022, doi:10.1109/TVT.2021.3133586.
Cui, G., He, Q., Chen, F., Jin, H., & Yang, Y. (2020). Trading off between User Coverage and Network Robustness for Edge Server Placement. IEEE Transactions on Cloud Computing, 1–12.
Huang, J and Tong, Z and Feng, Z, Geographical POI recommendation for Internet of Things: A federated learning approach using matrix factorization[J], International Journal of Communication Systems, pages:e5161, doi:10.1002/dac.5161.

No competing interests reported.

Download PDF

Editorial decision: Major revision
08 Jul, 2022
Reviews received at journal
02 Jul, 2022
Reviewers agreed at journal
25 Jun, 2022
Reviewers agreed at journal
21 Jun, 2022
Reviewers invited by journal
20 Jun, 2022
Editor assigned by journal
15 Jun, 2022
Submission checks completed at journal
14 Jun, 2022
First submitted to journal
11 Jun, 2022

You are reading this latest preprint version

Function	Dimensionality	Definition Domain	Minimum value
\(F1=\left\|x\right\|\)	\(n=1\)	\(-10\le x\le 10\)	\(0\)
\(F2=sin\left(x\right)\)	\(n=1\)	\(-10\le x\le 10\)	\(-1\)
\(F3=xsin\left(x\right)\)	\(n=1\)	\(0\le x\le 20\)	\(-17.3076\)
\(F4={\sum }_{i=1}^{n}{x}_{i}^{2}\)	\(n=30\)	\({\left[-\text{10,10}\right]}^{n}\)	\(0\)
\(F5={\sum }_{i=1}^{n}\left\|{x}_{\text{i}}\right\|+{\prod }_{i=1}^{n}\left\|{x}_{i}\right\|\)	\(n=30\)	\({\left[-\text{10,10}\right]}^{n}\)	\(0\)
\(F6={\sum }_{i=1}^{n}({x}_{i}^{2}-10cos2\pi {x}_{i}+10)\)	\(n=30\)	\({\left[-5.12, 5.12\right]}^{n}\)	\(0\)
\(F7=-20\text{exp}\left(-0.2\sqrt[2]{\frac{{\sum }_{i=1}^{n}{x}_{i}^{2}}{n}}\right)-\text{exp}\left(\frac{{\sum }_{i=1}^{n}cos2\pi {x}_{i}}{n}\right)+20+e\)	\(n=30\)	\({\left[-\text{32,32}\right]}^{n}\)	\(0\)
\(F8={\left({x}_{2}-\frac{5.1}{4{\pi }^{2}}{x}_{1}^{2}+\frac{5}{\pi }{x}_{1}-6\right)}^{2}+10\left(2-\frac{1}{8\pi }\right)-cos{x}_{1}+10\)	\(n=2\)	\({\left[-\text{1,1}\right]}^{2}\)	\(-2\)

Locality Sensitive Hashing-aware Fruit Fly Optimization Algorithm and its application in Edge Server Placement

Status:

Version 1

Abstract

Figures

1 Introduction

2 Related Background

2.1 Fruit fly optimization algorithm

2.2 Locality sensitive hashing

2.3 Edge Server Placement

3 Algorithm

3.1 FOA based on locality sensitive hashing mechanism

3.2 LSHFOA

4 Experimental Analysis

4.1 Experimental environment and parameter settings

4.2 Benchmark functions

5 Lshfoa-esp

6 Result And Discussion

6.1 LSHFOA

6.2 LSHFOA-ESP

7 Conclusion

Declarations

References

Additional Declarations

Status:

Version 1