tutorial

Biased Ranom-Key Genetic Algorithms: An Advanced Tutorial

Authors:

Mauricio G.C. Resende,

Celso C. RibeiroAuthors Info & Claims

GECCO '16 Companion: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion

Pages 483 - 514

https://doi.org/10.1145/2908961.2926996

Published: 20 July 2016 Publication History

Get Access

Abstract

A biased random-key genetic algorithm (BRKGA) is a general search procedure for finding optimal or near-optimal solutions to hard combinatorial optimization problems. It is derived from the random-key genetic algorithm of Bean (1994), differing in the way solutions are combined to produce offspring. BRKGAs have three key features that specialize genetic algorithms:

A fixed chromosome encoding using a vector of N random keys or alleles over the real interval [0, 1), where the value of N depends on the instance of the optimization problem;

A well-defined evolutionary process adopting parameterized uniform crossover to generate offspring and thus evolve the population;

The introduction of new chromosomes called mutants in place of the mutation operator usually found in evolutionary algorithms.

Such features simplify and standardize the procedure with a set of self-contained tasks from which only one is problem-dependent: that of decoding a chromosome, i.e. using, the keys to construct a solution to the underlying optimization problem, from which the objective function value or fitness can be computed. BRKGAs have the additional characteristic that, under a weak assumption, crossover always produces feasible offspring and, therefore, a repair or healing procedure to recover feasibility is not required in a BRKGA.

In this tutorial we review the basic components of a BRKGA and introduce an Application Programming Interface (API) for quick implementations of BRKGA heuristics. We then apply the framework to a number of hard combinatorial optimization problems, including 2-D and 3-D packing problems, network design problems, routing problems, scheduling problems, and data mining. We conclude with a brief review of other domains where BRKGA heuristics have been applied.

References

[1]

J.F. Gonçalves and M.G.C.Resende, "Biased random-key genetic algorithms for combinatorial optimization," J. of Heuristics, vol.17, pp. 487--525, 201 J.F. Gonçalves, M.G.C. Resende., and R.F. Toso, "An experimental comparison of biased and unbiased random-key genetic algorithms", Pesquisa Operacional, vol. 34, pp. 143--164, 2014.

Digital Library

Google Scholar

[2]

R. F. Toso and M.G.C. Resende, "A C++ Application Programming Interface for Biased Random-Key Genetic Algorithms," Optimization Methods & Software, vol. 30, pp. 81--93, 2015.

Digital Library

Google Scholar

[3]

J.F. Gonçalves and M.G.C. Resende, "A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem," Journal of Combinatorial Optimization, vol. 22, pp. 180--201, 2011.

Digital Library

Google Scholar

[4]

J.F. Gonçalves and M.G.C. Resende, "A parallel multi-population biased random-key genetic algorithm for a container loading problem," Computers & Operations Research, vol. 29, pp. 179--190, 2012.

Digital Library

Google Scholar

[5]

J.F. Gonçalves and M.G.C. Resende, "A biased random-key genetic algorithm for 2D and 3D bin packing problems," International J. of Production Economics, vol. 15, pp. 500--510, 2013.

Crossref

Google Scholar

[6]

J.F. Gonçalves and M.G.C. Resende, "A biased random-key genetic algorithm for the unequal area facility layout problem," European J. of Operational Research, vol. 246, pp. 86--107, 2015.

Crossref

Google Scholar

[7]

M. Ericsson, M.G.C.Resende, and P.M. Pardalos, "A genetic algorithm for the weight setting problem in OSPF routing," J. of Combinatorial Optimization, vol. 6, pp. 299--333, 2002.

Crossref

Google Scholar

[8]

L.S. Buriol, M.G.C.Resende, C.C. Ribeiro, and M. Thorup, "A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing," Networks, vol. 46, pp. 36--56, 2005.

Digital Library

Google Scholar

[9]

L. Breslau, I. Diakonikolas, N. Duffield, Y. Gu, M. Hajiaghayi, D.S. Johnson, H. Karloff, M.G.C. Resende, and S. Sen, "Disjoint-path facility location: Theory and practice," Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments (ALENEX11), SIAM, San Francisco, pp. 60--74, January 22, 2011.

Digital Library

Google Scholar

[10]

J.S. Brandão, T.G. Noronha, M.G.C. Resende, and C.C. Ribeiro, "Biased random key genetic algorithms for scheduling divisible loads: single- and multi-round cases," Proceedings of MISTA, Prague, 2015.

Google Scholar

Cited By

View all

Abdul Halim ADas SIsmail IAbdul Halim ADas SIsmail I(2025)Algorithm Parameters: Tuning and ControlInto a Deeper Understanding of Evolutionary Computing: Exploration, Exploitation, and Parameter Control10.1007/978-3-031-75577-4_2(153-283)Online publication date: 18-Jan-2025
https://doi.org/10.1007/978-3-031-75577-4_2
Muñoz-Sánchez RMartínez-Salazar IGonzález-Velarde JRíos Solís Y(2024)Two hybrid flow shop scheduling lines with assembly stage and compatibility constraintsPLOS ONE10.1371/journal.pone.030411919:6(e0304119)Online publication date: 21-Jun-2024
https://doi.org/10.1371/journal.pone.0304119
Noronha TRibeiro C(2024)Biased random-key genetic algorithms: A tutorial with applicationsProceedings of the 2024 8th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence10.1145/3665065.3665083(110-115)Online publication date: 24-Apr-2024
https://dl.acm.org/doi/10.1145/3665065.3665083
Show More Cited By

Index Terms

Biased Ranom-Key Genetic Algorithms: An Advanced Tutorial
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Bio-inspired approaches

Recommendations

Biased random-key genetic algorithms for combinatorial optimization

Random-key genetic algorithms were introduced by Bean (ORSA J. Comput. 6:154---160, 1994) for solving sequencing problems in combinatorial optimization. Since then, they have been extended to handle a wide class of combinatorial optimization problems. ...
A modified VNS metaheuristic for max-bisection problems

Variable neighborhood search (VNS) metaheuristic as presented in Festa et al. [Randomized heuristics for the MAX-CUT problem, Optim. Methods Software 17 (2002) 1033-1058] can obtain high quality solution for max-cut problems. Therefore, it is worthwhile ...
Local search algorithms for the k-cardinality tree problem

In this paper we deal with an NP-hard combinatorial optimization problem, the k-cardinality tree problem in node-weighted graphs. This problem has several applications, which justify the need for efficient methods to obtain good solutions. We review ...

Comments

Information & Contributors

Information

Published In

GECCO '16 Companion: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion

July 2016

1510 pages

ISBN:9781450343237

DOI:10.1145/2908961

Editor:
Tobias Friedrich
Hasso Plattner Institute
,
General Chair:
Frank Neumann
University of Adelaide
,
Program Chair:
Andrew M. Sutton
Hasso Plattner Institute

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 July 2016

Check for updates

Author Tags

Qualifiers

Tutorial

Conference

GECCO '16

Sponsor:

SIGEVO

GECCO '16: Genetic and Evolutionary Computation Conference

July 20 - 24, 2016

Colorado, Denver, USA

Acceptance Rates

GECCO '16 Companion Paper Acceptance Rate 137 of 381 submissions, 36%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
205
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)1

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Abdul Halim ADas SIsmail IAbdul Halim ADas SIsmail I(2025)Algorithm Parameters: Tuning and ControlInto a Deeper Understanding of Evolutionary Computing: Exploration, Exploitation, and Parameter Control10.1007/978-3-031-75577-4_2(153-283)Online publication date: 18-Jan-2025
https://doi.org/10.1007/978-3-031-75577-4_2
Muñoz-Sánchez RMartínez-Salazar IGonzález-Velarde JRíos Solís Y(2024)Two hybrid flow shop scheduling lines with assembly stage and compatibility constraintsPLOS ONE10.1371/journal.pone.030411919:6(e0304119)Online publication date: 21-Jun-2024
https://doi.org/10.1371/journal.pone.0304119
Noronha TRibeiro C(2024)Biased random-key genetic algorithms: A tutorial with applicationsProceedings of the 2024 8th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence10.1145/3665065.3665083(110-115)Online publication date: 24-Apr-2024
https://dl.acm.org/doi/10.1145/3665065.3665083
Melo RRibeiro CRiveaux J(2023)A biased random-key genetic algorithm for the minimum quasi-clique partitioning problemAnnals of Operations Research10.1007/s10479-023-05609-7Online publication date: 28-Sep-2023
https://doi.org/10.1007/s10479-023-05609-7
Ribeiro CUrrutia Sde Werra DRibeiro CUrrutia Sde Werra D(2023)Metaheuristics and Local SearchCombinatorial Models for Scheduling Sports Tournaments10.1007/978-3-031-37283-4_3(57-98)Online publication date: 23-Jun-2023
https://doi.org/10.1007/978-3-031-37283-4_3
Ma CKong MPei JPardalos P(2017)BRKGA-VNS for Parallel-Batching Scheduling on a Single Machine with Step-Deteriorating Jobs and Release TimesMachine Learning, Optimization, and Big Data10.1007/978-3-319-72926-8_34(414-425)Online publication date: 21-Dec-2017
https://doi.org/10.1007/978-3-319-72926-8_34

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Biased random-key genetic algorithms for combinatorial optimization

A modified VNS metaheuristic for max-bisection problems

Local search algorithms for the k-cardinality tree problem

Comments

Information

Published In

Sponsors

Publisher

Publication History

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations