evolutionary modeling

To build intelligent systems, evolutionary modeling is often used, based on Darwin's theory of the origin of species.
In evolutionary modeling can be distinguished:
• Evolutionary algorithms (modeling of the general laws of evolution). These are systems that use only evolutionary principles. They are successfully used for problems of functional optimization and can easily be described in mathematical language.
• Evolutionary models. These are systems that are biologically more realistic than evolutionary algorithms, but they have not proven to be useful in an applied sense. Evolutionary models are more similar to biological systems, have a complex behavior, little aimed at solving technical problems. These systems include the so-called "artificial life."
evolutionary algorithms
These include:
• Evolutionary programming
• Genetic algorithms
• Evolutionary strategies
• Classifier systems
• Genetic programming
Evolutionary algorithms model the basic principles in the theory of biological evolution — selection processes, mutations, and the restoration of a population of individuals.
Many individuals are called populations. The population evolves according to the selection rules in accordance with the objective function, set by the external environment. Each individual (individual) population is assigned the value of its fitness in the external environment. Only the most adapted species breed. Recombination and mutation allow individuals to change and adapt to the environment. Evolutionary algorithms are adaptive search engines.
evolutionary programming
Evolutionary programming was proposed by Dr. Lawrence J. Fogel in 1960. At that time, artificial intelligence was limited to two main areas of research: modeling the human brain (neural networks) and modeling human behavior (heuristic programming). An alternative version of Vogel rejected the modeling of the end product of evolution, and was aimed at modeling the process of evolution as a means of obtaining reasonable behavior. Vogel considers intelligence as an integral part of the ability to make predictions of the external environment in combination with the translation of each forecast into an expedient answer according to a given goal (for example, to maximize the gain function). Thus, in his opinion, forecasting is a prerequisite for reasonable behavior.
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 any type of dependence can be expressed on it. The process of building such programs is constructed as an evolution in the population of programs. If the system finds a program that accurately reproduces the desired dependency, it begins to make small modifications to it and selects only those that increase accuracy among the subsidiary programs.
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 dependence of target variables on other factors is carried out in the form of functions of a certain type. 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; only some signs (groups of arguments) are taken into account. Dependency formulas obtained are amenable to analysis and interpretation.
Modern evolutionary programming
The revival of evolutionary programming was continued in the 1980s. the developments concerned arbitrary data presentation and a generalized optimization problem.
Evolutionary programming has been applied to various engineering tasks:
• Management systems, identification systems.
• Routing traffic.
• Military planning.
• Signal processing.
• Game and tutorials.
genetic algorithm
A genetic algorithm is a heuristic search algorithm used to solve optimization and modeling problems by randomly selecting, combining and modifying the desired parameters using mechanisms resembling biological evolution.
evolutionary theory
Evolutionary theory claims that life on the planet first arose only in the simplest forms - in the form of unicellular organisms. These forms gradually became more complex, adapting to the environment, creating new species, and the first animals and people appeared over millions of years. Each species over time improves its qualities in order to effectively cope with the most important tasks of survival, self-defense, reproduction. Thus, a protective coloration appeared in many fish and insects, a tortoise shell, poison in a scorpion, etc.
With the help of evolution, nature constantly optimizes living organisms, finding time for non-ordinary solutions. It is not clear how this progress occurs, but it can be given a scientific explanation based only on two biological mechanisms — natural selection and genetic inheritance.
Natural selection and genetic inheritance
A key role in evolutionary theory is played by natural selection. Its essence lies in the fact that the fittest individuals survive better and bring more descendants than the less fit. Natural selection by itself does not yet ensure the development of a species. Therefore, it is important to learn how inheritance occurs, that is, how the properties of the descendants depend on the properties of the parents.
The basic law of inheritance is intuitive - descendants are like parents. In particular, the descendants of more adapted parents will most likely be among the fittest in their generation. For a clear understanding of heredity, you need to somewhat delve into the construction of a natural cell - into the world of genes and chromosomes.
Almost in every cell of any individual there is a set of chromosomes containing information about this individual. The main part of the chromosome is the DNA strand, which determines which chemical reactions will occur in a given cell, how it will develop and what functions to perform.
A gene is a segment of a DNA chain that is responsible for a specific property of an individual, for example, eye color, hair type, skin color, etc .. The entire set of human genetic traits is encoded using approximately 60 thousand genes.
There are two types of cells: sex (such as sperm and egg) and somatic. Each human somatic cell contains 46 chromosomes (23 pairs). In each pair, one of the chromosomes was received from the father, and the second from the mother. Paired chromosomes are responsible for the same signs — for example, the parent chromosome may contain a black-colored gene, and its maternal pair is a blue gene. There are certain laws governing the participation of certain genes in the development of an individual. In particular, in our example, the descendant will be black-eyed, because the blue eyes gene is “weak” and is inhibited by any other color genome.
In the germ cells of chromosomes only 23, and they are odd. During fertilization, the male and female germ cells merge and an embryo cell is formed, containing exactly 46 chromosomes. What properties will a descendant receive from his father, and which - from his mother? It depends on exactly which germ cells participated in fertilization. The fact is that the process of production of germ cells in the body undergoes changes, thanks to which the descendants differ from their parents. In particular, the following happens: the paired chromosomes of the somatic cells come close together, then their DNA strands break in several random places and the chromosomes exchange their parts (Fig. 1).

Fig.1. Conventional crossover scheme
This process ensures the emergence of new variants of chromosomes and is called “crossing-over” (in the literature on genetic algorithms *** the name crossover or crossing is also used). Each of the new chromosomes then appears inside one of the germ cells, and genetic information can be realized in the descendants of this individual.
The second important factor influencing heredity is mutations, which are expressed in the change of some DNA segments. Mutations are random and can be caused by various external factors, such as radioactive radiation. If the mutation occurred in the germ cell, then the altered gene can be passed on to the descendant and manifest as new properties. It is mutations that cause the emergence of new biological species, and crossing-over determines the variability within a species (for example, genetic differences between people).
optimization tasks
Evolution is a process of constant optimization of biological species. Natural selection ensures that the fittest individuals have a greater number of descendants, and due to genetic inheritance, some descendants will not only retain the high fitness of parents, but will also have some new properties. If the new properties are useful, then with a high probability they will pass into the next generation. Thus, there is an accumulation of useful qualities and a gradual increase in the fitness of the biological species as a whole. Knowing how to solve the problem of optimizing species in nature, you can apply a similar method to solve various real-world problems.
Optimization tasks are a common and important class of problems for practice. They have to be solved either in everyday life, distributing their time among various affairs, or at work, seeking maximum benefit from the effort. Some tasks are easy to solve, but there are those whose exact solution is almost impossible to find.
We introduce the notation and give a few classic examples. As a rule, in the optimization problem one can control several parameters (x1, x2, ..., xn), the goal is to maximize (or minimize) a certain function, f (x1, x2, ..., xn), depending on these parameters. The function f is called the objective function.
For example, if you need to maximize the target function "company income", then the controlled parameters will be the number of employees of the company, production volume, advertising costs, prices for final products, etc. These parameters are interrelated - for example, when reducing the number of employees total production will fall.
An effective way to solve optimization problems are genetic algorithms.
There are two main ways to solve such problems - overcome and gradient. Consider the classic traveling salesman problem. The essence of the task is to find a short route for all cities.
The transcend method is the simplest. To find the optimal solution (the maximum of the objective function), it is necessary to consistently calculate the function values ​​at all points. The disadvantage is a large number of calculations.
Another way is gradient descent. We choose random values ​​of the parameters, and then the value is gradually changed, reaching the maximum growth rate of the objective function. The algorithm can stop reaching a local maximum. Gradient methods are fast, but do not guarantee an optimal solution (since the objective function has several maxima).
A genetic algorithm is a combination of enumerated and gradient methods. Mechanisms of crossover (crossing) and mutations implement the selector part, and the selection of the best solutions - gradient descent.
That is, if a complex function of several variables is defined on a certain set, then the genetic algorithm is a program that for some time finds a point where the value of the function is close enough to the maximum possible value, this will be one of the best solutions.
The work of the genetic algorithm
Imagine an artificial world inhabited by many creatures (individuals), and each individual is a solution to the problem. We will consider an individual as more adapted, the better is its solution (the greater the value of the objective function it gives). Then the task of maximizing the objective function is reduced to the search for the most fit creature.
Of course, you cannot put all creatures in the virtual world at once, because there are so many of them. Instead, we will consider many generations replacing each other. If we apply natural selection and genetic inheritance, then the resulting environment will obey the laws of evolution. According to the definition of fitness, the goal of artificial evolution will be to create the best solutions.
Evolution is an endless process, during which the adaptability of individuals gradually increases. If you forcefully stop this process for a certain time after it starts and select the most adapted individual in the current generation, you can get an answer that is not absolutely accurate, but close to optimal. This is the general idea of ​​a genetic algorithm.
We describe the work of the genetic algorithm in more detail.
In order to talk about genetic inheritance, you need to give individuals chromosomes. In a genetic algorithm, a chromosome is a numerical vector to solve a problem. Which vectors should be considered in a specific problem, the user decides. Each of the positions of the chromosome vector is called a gene. The gene is responsible for a specific input parameter.
A simple genetic algorithm randomly generates an initial population of solutions. The work of a genetic algorithm is an iterative process that continues until a specified number of generations or another stopping criterion is fulfilled. In each generation of the genetic algorithm, selection is performed in proportion to fitness, single-point crossing-over and mutation.
1 At first, proportional selection assigns to each individual the probability Ps (i) equal to the ratio of its fitness to the total fitness of the population:

Then there is a selection (with substitution) of all n individuals for further genetic processing, in accordance with the value of Ps (i).
With this selection, members of the population with high fitness will be more likely to be selected than individuals with low fitness. After selection, n selected individuals are randomly divided into n / 2 pairs. For each pair with a probability Pc, a crossover can be applied. According to the probability of 1-Pc crossing over does not occur and unchanged individuals go to the stage of mutation. If crossing-over occurs, the descendants received replace the parents and proceed to mutation.
2 crossing-overs is an operation in which one or more new chromosomes are generated from two chromosomes. Single point crossing over works as follows. First, one of the l-1 break points is chosen randomly (the section between adjacent bits in a row).
Both parent structures are broken into two segments at this point. Then, the respective segments of different parents are glued together and two genotypes of descendants are obtained.
For example, suppose one parent consists of 10 zeros, and the other with 10 ones. Let out of 9 possible points of discontinuity be chosen the point 3 Parents and their descendants are shown below.
Father 1 0000000000 000 ~ 0000000 -> 111 ~ 0000000 1110000000 Child 1
Father 2 1111111111 111 ~ 1111111 -> 000 ~ 1111111 0001111111 Offspring 2
After the crossing-over stage, mutation operators are executed.
3 A mutation is a chromosome transformation that randomly changes one or more of its positions (genes). A common type of mutation is the random change of only one gene per chromosome.
In each line that undergoes a mutation, the random bit with the probability Pm is reversed.
4 The population obtained after the mutation replaces the old one and the cycle of one generation ends. The following generations are handled in a similar way: selection, crossing-over and mutation.
Genetic algorithm flowchart
First, the initial population of individuals (individuals) is generated, i.e. some set of solutions to the problem. As a rule, this is done randomly. Further reproduction is simulated within this population. For this, several pairs of individuals are randomly selected, crossing occurs between the chromosomes in each pair, and the resulting new chromosomes are embodied in the population of a new generation.
In the genetic algorithm, the basic principle of natural selection is preserved - the adapted an individual is (the greater the corresponding value of the objective function), the more likely he will participate in crossing.
Next, mutations are modeled - in several randomly selected individuals of a new generation, some genes change. The old population is partially or completely destroyed and the next generation is processed. The population of the next generation in most implementations of genetic algorithms contains as many individuals as the initial one, but due to selection, its fitness is on average higher.
Now the described processes of selection, crossing and mutation are repeated for the new population.
Шаги алгоритма повторяются итеративно, моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнено критерий остановки алгоритма. Such a criterion may be:
• Нахождение глобального или субоптимального решения;
• Исчерпание числа поколений, отведено на эволюцию;
• Исчерпание времени, которое отведено на эволюцию.
Генетические алгоритмы в основном предназначены для поиска решений в многомерных пространствах поиска.

В каждом следующем поколении будет наблюдаться возникновение новых решений задачи. Среди них будут как плохие, так и хорошие, но благодаря отбору число приемлемых решений будет расти. В природе не бывает абсолютных гарантий, и наиболее приспособленных тигр может погибнуть от ружейного выстрела, не оставив потомков. Имитируя эволюцию на компьютере, можно избежать подобных нежелательных событий и всегда сохранять жизнь лучшему из индивидуумов текущего поколения - такая методика называется "стратегией элитизма".
Исследователи генетических алгоритмов предлагают много других операторов отбора, кроссинговера и мутации. Вот лишь наиболее распространенные из них.
Элитные методы отбора гарантируют, что при отборе обязательно будут выживать только лучшие члены популяции. Распространенной является процедура обязательного сохранения самой лучшей особи и не предоставлять ее в процессы отбора, кроссинговера и мутации. Элитизм может быть внедрен практически в любой стандартный метод отбора.
Двухточечный кроссинговер и равномерное кроссинговер - альтернативы для одноточечного оператора. В двухточечном кроссинговере выбираются две точки разрыва, и родительские хромосомы обмениваются сегментом, находится между двумя этими точками. В равномерном кроссинговере, каждый бит первого родителя наследуется первым потомком с заданной вероятностью; в противном случае этот бит передается второму потомку. And vice versa.
Недостатки по сравнению с другими методами оптимизации:
• Функциональная оценка сложных проблем, часто является фактором, ограничивающим использование алгоритмов искусственной эволюции. Поиск оптимального решения для сложной задачи высокой размерности часто требует больших затрат. В реальных задачах, таких как задачи структурной оптимизации, вычисления функциональной оценки требует от нескольких часов до нескольких дней.
• Генетические алгоритмы плохо масштабируются под сложность решаемой проблемы. При увеличении области поиска решений увеличивается число элементов, подвергающихся мутациям. Это делает использование алгоритма чрезвычайно сложным.
• Условия остановки алгоритма различны для каждой проблемы.
• Во многих задачах генетические алгоритмы имеют тенденцию сходиться к локальному оптимуму или в спорных точек, вместо глобального оптимума для данной задачи. Это означает, что они "не знают", каким образом пожертвовать кратковременной высокой пригодностью для достижения долгосрочной годности.
Application of genetic algorithms
Genetic algorithms are used to solve the following tasks:
• Оптимизация функций
• Оптимизация запросов в базах данных
• Разнообразные задания на графах (задача коммивояжера)
• Составление расписаний
• Игровые стратегии
• Теория приближений
• Искусственная жизнь
• Биоинформатика
эволюционная стратегия
Эволюционная стратегия - эвристический метод оптимизации в разделе эволюционных алгоритмов, основанный на адаптации и эволюции.
The evolutionary strategy is similar to the genetic algorithm, but there are several significant differences.
Evolutionary strategy operates with vectors of real numbers. При поиске решения в эволюционной стратегии сначала происходит мутация и скрещивание особей для получения потомков, затем происходит детерминированный отбор без повторений лучших особей из общего поколения родителей и потомков. В качестве мутации часто используется добавление нормально распределенной случайной величины в каждой компоненты вектора. При этом параметры нормального распределения самоадаптуються в процессе выполнения алгоритма.