Введение в эволюционное моделирование. Каширина И.Л. - 9 стр.

                                     9
     Данная стратегия использует отсортированную по убыванию популя-
цию. Число особей для скрещивания выбирается в соответствии с порогом
T∈[0;1]. Порог определяет, какая доля особей, начиная с самой первой (са-
мой приспособленной), будет принимать участие в отборе. В принципе, по-
рог можно задать и равным 1, тогда все особи текущей популяции будут
допущены к отбору. Среди особей, допущенных к скрещиванию случайным
образом m/2 раз выбираются родительские пары, потомки которых образу-
ют новую популяцию.
                                Скрещивание
      Как только два решения-родителя выбраны, к ним применяется веро-
ятностный оператор скрещивания (crossover ), который строит на их основе
новые (1 или 2) решения-потомка. Отобранные особи подвергаются кроссо-
веру (иногда называемому рекомбинацией) с заданной вероятностью Pc. Ес-
ли каждая пара родителей порождает двух потомков, для воспроизводства
популяции необходимо скрестить m/2 пары. Для каждой пары с вероятно-
стью Pc применяется кроссовер. Соответственно, с вероятностью 1-Pc крос-
совер не происходит � �   и тогда неизмененные особи переходят на сле-
дующую стадию (мутации).
      Существует большое количество разновидностей оператора скрещива-
ния. Простейший одноточечный кроссовер работает следующим образом.
Сначала случайным образом выбирается одна из возможных точек разрыва.
(Точка разрыва � � участок между соседними битами в строке.) Обе роди-
тельские структуры разрываются на два сегмента по этой точке. Затем соот-
ветствующие сегменты различных родителей склеиваются и получаются два
генотипа потомков.
           Родитель 1     1 0 0 1 0 1 1 0 1 0 0 1
           Родитель 2     0 1 0 0 0 1 1 0 0 1 1 1

           Потомок 1      1 0 0 1 0 1 1 0 0 1 1 1
           Потомок 2      0 1 0 0 0 1 1 0 1 0 0 1
                Рис. 1. Пример работы одноточечного кроссовера
      В настоящее время исследователи ГА предлагают много других опера-
торов скрещивания. Двухточечный кроссовер и равномерный кроссовер
� � вполне достойные альтернативы одноточечному оператору. В двухто-
чечном кроссовере выбираются две точки разрыва, и родительские хромосо-
 мы обмениваются сегментом, который находится между двумя этими точка-
 ми. В равномерном кроссовере каждый бит первого потомка случайным об-
разом наследуется от одного из родителей; второму потомку достается бит
другого родителя.