Breeding Better Solutions: Evolving Good Golomb Rulers

In the previous Math Today column, Consortium 69, I introduced readers to the on-going search for optimal Golomb rulers. In this issue, we will use the problem of constructing good Golomb rulers as a context for understanding a novel approach to solving exceedingly difficult problems.

Given its simplicity, the approach is surprisingly effective, but then again, it should be-it is based on the process that produced the mass of neurons making sense of this sentence! Genetic algorithms solve problems by breeding better solutions from good solutions in a digital metaphor of evolution.

They were developed first by computer scientist John Holland 30 years ago, but their popularity has grown steadily along with the availability of computers and the supply of challenging optimization problems. Today they are used in an ever-widening range of applications. Among these applications are designing airplane wings, minimizing conflicts when scheduling university courses, digital-signal processing, and solving traveling salesperson problems.