Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Wireless Networks
Published in: Wireless Networks 7/2020

15-12-2018

Approximating the Pareto front of a bi-objective problem in telecommunication networks using a co-evolutionary algorithm

Authors: José-Fernando Camacho-Vallejo, Cristóbal Garcia-Reyes

Published in: Wireless Networks | Issue 7/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper studies a telecommunication network design problem. In this network, users must be connected to capacitated hubs. Then, hubs that concentrate users must be connected to each other and possibly to other hubs with no users. The connections in the network must lead to a tree topology. Hence, connection between hubs can be considered as looking for forming a Steiner tree. This problem is modeled as a bi-objective mathematical programming problem. One objective function minimizes user’s latency with respect to the information packages flowing through the capacitated hubs, and the other objective function aims the minimization of the total network’s connection cost. To approximate the Pareto front of this bi-objective problem, a co-evolutionary algorithm is developed. In the proposed algorithm, two populations are considered. Each population is associated with one objective function. The co-evolutionary operator consists of an information exchange between both populations that occurs after the genetic operators have been applied. As a result of this co-evolutionary operator, the non-dominated solutions are identified. Computational experimentation shows that the approximated Pareto fronts are representative despite their non-convexity, and they contain a sufficient number of non-dominated solutions over the tested instances. Also, the kth distance among non-dominated solutions is relatively small, which indicates that the approximated Pareto fronts are dense. Furthermore, the required computational time is very small for a problem with the characteristics herein considered.
previous article Packing ellipses in an optimized rectangular container
next article Towards a capability maturity model for digital forensic readiness

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Van Hoesel, S. (2005). Optimization in telecommunication networks. Statistica Neerlandica, 59(2), 180–205.MathSciNetMATH
2.
Corne, D., Oates, M. J., & Smith, G. D. (Eds.). (2000). Telecommunications optimization: Heuristics and adaptive techniques. New York: Wiley.
3.
Vasant, P., Litvinchev, I., & Marmolejo-Saucedo, J. A. (Eds.). (2017). Modeling, simulation, and optimization. Berlin: Springer.
4.
Minoux, M. (1989). Networks synthesis and optimum network design problems: Models, solution methods and applications. Networks, 19(3), 313–360.MathSciNetMATH
5.
6.
Du, D. Z., Lu, B., Ngo, H., & Pardalos, P. M. (2009). Steiner tree problems. In C. A. Floudas & P. M. Pardalos (Eds.), Encyclopedia of optimization (2nd ed.). Berlin: Springer.
7.
Dror, M., & Haouari, M. (2000). Generalized Steiner problems and other variants. Journal of Combinatorial Optimization, 4, 415–436.MathSciNetMATH
8.
Biniaz, A., Maheshwari, A., & Smid, M. (2015). On the hardness of full Steiner tree problems. Journal of Discrete Algorithms, 34, 118–127.MathSciNetMATH
9.
Khuller, S., & Zhu, A. (2002). The general Steiner tree-star problem. Information Processing Letters, 84, 215–220.MathSciNetMATH
10.
Marmolejo, J. A., Litvinchev, I., Aceves, R., & Ramirez, J. M. (2011). Multiperiod optimal planning of thermal generation using cross decomposition. Journal of Computer and Systems Sciences International, 50(5), 793–804.MathSciNetMATH
11.
Voss, S. (1992). Steiner’s problem in graphs: Heuristic methods. Discrete Applied Mathematics, 40, 45–72.MathSciNetMATH
12.
Plesník, J. (1992). Heuristics for the Steiner problem in graphs. Discrete Applied Mathematics, 37, 451–463.MathSciNetMATH
13.
Martins, S. L., Ribeiro, C., & Souza, M. (1998). A parallel GRASP for the Steiner problem in graphs. In A. Ferreira, & J. Rolim, (Eds.), Proceedings of IRREGULAR98 5th international symposium on solving irregularly structured problems in parallel, vol. 1457 of lecture notes in computer science (pp. 285–297). Berlin: Springer.
14.
Consoli, S., Pérez, J. M., Darby-Dowman, K., & Mladenović, N. (2008). Discrete particle swarm optimization for the minimum labelling Steiner tree problem. In Nature inspired cooperative strategies for optimization (NICSO 2007) (pp. 313–322). Berlin: Springer.
15.
Ribeiro, C. C., & De Souza, M. C. (2000). Tabu search for the Steiner problem in graphs. Networks: An International Journal, 36(2), 138–146.MathSciNetMATH
16.
Gendreau, M., Larochelle, J. F., & Sanso, B. (1999). A tabu search heuristic for the Steiner tree problem. Networks: An International Journal, 34(2), 162–172.MathSciNetMATH
17.
Bastos, M. P., & Ribeiro, C. C. (2002). Reactive tabu search with path-relinking for the Steiner problem in graphs. In C. C. Ribeiro, & P. Hansen (Eds.), Essays and surveys in metaheuristics. Operations research/computer science interfaces series (Vol. 15, pp. 39–58). Boston, MA: Springer.
18.
Consoli, S., Darby-Dowman, K., Mladenović, N., & Moreno-Pérez, J. A. (2009). Variable neighbourhood search for the minimum labelling Steiner tree problem. Annals of Operations Research, 172(1), 71–96.MathSciNetMATH
19.
Camacho-Vallejo, J.-F., Mar-Ortiz, J., López-Ramos, F., & Rodríguez, R. P. (2015). A genetic algorithm for the bi-level topological design of local area networks. PLoS ONE, 10(6), 1–21.
20.
Dehouche, N. (2018). Devolutionary genetic algorithms with application to the minimum labeling Steiner tree problem. Evolving Systems, 9, 157–168.
21.
Liu, L., Song, Y., Zhang, H., Ma, H., & Vasilakos, A. V. (2015). Physarum optimization: A biology-inspired algorithm for the Steiner tree problem in networks. IEEE Transactions on Computers, 64(3), 818–831.MathSciNetMATH
22.
Gouveia, L., Leitner, M., & Ljubić, I. (2014). Hop constrained Steiner trees with multiple root nodes. European Journal of Operational Research, 236, 100–112.MathSciNetMATH
23.
Fu, Z.-H., & Hao, J.-K. (2014). Breakout local search for the Steiner tree problem with revenue, budget and hop constraints. European Journal of Operational Research, 232, 209–220.MathSciNetMATH
24.
Leggieri, V., Haouari, M., & Triki, Ch. (2014). The Steiner tree problem with delays: A compact formulation and reduction procedures. Discrete Applied Mathematics, 164, 178–190.MathSciNetMATH
25.
DiPuglia, L., Gaudioso, M., Guerriero, F., & Miglionico, G. (2018). A Lagrangean-based decomposition approach for the link constrained Steiner tree problem. Optimization Methods and Software, 33(3), 650–670.MathSciNetMATH
26.
Xu, J., Chiu, S. Y., & Glover, F. (1996). Using tabu search to solve the Steiner tree-star problem in telecommunications network design. Telecommunication Systems, 6, 117–125.
27.
Lee, Y., Lu, L., & Qiu, Y. (1994). Strong formulations and cutting planes for designing digital data service networks. Telecommunication Systems, 2, 261–274.
28.
Clarke, L. W., & Anandalingam, G. (1996). An integrated system for designing minimum cost survivable telecommunications networks. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 26(6), 856–862.
29.
Ersoy, C., & Panwar, S. S. (1993). Topological design of interconnected LAN/MAN networks. IEEE Journal on Selected Areas in Communications, 2(8), 1172–1182.
30.
Girard, A. (1993). Revenue optimization of telecommunication networks. IEEE Transactions on Communications, 41(4), 583–591.MATH
31.
Chen, D., Du, D. Z., Hu, X. D., Lin, G. H., Wang, L., & Xue, G. (2000). Approximations for Steiner trees with minimum number of Steiner points. Journal of Global Optimization, 18(1), 17–33.MathSciNetMATH
32.
Orlowski, S., & Wessaly, R. (2006). The effect of hop limits on optimal cost in survivable network design. In S. Raghavan, & G. Anandalingam (Eds.) Telecommunications planning: Innovations in pricing, network design and management. Operations research/computer science interfaces series (Vol. 33, pp. 151–166). Boston, MA: Springer.
33.
Sitters, R. (2002). The minimum latency problem is NP-hard for weighted trees. In International conference on integer programming and combinatorial optimization (pp. 230–239), Berlin: Springer.
34.
Martins, S. L., & Ferreira, N. G. (2011). A bi-criteria approach for Steiner’s tree problems in communication networks. In U. Krieger, & P. Van Mieghem (Eds.), Proceedings of international workshop on modeling, analysis and control of complex networks, ITCP (International Teletraffic Congress, San Francisco) (pp. 37–44).
35.
Marathe, M. V., Ravi, R., Sundaram, R., Ravi, S. S., Rosenkrantz, D. J., & Hunt, H. B, I. I. I. (1998). Bicriteria network design problems. Journal of Algorithms, 28(1), 142–171.MathSciNetMATH
36.
Potter, M. A. (1997). The design and analysis of a computational model of cooperative co-evolution, Ph.D. Thesis, George Mason University.
37.
Venter, G., & Haftka, R. T. (1996). A two species genetic algorithm for designing composite laminates subjected to uncertainty. In Proceedings of 37th AIAA/ASME/ASCE/AHS/ASC structures, structural dynamics, and materials conference (pp. 1848–1857).
38.
Sun, Y., Zhang, L., & Gu, X. (2012). A hybrid co-evolutionary cultural algorithm based on particle swarm optimization for solving global optimization problems. Neurocomputing, 98, 76–89.
39.
Goh, C. K., Tan, K. C., Liu, D. S., & Chiam, S. C. (2010). A competitive and cooperative co-evolutionary approach to multi-objective particle swarm optimization algorithm design. European Journal of Operational Research, 202(1), 42–54.MATH
40.
Gen, M., Kumar, A., & Kim, J. R. (2005). Recent network design techniques using evolutionary algorithms. International Journal of Production Economics, 98(2), 251–261.
41.
Wang, X., Wang, S., & Ma, J. J. (2007). An improved co-evolutionary particle swarm optimization for wireless sensor networks with dynamic deployment. Sensors, 7(3), 354–370.
42.
Casas-Ramírez, M. S., & Camacho-Vallejo, J. F. (2017). Solving the p-median bilevel problem with order through a hybrid heuristic. Applied Soft Computing, 60, 73–86.
43.
Kim, J. R., Lee, J. U., & Jo, J. B. (2009). Hierarchical spanning tree network design with Nash genetic algorithm. Computers & Industrial Engineering, 56(3), 1040–1052.
44.
Sipper, M., Fu, W., Ahuja, K., & Moore, J. H. (2018). Investigating the parameter space of evolutionary algorithms. BioData Mining, 11(2), 2–14.
45.
Martí, R., González-Velarde, J. L., & Duarte, A. (2009). Heuristics for the bi-objective path dissimilarity problem. Computers & Operations Research, 36(11), 2905–2912.MATH
46.
Bard, J. F. (1998). Practical bilevel optimization: Algorithms and applications. Dordrecht: Kluwer.MATH
47.
48.
Sinha, A., Malo, P., & Deb, K. (2018). A review on bilevel optimization: From classical to evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22(2), 276–295.
49.
Cruz-Mejia, O., Marmolejo, J. A., & Vasant, P. (2018). Lead time performance in a internet product delivery supply chain with automatic consolidation. Journal of Ambient Intelligence and Humanized Computing, 9(3), 867–874.
50.
Ibarra-Rojas, O. J., Delgado, F., Giesen, R., & Muñoz, J. C. (2015). Planning, operation, and control of bus transport systems: A literature review. Transportation Research Part B: Methodological, 77, 38–75.
Metadata
Title
Approximating the Pareto front of a bi-objective problem in telecommunication networks using a co-evolutionary algorithm
Authors
José-Fernando Camacho-Vallejo
Cristóbal Garcia-Reyes
Publication date
15-12-2018
Publisher
Springer US
Published in
Wireless Networks / Issue 7/2020
Print ISSN: 1022-0038
Electronic ISSN: 1572-8196
DOI
https://doi.org/10.1007/s11276-018-01921-4

Other articles of this Issue 7/2020

Wireless Networks 7/2020 Go to the issue

OriginalPaper

Enhancing iris template matching with the optimal path method

OriginalPaper

Break-and-join tree construction for latency-aware data aggregation in wireless sensor networks

OriginalPaper

An optimization model for investment in technology and government regulation

OriginalPaper

Impacts of sleeping time during the day on the timing and level of basal heart rate: analysis of ALLSTAR big data

OriginalPaper

Channel estimation and error correction for UWOC system with vertical non-line-of-sight channel

OriginalPaper

Model-aided distributed shallow learning for OFDM receiver in IEEE 802.11 channel model