IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v321y2025i1p1-22.html
   My bibliography  Save this article

Biased random-key genetic algorithms: A review

Author

Listed:
  • Londe, Mariana A.
  • Pessoa, Luciana S.
  • Andrade, Carlos E.
  • Resende, Mauricio G.C.

Abstract

This paper is a comprehensive literature review of Biased Random-Key Genetic Algorithms (BRKGA). BRKGA is a metaheuristic that employs random-key-based chromosomes with biased, uniform, and elitist mating strategies in a genetic algorithm framework. The review encompasses over 150 papers with a wide range of applications, including classical combinatorial optimization problems, real-world industrial use cases, and non-orthodox applications such as neural network hyperparameter tuning in machine learning. Scheduling is by far the most prevalent application area in this review, followed by network design and location problems. The most frequent hybridization method employed is local search, and new features aim to increase population diversity. We also detail challenges and future directions for this method. Overall, this survey provides a comprehensive overview of the BRKGA metaheuristic and its applications and highlights important areas for future research.

Suggested Citation

  • Londe, Mariana A. & Pessoa, Luciana S. & Andrade, Carlos E. & Resende, Mauricio G.C., 2025. "Biased random-key genetic algorithms: A review," European Journal of Operational Research, Elsevier, vol. 321(1), pages 1-22.
    • Handle: RePEc:eee:ejores:v:321:y:2025:i:1:p:1-22
    DOI: 10.1016/j.ejor.2024.03.030
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724002303
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.03.030?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Julliany S. Brandão & Thiago F. Noronha & Celso C. Ribeiro, 2016. "A biased random-key genetic algorithm to maximize the number of accepted lightpaths in WDM optical networks," Journal of Global Optimization, Springer, vol. 65(4), pages 813-835, August.
    2. Caio César Freitas & Dario José Aloise & Fábio Francisco Costa Fontes & Andréa Cynthia Santos & Matheus Silva Menezes, 2023. "A biased random-key genetic algorithm for the two-level hub location routing problem with directed tours," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 45(3), pages 903-924, September.
    3. Ricardo Silva & Mauricio Resende & Panos Pardalos, 2014. "Finding multiple roots of a box-constrained system of nonlinear equations with a biased random-key genetic algorithm," Journal of Global Optimization, Springer, vol. 60(2), pages 289-306, October.
    4. H. Faria & M. G. C. Resende & D. Ernst, 2017. "A biased random key genetic algorithm applied to the electric distribution network reconfiguration problem," Journal of Heuristics, Springer, vol. 23(6), pages 533-550, December.
    5. Snyder, Hannah, 2019. "Literature review as a research methodology: An overview and guidelines," Journal of Business Research, Elsevier, vol. 104(C), pages 333-339.
    6. Xiaoyu Yu & Jingyi Qian & Yajing Zhang & Min Kong, 2023. "Supply Chain Scheduling Method for the Coordination of Agile Production and Port Delivery Operation," Mathematics, MDPI, vol. 11(15), pages 1-24, July.
    7. Bonfim Amaro Júnior & Plácido Rogério Pinheiro & Pedro Veras Coelho, 2017. "A Parallel Biased Random-Key Genetic Algorithm with Multiple Populations Applied to Irregular Strip Packing Problems," Mathematical Problems in Engineering, Hindawi, vol. 2017, pages 1-11, September.
    8. Beume, Nicola & Naujoks, Boris & Emmerich, Michael, 2007. "SMS-EMOA: Multiobjective selection based on dominated hypervolume," European Journal of Operational Research, Elsevier, vol. 181(3), pages 1653-1669, September.
    9. R. M. A. Silva & M. G. C. Resende & P. M. Pardalos, 2015. "A Python/C++ library for bound-constrained global optimization using a biased random-key genetic algorithm," Journal of Combinatorial Optimization, Springer, vol. 30(3), pages 710-728, October.
    10. Vivek Kumar Singh & Prashasti Singh & Mousumi Karmakar & Jacqueline Leta & Philipp Mayr, 2021. "The journal coverage of Web of Science, Scopus and Dimensions: A comparative analysis," Scientometrics, Springer;Akadémiai Kiadó, vol. 126(6), pages 5113-5142, June.
    11. David S. Johnson & Lee Breslau & Ilias Diakonikolas & Nick Duffield & Yu Gu & MohammadTaghi Hajiaghayi & Howard Karloff & Mauricio G. C. Resende & Subhabrata Sen, 2020. "Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs," Operations Research, INFORMS, vol. 68(3), pages 896-926, May.
    12. Mauricio Resende, 2012. "Biased random-key genetic algorithms with applications in telecommunications," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 20(1), pages 130-153, April.
    13. F. Stefanello & L. S. Buriol & M. J. Hirsch & P. M. Pardalos & T. Querido & M. G. C. Resende & M. Ritt, 2017. "On the minimization of traffic congestion in road networks with tolls," Annals of Operations Research, Springer, vol. 249(1), pages 119-139, February.
    14. Geiza Silva & André Leite & Raydonal Ospina & Víctor Leiva & Jorge Figueroa-Zúñiga & Cecilia Castro, 2023. "Biased Random-Key Genetic Algorithm with Local Search Applied to the Maximum Diversity Problem," Mathematics, MDPI, vol. 11(14), pages 1-11, July.
    15. Pinto, Bruno Q. & Ribeiro, Celso C. & Rosseti, Isabel & Plastino, Alexandre, 2018. "A biased random-key genetic algorithm for the maximum quasi-clique problem," European Journal of Operational Research, Elsevier, vol. 271(3), pages 849-865.
    16. Oliveira, Beatriz B. & Carravilla, Maria Antónia & Oliveira, José F. & Costa, Alysson M., 2019. "A co-evolutionary matheuristic for the car rental capacity-pricing stochastic problem," European Journal of Operational Research, Elsevier, vol. 276(2), pages 637-655.
    17. Stanisław Mikulski & Andrzej Tomczewski, 2021. "Use of Energy Storage to Reduce Transmission Losses in Meshed Power Distribution Networks," Energies, MDPI, vol. 14(21), pages 1-20, November.
    18. Ruiz, Ruben & Stutzle, Thomas, 2007. "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 2033-2049, March.
    19. Thiago Noronha & Mauricio Resende & Celso Ribeiro, 2011. "A biased random-key genetic algorithm for routing and wavelength assignment," Journal of Global Optimization, Springer, vol. 50(3), pages 503-518, July.
    20. Caserta, Marco & Reiners, Torsten, 2016. "A pool-based pattern generation algorithm for logical analysis of data with automatic fine-tuning," European Journal of Operational Research, Elsevier, vol. 248(2), pages 593-606.
    21. Ramos, António G. & Silva, Elsa & Oliveira, José F., 2018. "A new load balance methodology for container loading problem in road transportation," European Journal of Operational Research, Elsevier, vol. 266(3), pages 1140-1152.
    22. Eduardo Queiroga & Rian G. S. Pinheiro & Quentin Christ & Anand Subramanian & Artur A. Pessoa, 2021. "Iterated local search for single machine total weighted tardiness batch scheduling," Journal of Heuristics, Springer, vol. 27(3), pages 353-438, June.
    23. Pessoa, Luciana S. & Andrade, Carlos E., 2018. "Heuristics for a flowshop scheduling problem with stepwise job objective function," European Journal of Operational Research, Elsevier, vol. 266(3), pages 950-962.
    24. Andrade, Carlos E. & Toso, Rodrigo F. & Gonçalves, José F. & Resende, Mauricio G.C., 2021. "The Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path-Relinking and its real-world applications," European Journal of Operational Research, Elsevier, vol. 289(1), pages 17-30.
    25. Tangpattanakul, Panwadee & Jozefowiez, Nicolas & Lopez, Pierre, 2015. "A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite," European Journal of Operational Research, Elsevier, vol. 245(2), pages 542-554.
    26. Oliveira, Beatriz Brito & Carravilla, Maria Antónia & Oliveira, José Fernando, 2018. "Integrating pricing and capacity decisions in car rental: A matheuristic approach," Operations Research Perspectives, Elsevier, vol. 5(C), pages 334-356.
    27. Bernardo F. Almeida & Isabel Correia & Francisco Saldanha-da-Gama, 2018. "A biased random-key genetic algorithm for the project scheduling problem with flexible resources," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(2), pages 283-308, July.
    28. Galrão Ramos, A. & Oliveira, José F. & Gonçalves, José F. & Lopes, Manuel P., 2016. "A container loading algorithm with static mechanical equilibrium stability constraints," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 565-581.
    29. M. Ericsson & M.G.C. Resende & P.M. Pardalos, 2002. "A Genetic Algorithm for the Weight Setting Problem in OSPF Routing," Journal of Combinatorial Optimization, Springer, vol. 6(3), pages 299-333, September.
    30. Yipeng Huang & Andréa Cynthia Santos & Christophe Duhamel, 2020. "Bi-objective methods for road network problems with disruptions and connecting requirements," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 71(12), pages 1959-1971, December.
    31. Pedrola, Oscar & Careglio, Davide & Klinkowski, Miroslaw & Velasco, Luis & Bergman, Keren & Solé-Pareta, Josep, 2013. "Metaheuristic hybridizations for the regenerator placement and dimensioning problem in sub-wavelength switching optical networks," European Journal of Operational Research, Elsevier, vol. 224(3), pages 614-624.
    32. Pedro Pinacho-Davidson & Christian Blum, 2020. "Barrakuda : A Hybrid Evolutionary Algorithm for Minimum Capacitated Dominating Set Problem," Mathematics, MDPI, vol. 8(11), pages 1-26, October.
    33. Carrabs, Francesco, 2021. "A biased random-key genetic algorithm for the set orienteering problem," European Journal of Operational Research, Elsevier, vol. 292(3), pages 830-854.
    34. Jens Rocholl & Lars Mönch, 2021. "Decomposition heuristics for parallel-machine multiple orders per job scheduling problems with a common due date," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 72(8), pages 1737-1753, August.
    35. Oliveira, Beatriz Brito & Carravilla, Maria Antónia & Oliveira, José Fernando, 2022. "A diversity-based genetic algorithm for scenario generation," European Journal of Operational Research, Elsevier, vol. 299(3), pages 1128-1141.
    36. Min Kong & Jun Pei & Jin Xu & Xinbao Liu & Xiaoyu Yu & Panos M. Pardalos, 2020. "A robust optimization approach for integrated steel production and batch delivery scheduling with uncertain rolling times and deterioration effect," International Journal of Production Research, Taylor & Francis Journals, vol. 58(17), pages 5132-5154, September.
    37. Jonatas B. C. Chagas & Julian Blank & Markus Wagner & Marcone J. F. Souza & Kalyanmoy Deb, 2021. "A non-dominated sorting based customized random-key genetic algorithm for the bi-objective traveling thief problem," Journal of Heuristics, Springer, vol. 27(3), pages 267-301, June.
    38. Fernando Stefanello & Vaneet Aggarwal & Luciana S. Buriol & Mauricio G. C. Resende, 2019. "Hybrid algorithms for placement of virtual machines across geo-separated data centers," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 748-793, October.
    39. Bruno Q. Pinto & Celso C. Ribeiro & Isabel Rosseti & Thiago F. Noronha, 2020. "A biased random-key genetic algorithm for routing and wavelength assignment under a sliding scheduled traffic model," Journal of Global Optimization, Springer, vol. 77(4), pages 949-973, August.
    40. Dalila B. M. M. Fontes & S. Mahdi Homayouni, 2023. "A bi-objective multi-population biased random key genetic algorithm for joint scheduling quay cranes and speed adjustable vehicles in container terminals," Flexible Services and Manufacturing Journal, Springer, vol. 35(1), pages 241-268, March.
    41. James C. Bean, 1994. "Genetic Algorithms and Random Keys for Sequencing and Optimization," INFORMS Journal on Computing, INFORMS, vol. 6(2), pages 154-160, May.
    42. Li, Xueping & Zhang, Kaike, 2018. "Single batch processing machine scheduling with two-dimensional bin packing constraints," International Journal of Production Economics, Elsevier, vol. 196(C), pages 113-121.
    43. Karimi-Mamaghan, Maryam & Mohammadi, Mehrdad & Meyer, Patrick & Karimi-Mamaghan, Amir Mohammad & Talbi, El-Ghazali, 2022. "Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art," European Journal of Operational Research, Elsevier, vol. 296(2), pages 393-422.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    2. Andrade, Carlos E. & Toso, Rodrigo F. & Gonçalves, José F. & Resende, Mauricio G.C., 2021. "The Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path-Relinking and its real-world applications," European Journal of Operational Research, Elsevier, vol. 289(1), pages 17-30.
    3. Soares, Leonardo Cabral R. & Carvalho, Marco Antonio M., 2020. "Biased random-key genetic algorithm for scheduling identical parallel machines with tooling constraints," European Journal of Operational Research, Elsevier, vol. 285(3), pages 955-964.
    4. Giménez-Palacios, Iván & Parreño, Francisco & Álvarez-Valdés, Ramón & Paquay, Célia & Oliveira, Beatriz Brito & Carravilla, Maria Antónia & Oliveira, José Fernando, 2022. "First-mile logistics parcel pickup: Vehicle routing with packing constraints under disruption," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    5. Gonçalves, José Fernando & Wäscher, Gerhard, 2020. "A MIP model and a biased random-key genetic algorithm based approach for a two-dimensional cutting problem with defects," European Journal of Operational Research, Elsevier, vol. 286(3), pages 867-882.
    6. R. M. A. Silva & M. G. C. Resende & P. M. Pardalos, 2015. "A Python/C++ library for bound-constrained global optimization using a biased random-key genetic algorithm," Journal of Combinatorial Optimization, Springer, vol. 30(3), pages 710-728, October.
    7. Caio César Freitas & Dario José Aloise & Fábio Francisco Costa Fontes & Andréa Cynthia Santos & Matheus Silva Menezes, 2023. "A biased random-key genetic algorithm for the two-level hub location routing problem with directed tours," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 45(3), pages 903-924, September.
    8. Fernando Stefanello & Vaneet Aggarwal & Luciana S. Buriol & Mauricio G. C. Resende, 2019. "Hybrid algorithms for placement of virtual machines across geo-separated data centers," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 748-793, October.
    9. Bruno Q. Pinto & Celso C. Ribeiro & Isabel Rosseti & Thiago F. Noronha, 2020. "A biased random-key genetic algorithm for routing and wavelength assignment under a sliding scheduled traffic model," Journal of Global Optimization, Springer, vol. 77(4), pages 949-973, August.
    10. Xiaoyu Yu & Jingyi Qian & Yajing Zhang & Min Kong, 2023. "Supply Chain Scheduling Method for the Coordination of Agile Production and Port Delivery Operation," Mathematics, MDPI, vol. 11(15), pages 1-24, July.
    11. Gonçalves, José Fernando & Resende, Mauricio G.C., 2015. "A biased random-key genetic algorithm for the unequal area facility layout problem," European Journal of Operational Research, Elsevier, vol. 246(1), pages 86-107.
    12. F. Stefanello & L. S. Buriol & M. J. Hirsch & P. M. Pardalos & T. Querido & M. G. C. Resende & M. Ritt, 2017. "On the minimization of traffic congestion in road networks with tolls," Annals of Operations Research, Springer, vol. 249(1), pages 119-139, February.
    13. José Fernando Gonçalves & Mauricio G. C. Resende, 2011. "A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem," Journal of Combinatorial Optimization, Springer, vol. 22(2), pages 180-201, August.
    14. L. A. C. Roque & D. B. M. M. Fontes & F. A. C. C. Fontes, 2014. "A hybrid biased random key genetic algorithm approach for the unit commitment problem," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 140-166, July.
    15. Julliany S. Brandão & Thiago F. Noronha & Celso C. Ribeiro, 2016. "A biased random-key genetic algorithm to maximize the number of accepted lightpaths in WDM optical networks," Journal of Global Optimization, Springer, vol. 65(4), pages 813-835, August.
    16. Tangpattanakul, Panwadee & Jozefowiez, Nicolas & Lopez, Pierre, 2015. "A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite," European Journal of Operational Research, Elsevier, vol. 245(2), pages 542-554.
    17. Geiza Silva & André Leite & Raydonal Ospina & Víctor Leiva & Jorge Figueroa-Zúñiga & Cecilia Castro, 2023. "Biased Random-Key Genetic Algorithm with Local Search Applied to the Maximum Diversity Problem," Mathematics, MDPI, vol. 11(14), pages 1-11, July.
    18. Pinto, Bruno Q. & Ribeiro, Celso C. & Rosseti, Isabel & Plastino, Alexandre, 2018. "A biased random-key genetic algorithm for the maximum quasi-clique problem," European Journal of Operational Research, Elsevier, vol. 271(3), pages 849-865.
    19. Ayşegül Altın & Bernard Fortz & Mikkel Thorup & Hakan Ümit, 2013. "Intra-domain traffic engineering with shortest path routing protocols," Annals of Operations Research, Springer, vol. 204(1), pages 65-95, April.
    20. Dalila B. M. M. Fontes & S. Mahdi Homayouni, 2023. "A bi-objective multi-population biased random key genetic algorithm for joint scheduling quay cranes and speed adjustable vehicles in container terminals," Flexible Services and Manufacturing Journal, Springer, vol. 35(1), pages 241-268, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:321:y:2025:i:1:p:1-22. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.