research-article

Open access

Comparing Evolutionary Optimization Algorithms for the Fog Service Placement Problem

Authors:

Carlos GuerreroAuthors Info & Claims

UCC '23: Proceedings of the IEEE/ACM 16th International Conference on Utility and Cloud Computing

Article No.: 57, Pages 1 - 6

https://doi.org/10.1145/3603166.3632547

Published: 04 April 2024 Publication History

Abstract

In this work, we compare the performance of six popular evolutionary algorithms to address the problem of allocating applications to devices in a fog infrastructure. The optimization of application placement is carried out with the objectives of minimizing the number of devices assigned to applications and reducing the network distance between applications and the users who request them. We evaluate the algorithms based on their proximity to the true Pareto front and the diversity of the solution space they provide. The experimental phase demonstrates that the non-dominated sorting genetic algorithm family (NSGA) of algorithms achieves Pareto fronts that closely approach the true Pareto front, as determined by ILP optimization.

References

[1]

2020. Multi-Agent Genetic Algorithm for Efficient Load Balancing in Cloud Computing. International Journal of Innovative Technology and Exploring Engineering (2020). https://api.semanticscholar.org/CorpusID:243179574

[2]

Merve Nur Aktan and Hasan Bulut. 2021. Metaheuristic task scheduling algorithms for cloud computing environments. Concurrency and Computation: Practice and Experience 34 (2021). https://api.semanticscholar.org/CorpusID:237680048

[3]

Nicola Beume, Boris Naujoks, and Michael Emmerich. 2007. SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research 181, 3 (2007), 1653--1669.

[4]

Julian Blank and Kalyanmoy Deb. 2020. Pymoo: Multi-Objective Optimization in Python. IEEE Access 8 (2020), 89497--89509.

[5]

Antonio Brogi, Stefano Forti, Carlos Guerrero, and Isaac Lera. 2019. Meet Genetic Algorithms in Monte Carlo: Optimised Placement of Multi-Service Applications in the Fog. 2019 IEEE International Conference on Edge Computing (EDGE) (2019), 13--17. https://api.semanticscholar.org/CorpusID:201666743

[6]

Antonio Brogi, Stefano Forti, Carlos Guerrero, and Isaac Lera. 2020. How to place your apps in the fog: State of the art and open challenges. Software: Practice and Experience 50, 5 (2020), 719--740.

[7]

Claudia Canali and Riccardo Lancellotti. 2019. GASP: Genetic Algorithms for Service Placement in Fog Computing Systems. Algorithms 12 (2019), 201. https://api.semanticscholar.org/CorpusID:204183689

[8]

Ying Chang-tian and Yu Jiong. 2012. Energy-Aware Genetic Algorithms for Task Scheduling in Cloud Computing. 2012 Seventh ChinaGrid Annual Conference (2012), 43--48. https://api.semanticscholar.org/CorpusID:36856293

[9]

Ran Cheng, Yaochu Jin, Markus Olhofer, and Bernhard Sendhoff. 2016. A Reference Vector Guided Evolutionary Algorithm for Many-Objective Optimization. IEEE Transactions on Evolutionary Computation 20, 5 (2016), 773--791.

[10]

Indraneel Das and J. E. Dennis. 1998. Normal-Boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems. SIAM Journal on Optimization 8, 3 (1998), 631--657.

Digital Library

[11]

Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, and T. Meyarivan. 2002. A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA-II. Lecture rates in Computer Science 1917.

[12]

Kalyanmoy Deb and Himanshu Jain. 2014. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Non-dominated Sorting Approach, Part I: Solving Problems With Box Constraints. IEEE Transactions on Evolutionary Computation 18, 4 (2014), 577--601.

[13]

Kusum Deep, Krishna Pratap Singh, M.L. Kansal, and C. Mohan. 2009. A real coded genetic algorithm for solving integer and mixed integer optimization problems. Appl. Math. Comput. 212, 2 (2009), 505--518.

Digital Library

[14]

Kusum Deep and Manoj Thakur. 2007. A new mutation operator for real coded genetic algorithms. Appl. Math. Comput. 193, 1 (2007), 211--230.

[15]

Carlos Fonseca and Peter Fleming. 1999. Genetic Algorithms for Multiobjective Optimization: Formulation Discussion and Generalization. the fifth Intl conference on Genetic Algorithms 93 (02 1999).

[16]

José Gonçalves and Mauricio Resende. 2011. Biased random-key genetic algorithms for combinatorial optimization. J. Heuristics 17 (10 2011), 487--525.

Digital Library

[17]

Carlos Guerrero, Isaac Lera, and Carlos Juiz. 2022. Genetic-based optimization in fog computing: Current trends and research opportunities. Swarm and Evolutionary Computation 72 (2022), 101094.

[18]

Ahmed Hamed and Monagi H. Alkinani. 2021. Task Scheduling Optimization in Cloud Computing Based on Genetic Algorithms. Computers, Materials & Continua (2021). https://api.semanticscholar.org/CorpusID:239747753

[19]

Sourabh Katoch, Sumit Singh Chauhan, and Vijay Kumar. 2020. A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications 80 (2020), 8091--8126. https://api.semanticscholar.org/CorpusID:226227415

Digital Library

[20]

Mohammad Ali Khoshkholghi, Javid Taheri, Deval Bhamare, and Andreas Kassler. 2019. Optimized Service Chain Placement Using Genetic Algorithm. 2019 IEEE Conference on Network Softwarization (NetSoft) (2019), 472--479. https://api.semanticscholar.org/CorpusID:201620078

[21]

Ke Li, Renzhi Chen, Guangtao Fu, and Xin Yao. 2019. Two-Archive Evolutionary Algorithm for Constrained Multiobjective Optimization. IEEE Transactions on Evolutionary Computation 23, 2 (2019), 303--315.

[22]

Adyson Magalhães Maia, Yacine Ghamri-Doudane, Dario Vieira, and Miguel Franklin de Castro. 2019. A Multi-Objective Service Placement and Load Distribution in Edge Computing. 2019 IEEE Global Communications Conference (GLOBECOM) (2019), 1--7. https://api.semanticscholar.org/CorpusID:211686170

Digital Library

[23]

Mohsen Mosayebi and Manbir Sodhi. 2020. Tuning Genetic Algorithm Parameters Using Design of Experiments. Association for Computing Machinery, New York, NY, USA, 1937--1944.

Digital Library

[24]

Giuseppe Portaluri and Stefano Giordano. 2015. Power efficient resource allocation in cloud computing data centers using multi-objective genetic algorithms and simulated annealing. 2015 IEEE 4th International Conference on Cloud Networking (CloudNet) (2015), 319--321. https://api.semanticscholar.org/CorpusID:9498321

[25]

Haitham Seada and Kalyanmoy Deb. 2016. A Unified Evolutionary Optimization Procedure for Single, Multiple, and Many Objectives. IEEE Transactions on Evolutionary Computation 20, 3 (2016), 358--369.

Digital Library

[26]

N. Srinivas and Kalyanmoy Deb. 1994. Muiltiobjective Optimization Using Nondominated Sorting in Genetic Algorithms. Evol. Comput. 2, 3 (sep 1994), 221--248.

Digital Library

[27]

Gilbert Syswerda et al. 1989. Uniform crossover in genetic algorithms. In ICGA, Vol. 3. 2--9.

Cited By

Lera IGuerrero C(2024)Multi-objective application placement in fog computing using graph neural network-based reinforcement learningThe Journal of Supercomputing10.1007/s11227-024-06439-580:19(27073-27094)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s11227-024-06439-5

Recommendations

Evaluation and efficiency comparison of evolutionary algorithms for service placement optimization in fog architectures
Abstract
This study compares three evolutionary algorithms for the problem of fog service placement: weighted sum genetic algorithm (WSGA), non-dominated sorting genetic algorithm II (NSGA-II), and multiobjective evolutionary algorithm based on ...
Highlights
- Comparison of three evolutionary algorithms for fog service placement.
- ...
Evolutionary algorithms and multi-objectivization for the travelling salesman problem
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

This paper studies the multi-objectivization of single-objective optimization problems (SOOP) using evolutionary multi-objective algorithms (EMOAs). In contrast to the single-objective case, diversity can be introduced by the multi-objective view of the ...
Distributed genetic algorithm for application placement in the compute continuum leveraging infrastructure nodes for optimization
Abstract
The increasing complexity of Compute Continuum environments calls for efficient resource optimization techniques. In this paper, we propose and evaluate three distributed designs of a genetic algorithm (GA) for resource optimization, within an ...
Highlights
- Three distributed genetic algorithm designs for the Compute Continuum.
- Resource optimization execution distributed across the infrastructure’s devices.
- Lightweight implementation using the MQTT protocol.
- Experiments based on a ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

UCC '23: Proceedings of the IEEE/ACM 16th International Conference on Utility and Cloud Computing

December 2023

502 pages

ISBN:9798400702341

DOI:10.1145/3603166

Co-chairs:
Omer Rana,
Massimo Villari,
Program Co-chairs:
Song Fu,
Lorenzo Carnevale

Copyright © 2023 Copyright is held by the owner/author(s). Publication rights licensed to ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 April 2024

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

MCIN/AEI/10.13039 /501100011033
European Union NextGenerationEU/PRTR

Conference

UCC '23

Sponsor:

SIGARCH

UCC '23: IEEE/ACM 16th International Conference on Utility and Cloud Computing

December 4 - 7, 2023

Taormina (Messina), Italy

Acceptance Rates

Overall Acceptance Rate 38 of 125 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
110
Total Downloads

Downloads (Last 12 months)110
Downloads (Last 6 weeks)12

Reflects downloads up to 28 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lera IGuerrero C(2024)Multi-objective application placement in fog computing using graph neural network-based reinforcement learningThe Journal of Supercomputing10.1007/s11227-024-06439-580:19(27073-27094)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s11227-024-06439-5

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents