Note from the Editor

We continue to announce the winners of the INFORMS Journal on Computing (IJOC) Test of Time Paper Award to cover the backlog of awards since the journal’s inception. The energetic and able committee chaired by John Chinneck, with members Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff, has selected the awardee, covering the period 1991–1995. What follows is the citation from the award committee and then a reflection on the paper and this award by the author.

I want to thank the committee for their superb efforts and am very pleased to share this recognition of the impactful heritage of our journal.

All my best,

The Test of Time Award for papers published in the INFORMS Journal on Computing during the years 1991–1995 is awarded to:

Genetic Algorithms and Random Keys for Sequencing and Optimization

James C. Bean

ORSA Journal on Computing 6(2):154–160, 1994

https://pubsonline.informs.org/doi/10.1287/ijoc.6.2.154

Test of Time Award Citation 1991–1995

Genetic algorithms (GAs) have been around since the 1960 s. They have been used by computer scientists and operations researchers to find good solutions to optimization problems. In a GA, feasible solutions mimic a population of individuals that mate and produce offspring that survive based on Darwin’s notion of survival of the fittest. The idea is that individuals (i.e., feasible solutions) tend to become more fit (i.e., less costly) from one generation to the next. The fundamental operations in a GA are reproduction and crossover. These must be defined in a GA and applied at each generation.

One of the limitations of early GAs for solving difficult optimization problems, such as the traveling salesman problem (TSP), was that crossover of two adults did not always result in viable offspring (i.e., a feasible solution). The random keys representation remedied this weakness. In this paper, Bean presents the random keys idea and shows how to apply it in a variety of settings (e.g., machine scheduling, TSP, vehicle routing, the quadratic assignment problem, etc.). Bean presents extensive computational results to demonstrate that the approach performs well. The paper is well written, and it has been cited nearly 2,000 times, according to Google Scholar.

Retrospective on the Random Keys Paper for Test of Time Award by the Author, James C. Bean

Many thanks to Editor-in-Chief Alice Smith and the selection committee for devising this recognition program and for selecting this paper for recognition.

Prior to this work I had used traditional discrete optimization methods for several applied problems (Bean et al. 1981, 1987, 1990; Bean and Bean 1985; Noon and Bean 1991). As the problems grew more complex, the traditional methods became too time consuming to solve the real examples on hardware of the day. I began attending seminars at the University of Michigan Center for the Study of Complex Systems and then applying genetic algorithms to these difficult discrete optimization problems (Hadj-Alouane and Bean 1997, Hadj-Alouane et al. 1999).

At that time, many implementations of genetic algorithms used operators close to their biological counterparts. The genetic algorithm implementation in the papers above used more general mathematical structures. For example, we copy to the best solutions from one generation to the next to maintain a monotonically improving best solution, crossover is done independently at every gene rather than exchanging segments of the chromosome, and immigration is used rather than mutation to maintain ergodicity. The concept of immigration leads trivially to convergence in probability of the algorithm in many cases. Early applications provided some strong results, including the mall merchandising problem that had been difficult via the traditional optimization techniques (Bean et al. 1990).

Then, we approached a highly nonlinear problem in ordinary design. The feasible region was very fractionated, and the union of feasible subregions was of small measure within the enclosing convex hull. The genetic algorithm had great difficulty in mating two feasible solutions to find another feasible solution. The search was reduced to a simple sampling of the convex hull that did not converge in reasonable times.

At the Symposium on Operations Research and Complex Adaptive Systems at the Santa Fe Institute in May 1992, these barriers to application of complex systems algorithms (including genetic algorithms) to operations research problems were a center of discussion. During one talk, I recall wondering if we could replace the feasible region of the ordinary design problem with an alternative space that would be more amenable to the genetic algorithm. We could then map from the easy space to the actual space. The concept of random keys, in its simplest form, is a search of a hypercube. The complexity of the problem is transferred to the construction of a feasible solution from the sequence determined by sorting the keys. In some ways, random keys constructs a myopic heuristic where the genetic algorithm is giving the myopic algorithm an advanced order with which to place the items.

At an ensuing meeting, I put the random keys concept on the table, and we talked through its potential application to several problems. We were able to construct a random keys approach to each. Other than literature search and computation, the random keys paper was written on the plane from Albuquerque back to Detroit. The random keys concept was later applied in Norman and Bean 1999, Norman and Bean 2000, Xu and Bean 2016, and by many other authors.

Several years later I was attending an INFORMS National Meeting and noted in the bulletin that there was an entire session focused on applications of random keys to various problems. I was impressed at the innovation others had brought to this meta-algorithm. That was the first inkling I had of the breadth of use of random keys. I would like to thank those who have chosen to build on this platform. It is very gratifying.