Memetic evolutionary algorithms to design optical networks with a local search that improves diversity

• Published in: Expert systems with applications 2023-12, Vol.232, p.120805, Article 120805
• Main Authors: Candeias, Jorge, de Araújo, Danilo R.B., Miranda, Péricles, Bastos-Filho, Carmelo J.A.
• Format: Article
• Language: English
• Subjects: Evolutionary algorithms; Local search; Manyobjective optimization; Network design; Optical networks; Pivot rules
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2023.120805

The last few years have seen an increasing demand for high-capacity Internet services, and this need has intensified in the years 2020 and 2021. In 2020 and 2021, Internet usage grew by 50% in several European countries, mainly due to home office, video streaming, hybrid teaching, and others. High-capacity optical networks usually meet this growing demand for Internet services. Thus, investigations that can improve the quality of optical networks are highly relevant in the current context. One of the research problems in this area is related to the physical topology design (PTD) of optical networks, which is classified as NP-hard. Several studies on PTD consider the application of meta-heuristics that obtain suboptimal solutions in a time compatible with engineering applications. However, meta-heuristics and local search techniques have been combined in several other optimization problems, which is not typical for the PTD problem. This paper proposes a solution to the PTD problem that combines a known multipurpose optimization algorithm, the NSGA-III, with operators considering the domain-specific knowledge of the problem to provide superior-quality networks. According to our results, the new proposal presents quality up to 8% higher than previous proposals concerning the hypervolume metrics (HV), maintaining a similar computational cost. •Proposal of pivot rules for local search in many objective algorithms for PTD.•Provide a method for efficient exploration of neighborhood for network optimization.•Proposal of a new local search that considers both convergence and diversity.•Hybridization of NSGA-III with the proposed LS, providing superior quality solutions.