Reprinted from EvoNews, Issue 8, 1998, written by Mij Kelley, copyright EvoNet, 1998
An exclusive interview with David Fogel
Where do ideas come from? Do they spring fully formed from the heads of geniuses, or do they develop in fits and starts, passing from human brain to human brain, adapting, cross fertilising and gradually evolving in the virtual ideas factory that is collective human consciousness?
From the evidence of Evolutionary Computation: The Fossil Record, ideas are generated in parallel – lots of isolated, highly active brains and a modest amount of information transfer. As a result, evolutionary computing was invented on at least ten separate occasions in a 15-year timespan. ‘It’s a classic example of convergent evolution,’ says the book’s author, David Fogel.
David Fogel is of course the son of Lawrence Fogel who in 1960 invented Evolutionary Programming – an iterative mutation and selection procedure which in its first incarnation was used to evolve finite state machines to predict sequences of symbols. Four years later, and completely independently, Rechenberg, Schwefel and Bienert invented Evolution Strategies.
In fact, evolutionary computing appeared in various guises throughout the ’fifties and ’sixties – but made no impact on mainstream artificial intelligence research, which continued doggedly attempting to model the products, rather than the process, of evolution. Quite simply: ‘Everyone who proposed an evolutionary computation before 1975 was ahead of their time,’ says David Fogel. As a result, their work has frequently been misunderstood, lost or forgotten.
Fogel’s response has been to republish 30 landmark papers from the history of evolutionary computing. ‘There was and is a need to set the record straight,’ he says. ‘Only a small handful of pioneers in evolutionary computation have been given the credit they are due.’ He cites, as an example, the use of recombination in population-based evolutionary simulations. ‘This,’ he says, ‘did not arise in a single major innovation – as has been offered in some books – but was commonly applied in multiple independent investigations dating into the 1950s.’
He points to the work of Alex Fraser (who from 1957 onwards evolved binary strings in a population undergoing cross-over) and Hans Bremermann (who in the early to mid-1960s used binary strings as well as real-valued strings with recombination from two or more parents). Both Fraser and Bremermann, he believes, could legitimately lay claim to the title of father of the genetic algorithm. As for the suggestion that Bremermann merely recommended using crossover but didn’t do any experiments: ‘This is simply not correct,’ Fogel insists. ‘Not only did Bremermann report experiments, he even reported the CPU time required and the conditions that appeared to affect the efficiency of his evolutionary algorithms.’
Although Fogel acknowledges that his purpose in The Fossil Record is to draw attention to these neglected pioneers, he’s keen that this should not be at the expense of those who are already widely recognised. ‘Giving credit is not like slicing up a pie: the more that goes to one, by consequence the less that goes to another. We should delight in the fact that evolutionary computation appears to have had about 10 independent beginnings, arising in different forms within a 15-year time period from 1953 to 1968.’
But The Fossil Record is much more than a catalogue of who thought what, when. It is a treasure trove – of unexpected spins on old ideas, of papers that went too quickly out of print, of conjectures that were never properly tested due to lack of computing power. Fogel believes that many of these ideas deserve further exploration (he identifies four in the panel on page 7) and with his book appearing on more and more course reading lists, he is, he says ‘looking forward to hearing about students’ projects on these ideas’.
Despite his evident interest in the theoretical and mathematical basis of evolutionary computing, his publications (which include several books and numerous research papers) and his high profile on the conference circuit, David Fogel is first and foremost a practitioner. He is, after all, the son of the man who set up Decision Science Inc. – the first ever business to be based on evolutionary algorithms. Nowadays Lawrence Fogel is President of Natural Selection Inc, where his son is Vice President and Chief Scientist.
‘We have been delivering commercial applications of evolutionary programming at NSI since we started in 1993,’ David Fogel explains. ‘The problem domains we find success in include pharmaceutical design, automatic target recognition and scheduling. We tend not to concentrate on one specific area of application, having worked in medical, financial, military, industrial, transportation, manufacturing, optical character recognition, and many other areas. We learn a great deal from the diversity of applications that cannot be learned by pigeon-holing in one area.’
In addition to developing evolutionary neural networks to detect and diagnose breast cancer from film screen mammograms, current research at NSI focuses on docking problems in molecular drug design. In particular, Fogel points to his work with Agouron Pharmaceuticals ‘where evolutionary algorithms are being used to design new drugs and the programs are being used on a daily basis’.
Clearly EP has come a long way since the symbol-predicting finite state machines of the 1960s. It has been extended to real-valued and combinatorial problems, population sizes have been increased and selection is now probabilistic. In 1991, self-adaptation was added, with genetic operators being encoded on the chromosome and subject, themselves, to evolution.
According to conventional wisdom Evolutionary Programming (‘as defined by Lawrence Fogel’) relies exclusively on mutation as the genetic operator. This is a myth that Fogel is quick to dispel, pointing out that in the 1960s his father suggested a recombination of multiple machines in a majority logic operator (using three or more parents) which was not implemented because of the memory constraints of the machines of the time. He himself takes an undogmatic view of recombination, describing it as ‘just another variation operator you can apply’.
‘Sometimes it is reasonable and sensible to employ, other times it is harmful. There are many forms of recombination and each has its place and by consequence has other places where it fails. We know from the No Free Lunch theorems that there cannot be one best operator for all problems, so we have to try to discern for which problems a particular operator will be most suited. For example, blending recombinations accelerate convergence on a sphere function – but of course we don’t want to use evolutionary algorithms to locate the minimum of a bowl, as there are much better heuristics for this. One-point crossover may work well when components are independent and can be strung into ever longer "building blocks", but we know from Ralf Salomon’s work at University of Zurich that when the components of a problem become increasingly interdependent this operator breaks down.
‘Recombination, in all of its forms, is just another tool in the arsenal of an evolutionary algorithmist, and it should be applied when appropriate. In most cases, I find it to be applied inappropriately because it is used by default, simply as a matter of course. This is where experience has to come into play to make the proper judgement about algorithm design. There’s no substitute for real-world experience.’
He takes an equally practical approach to representation. ‘You should pick what best suits the problem at hand,’ he says. ‘If you face a continuous-valued problem, you will probably have a better view of the situation if you use floating point vectors rather than encoding your solution in binary, octal, hex, or something else. If you need to process a series of algorithmic steps, perhaps a parse tree, or a finite state machine, or a neural network may be appropriate.’
For Fogel, the key point here is that: ‘it’s now possible to prove that there is nothing to be gained in one representation that cannot be gained in another (given a few not-so-restrictive assumptions about the representations). So there is no general advantage to coding things in binary, or anything else for that matter. Again, the best advice is to use what makes sense to you as the engineer.’
But historic preferences for particular representations and genetic operators are what distinguish the main schools of evolutionary computing. If these preferences pass away, so too will the distinction between approaches. And that – according to David Fogel – will be no bad thing. After four years researching the history of evolutionary computing, he has a unique historical perspective on the field, and strong views about the way forward.
‘Given the independent developments of Genetic Algorithms, Evolution Strategies and Evolutionary Programming, each followed similar but slightly different paths until the early 1990s. GAs strongly emphasised binary strings, one-point crossover, building blocks, and proportional selection. ES emphasised floating-point representations, plus or comma selection, and self-adaptation of Gaussian mutations. EP emphasised variable length encodings on dynamic problems with respect to arbitrary payoff functions. Since the late 1980s and early 1990s, each of these methods has been extended to include the main facets of the others. We now have all of these variants using arbitrary representations, variation operators, and selection mechanisms. So it makes little sense to keep describing things in terms of GA, ES, or EP. It’s much more useful to describe things as "evolutionary computation" and "evolutionary algorithms" and move on from there.’