Genetic Algorithms and Random Keys for Sequencing and Optimization

TLDR

Genetic algorithms often struggle to preserve feasibility when generating offspring for sequencing and optimization tasks. The study proposes a general genetic algorithm for diverse sequencing and optimization problems such as machine scheduling, resource allocation, and the quadratic assignment problem. Feasibility issues are mitigated by employing a robust representation technique called random keys. Computational experiments demonstrate the algorithm’s effectiveness on machine scheduling, resource allocation, and quadratic assignment problems. Published in INFORMS Journal on Computing (ISSN 1091‑9856), formerly ORSA Journal on Computing (ISSN 0899‑1499).

Abstract

In this paper we present a general genetic algorithm to address a wide variety of sequencing and optimization problems including multiple machine scheduling, resource allocation, and the quadratic assignment problem. When addressing such problems, genetic algorithms typically have difficulty maintaining feasibility from parent to offspring. This is overcome with a robust representation technique called random keys. Computational results are shown for multiple machine scheduling, resource allocation, and quadratic assignment problems. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.