Evolutionary modeling

The use of Darwinism principles for automated problem solving began in the 1950s. By 1960, three different interpretations of this idea were being developed in three different places. Evolutionary programming was introduced by Lawrence J. Vogel in the USA, while John Henry Holland called his method a genetic algorithm . In Germany, Ingo Rechenberg and Hans-Paul Schwefel presented an evolutionary strategy approach. These areas have been developed separately for approximately 15 years. Since the beginning of the nineties, they have been unified as “dialects” of one technology called evolutionary computing. In addition, in the early nineties, a fourth stream appeared - genetic programming . Since the 1990s, evolutionary computing has largely become connected with the idea of swarm intelligence, and nature-inspired algorithms are becoming an increasingly significant part of this direction.

Thus, the terms “evolutionary programming”, “evolutionary strategies”, “genetic algorithms” and “genetic programming” are considered as special cases of the general term “evolutionary computing” or “evolutionary modeling”.

Modeling evolution using ideas from evolutionary algorithms and artificial life began with the work of Niels Aall Barricelli in the 1960s, and was extended by Alex Fraser, who published a number of works on modeling artificial selection . ^[1] Evolutionary algorithms became a universally recognized optimization method as a result of the work of Ingo Rechenberg in the 1960s and early 1970s, which used them to solve complex engineering problems. ^[2] Genetic algorithms have become especially popular thanks to the work of John Holland . ^[3] Along with the growth of academic interest, a sharp increase in the power of computers has allowed practical applications, including the automatic evolution of computer programs. ^[4] Evolutionary algorithms are currently used to solve multidimensional problems more efficiently than software developed by humans. ^[5]

The figure depicts the working scheme of one of the varieties of evolutionary calculations - the genetic algorithm (GA), but from it you can understand the general idea of ​​the approach.

The initial population is understood to mean a certain amount of objects, usually obtained at random. In GA, such objects are vectors (“genotypes”) of genes, where each gene can be a bit, number, or some other object. Evolutionary strategy (ES) operates with vectors of real numbers. In genetic (GP) and evolutionary (EP) programming, the role of objects is played by programs that are better and better (in accordance with a certain fitness function) solving a computational problem.

Mutation and Crossing

Mutation is a random change in the "genotype." In GA and ES, the mutation operator can be implemented by simply adding a normally distributed random variable to each component of the vector. In GP and ES, this operation is highly dependent on the encoding method of the grown programs. For example, in tree coding (see the figure), it can be implemented by randomly changing information in a node or by adding, deleting a node or an entire subtree.

The “crossing” operator recombines the candidate solutions, the role of which is similar to the role of crossing in wildlife. Reproduction in evolutionary computing is usually sexual — to produce a descendant, you need several parents, usually two. Reproduction in different algorithms is defined differently - it, of course, depends on the presentation of the data. The main requirement for reproduction is for the descendant or descendants to be able to inherit the traits of both parents by “mixing” them in some way.

Selection (selection)

At the stage of selection, it is necessary to select a certain share from the whole population, which will remain “alive” at this stage of evolution. There are different ways to select. The survival probability of an individual h must depend on the value of the so-called Fitness function (h). This function should be set so that by its value on a given genotype (vector of genes, the results of the cultivated program), one can judge the degree of success of this genotype. The fraction of surviving s itself is usually a parameter of the genetic algorithm, and it is simply set in advance. According to the results of selection from N individuals of the population H, sN individuals should remain that will be included in the final population H '. The remaining individuals die.

In the early 70's, Nobel laureate M. Eigen made an impressive attempt to build models of the appearance of molecular genetic information processing systems in the Earth’s early biosphere ^[6] . The most famous of them is the “quasivid” model, which describes the simple evolution of polynucleotide (information) sequences. Following Eigen in 1980, Novosibirsk scientists V. Ratner and V. Shamin proposed the “sizer” model ^[7] .

In the quasivid model, the phased evolution of a population of information sequences ( vectors ) is considered, the components of which acquire a small number of discrete values. The fitness of “individuals” in models is defined as functions of vectors. At each stage, individuals are selected in the next generation population with probabilities proportional to their fitness, as well as individuals mutations - random equally probable replacements of vector components.

The sizer model in the simplest case considers a system of three types of macromolecules : a polynucleotide matrix and translation and replication enzymes encoded by this matrix. A polynucleotide matrix is ​​a kind of memory device that stores information about the functional units of the sizer - enzymes. The translation enzyme provides the “production" of an arbitrary enzyme from the information recorded in the matrix. The replication enzyme provides a copy of the polynucleotide matrix. Sizers are sufficient for self-reproduction . Including additional enzymes encoded by the polynucleotide matrix in the sizer scheme, it is possible to provide the sizer with any properties, for example, the property of regulating the synthesis of certain enzymes and adapting to environmental changes. ^[8]

Evolutionary computing (EV) is often used to organize stochastic search, especially in the case of multimodal problems, when deterministic optimization methods or simpler stochastic methods do not allow us to study the behavior of the objective function outside the areas of local optima. EV methods do not guarantee the detection of a global optimum in polynomial time. The practical interest in them is explained by the fact that these methods, as practice shows, allow one to find better (or “good enough”) solutions to very difficult search problems in less time than other methods commonly used in these cases. A typical limitation on their use is the need (to build a good solution) to repeatedly calculate the objective function (the word "many times" usually means numbers from hundreds to millions). Nevertheless, the EV methods turned out to be quite effective for solving a number of real problems of engineering design, planning, routing and placement, managing securities portfolios, searching for optimal energy states of chemical and molecular structures, as well as in many other areas that allow a suitable set of representations, operators , volumes and structures of populations, etc.

Since evolution, apparently, is the basis of the information processing mechanism in natural systems, researchers seek to build theoretical and computer models that really explain the principles of this mechanism (see. " Natural Computer Science "). For studies of this direction, it is typical to understand that models should contain not only the birth and death of populations, but also something between them. Most often, the following concepts are involved.

Swarm intelligence describes the collective behavior of a decentralized, self-organizing system. It is considered in the theory of artificial intelligence as a method of optimization. The term was coined by Gerardo Beni and Wang Jing in 1989, in the context of a cellular robot system ^[9] . Swarm intelligence systems, as a rule, consist of many agents (multi- agent system ) locally interacting with each other and with the environment. Agents themselves are usually quite simple, but all together, interacting locally, create the so-called swarm intelligence. An example in nature is a colony of ants , a swarm of bees , a flock of birds, fish ...

Collective intelligence is a term that appeared in sociology in the mid-1980s when studying the process of collective decision-making. Researchers at NJIT have defined collective intelligence as the ability of a group to find solutions to problems that are more effective than the best individual solutions in this group.

Sociological direction - since human society is a real, besides well observable and documented (unlike the human brain), information processing tool, sociological metaphors and reminiscences are present in works on cybernetics and related areas from the very beginning. If swarm intelligence is focused on obtaining complex behavior in a system of simple elements, this approach, on the contrary, explores the construction of simple and special objects on the basis of complex and universal: “the state is dumber than most of its members” ^[10] . This trend is characterized by the desire to give sociological concepts definitions from the field of computer science. So in ^{[11] the} elite is defined as the bearer of a particular private model of the real world, and the basis (that is, the people) plays the role of an arbiter between the elites. The evolutionary process is the creation and death of elites. The basis is not able to understand the essence of the ideas and models presented by the elites, and does not set itself such a task. However, it is precisely because of his lack of involvement that he retains the ability to have a clear emotional assessment, which allows him to easily distinguish between charismatic elites and rotting ones who try to maintain their privileges, realizing that their idea or model has not been confirmed.

• International Conference on Evolutionary Computation Theory and Applications (ECTA, 09-22.09.2013 Vilamoura, Portugal) ^[12]
• IEEE Congress on Evolutionary Computation (CEC)
• Genetic and Evolutionary Computation Conference (GECCO) ^[13]
• International Conference on Parallel Problem Solving From Nature (PPSN) ^[14]

• Emelyanov V.V., Kureichik V.V., Kureichik V.M. Theory and practice of evolutionary modeling. - M .: Fizmatlit, 2003 .-- 432 p. - ISBN 5-9221-0337-7 .
• Kureichik V.M., Lebedev B.K., Lebedev O.K. Search adaptation: theory and practice. - M .: Fizmatlit, 2006 .-- 272 p. - ISBN 5-9221-0749-6 .
• Gladkov L.A., Kureichik V.V., Kureichik V.M. Genetic Algorithms: A Training Manual. - 2nd ed .. - M .: Fizmatlit, 2006. - 320 p. - ISBN 5-9221-0510-8 .
• Gladkov L. A., Kureichik V. V., Kureichik V. M. et al. Bio-inspired methods in optimization: monograph. - M .: Fizmatlit, 2009 .-- 384 p. - ISBN 978-5-9221-1101-0 .
• Rutkovsky L. Methods and technologies of artificial intelligence. - M .: Hot line-Telecom, 2010 .-- 520 p. - ISBN 5-9912-0105-6 .
• Rutkovskaya D., Pilinsky M., Rutkovsky L. Neural networks, genetic algorithms and fuzzy systems = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. - 2nd ed .. - M .: Hot line-Telecom, 2008. - 452 p. - ISBN 5-93517-103-1 .