Optimization Online


Biased and unbiased random-key genetic algorithms: An experimental analysis

José F. Gonçalves(jfgoncal***at***fep.up.pt)
Mauricio G.C. Resende(mgcr***at***research.att.com)
Rodrigo F. Toso(rtoso***at***cs.rutgers.edu)

Abstract: We study the runtime performance of three types of random-key genetic algorithms: the unbiased algorithm of Bean (1994); the biased algorithm of Gonçalves and Resende (2011); and a greedy version of Bean's algorithm on 12 instances from four types of covering problems: general-cost set covering, Steiner triple covering, general-cost set K-covering, and unit-cost covering by pairs. The experiments show that, in 11 of the 12 instances, the greedy version of Bean's algorithm is faster than Bean's original method and that the biased variant is faster than both variants of Bean's algorithm.

Keywords: Genetic algorithm, biased random-key genetic algorithm, random keys, combinatorial optimization, heuristics, metaheuristics, experimental algorithms

Category 1: Combinatorial Optimization (Meta Heuristics )

Category 2: Global Optimization (Stochastic Approaches )

Category 3: Optimization Software and Modeling Systems (Optimization Software Benchmark )

Citation: AT&T Labs Research Technical Report, Florham Park, NJ, Dec. 2012.

Download: [PDF]

Entry Submitted: 01/23/2013
Entry Accepted: 01/24/2013
Entry Last Modified: 01/23/2013

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 Optimization Society