Active GA Accelerated by Simulated Annealing to Solve SPP in Packet Networks

Daniel S. Fonseca; Elizabeth F. Wanner; Carolina G. Marcelino; Gabriel P. Silva; Silvia Jimenez-Fernandez; Sancho Salcedo-Sanz

doi:10.1007/978-3-031-23236-7_24

Active GA Accelerated by Simulated Annealing to Solve SPP in Packet Networks

Daniel S. Fonseca^*, Elizabeth F. Wanner, Carolina G. Marcelino, Gabriel P. Silva, Silvia Jimenez-Fernandez, Sancho Salcedo-Sanz

^*Corresponding author for this work

Research output: Chapter in Book/Published conference output › Conference publication

Abstract

This paper presents two approaches to deal with the shortest path problem (SPP) solution for routing network packets in an optimized way. The first one uses Simulated Annealing (SA), and the second one is a novel hybridization of the Genetic Algorithm with Dijkstra mutation accelerated by the SA (SGA). Also, two different case scenario configurations, each with 144 nodes, are employed to assess these two proposals, and the total time spent to fill out the routing tables, referring to the transmission of a packet from the initial to the destiny nodes, is measured. A statistical comparison is applied to identify differences among the algorithm’s solutions. Experiments and simulations have shown that the SGA presented competitive results compared to standard SA and can solve the problem with fast convergence, which makes us conclude that it can operate efficiently in actual computer networks.

Original language	English
Title of host publication	Optimization, Learning Algorithms and Applications - Second International Conference, OL2A 2022, Proceedings
Editors	Ana I. Pereira, Andrej Košir, Florbela P. Fernandes, Maria F. Pacheco, João P. Teixeira, Rui P. Lopes
Publisher	Springer
Pages	342-356
ISBN (Print)	9783031232350
DOIs	https://doi.org/10.1007/978-3-031-23236-7_24
Publication status	Published - 1 Jan 2023
Event	2nd International Conference on Optimization, Learning Algorithms and Applications, OL2A 2022 - Braganca, Portugal Duration: 24 Oct 2022 → 25 Oct 2022

Publication series

Name	Communications in Computer and Information Science
Volume	1754 CCIS
ISSN (Print)	1865-0929
ISSN (Electronic)	1865-0937

Conference

Conference	2nd International Conference on Optimization, Learning Algorithms and Applications, OL2A 2022
Country/Territory	Portugal
City	Braganca
Period	24/10/22 → 25/10/22

Funding

Acknowledgment. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 754382. This research has also been partially supported by Comunidad de Madrid, PROMINT-CM project (grant ref: P2018/EMT-4366) and by the project PID2020-115454GB-C21 of the Spanish Ministry of Science and Innovation (MICINN). The authors thank UAH, UFRJ and CEFET-MG for the infrastructure, and Brazilian research agencies for partially support: CAPES (Finance Code 001), FAPERJ, FAPEMIG, and National Council for Scientific and Technological Development - CNPq. “The content of this publication does not reflect the official opinion of the European Union. Responsibility for the information and views expressed herein lies entirely with the author(s).” This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk̷lodowska-Curie grant agreement No 754382. This research has also been partially supported by Comunidad de Madrid, PROMINT-CM project (grant ref: P2018/EMT-4366) and by the project PID2020-115454GB-C21 of the Spanish Ministry of Science and Innovation (MICINN). The authors thank UAH, UFRJ and CEFET-MG for the infrastructure, and Brazilian research agencies for partially support: CAPES (Finance Code 001), FAPERJ, FAPEMIG, and National Council for Scientific and Technological Development-CNPq. “The content of this publication does not reflect the official opinion of the European Union. Responsibility for the information and views expressed herein lies entirely with the author(s).”

Keywords

Evolutionary algorithms
Optimization
Shortest path problem

Access to Document

10.1007/978-3-031-23236-7_24

Cite this

Fonseca, D. S., Wanner, E. F., Marcelino, C. G., Silva, G. P., Jimenez-Fernandez, S., & Salcedo-Sanz, S. (2023). Active GA Accelerated by Simulated Annealing to Solve SPP in Packet Networks. In A. I. Pereira, A. Košir, F. P. Fernandes, M. F. Pacheco, J. P. Teixeira, & R. P. Lopes (Eds.), Optimization, Learning Algorithms and Applications - Second International Conference, OL2A 2022, Proceedings (pp. 342-356). (Communications in Computer and Information Science; Vol. 1754 CCIS). Springer. https://doi.org/10.1007/978-3-031-23236-7_24

Fonseca, Daniel S. ; Wanner, Elizabeth F. ; Marcelino, Carolina G. et al. / Active GA Accelerated by Simulated Annealing to Solve SPP in Packet Networks. Optimization, Learning Algorithms and Applications - Second International Conference, OL2A 2022, Proceedings. editor / Ana I. Pereira ; Andrej Košir ; Florbela P. Fernandes ; Maria F. Pacheco ; João P. Teixeira ; Rui P. Lopes. Springer, 2023. pp. 342-356 (Communications in Computer and Information Science).

@inproceedings{58be4fc49d274938948cca08ab9dd114,

title = "Active GA Accelerated by Simulated Annealing to Solve SPP in Packet Networks",

abstract = "This paper presents two approaches to deal with the shortest path problem (SPP) solution for routing network packets in an optimized way. The first one uses Simulated Annealing (SA), and the second one is a novel hybridization of the Genetic Algorithm with Dijkstra mutation accelerated by the SA (SGA). Also, two different case scenario configurations, each with 144 nodes, are employed to assess these two proposals, and the total time spent to fill out the routing tables, referring to the transmission of a packet from the initial to the destiny nodes, is measured. A statistical comparison is applied to identify differences among the algorithm{\textquoteright}s solutions. Experiments and simulations have shown that the SGA presented competitive results compared to standard SA and can solve the problem with fast convergence, which makes us conclude that it can operate efficiently in actual computer networks.",

keywords = "Evolutionary algorithms, Optimization, Shortest path problem",

author = "Fonseca, {Daniel S.} and Wanner, {Elizabeth F.} and Marcelino, {Carolina G.} and Silva, {Gabriel P.} and Silvia Jimenez-Fernandez and Sancho Salcedo-Sanz",

year = "2023",

month = jan,

day = "1",

doi = "10.1007/978-3-031-23236-7_24",

language = "English",

isbn = "9783031232350",

series = "Communications in Computer and Information Science",

publisher = "Springer",

pages = "342--356",

editor = "Pereira, {Ana I.} and Andrej Ko{\v s}ir and Fernandes, {Florbela P.} and Pacheco, {Maria F.} and Teixeira, {Jo{\~a}o P.} and Lopes, {Rui P.}",

booktitle = "Optimization, Learning Algorithms and Applications - Second International Conference, OL2A 2022, Proceedings",

address = "Germany",

note = "2nd International Conference on Optimization, Learning Algorithms and Applications, OL2A 2022 ; Conference date: 24-10-2022 Through 25-10-2022",

}

Fonseca, DS, Wanner, EF, Marcelino, CG, Silva, GP, Jimenez-Fernandez, S & Salcedo-Sanz, S 2023, Active GA Accelerated by Simulated Annealing to Solve SPP in Packet Networks. in AI Pereira, A Košir, FP Fernandes, MF Pacheco, JP Teixeira & RP Lopes (eds), Optimization, Learning Algorithms and Applications - Second International Conference, OL2A 2022, Proceedings. Communications in Computer and Information Science, vol. 1754 CCIS, Springer, pp. 342-356, 2nd International Conference on Optimization, Learning Algorithms and Applications, OL2A 2022, Braganca, Portugal, 24/10/22. https://doi.org/10.1007/978-3-031-23236-7_24

Active GA Accelerated by Simulated Annealing to Solve SPP in Packet Networks. / Fonseca, Daniel S.; Wanner, Elizabeth F.; Marcelino, Carolina G. et al.
Optimization, Learning Algorithms and Applications - Second International Conference, OL2A 2022, Proceedings. ed. / Ana I. Pereira; Andrej Košir; Florbela P. Fernandes; Maria F. Pacheco; João P. Teixeira; Rui P. Lopes. Springer, 2023. p. 342-356 (Communications in Computer and Information Science; Vol. 1754 CCIS).

Research output: Chapter in Book/Published conference output › Conference publication

TY - GEN

T1 - Active GA Accelerated by Simulated Annealing to Solve SPP in Packet Networks

AU - Fonseca, Daniel S.

AU - Wanner, Elizabeth F.

AU - Marcelino, Carolina G.

AU - Silva, Gabriel P.

AU - Jimenez-Fernandez, Silvia

AU - Salcedo-Sanz, Sancho

PY - 2023/1/1

Y1 - 2023/1/1

N2 - This paper presents two approaches to deal with the shortest path problem (SPP) solution for routing network packets in an optimized way. The first one uses Simulated Annealing (SA), and the second one is a novel hybridization of the Genetic Algorithm with Dijkstra mutation accelerated by the SA (SGA). Also, two different case scenario configurations, each with 144 nodes, are employed to assess these two proposals, and the total time spent to fill out the routing tables, referring to the transmission of a packet from the initial to the destiny nodes, is measured. A statistical comparison is applied to identify differences among the algorithm’s solutions. Experiments and simulations have shown that the SGA presented competitive results compared to standard SA and can solve the problem with fast convergence, which makes us conclude that it can operate efficiently in actual computer networks.

AB - This paper presents two approaches to deal with the shortest path problem (SPP) solution for routing network packets in an optimized way. The first one uses Simulated Annealing (SA), and the second one is a novel hybridization of the Genetic Algorithm with Dijkstra mutation accelerated by the SA (SGA). Also, two different case scenario configurations, each with 144 nodes, are employed to assess these two proposals, and the total time spent to fill out the routing tables, referring to the transmission of a packet from the initial to the destiny nodes, is measured. A statistical comparison is applied to identify differences among the algorithm’s solutions. Experiments and simulations have shown that the SGA presented competitive results compared to standard SA and can solve the problem with fast convergence, which makes us conclude that it can operate efficiently in actual computer networks.

KW - Evolutionary algorithms

KW - Optimization

KW - Shortest path problem

UR - https://link.springer.com/chapter/10.1007/978-3-031-23236-7_24

UR - http://www.scopus.com/inward/record.url?scp=85147994607&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-23236-7_24

DO - 10.1007/978-3-031-23236-7_24

M3 - Conference publication

AN - SCOPUS:85147994607

SN - 9783031232350

T3 - Communications in Computer and Information Science

SP - 342

EP - 356

BT - Optimization, Learning Algorithms and Applications - Second International Conference, OL2A 2022, Proceedings

A2 - Pereira, Ana I.

A2 - Košir, Andrej

A2 - Fernandes, Florbela P.

A2 - Pacheco, Maria F.

A2 - Teixeira, João P.

A2 - Lopes, Rui P.

PB - Springer

T2 - 2nd International Conference on Optimization, Learning Algorithms and Applications, OL2A 2022

Y2 - 24 October 2022 through 25 October 2022

ER -

Fonseca DS, Wanner EF, Marcelino CG, Silva GP, Jimenez-Fernandez S, Salcedo-Sanz S. Active GA Accelerated by Simulated Annealing to Solve SPP in Packet Networks. In Pereira AI, Košir A, Fernandes FP, Pacheco MF, Teixeira JP, Lopes RP, editors, Optimization, Learning Algorithms and Applications - Second International Conference, OL2A 2022, Proceedings. Springer. 2023. p. 342-356. (Communications in Computer and Information Science). doi: 10.1007/978-3-031-23236-7_24