Should we add functions to work with the genetic algorithm for AI training? | Добавить ли функции, для работы с генетическом алгоритмом обучения ИИ? #2
Algorithm terms and definitionsТермины и определения алгоритма
*Eng
How does he work?
The first stage is the creation of a population. In this case, a population is not a collection of biological individuals, but a set of possible solutions to an existing problem, which form a search space.
The second stage is calculating the fitness function. This function takes as input a potential solution to a problem (candidate solution) and produces a value that evaluates its suitability. In the case of a classical genetic algorithm, the objective function and the fitness function are one and the same.
Next, let’s check whether the algorithm’s stopping condition is met. The algorithm will stop executing if the expected optimal value is reached, if the resulting value no longer improves, or after a specified time/number of iterations. After stopping, the fittest chromosome is selected (based on the highest function value). If the stopping condition is not met, then, based on the results of natural selection, chromosomes will be selected to produce descendants.
The third stage is crossing (in Russian sources - “crossover”, less often “crossover”) and mutation.
Crossing, mutation and selection are genetic operators. As in nature, the probability of crossing is several orders of magnitude higher than the probability of mutation. Crossing maintains infinite diversity in a population; it is the redistribution of the genetic material of the parents, thanks to which new combinations of genes appear in the offspring. But what “genes” and “chromosomes” can we talk about outside the context of living nature? In a genetic algorithm, a “chromosome” is a set of parameters that define a proposed possible solution, and a “gene” is one of the “letters” of the “chromosome” string, usually having a binary value. As we remember, as a result of selection, the fittest chromosomes are selected - these genetic operators are applied to them. You are probably now thinking how crossing can occur on such “chromosomes”. Several scenarios are possible, we will mention only a few of them.
Single-point crossover: there is a pair of parent chromosomes with a set of genes L, for which the so-called crossing point Px is randomly selected - this is a certain position of the gene in the chromosome. K [1; Px] of one parent chromosome is attached [Px+1; L] is different, and the first child is obtained. The second descendant is also obtained by crossing, but “in the opposite direction.”
*RUS
Как он работает?
Первый этап — создание популяции. В данном случае популяция — это не совокупность биологических особей, а множество возможных решений имеющейся проблемы, которые образуют пространство поиска (space search).
Второй этап — подсчёт функции пригодности (приспособленности, fitness function). Данная функция принимает на вводе потенциальное решение проблемы (candidate solution), а выдаёт значение, оценивающее его пригодность. В случае с классическим генетическим алгоритмом целевая функция и функция пригодности — это одно и то же. Далее проверим, выполнено ли условие остановки алгоритма. Алгоритм прекратит исполняться, если достигнуто ожидаемое оптимальное значение, если полученное значение больше не улучшается или по истечении заданного времени/количества итераций. После остановки происходит выбор самой приспособленной хромосомы (по наибольшему значению функции). Если же условие остановки не выполнено, то по результатам естественного отбора будет производиться селекция хромосом для производства потомков.
Третий этап – скрещивание ( в русских источниках — «кроссинговер», реже «кроссовер») и мутация.
Скрещивание, мутация и селекция – это генетические операторы. Как и в природе, вероятность скрещивания на несколько порядков выше вероятности мутации. Скрещивание поддерживает бесконечное разнообразие в популяции, это перераспределение генетического материала родителей, благодаря которому у потомков появляются новые сочетания генов. Но о каких «генах» и «хромосомах» может идти речь вне контекста живой природы? В генетическом алгоритме «хромосома» — набор параметров, определяющих предлагаемое возможное решение, а «ген» — это одна из «букв» строки «хромосомы», как правило, имеющая двоичное значение. Как мы помним, в результате селекции отбираются самые приспособленные хромосомы — к ним и применяются эти генетические операторы. Наверное, вы сейчас думаете, каким же образом может происходить скрещивание у таких «хромосом». Возможно несколько сценариев, упомянем лишь некоторые из них.
Одноточечный кроссинговер (single-point crossover): есть пара родительских хромосом с набором генов L, для них случайным образом выбирается так называемая точка скрещивания Px – это некая позиция гена в хромосоме. К [1; Px] одной родительской хромосомы присоединяется [Px+1; L] другой, и получается первый потомок. Второй потомок получается также скрещиванием, но «в обратную сторону».
Algorithm terms and definitions Термины и определения алгоритма
*Eng How does he work? The first stage is the creation of a population. In this case, a population is not a collection of biological individuals, but a set of possible solutions to an existing problem, which form a search space.
The second stage is calculating the fitness function. This function takes as input a potential solution to a problem (candidate solution) and produces a value that evaluates its suitability. In the case of a classical genetic algorithm, the objective function and the fitness function are one and the same.
Next, let’s check whether the algorithm’s stopping condition is met. The algorithm will stop executing if the expected optimal value is reached, if the resulting value no longer improves, or after a specified time/number of iterations. After stopping, the fittest chromosome is selected (based on the highest function value). If the stopping condition is not met, then, based on the results of natural selection, chromosomes will be selected to produce descendants.
The third stage is crossing (in Russian sources - “crossover”, less often “crossover”) and mutation.
Crossing, mutation and selection are genetic operators. As in nature, the probability of crossing is several orders of magnitude higher than the probability of mutation. Crossing maintains infinite diversity in a population; it is the redistribution of the genetic material of the parents, thanks to which new combinations of genes appear in the offspring. But what “genes” and “chromosomes” can we talk about outside the context of living nature? In a genetic algorithm, a “chromosome” is a set of parameters that define a proposed possible solution, and a “gene” is one of the “letters” of the “chromosome” string, usually having a binary value. As we remember, as a result of selection, the fittest chromosomes are selected - these genetic operators are applied to them. You are probably now thinking how crossing can occur on such “chromosomes”. Several scenarios are possible, we will mention only a few of them.
Single-point crossover: there is a pair of parent chromosomes with a set of genes L, for which the so-called crossing point Px is randomly selected - this is a certain position of the gene in the chromosome. K [1; Px] of one parent chromosome is attached [Px+1; L] is different, and the first child is obtained. The second descendant is also obtained by crossing, but “in the opposite direction.”
*RUS Как он работает? Первый этап — создание популяции. В данном случае популяция — это не совокупность биологических особей, а множество возможных решений имеющейся проблемы, которые образуют пространство поиска (space search).
Второй этап — подсчёт функции пригодности (приспособленности, fitness function). Данная функция принимает на вводе потенциальное решение проблемы (candidate solution), а выдаёт значение, оценивающее его пригодность. В случае с классическим генетическим алгоритмом целевая функция и функция пригодности — это одно и то же. Далее проверим, выполнено ли условие остановки алгоритма. Алгоритм прекратит исполняться, если достигнуто ожидаемое оптимальное значение, если полученное значение больше не улучшается или по истечении заданного времени/количества итераций. После остановки происходит выбор самой приспособленной хромосомы (по наибольшему значению функции). Если же условие остановки не выполнено, то по результатам естественного отбора будет производиться селекция хромосом для производства потомков.
Третий этап – скрещивание ( в русских источниках — «кроссинговер», реже «кроссовер») и мутация.
Скрещивание, мутация и селекция – это генетические операторы. Как и в природе, вероятность скрещивания на несколько порядков выше вероятности мутации. Скрещивание поддерживает бесконечное разнообразие в популяции, это перераспределение генетического материала родителей, благодаря которому у потомков появляются новые сочетания генов. Но о каких «генах» и «хромосомах» может идти речь вне контекста живой природы? В генетическом алгоритме «хромосома» — набор параметров, определяющих предлагаемое возможное решение, а «ген» — это одна из «букв» строки «хромосомы», как правило, имеющая двоичное значение. Как мы помним, в результате селекции отбираются самые приспособленные хромосомы — к ним и применяются эти генетические операторы. Наверное, вы сейчас думаете, каким же образом может происходить скрещивание у таких «хромосом». Возможно несколько сценариев, упомянем лишь некоторые из них.
Одноточечный кроссинговер (single-point crossover): есть пара родительских хромосом с набором генов L, для них случайным образом выбирается так называемая точка скрещивания Px – это некая позиция гена в хромосоме. К [1; Px] одной родительской хромосомы присоединяется [Px+1; L] другой, и получается первый потомок. Второй потомок получается также скрещиванием, но «в обратную сторону».
Source | Источники https://3dnews.ru/1050009/iskusstvenniy-intellekt-geneticheskiy-algoritm-i-ego-primeneniya https://rayenmhamdi.github.io/images/aioverview/ga.png