Thursday, March 22, 2012

IEEE Transactions on Evolutionary Computation by David Fogel

A remembrance by David Fogel

IEEE Transactions on Evolutionary Computation
Vol. 6. No. 5, October 2002

The evolutionary computation community lost one of its pioneers on July 14, 2002, when Alex Fraser passed away as a result of complications from a heart attack. Fraser was one of the first to conceive and execute computer simulations of genetic systems, and his efforts in the 1950s and 1960s had a profound impact on computational models of evolutionary systems. The simulation algorithms he used were important not only in the simulation of genetical problems, but provided a menu of techniques that enriched the entire simulation effort in any problem that involved probability sampling among a population of alternatives, the heart of Monte Carlo methods.

Fraser was born in London, U.K., and lived in Hong Kong for most of his youth; however, he studied at the University of New Zealand, and later went to the University of Edinburgh, and subsequently to the Commonwealth Scientific and Industrial Research Organisation (CSIRO) in Sydney, Australia. It was at the CSIRO where Fraser made his seminal contributions to evolutionary computation. Following the construction of the ILLIAC computer at the University of Chicago, CSIRO designed and built their own version, called the SILLIAC, and Fraser began using it to simulate genetic selection processes.

Beginning with [1], Fraser embarked on a comprehensive series of simulations of evolutionary processes [2]-[13], and encouraged and collaborated with others on many related publications in this series [14]-[18]. Fraser published extensively in the Australian Journal of Biological Sciences, and his efforts influenced colleagues in evolutionary biology significantly [19]-[21].

Fraser's first efforts [1], published in 1957, studied the case of diploid organisms represented by binary strings of a given length, say n. Each bit in a string represented an allele (either dominant or recessive) and the phenotype of each organism was determined by its genetic composition. Reproduction was accomplished using an n-point crossover operator where each position along an organism's genetic string was assigned a probability of breaking for recombination. Interactions between genes could be addressed nominally by forming linkage groups. This was accomplished by varying the probability of crossover occurring at each locus along the strings.

The general procedure was for a population of P parents to give rise to P' offspring via recombination. Selection would then eliminate all but P of the offspring (as well as all of the parents) for the next generation based on a function of the assigned phenotypic value. In general, the rule for determining phenotypes could be arbitrary, but Fraser [1] offered some specific possibilities to model the effects of dominance and recessiveness. Selection could then be applied toward the extreme values of the phenotype (essentially performing function optimization, either maximization or minimisation) or the mean values (stabilizing selection against extremes). The possibility for varying the number of progeny per parent based on the parental phenotypes was also introduced.

Subsequent efforts in Fraser's series of publications studied varying effects of linkage, epistasis, rates of reproduction, and additional factors on the rates of advance under selection, as well as the genetic variability of a population and other statistics. His work inspired other efforts in computer models of population genetics [22]-[26], all of which relied on recombination and mating, which had become routine practice. By 1968, Fraser had placed his work in the context of purposive learning systems [8], and included an inversion operator to reorder alleles and build arbitrary linkages between genes. In retrospect, his computational procedures presaged the mechanisms that would later become common in traditional genetic algorithms. In 1970, together with Don Burnell, Fraser published the book Computer Models in Genetics [11], which provided a comprehensive treatment of his efforts spanning over a decade and was the second book in the field of evolutionary computation.

Sadly, Fraser suffered a stroke in 1983, after he had moved to the United States over a decade earlier to take on a visiting professorship at the University of California at Davis, before taking the Headship of Biological Sciences at the University of Cincinnati in 1967. The stroke left him unable to converse normally, and he would rarely engage in telephone conversations. The timing of this unfortunate event was most tragic because Fraser was left unable to engage his colleagues just at the time when interest in evolutionary models and simulations was beginning to rise within computer science.

In the mid-1990s, I began research for the book, Evolutionary Computation: The Fossil Record [27], which offers an historical review of efforts in evolutionary algorithms from the early 1950s to the early 1990s. With a bit of fortune, I was able to locate Fraser, and communicating through his wife, Anne, was able to identify and research the vast majority of his early efforts, as well as have him review my editorial introduction to his work, which appears in [27]. Two of his papers are reprinted in [27].

In 1999, Fraser received the 1999 IEEE Neural Networks Council Pioneer Award in Evolutionary Computation. I believe this was but a small recognition, and it came too late. Yet, even though Alex could not come to accept the award in person--it was accepted by his son-in-law who read a gracious statement on Fraser's behalf--he was grateful for the award. His wife would later write to me that he was very proud of this recognition.

I found Fraser still keen on the idea of computer models of evolution, and was extremely pleased and honored to be able to co-author with him the paper "Running races with Fraser's recombination," [28] which I presented at the 2000 Congress on Evolutionary Computation in San Diego, CA. This paper studied the effects of competing different forms of recombination, including one-point, two-point, and uniform crossover, with Fraser's recombination method that could assign arbitrary probabilities to crossing points, with these probabilities evolved online with a self-adaptive mechanism. Individuals were tagged with bits that identified which operator would be applied. Over generations of optimization on alternative functions, different operators showed greater or lesser degrees of match to the problem (in line with [29]), with uniform crossover and Fraser's recombination providing generally better results than one- or two-point crossover across the test suite.

Although my own direct interaction with Alex was brief, it will stay with me forever. Once, while finishing the preparations for [27], I had phoned Anne to assist me with some final clarifications on his early work. She informed me to hold on, and Alex came to the phone. For what could have been no more than 30 seconds, he thanked me, as best as he could while slurring his words, for helping bring attention to his work. Knowing how difficult it was for him speak following his stroke made this moment all the more poignant.

I regret that Alex is no longer with us to share in the bright future of the field that he helped create, but I feel fortunate to have been able to bring light to his efforts and even collaborate with him. I hope that others in the evolutionary computation community will be encouraged to revisit his contributions and explore his lines of thought using our modern high-speed computing machines. We have the capability to take these explorations far beyond what Alex could have imagined when he constructed the SILLIAC. In doing so, we can return only a small contribution of what he has given us.

DAVID B. FOGEL, Editor-in-Chief

Natural Selection, Inc.

La Jolla, CA 92037 USA


Thanks are owed to Anne Fraser, Larry Erway, and Richard Lewontin for assisting with this remembrance.


[1] A. S. Fraser, "Simulation of genetic systems by automatic digital computers. I. Introduction," Aust. J. Biol. Sci., vol. 10, pp. 484-491, 1957.

[2] ----,"Simulation of genetic systems by automatic digital computers. II. Effects of linkage or rates of advance under selection," Aust. J. Biol. Sci., vol. 10, pp. 492-499, 1957.

[3] ----, "Monte Carlo analyses of genetic models," Nature, vol. 181, pp. 208-209, 1958.

[4] ----, "Simulation of genetic systems by automatic digital computers. 5-linkage, dominance and epistasis," in Biometrical Genetics, O. Kempthome, Ed. New York: Pergamon, 1960, pp. 70-83.

[5] ----, "Simulation of genetic systems by automatic digital computers. VI. Epistasis," Aust. J. Biol. Sci., vol. 13, no. 2, pp. 150-162, 1960.

[6] "Simulation of genetic systems by automatic digital computers. VII. Effects of reproduction rate, and intensity of selection, on genetic structure," Aust. J. Biol. Sci., vol. 13, pp. 344-350, 1960.

[7] ----, "Simulation of genetic systems," J. Theoret. Biol., vol. 2, pp. 329-346, 1962.

[8] ----, "The evolution of purposive behavior," in Purposive Systems, H. von Foerster, J. D. White, L. J. Peterson, and J. K. Russell, Eds. Washington, DC: Spartan, 1968, pp. 15-23.

[9] A. S. Fraser and D. Burnell, "Simulation of genetic systems. XI. Inversion polymorphism," Amer: J. Human Genet., vol. 19, no. 3, pp. 270-287, 1967.

[10] ----, "Simulation of genetic systems. XII. Models of inversion polymorphism," Genetics, vol. 57, pp. 267-282, 1967.

[11] ----, Computer Models in Genetics. New York: McGraw-Hill, 1970.

[12] A. S. Fraser, D. Burnell, and D. Miller, Simulation of genetic systems. X. Inversion polymorphism," J. Theoret. Biol., vol. 13, pp. 1-14, 1966.

[13] A. S. Fraser and P. E. Hansche, "Simulation of genetic systems. Major and minor loci," in Proc. llth Int. Congress on Genetics, S. J. Geerts,

Ed. Oxford, U.K.: Pergamon, 1965, vol. 3, pp. 507-516.

[14] J. S. F. Barker, "Simulation of genetic systems by automatic digital computers. III. Selection between alleles at an autosomal locus," Aust. J. Biol. Sci., vol. 11, pp. 603-612, 1958.

[15] ----, "Simulation of genetic systems by automatic digital computers. IV. Selection between alleles at a sex-linked locus," Aust. J. Biol. Sci.,
vol. 11, pp. 613-625, 1958.

[16] J. L. Gill, "Simulation of genetic systems," Biometrics, vol. 19, p. 654, 1963.

[17] ---- "Effects of finite size on selection advance in simulated genetic populations," Aust. J. Biol. Sci., vol. 18, pp. 599-617, 1965.

[18] ----, "Selection and linkage in simulated genetic populations," Aust. J. Biol. Sci., vol. 18, pp. 1171-1187, 1965.

[19] J. Felsenstein, private communication, 1998.

[20] C. Taylor, private communication.

[21] R. Lewontin, private communication.

[22] E G. Martin and C. C. Cockerham, "High speed selection studies," in Biometrical Genetics, O. Kempthome, Ed. London, U.K.: Pergamon, 1460, pp. 35-45.

[23] J. L. Crosby, "The use of electronic computation in the study of random fluctuations in rapidly evolving populations," Phil. Trans. Roy. Soc. B, vol. 242, pp. 415-417, 1960.

[24] ----, "Evolution by computer," New Scientist, vol. 17, pp. 415-417, 1963.

[25] ----, Computer Simulation in Genetics. New York: Wiley, 1973.

[26] K. E. Justice and J. M. Gervinski, "Electronic simulation of the dynamics of evolving biological systems," in Cybernetics Problems in Bionics, H. L. Oestreicher and D. R. Moore, Eds. New York: Gordon and Breach, 1968, pp. 205-228.

[27] D. B. Fogel, Ed., Evolutionary Computation: The Fossil Record. Piscataway, NJ: IEEE Press, 1998.

[28] D. B. Fogel and A. S. Fraser, "Running races with Fraser's recombination," in Proc. 2000 Congress on Evolutionary Computation. Piscataway, NJ: IEEE Press, 2000, vol. 2, pp. 1217-1222.

[29] D. H. Wolpert and W. G. Macready, "No free lunch theorems for optimization," IEEE Trans. Evol. Comput., vol. 1, pp. 67-82, Apr. 1997.

1 comment:

  1. I do accept as true with all of the ideas you have presented to your post.

    They're really convincing and can certainly work. Nonetheless, the posts are too quick for starters. May you please lengthen them a little from next time? Thank you for the post.
    Also see my website: diet that works