Skip to main content

Advertisement

SpringerLink
Log in

Biased random-key genetic algorithms with applications in telecommunications

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

This paper surveys several applications of biased random-key genetic algorithms (BRKGA) in optimization problems that arise in telecommunications. We first review the basic concepts of BRKGA. This is followed by a description of BRKGA-based heuristics for routing in IP networks, design of survivable IP networks, redundant server location for content distribution, regenerator location in optical networks, and routing and wavelength assignment in optical networks.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Andrade DV, Buriol LS, Resende MGC, Thorup M (2006) Survivable composite-link IP network design with OSPF routing. In: Proceedings of the eighth INFORMS telecommunications conference

    Google Scholar 

  • Bannerjee D, Mukherjee B (1995) Practical approach for routing and wavelength assignment in large wavelength routed optical networks. IEEE J Sel Areas Commun 14:903–908

    Article  Google Scholar 

  • Bean JC (1994) Genetic algorithms and random keys for sequencing and optimization. ORSA J Comput 6:154–160

    Article  Google Scholar 

  • Breslau L, Diakonikolas I, Duffield N, Gu Y, Hajiaghayi M, Johnson DS, Resende MGC, Sen S (2011) Disjoint-path facility location: theory and practice. In: ALENEX 2011: workshop on algorithm engineering and experiments, January 2011

    Google Scholar 

  • Buriol LS, Resende MGC, Ribeiro CC, Thorup M (2002) A memetic algorithm for OSPF routing. In: Proceedings of the 6th INFORMS telecom, Citeseer, pp 187–188

    Google Scholar 

  • Buriol LS, Resende MGC, Ribeiro CC, Thorup M (2005) A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing. Networks 46:36–56

    Article  Google Scholar 

  • Buriol LS, Resende MGC, Thorup M (2007) Survivable IP network design with OSPF routing. Networks 49:51–64

    Article  Google Scholar 

  • Buriol LS, Hirsch MJ, Querido T, Pardalos PM, Resende MGC, Ritt M (2010) A biased random-key genetic algorithm for road congestion minimization. Optim Lett 4:619–633

    Article  Google Scholar 

  • Chen S, Ljubić I, Raghavan S (2010) The regenerator location problem. Networks 55:205–220

    Google Scholar 

  • Dijkstra E (1959) A note on two problems in connection of graphs. Numer Math 1:269–271

    Article  Google Scholar 

  • Duarte A, Martí R, Resende MGC, Silva RMA (2010) Randomized heuristics for the regenerator location problem. Technical report, AT&T Labs Research, Florham Park, New Jersey. URL http://www.research.att.com/~mgcr/doc/gpr-regenloc.pdf

  • Ericsson M, Resende MGC, Pardalos PM (2002) A genetic algorithm for the weight setting problem in OSPF routing. J Comb Optim 6:299–333

    Article  Google Scholar 

  • Flammini M, Machetti A, Monaco G, Moscardelli L, Zaks S (2009) On the complexity of the regenerator placement problem in optical networks. In: Proceedings of SPAA, Calgary, pp 154–162

    Google Scholar 

  • Fontes DBMM, Gonçalves JF (2007) Heuristic solutions for general concave minimum cost network flow problems. Networks 50:67–76

    Article  Google Scholar 

  • Fortz B, Thorup M (2004) Increasing Internet capacity using local search. Comput Optim Appl 29:13–48. Preliminary short version of this paper published as “Internet traffic engineering by optimizing OSPF weights.” In Proc IEEE INFOCOM 2000—the conference on computer communications

    Article  Google Scholar 

  • Gendreau M, Potvin J-Y (eds) (2010) Handbook of metaheuristics, 2nd edn. International series in operations research & management science, vol 146. Springer, Berlin

    Google Scholar 

  • Glover F, Kochenberger G (eds) (2003) Handbook of metaheuristics. Kluwer Academic, Dordrecht

    Google Scholar 

  • Gonçalves JF (2007) A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem. Eur J Oper Res 183:1212–1229

    Article  Google Scholar 

  • Gonçalves JF, Almeida J (2002) A hybrid genetic algorithm for assembly line balancing. J Heuristics 8:629–642

    Article  Google Scholar 

  • Gonçalves JF, Beirão NC (1999) Um algoritmo genético baseado em chaves aleatórias para sequenciamento de operações. Rev Assoc Port Desenvolv Investig Oper 19:123–137

    Google Scholar 

  • Gonçalves JF, Resende MGC (2004) An evolutionary algorithm for manufacturing cell formation. Comput Ind Eng 47:247–273

    Article  Google Scholar 

  • Gonçalves JF, Resende MGC (2010a) A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem. Technical report, AT&T Labs Research, Florham Park, NJ 07733 USA. J Comb Optim. doi:10.1007/s10878-009-9282-1

  • Gonçalves JF, Resende MGC (2010b) Biased random-key genetic algorithms for combinatorial optimization. J Heuristics. doi:10.1007/s10732-010-9143-1

    Google Scholar 

  • Gonçalves JF, Resende MGC (2010c) A parallel multi-population biased random-key genetic algorithm for a container loading problem. Technical report, AT&T Labs Research, URL http://www.research.att.com/~mgcr/doc/brkga-pack3d.pdf

  • Gonçalves JF, Mendes JJM, Resende MGC (2005) A hybrid genetic algorithm for the job shop scheduling problem. Eur J Oper Res 167:77–95

    Article  Google Scholar 

  • Gonçalves JF, Mendes JJM, Resende MGC (2008) A genetic algorithm for the resource constrained multi-project scheduling problem. Eur J Oper Res 189:1171–1190

    Article  Google Scholar 

  • Gonçalves JF, Resende MGC, Mendes JJM (2010) A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem. J Heuristics. doi:10.1007/s10732-010-9142-2

  • Mendes JJM, Gonçalves JF, Resende MGC (2009) A random key based genetic algorithm for the resource constrained project scheduling problem. Comput Oper Res 36:92–109

    Article  Google Scholar 

  • Noronha TF, Ribeiro CC (2006) Routing and wavelength assignment by partition coloring. Eur J Oper Res 171:797–810

    Article  Google Scholar 

  • Noronha TF, Resende MGC, Ribeiro CC (2010) A biased random-key genetic algorithm for routing and wavelength assignment. J Glob Optim. doi:10.1007/s10898-010-9608-7

    Google Scholar 

  • Reis R, Ritt M, Buriol LS, Resende MGC (2010) A biased random-key genetic algorithm for OSPF and DEFT routing to minimize network congestion. Int Trans Oper Res. doi:10.1111/j.1475-3995.2010.00771.x

    Google Scholar 

  • Resende MGC, Pardalos PM (eds) (2006) Handbook of optimization in telecommunications. Springer, Berlin

    Google Scholar 

  • Resende MGC, Toso RF, Gonçalves JF, Silva RMA (2011) A biased random-key genetic algorithm for the Steiner triple covering problem. Optim Lett. doi:10.1007/s11590-011-0285-3

  • Skorin-Kapov N (2007) Routing and wavelength assignment in optical networks using bin packing based algorithms. Eur J Oper Res 177:1167–1179

    Article  Google Scholar 

  • Spears WM, DeJong KA (1991) On the virtues of parameterized uniform crossover. In: Proceedings of the fourth international conference on genetic algorithms, pp 230–236

    Google Scholar 

  • Valente JMS, Gonçalves JF (2008) A genetic algorithm approach for the single machine scheduling problem with linear earliness and quadratic tardiness penalties. Comput Oper Res 35:3696–3713

    Article  Google Scholar 

  • Valente JMS, Gonçalves JF, Alves RAFS (2006) A hybrid genetic algorithm for the early/tardy scheduling problem. Asia-Pac J Oper Res 23:393–405

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Algorithms and Optimization Research Department, AT&T Labs Research, 180 Park Avenue, Room C241, Florham Park, NJ, 07932, USA

    Mauricio G. C. Resende

Authors
  1. Mauricio G. C. Resende
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mauricio G. C. Resende.

Additional information

AT&T Labs Research Technical Report.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Resende, M.G.C. Biased random-key genetic algorithms with applications in telecommunications. TOP 20, 130–153 (2012). https://doi.org/10.1007/s11750-011-0176-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-011-0176-x

Keywords

Mathematics Subject Classification (2000)

Search

Navigation