Evolutionary programming

Evolutionary programming was invented by Dr. Lawrence J. Fogel (1928-2007) while serving at the National Science Foundation in 1960. He had been tasked to provide a report to the U.S. Congress on the worth of investing in basic research. One of the topics of consideration was Artificial Intelligence.

At the time, artificial intelligence was limited to two main avenues of investigation: modeling the human brain or “neural networks,” and modeling the problem solving behavior of human experts or “heuristic programming". The former addressed making mathematical models of neurons and their connectivity, but little was really known then about how the brain actually operates. The latter approach was initially conducted through search-based approaches and later joined by knowledge-based or "expert system" approaches. The heuristic approach requires knowledge about the problem domain and some form of expertise. Both focused on emulating humans as the most advanced intelligent organism produced by evolution.

The alternative, envisioned by Dr. Fogel, was to refrain from modeling the end product of evolution but rather to model the process of evolution itself as a vehicle for producing intelligent behavior (Fogel, 1962, 1963). Fogel viewed intelligence as a composite ability to make predictions in an environment coupled with the translation of each prediction into a suitable response in light of a given goal (e.g. to maximize a payoff function). Thus, he viewed prediction as a prerequisite for intelligent behavior. The modeling of evolution as an optimization process was a consequence of Dr. Fogel’s expertise in the emerging fields of “biotechnology” (at the time defined as the utilization of mathematics to describe the functioning of a human operator), cybernetics, and engineering.

Dr. Fogel crafted a series of experiments in which finite state machines (FSMs) represented individual organisms in a population of problem solvers. These graphical models are used to describe the behavior or computer software and hardware, which is why he termed his approach "Evolutionary Programming". The experimental procedure was as follows. A population of FSMs is exposed to the environment – that is, the sequence of symbols that has been observed up to the current time. For each parent machine, as each input symbol is presented to the machine, the corresponding output symbol is compared with the next input symbol. The worth of this prediction is then measured with respect to the payoff function (e.g., all-none, squared error). After the last prediction is made, a function of the payoff for the sequence of symbols (e.g., average payoff per symbol) indicates the fitness of the machine or program. Offspring machines are created by randomly mutating the parents and are scored in a similar manner. Those machines that provide the greatest payoff are retained to become parents of the next generation, and the process iterates. When new symbols are to be predicted, the best available machine serves as the basis for making such a prediction and the new observation is added to the available database. Fogel described this process as “evolutionary programming” in contrast to “heuristic programming.”

The merits of evolutionary programming were investigated by Dr. Fogel upon his return to Convair (San Diego) in July, 1961 through application to problems in prediction, system identification, and control in a series of studies led by Fogel and colleagues (Fogel, 1964; Fogel et al. 1964, 1965a, 1965b) leading to the first book in the field of evolutionary computation (Fogel et al. 1966). This early work was followed by that of several other researchers, who extended the evolutionary programming process to areas such as: predicting and classifying time series (Walsh, 1967; Lutter, 1968; Lutter and Huntsinger, 1969; Burgin, 1974, and others); modeling systems (Kaufman, 1967); and gaming (Burgin, 1969, Fogel and Burgin, 1969). Some of these efforts were among the first to use coevolution or utilize multiparent recombination of existing solutions. Although some early descriptions of Fogel’s evolutionary programming incorrectly asserted that it was limited to one parent and one offspring and that recombining traits from two or more parents was excluded (e.g., Holland, 1975; Rada, 1981; Goldberg, 1989), it is clear today that sexual reproduction and crossover were fundamental to his approach.

In 1964, Dr. Fogel received his Ph.D. in electrical engineering from the University of California, Los Angeles and his dissertation “On the Origin of Intellect” focused on artificial intelligence through simulated evolution. The early work also led Dr. Fogel, Dr. Al Owens, and Dr. Michael Walsh to establish Decision Science, Inc. in 1965. This was the first company in the world devoted solely to commercialization of evolutionary algorithms.

In the 1970s, owing primarily to the guidance of Prof. Donald Dearholt at New Mexico State University, more evolutionary computation research was published in evolutionary programming than any other form of simulated evolution. Most of this research used evolutionary programming for pattern recognition (Root, 1970; Cornett, 1972; Lyle, 1972; Holmes, 1973; Trellue, 1973; Montez, 1974; Atmar, 1976; Vincent, 1976; Williams, 1977; Dearholt, 1976). Handwritten characters were used primarily as a testbed for the recognition tasks. The experiments included adaptive mutation parameters. Atmar (1976) provided an early example of simulating evolution in an artificial life setting, evolving FSMs to recognize patterns that varied by location in a simulated environment. Atmar (1976) was also possibly the first to suggest and describe how evolutionary programming could be designed for what is now known as “evolvable hardware.” Angeline and Pollack (1993) described how evolutionary programming could be used to evolve computer programs, while Tamburino et al. (1993) applied evolutionary programming to pattern recognition problems. Yao et al. (1999) described mutation strategies that in certain circumstances increased the rate of convergence in evolutionary programming.

[edit] Modern evolutionary programming

Evolutionary programming was extended in the 1980s to use arbitrary data representations and be applied to generalized optimization problems. The same general process of population-based random variation and selection was applied to data structures such as real-valued vectors (Fogel and Atmar, 1990; Fogel et al., 1990; Davis, 1994), permutations (Fogel, 1998), matrixes (Fogel et al., 1993), variable-length vectors (Fogel, 1990), binary strings (Fogel, 1989), and so forth. David Fogel (1988) introduced a form of tournament selection to Evolutionary Programming that allowed lesser-scoring solutions a probabilistic opportunity to survive as parents. This provided a “soft selection” mechanism (Galar, 1985), and the ability to more rapidly escape points of local optima (see also simulated annealing). Fogel et al. (1991; 1992) also introduced the idea of self-adaptation of variation parameters, in which solutions carry both the information about how to address a problem as well as the information about how to create offspring, with both being subject to variation.

[edit] Application areas

Evolutionary programming has been applied to diverse engineering problems including traffic routing and planning (McDonnell et al., 1997), pharmaceutical design (Duncan and Olson, 1996; Gehlhaar and Fogel, 1996 ), epidemiology (Fogel and Fogel, 1986), cancer detection (Fogel et al. 1997, 1998), military planning (Fogel et al., 1993), control systems (Jeon et al., 1997), system identification (Fogel, 1990), signal processing (Porto, 1990), power engineering (Lai and Ma, 1996), learning in games (Fogel and Burgin, 1969), among others. Evolutionary Programming is applicable to any of the areas for which evolutionary algorithms are applicable.

[edit] Current nomenclature

Evolutionary Programming was one of the main avenues of research in evolutionary computation in the early 1990s, including genetic algorithms along with genetic programming, and evolution strategies. At this time, the term “evolutionary computation” was invented to describe the entire field of study. Whereas some members of the genetic algorithm and evolution strategies communities have opted to retain these terms, virtually all of the researchers active in Evolutionary Programming recognize the value of a single encompassing term for the entire field and have adopted this term to describe their work. This is particularly true because in the modern version of Evolutionary Programming, it can employ any data representation, any variation operators, and any selection procedure.

[edit] References

• P.J. Angeline and J. Pollack (1993) “Evolutionary module acquisition,” Proc. Second Annual Conf. on Evolutionary Programming, Fogel and Atmar (Eds.), Evolutionary Programming Society, pp. 154-163.

• J.W. Atmar (1976) “Speculation on the evolution of intelligence and its possible realization in machine form,” Sc.D. dissertation, New Mexico State University, Las Cruces, NM.

• G.H. Burgin (1969) “On playing two-person zero-sum games against nonminimax players,” IEEE Trans. Systems Science and Cybernetics, Vol. SSC-5, pp. 369-370.

• G.H. Burgin (1974) “System identification by quasilinearization and evolutionary programming,” J. Cybernetics, Vol. 2:3, pp. 4-23.

• F.N. Cornett (1972) “An application of evolutionary programming to pattern recognition,” Master’s thesis, New Mexico State University, Las Cruces, NM.

• M. Davis (1994) “The natural formation of Gaussian mutation strategies in evolutionary programming,” Proc. 3rd Annual Conf. Evol. Prog., A.V. Sebald and L.J. Fogel (eds.), World Scientific, River Edge, NJ, pp. 242-252.

• D.W. Dearholt (1976) “Some experiments on generalization using evolving automata,” Proc. 9th Intern. Conf. on Systems Sciences, Honolulu, HI, pp. 131-133.

• B.S. Duncan and A.J. Olson (1996) “Applications of evolutionary programming for the prediction of protein-protein interactions,” Evolutionary Programming V, L.J. Fogel, P.J. Angeline and T. Baeck (eds.), MIT Press, Cambridge, pp. 411-417.

• D.B. Fogel (1988) “An evolutionary approach to the traveling salesman problem,” Biological Cybernetics, Vol. 60, pp. 139-144.

• D.B. Fogel (1989) “Evolutionary programming for voice feature analysis,” Proc. 23rd Asilomar Conf. Signals, Systems, and Computers, R.R. Chen (ed.), Pacific Grove, CA, pp. 381-383.

• D.B. Fogel (1990) “System identification through simulated evolution,” Master’s thesis, UC San Diego.

• D.B. Fogel and J.W. Atmar (1990) “Comparing genetic operators with Gaussian mutation in simulated evolutionary processes using linear systems,” Biological Cybernetics, Vol. 63, pp. 111-114.

• D.B. Fogel, L.J. Fogel, and J.W. Atmar (1991) “Meta-evolutionary programming,” Proc. 25th Asilomar Conf. Signals, Systems, and Computers, R.R. Chen (ed.), Pacific Grove, CA, pp. 540-545.

• D.B. Fogel, L.J. Fogel, and W. Atmar (1993) “Evolutionary programming for ASAT battle management,” Proc. 27th Asilomar Conf. on Signals, Systems, and Computers, A. Singh (ed.), IEEE Computer Society Press, Los Alamitos, CA, pp. 617-621.

• D.B. Fogel, L.J. Fogel, W. Atmar, and G.B. Fogel (1992) “Hierarchic methods of evolutionary programming,” Proc. Of the First Annual Conf. on Evolutionary Programming, Evolutionary Programming Society, D.B. Fogel and W. Atmar (Eds.), La Jolla, CA, pp. 175-182.

• D.B. Fogel, L.J. Fogel, and V.W. Porto (1990) “Evolving neural networks,” Biological Cybernetics, Vol. 63, pp. 487-493.

• D.B. Fogel, E.C. Wasson, E.M. Boughton, and V.W. Porto (1997) “A step toward computer-assisted mammography using evolutionary programming and neural networks,” Cancer Letters, Vol. 119, pp. 93-97.

• D.B. Fogel, E.C. Wasson, E.M. Boughton and V.W. Porto (1998) “Evolving artificial neural networks for screening features from mammograms,” Artificial Intelligence in Medicine, Vol. 14, pp. 317-326.

• L.J. Fogel (1962) “Autonomous automata,” Industrial Research, Vol. 4, pp. 14-19.

• L.J. Fogel (1963) Biotechnology: Concepts and Applications, Prentice-Hall, Englewood, NJ.

• L.J. Fogel (1964) “On the organization of intellect,” Ph.D. dissertation, UCLA.

• L.J. Fogel and G.H. Burgin (1969) “Competitive goal-seeking through evolutionary programming,” Final Report, Contract AF 19(628)-5927, Air Force Cambridge Research Laboratories.

• L.J. Fogel and D.B. Fogel (1986) “Artificial intelligence through evolutionary programming,” Final Report, Contract PO-9-X56-1102C-1, U.S. Army Research Institute.

• L.J. Fogel, A.J. Owens, and M.J. Walsh (1964) “On the evolution of artificial intelligence,” Proc. 5th National Symp. On Human Factors in Engineering, IEEE, San Diego, CA, pp. 63-76.

• L.J. Fogel, A.J. Owens, and M.J. Walsh (1965a) “Intelligent decision-making through a simulation of evolution,” IEEE Transactions on Human Factors Electronics, Vol. 6, pp. 13-23.

• L.J. Fogel, A.J. Owens, and M.J. Walsh (1965b) “Intelligent decision-making through a simulation of evolution,” Behavioral Science, Vol. 11, pp. 253-272.

• L.J. Fogel, A.J. Owens, and M.J. Walsh (1966) Artificial Intelligence through Simulated Evolution, John Wiley, NY.

• R. Galar (1985) “Handicapped individual in evolutionary processes,” Biological Cybernetics, Vol. 53, pp. 1-9.

• D.K. Gehlhaar and D.B. Fogel (1996) “Tuning evolutionary programming for conformationally flexible molecular docking,” Evolutionary Programming V, L.J. Fogel, P.J. Angeline, and T. Baeck (eds.), MIT Press, Cambridge, MA, pp. 419-429.

• D.E. Goldberg (1989) Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA.

• J.H. Holland (1975) Adaptation in Natural and Artificial Systems, Univ. Michigan Press, Ann Arbor, MI.

• V.P. Holmes (1973) “Recognizing prime numbers with an evolutionary program,” Master’s thesis, New Mexico State University, Las Cruces, NM.

• J.-Y. Jeon, J.-H. Kim, and K. Koh (1997) “Experimental evolutionary programming-based high-precision control,” IEEE Control Sys. Tech., Vol. 17, pp. 66-74.

• H. Kaufman (1967) “An experimental investigation of process identification by competitive evolution,” IEEE Trans. Systems Science and Cybernetics, Vol. SSC-3:1, pp. 11-16.

• L.L. Lai and J.T. Ma (1996) “Application of evolutionary programming to transient and subtransient parameter estimation,” IEEE Trans. Energy Convers., Vol. 11, pp. 523-529.

• B.E. Lutter (1968) “The application of artificial intelligence through the evolutionary programming technique to the control of chemical engineering processes,” Master’s thesis, South Dakota School of Mines and Technology, Rapid City, SD.

• B.E. Lutter and R.C. Huntsinger (1969) “Engineering applications of finite automata,” Simulation, Vol. 13, pp. 5-11.

• M.R. Lyle (1972) “An investigation into scoring techniques in evolutionary programming,” Master’s thesis, New Mexico State University, Las Cruces, NM.

• J.R. McDonnell, W.C. Page, D.B. Fogel, and L.J. Fogel (1997) “Optimizing fuel distribution through evolutionary programming,” Evolutionary Programming VI, P.J. Angeline, R.G. Reynolds, J.R. McDonnell, and R. Eberhart (eds.), Springer, Berlin, pp. 373-382.

• J. Montez (1974) “Evolving automata for classifying electrocardiograms,” Master’s thesis, New Mexico State University, Las Cruces, NM.

• V.W. Porto (1990) “Evolutionary methods for training neural networks for underwater pattern classification,” Proc. 24th Asilomar Conference on Signals, Systems, and Computers, R.R. Chen (ed.), Maple Press, San Jose, CA, pp. 376-380.

• R. Rada (1981) “Evolution and gradualness,” BioSystems, Vol. 14, pp. 211-218.

• R. Root (1970) “An investigation of evolutionary programming,” Master’s Thesis, New Mexico State University, Las Cruces, NM.

• L.A. Tamburino, M.A. Zmuda, and M.M. Rizki (1993) “Applying evolutionary search to pattern recognition problems,” Proc. Second Annual Conf. on Evolutionary Programming, Fogel and Atmar (Eds.), Evolutionary Programming Society, pp. 183-191.

• R.E. Trellue (1973) “The recognition of handprinted characters through evolutionary programming,” Master’s thesis, New Mexico State University, Las Cruces, NM.

• R.W. Vincent (1976) “Evolving automata used for recognition of digitized strings,” Master’s thesis, New Mexico State University, Las Cruces, NM.

• M.J. Walsh (1967) “Evolution of finite automata for prediction,” Final Report, Contract No. RADC-TR-67-555. Rome Air Development Center, Grifiss AFB, NY.

• G.L. Williams (1977) “Recognition of hand-printed numerals using evolving automata,” Master’s thesis, New Mexico State University, Las Cruces, NM.

• X. Yao, Y. Liu, and G. Lin (1999) “Evolutionary programming made faster,” IEEE Transactions on Evolutionary Computation, Vol. 3:2, pp. 82-102.

[edit] See also

Evolution strategies, Genetic algorithms, Genetic programming, Differential evolution, Particle swarm optimization, Ant colony optimization, Cultural algorithms