Lecture
Evolutionary programming was invented by Dr. Lawrence J. Fogel at the National Science Foundation in 1960. He was commissioned to submit a report to the US Congress on the amount of investment in basic research. One of the issues of consideration was artificial intelligence.
At that time, artificial intelligence was limited to two main areas of research: the modeling of the human brain (neural networks) and the modeling of solving problems of human behavior (heuristic programming). An alternative provided by Dr. Fogel, had to abandon the modeling of the end product of evolution, and, rather, to model the process of evolution, using itself as a vehicle to obtain reasonable behavior (Vogel, 1962, 1963). Vogel considers intelligence as an integral part of the ability to make environmental predictions in combination with the translation of each forecast into a suitable answer in the light of a given goal (for example, to maximize the gain function). Thus, in his opinion, forecasting is a prerequisite for reasonable behavior. The modeling of evolution as an optimization of the process was the result of Dr. Vogel’s experience in new areas of “biotechnology”, cybernetics and technology. Dr. Vogel conducted a series of experiments in which the automata represented individual organisms. Automata are graphical models used to describe behavior or software and hardware, so he called his approach evolutionary programming.
The advantages of evolutionary programming were studied by Dr. Vogel after his return to San Diego in July 1961, when addressing the problems of predicting the identification and control system in a series of studies then led by Vogel and his colleagues, leading scientists in the field of evolutionary computing. In some early descriptions of evolutionary programming, Vogel incorrectly claimed that it was limited to one parent and one descendant.
In 1964, Vogel received his doctorate in electrical engineering from the University of California at Los Angeles. His dissertation, On the Origin of Intellect, was devoted to artificial intelligence by simulating evolution. Early work also led Dr. Vogel, Dr. Al Owens, and Dr. Michael Walsh to create solutions for Science, Inc. in 1965. It was the first company in the world dedicated exclusively to the commercialization of evolutionary algorithms.
In 1970, thanks primarily to the guidance of Professor Donald Derholt at the State University of New Mexico, a wider study of computation for evolutionary programming was published than for any other form of simulated evolution. Most of these studies used evolutionary programs for pattern recognition (Root, 1970; Cornett, 1972; Lyle, 1972; Holmes, 1973; Trellue, 1973; Montes, 1974; Atmar, 1976; Vincent, 1976; Williams, 1977; Dearholt, 1976) . As an example, handwritten characters were mainly used for recognition. The experiments included the parameters of adaptive mutations. The work of Atmar (1976) is one of the earliest examples of imitation of evolution in an environment of artificial life. Atmar (1976) may have been the first to suggest and describe how evolutionary programming can be designed for what is now known as the “extended equipment base”. Angeline and Pollack (1993) described how evolutionary programming can be used to develop computer programs.
Hypotheses about the form of the dependence of the target variable on other variables are formulated by the system in the form of programs in a certain internal programming language. If it is a universal language, then theoretically it can express the dependence of any kind. The process of building such programs is constructed as an evolution in the world of programs (this method is a bit similar to genetic algorithms). If the system finds a program that accurately expresses the desired dependency, it begins to make small modifications to it and selects among the daughter programs built in this way that increase accuracy. The system "grows" several genetic lines of programs that compete with each other in exactly finding the desired dependency. A special translation module translates the dependencies found from the internal language of the system to a user-friendly language (mathematical formulas, tables, etc.), making them easily accessible. In order to make the obtained results more comprehensible for the non-mathematical user, there is a large arsenal of various visualization tools for the identified dependencies.
The search for the dependence of the target variables on others is carried out in the form of functions of a certain kind. For example, in one of the most successful algorithms of this type - the method of group accounting of arguments (MGUA), the dependence is sought in the form of polynomials. Moreover, complex polynomials are replaced by several simple ones that take into account only certain signs (groups of arguments). Commonly used pairwise association of signs. This method does not have great advantages compared with neural networks with a ready-made set of standard non-linear functions, but the resulting dependency formulas, in principle, are amenable to analysis and interpretation (although in practice it is still difficult).
The study of evolutionary programming was continued in the 1980s using arbitrary data representations and was applied to the generalized optimization problem. Evolutionary programming based on random variability and selection has been applied to structures such as real vectors (Vogel and Atmar, 1990; Vogel, 1990; Davis, 1994), permutations (Vogel, 1998), matrices (Vogel, 1993), vectors variable length (Vogel, 1990), binary strings (Vogel, 1989) and so on. David Vogel (1988) presented an evolutionary programming selection form using a tournament. Vogel (1991, 1992) also put forward the idea of self-adapting changes in parameters, which contain information on how to solve the problem, as well as information on how to create offspring.
Evolutionary programming has been applied to various engineering tasks, including traffic routing and planning (McDonnell, 1997), pharmaceutical designs (Duncan and Olson, 1996; Vogel, 1996), epidemiology (Vogel, 1986), cancer detection (Vogel 1997, 1998), military planning (Vogel, 1993), control systems (Chong, 1997), identification systems (Vogel, 1990), signal processing (Porto, 1990), power engineering (Lai Ma, 1996), training in games (Vogel and Burgin, 1969) etc.
Comments
To leave a comment
Evolutionary algorithms
Terms: Evolutionary algorithms