Брачный пул
Пул спаривания — это концепция, используемая в эволюционных вычислениях , которая относится к семейству алгоритмов, используемых для решения задач оптимизации и поиска. [1]
Пул спаривания формируется из решений-кандидатов, которые, по мнению операторов отбора, имеют наибольшую приспособленность в текущей популяции. Решения, включенные в пул спаривания, называются родительскими. Отдельные решения могут быть неоднократно включены в пул для спаривания, при этом особи с более высокими показателями приспособленности имеют более высокие шансы быть включенными несколько раз. скрещивания Затем к родителям применяются операторы , что приводит к рекомбинации генов, признанных лучшими. Наконец, случайные изменения в генах вносятся посредством операторов мутации , увеличивая генетическую изменчивость в генофонде. Эти два оператора повышают шансы на создание новых, превосходных решений. Таким образом создается новое поколение решений – дети, которые составят следующее население. В зависимости от метода отбора общее количество родителей в пуле для спаривания может отличаться от размера исходной популяции, в результате чего новая популяция будет меньше. Чтобы продолжить алгоритм с популяцией одинакового размера, можно выбрать случайных особей из старой популяции и добавить ее в новую популяцию. [1] [2] [3]
На этом этапе оценивается пригодность новых решений. Если условия завершения выполняются, процессы завершаются. В противном случае они повторяются.
Повторение шагов приводит к появлению возможных решений, которые со временем эволюционируют в сторону наиболее оптимального решения. Гены будут становиться все более однородными в направлении наиболее оптимального гена, этот процесс называется конвергенцией . Если 95% населения имеют одну и ту же версию гена, ген конвергирован. Когда все индивидуальные значения приспособленности достигают значения лучшей особи, т.е. все гены сближаются, достигается конвергенция популяций. [1] [4]
Создание пула для спаривания [ править ]
Для создания пула для спаривания можно применить несколько методов. Все эти процессы включают в себя селекцию определенного количества особей внутри популяции. Существует множество критериев, которые можно использовать, чтобы определить, какие особи попадают в пул для спаривания, а какие остаются позади. Методы отбора можно разделить на три основных типа: пропорциональный отбор по приспособленности, отбор на основе порядкового номера и отбор на основе пороговых значений.
Пропорциональный выбор фитнеса [ править ]
В случае пропорционального отбора по фитнесу для входа в пул отбираются случайные люди. Однако те, у кого более высокий уровень приспособленности, с большей вероятностью будут выбраны и, следовательно, имеют больше шансов передать свои особенности следующему поколению. [1] [4]
Одним из методов, используемых в этом типе родительского отбора, является выбор на колесе рулетки. Этот подход делит гипотетическое круглое колесо на разные слоты, размер которых равен значениям приспособленности каждого потенциального кандидата. После этого колесо вращается, и фиксированная точка определяет, какой человек будет выбран. Чем выше значение приспособленности человека, тем выше вероятность быть выбранным в качестве родителя в результате случайного вращения колеса. Альтернативно может быть реализована стохастическая универсальная выборка. Этот метод выбора также основан на вращении прялки. Однако в этом случае имеется более одной фиксированной точки, и в результате все члены пула сопряжения будут выбраны одновременно. [4] [5]
Выбор по порядковому номеру [ править ]
Методы отбора на основе порядкового номера включают турнирный и рейтинговый отбор. Отбор турниров включает в себя случайный отбор особей из популяции и последующее сравнение их уровней физической подготовки. Победителями этих «турниров» становятся те, у кого самые высокие ценности, и они будут помещены в пул для спаривания в качестве родителей. При ранжировании все люди сортируются по показателям их физической подготовки. Затем отбор родителей производится в соответствии с рангом кандидатов. У каждого человека есть шанс быть избранным, но предпочтение отдается людям с более высоким рейтингом. [4] [5]
Выбор на основе порога [ править ]
Последний тип метода выбора называется пороговым методом. Сюда входит метод отбора усечения, который сортирует людей на основе их фенотипических значений по определенному признаку, а затем выбирает долю из них, находящуюся в пределах определенного порога, в качестве родителей. [6]
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б с д Регупати, Р. «Оптимизация стоимости многоэтажной каркасной структуры с использованием гибридного генетического алгоритма». Международный исследовательский журнал техники и технологий (IRJET) , том. 04, нет. 07 июля 2017 г., с. 890., www.irjet.net/archives/V4/i7/IRJET-V4I7211.pdf.
- ^ Шаттен, Александр (19 июня 2002 г.). «Генетические алгоритмы» .
- ^ Митчелл, Мелани; Тейлор, Чарльз Э. (ноябрь 1999 г.). «Эволюционные вычисления: обзор» . Ежегодный обзор экологии и систематики . 30 (1): 593–616. doi : 10.1146/annurev.ecolsys.30.1.593 . ISSN 0066-4162 .
- ^ Jump up to: Перейти обратно: а б с д Бисли Д., Булл Д.Р. и Мартин Р.Р. (1993). Обзор генетических алгоритмов: Часть 1, основы. Университетская информатика, 15(2), 56-69.
- ^ Jump up to: Перейти обратно: а б Ганди, Сонали (4 сентября 2020 г.). «Сравнительный анализ схемы выбора» (PDF) . Международный журнал мягких вычислений и инженерии (IJSCE) . 2 : 131–134.
- ^ Хартмут, Польхайм. «Эволюционные алгоритмы 3 Выбор» . Геатбкс . Проверено 15 сентября 2020 г.