nPGSAO: A Hybrid Particle Swarm Optimization and Genetic Algorithm With Niching Technology for Edge Server Placement

In this article, we focus on the edge server placement problem (ESPP). ESPP is to decide positions (edge stations) where purchased edge servers (ESs) are placed when a service provider builds or upgrades its edge computing solution. The decision of ESPP largely determines the overall service quality and resource efficiency. We aim at providing ESPP solutions for optimizing the service quality in terms of the system response time, given a set of purchased ESs. To achieve this aim, we first deduce the optimal request dispatch for each edge station based on queue theory and Binomial theorem. Then, based on the deduced result, we formulate ESPP into a discrete nonlinear constrained optimization model. Because ESPP is NP-hard and generally multimodality, we designed a hybrid meta-heuristic algorithm to combine advantages of particle swarm optimization (PSO) and genetic algorithm (GA) as well as the niching technology, which is named nPGSAO. The basic idea of nPGSAO is grouping similar individuals into a niche and finding the niche best. Then, nPGSAO evolves each individual by integrating the swarm intelligence of PSO into the evolutionary process of GA based on its personal and niching best. To evaluate the performance of nPGSAO, we conducted extensive simulated experiments. The results show that nPGSAO achieves 5.78%–40.4% better response time with varied ESPP scale, compared to 11 up-to-date algorithms, and has a linear time complexity with the ESPP scale. These confirm the superior performance and scalability of nPGSAO.