Optimization Online


Biased random-key genetic algorithms for combinatorial optimization

José F. Gonçalves(jfgoncal***at***fep.up.pt)
Mauricio G.C. Resende(mgcr***at***research.att.com)

Abstract: Random-key genetic algorithms were introduced by Bean (1994) for solving sequencing problems in combinatorial optimization. Since then, they have been extended to handle a wide class of combinatorial optimization problems. This paper presents a tutorial on the implementation and use of biased random-key genetic algorithms for solving combinatorial optimization problems. Biased random-key genetic algorithms are a variant of random-key genetic algorithms, where one of the parents used for mating is biased to be of higher fitness than the other parent. After introducing the basics of biased random-key genetic algorithms, the paper discusses in some detail implementation issues, illustrating the ease in which sequential and parallel heuristics based on biased random-key genetic algorithms can be developed. A survey of applications that have recently appeared in the literature is also given.

Keywords: Genetic algorithms, biased random-key genetic algorithms, random-key genetic algorithms, combinatorial optimization, metaheuristics.

Category 1: Combinatorial Optimization (Meta Heuristics )

Category 2: Global Optimization (Stochastic Approaches )

Citation: AT&T Labs Research Technical Report, Florham Park, NJ, October 9, 2009.

Download: [PDF]

Entry Submitted: 10/09/2009
Entry Accepted: 10/13/2009
Entry Last Modified: 10/09/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society