Бассейн спаривания в эволюционных вычислениях: методы и принципы.
Mating pool
Маточный пул в эволюционных вычислениях: выбор лучших решений для оптимизации и поиска. Высокая пригодность = больше шансов на скрещивание и создание новых генов.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Парный пул – это концепция, используемая в эволюционных вычислениях, относящаяся к семейству алгоритмов, применяемых для решения задач оптимизации и поиска. Парный пул формируется из кандидатов в решения, которые операторы отбора признают наиболее приспособленными в текущей популяции. Решения, включенные в парный пул, называются родителями. Отдельные решения могут многократно включаться в парный пул, при этом особи с более высокими значениями приспособленности имеют больше шансов на многократное включение. Затем к родителям применяются операторы кроссовера, что приводит к рекомбинации генов, признанных наилучшими. Далее, случайные изменения в генах вводятся посредством операторов мутации, увеличивая генетическое разнообразие в генофонде. Эти два оператора повышают вероятность создания новых, более качественных решений. Таким образом, создается новое поколение решений – потомки, которые составят следующую популяцию. В зависимости от метода отбора, общее количество родителей в парном пуле может отличаться от размера исходной популяции, что приводит к формированию новой популяции меньшего размера. Чтобы продолжить алгоритм с популяцией того же размера, случайные особи из старой популяции могут быть выбраны и добавлены в новую популяцию. На этом этапе оценивается приспособленность новых решений. Если условия завершения выполнены, процесс завершается. В противном случае он повторяется. Повторение этих шагов приводит к появлению кандидатов в решения, которые со временем эволюционируют в сторону наиболее оптимального решения. Гены будут становиться все более однородными в направлении наиболее оптимального гена, этот процесс называется конвергенцией. Если 95% популяции имеют одну и ту же версию гена, то ген достиг конвергенции. Когда все значения приспособленности отдельных особей достигают значения лучшей особи, то есть все гены сошлись, достигается конвергенция популяции.
A mating pool is a concept used in evolutionary computation, which refers to a family of algorithms used to solve optimization and search problems. The mating pool is formed by candidate solutions that the selection operators deem to have the highest fitness in the current population. Solutions that are included in the mating pool are referred to as parents. Individual solutions can be repeatedly included in the mating pool, with individuals of higher fitness values having a higher chance of being included multiple times. Crossover operators are then applied to the parents, resulting in recombination of genes recognized as superior. Lastly, random changes in the genes are introduced through mutation operators, increasing the genetic variation in the gene pool. Those two operators improve the chance of creating new, superior solutions. A new generation of solutions is thereby created, the children, who will constitute the next population. Depending on the selection method, the total number of parents in the mating pool can be different to the size of the initial population, resulting in a new population that’s smaller. To continue the algorithm with an equally sized population, random individuals from the old populations can be chosen and added to the new population. At this point, the fitness value of the new solutions is evaluated. If the termination conditions are fulfilled, processes come to an end. Otherwise, they are repeated. The repetition of the steps result in candidate solutions that evolve towards the most optimal solution over time. The genes will become increasingly uniform towards the most optimal gene, a process called convergence. If 95% of the population share the same version of a gene, the gene has converged. When all the individual fitness values have reached the value of the best individual, i. e. all the genes have converged, population convergence is achieved.
Создание брачного пула
Для создания брачного бассейна можно использовать несколько методов. Все эти процессы включают селективное разведение определенного числа особей внутри популяции. Существует множество критериев, которые можно использовать для определения того, какие особи попадут в брачный бассейн, а какие будут исключены. Методы отбора можно разделить на три основных типа: пропорциональный отбор, отбор на основе ранга и отбор на основе порогового значения.
Several methods can be applied to create a mating pool. All of these processes involve the selective breeding of a particular number of individuals within a population. There are multiple criteria that can be employed to determine which individuals make it into the mating pool and which are left behind. The selection methods can be split into three general types: fitness proportionate selection, ordinal based selection and threshold based selection.
Пропорциональный подбор
В случае пропорционального отбора, случайные индивиды включаются в пул. Однако особи с более высоким уровнем приспособленности имеют больше шансов быть выбранными и, следовательно, передать свои признаки следующему поколению.
In the case of fitness proportionate selection, random individuals are selected to enter the pool. However, the ones with a higher level of fitness are more likely to be picked and therefore have a greater chance of passing on their features to the next generation.
Выбор на основе порядка
Методы отбора на основе порядка включают в себя отбор по турниру и рейтинговый отбор. Отбор по турниру предполагает случайный выбор особей из популяции и последующее сравнение их приспособленности. Победители этих "турниров" – особи с наивысшими значениями приспособленности, которые помещаются в брачный пул в качестве родителей. При рейтинговом отборе все особи сортируются по значениям приспособленности. Затем выбор родителей производится на основе ранга кандидатов. Каждая особь имеет шанс быть выбранной, но особи с более высоким рангом имеют преимущество.
The ordinal based selection methods include the tournament and ranking selection. Tournament selection involves the random selection of individuals of a population and the subsequent comparison of their fitness levels. The winners of these “tournaments” are the ones with the highest values and will be put into the mating pool as parents. In ranking selection all the individuals are sorted based on their fitness values. Then, the selection of the parents is made according to the rank of the candidates. Every individual has a chance of being chosen, but higher ranked ones are favored